Algoritmo: differenze tra le versioni

Versione delle 16:43, 2 feb 2025

Versione delle 16:44, 2 feb 2025

Riga 16:

== Definizione ==

Nel [[XX secolo]], il concetto di algoritmo venne formalizzato per risolvere il problema matematico della "decisione" (''[[Entscheidungsproblem]]''), posto da [[David Hilbert]] nel 1928, e altre successive formalizzazioni giunsero con lo sviluppo dei concetti di "[[effective calculability|calcolabilità effettiva]]"<ref>Kleene 1943 in Davis 1965:274</ref> e di "metodo effettivo"<ref>Rosser 1939 in Davis 1965:225</ref>. Le formalizzazioni matematiche più famose sono le [[funzioni ricorsive]] di [[Kurt Gödel|Gödel]]–[[Jacques Herbrand|Herbrand]]–[[Stephen Cole Kleene|Kleene]] del 1930, 1934 e 1935; il [[lambda calcolo]] di [[Alonzo Church]] e la [[Formulation 1]] di [[Emil Leon Post]] del 1936; e, infine, la [[macchina di Turing]] del 1936–37 e 1939. Nonostante ciò, una definizione del concetto di algoritmo che sia formale e non tecnica manca tuttora<ref>

{{Cita libro|nome=Yiannis N.|cognome=Moschovakis|capitolo=What is an algorithm?|titolo=Mathematics Unlimited — 2001 and beyond|curatore-nome=B.|curatore-cognome=Engquist|curatore-nome2=W.|curatore-cognome2=Schmid|editore=Springer|anno=2001|pp=919–936 (Part II)|url=http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.32.8093}}</ref> e si è pertanto costretti ad accontentarsi dell'idea intuitiva di algoritmo come "una sequenza ordinata e finita di passi (operazioni o istruzioni) elementari che conduce a un ben determinato risultato in un tempo finito".

=== Modelli formali ===

{{vedi anche|Teoria della calcolabilità#Che cos'è un algoritmo}}

[[File:Quicksort example small.png|thumb|Rappresentazione grafica dell'algoritmo [[Quicksort]]]]

La definizione di algoritmo appena riportata è piuttosto informale, menRiccardomentre Antimo Leroy Piernoraera necessario disporre di una definizione più rigorosa per trattare il concetto di algoritmo con strumenti matematici. Al tal fine sono stati definiti alcuni [[Modello matematico|modelli matematici]] di algoritmo, fra i quali uno dei più celebri è la [[macchina di Turing]]. Essa rappresenta una sorta di ''computer'' ideale corredato di un [[Programma (informatica)|programma]] da eseguire, ma, rispetto a un computer reale, la macchina di Turing ha un funzionamento estremamente più semplice che possa essere facilmente descritto con termini matematici, facendo uso di concetti come [[insieme]], [[relazione (matematica)|relazione]] e [[funzione (matematica)|funzione]].

La [[architettura di von Neumann|macchina di Von Neumann]], che è il modello di architettura primigenio di tutti i computer attuali, è equivalente, in termini di potere di calcolo, alla macchina di Turing. In altre parole, è stato dimostrato che un certo problema può essere risolto da un computer (opportunamente programmato) se e solo se esso può essere risolto anche da una macchina di Turing. Oltre alla macchina di Turing, proposta da [[Alan Turing]] nel [[1936]], nello stesso periodo altri matematici hanno elaborato diverse rappresentazioni formali del concetto di algoritmo, fra i quali ricordiamo, per esempio, il [[lambda calcolo]]. Dopo alcuni anni, emerse che tutti questi modelli erano equivalenti: {{Senza fonte|i problemi che una macchina di Turing poteva risolvere erano gli stessi che poteva risolvere una macchina di von Neumann e anche gli stessi che poteva risolvere una funzione costruita col lambda calcolo}}.