Istruzioni dettagliate che definiscono un processo computazionale (che si dice poi algoritmico), che inizia con un input arbitrario (su un certo numero di input possibili per l’algoritmo dato), e con istruzioni volte a ottenere un risultato (o output) che è completamente determinato dall’input. Per esempio, le regole insegnate nelle scuole elementari per l’addizione, la sottrazione, la moltiplicazione e la divisione in colonna sono algoritmi; in questi algoritmi i possibili risultati sono numeri interi non negativi scritti nel sistema decimale, mentre i possibili input sono coppie ordinate di tali numeri. Non si presume, in generale, che il risultato sia necessariamente ottenuto: il processo di applicazione di un algoritmo a un qualche possibile input (cioè un processo algoritmico che procede a partire da questo input) può anche terminare senza che sia stato ottenuto un risultato (in tal caso si ha un no-result stop) o può non terminare affatto. Se il processo termina (non termina), allora si dice che l’input è adatto (non è adatto) per l’algoritmo in questione.
Un risultato importante in questo campo è l’indecidibilità del cosiddetto problema di arresto. È possibile costruire un algoritmo $ \alpha $ tale che non esiste un algoritmo per decidere se un input arbitrario che è possibile per $ \alpha $ è anche adatto per $ \alpha $. In particolare, si può trovare un algoritmo $ \alpha $ per il quale l’insieme dei suoi input possibili è l’insieme dei numeri naturali.
La nozione di algoritmo è uno dei concetti centrali della matematica moderna, specialmente nell’area dei calcoli. Un esempio è dato di seguito. Trovare la soluzione numerica di equazioni di un dato tipo equivale a costruire un algoritmo che converte un’equazione arbitraria di questo tipo e un numero razionale positivo arbitrario $ \epsilon $ in un numero (o un insieme di numeri) che differisce dalla radice (o dalle radici) di questa equazione per meno di $ \epsilon $. Tuttavia, il termine “processo computazionale”, come usato nel contesto di un algoritmo, non deve essere inteso come mero calcolo numerico: anche in algebra elementare si usano calcoli con lettere. I calcoli aritmetici standard coinvolgono alcuni simboli che non sono numeri (parentesi, segni di uguaglianza, simboli per operatori aritmetici). Di conseguenza, è opportuno considerare algoritmi che coinvolgono simboli arbitrari e oggetti composti da simboli. L’esempio più semplice di un tale oggetto è una sequenza lineare di simboli che forma una parola. È anche possibile considerare oggetti “non lineari” – matrici algebriche, alberi di derivazione di qualche linguaggio formale e grafi generali. Intuitivamente, il requisito minimo per gli input e i risultati degli algoritmi è che devono essere oggetti costruttivi (cfr. Oggetto costruttivo). Quindi, il concetto di algoritmo è molto generale. Si può parlare di un algoritmo per la traduzione da una lingua all’altra, di un algoritmo di un controllore del traffico aereo (che elabora informazioni sui movimenti degli aerei secondo regole fisse), e altri esempi di processi di controllo descritti algoritmicamente. Di conseguenza, il concetto di algoritmo è una delle idee centrali della cibernetica e dell’informatica.
Esempio di un algoritmo.
Lasciamo che i possibili input e i possibili risultati siano tutte le possibili parole dell’alfabeto $ \{ a, b \} $. La transizione da una parola $ X $ ad una parola $ Y $ è “ammissibile” nei seguenti due casi (dove $ P $ indica una parola arbitraria): 1) $ X $ è della forma $ aP $, e $ Y $ è della forma $ Pb $; oppure 2) $ X $ è della forma $ baP $, mentre $ Y $ è della forma $ Paba $. Le istruzioni sono formulate come segue: “designando qualche parola come input, eseguire le transizioni permesse fino ad ottenere una parola della forma aaP; poi fermarsi e lasciare che la parola P sia il risultato” . Queste istruzioni costituiscono un algoritmo, che sarà indicato con $ \mathfrak A $. Prendiamo la parola $ babaa $ come input. Dopo una transizione si ottiene $ baaaba $; dopo la seconda, si ottiene $ aabaaba $. Qui l’algoritmo si ferma con $ baaba $ come risultato. Consideriamo un altro input $ baaba $. Si ottiene, in successione, $ abaaba, baabab, abababa, bababab, babababa , . . . $. Si può dimostrare che questo processo non finirà mai (cioè nessuna delle parole generate inizierà mai con $ aa $). Ora prendiamo $ abaab $ come input. Si ottiene $ baabb, abbaba, bbabab $; non sono possibili altre transizioni ammissibili e, allo stesso tempo, la condizione di terminazione non è soddisfatta. Si ha uno stop senza risultato. Così, l’input $ babaa $ è adatto a $ \mathfrak A $, e gli input $ baaba $ e $ abaab $ non lo sono.
Il significato degli algoritmi.
Nella scienza, gli algoritmi si incontrano ovunque: una soluzione “generale” di un problema richiede un algoritmo. La capacità dell’uomo di sommare i numeri ne è un esempio. Non nel senso che può trovare, prima o poi, la somma di due numeri qualsiasi, ma piuttosto nel senso che possiede un metodo per l’addizione unica di due numeri qualsiasi dati in forma scritta, cioè un algoritmo di addizione come il noto metodo di addizione in colonna. “Generalmente” la risoluzione di un problema viene formalizzata come risoluzione di un problema algoritmico. Un problema algoritmico consiste di istanze di problemi separati, e un unico algoritmo deve essere trovato per la soluzione di tutti loro. Se non esiste un tale algoritmo, si dice che il problema algoritmico è irrisolvibile. Così, il problema di risolvere numericamente equazioni di un dato tipo e il problema della traduzione automatica sono problemi algoritmici. Le loro istanze problematiche sono, rispettivamente, trovare la soluzione numerica di singole equazioni del tipo dato e la traduzione di singole frasi. Altri esempi sono la verifica delle uguaglianze algebriche in algebra; il problema algoritmico del riconoscimento della deducibilità delle proposizioni da assiomi dati in logica matematica. (Nella logica matematica il concetto di algoritmo è importante anche perché serve come base del concetto chiave di calcolo, che è una generalizzazione e una forma più precisa dei concetti intuitivi di “prova” e “dimostrazione”). Lo stabilire l’irrisolvibilità di un dato problema algoritmico (per esempio il problema di stabilire la verità o la dimostrabilità di frasi in un qualche linguaggio logico-matematico) è importante, perché mostra che, in linea di principio, specifiche istanze di quel problema possono essere risolte solo con metodi che sono specifici per ogni singola istanza del problema.
L’importanza scientifica del concetto di algoritmo è stata riconosciuta da molto tempo. Fin dai tempi più antichi, le persone hanno cercato metodi costruttivi per risolvere i problemi matematici. Tali sforzi di solito hanno beneficiato della nuova disponibilità di notazioni simboliche adeguate. Questo processo ha dato un contributo significativo alla conoscenza scientifica, soprattutto dopo che era diventato chiaro che alcuni problemi sono intrinsecamente irrisolvibili (la quadratura del cerchio, ecc.). Dopo che era stato riconosciuto che certi problemi non possono essere risolti con calcoli diretti, il concetto teorico di insieme è nato nel XIX secolo. È solo dopo un periodo di rapido sviluppo di questo concetto (che non comportava problemi di metodi costruttivi nel loro senso moderno), che è stato possibile a metà del XX secolo tornare ai problemi costruttivi, ma questo è stato fatto su un piano diverso, arricchito dal concetto di algoritmo che si era cristallizzato nel frattempo. Questo concetto costituisce la base della tendenza costruttiva in matematica.
La parola “algoritmo” deriva dalla parola “algoritmi”, che è la traslitterazione latina del nome del matematico arabo del IX secolo Al-Khwarizmi. Un “algoritmo” nell’Europa del Medioevo era “il sistema decimale-posizionale e l’arte di calcolare con esso”, poiché è attraverso la traduzione latina (XII secolo) del trattato di Al-Khwarizmi che il sistema posizionale fu introdotto in Europa.
La struttura di un processo algoritmico.
Un processo algoritmico è un processo di conversione consecutiva di oggetti costruttivi per “passi” discreti, ogni passo consiste nella sostituzione di un oggetto costruttivo con un altro. Così, quando si applica l’algoritmo $ \mathfrak A $ alla parola $ baaba $, seguono, in successione, le parole $ baaba, abaaba, baabab $, ecc. Se si applica, per esempio, l’algoritmo di sottrazione colonnare alla coppia di numeri <307, 49 >, si ottengono, in successione, i seguenti oggetti costruttivi:
$$ \begin{array}{rrrr}307 &3 \punto 0} 7 &punto 3} \dot{0} 7 &\dot{3} \punto 0} 7 \underline{- 49} &Sottolinea- 49 &sottolinea- 49 } &Sottolinea- 49 \\{} & 8 &58 &258 \end{array}$$
Si noterà che, in una serie di oggetti costruttivi successivi, ogni oggetto costruttivo successivo è completamente determinato (nel quadro dell’algoritmo dato) dall’oggetto costruttivo immediatamente precedente. Nell’approccio più rigoroso, si assume anche che la transizione da un qualsiasi oggetto costruttivo a quello immediatamente successivo sia sufficientemente “elementare” – nel senso che la trasformazione di un passo dell’oggetto precedente in quello immediatamente successivo è locale (non è l’intero oggetto costruttivo che viene trasformato, ma solo la sua parte limitata dall’algoritmo; inoltre, questa stessa trasformazione non è determinata dall’intero oggetto precedente, ma solo da una parte limitata di esso).
Di conseguenza, non si ha solo un insieme di possibili input e un insieme di possibili risultati, ma anche un insieme di possibili risultati intermedi, che rappresentano il mezzo di lavoro in cui il processo algoritmico si evolve. Per quanto riguarda $ \mathfrak A $, tutti questi tre insiemi coincidono, ma questo non è vero per l’algoritmo di sottrazione a colonne – i possibili input sono coppie di numeri, i possibili risultati sono numeri (tutti nel sistema decimale), mentre i possibili risultati intermedi sono record “a tre piani” del tipo
$$ \begin{array}{r} p \sottolinea{- q } \ r \end{array}$$
dove $ q $ è il record scritto del numero nel sistema decimale, $ r $ è un record simile o la parola vuota, mentre $ p $ è il record scritto di un numero nel sistema decimale, con punti sopra alcune delle cifre. Come regola, si possono distinguere diversi parametri (non indipendenti) caratteristici di un algoritmo: 1) l’insieme dei possibili input; 2) l’insieme dei possibili risultati; 3) l’insieme dei possibili risultati intermedi; 4) la regola di partenza; 5) la regola di transizione diretta; 6) la regola di terminazione; e 7) la regola di recupero del risultato.
Formalizzare il concetto di algoritmo.
Il concetto di algoritmo nella sua forma generale è un concetto matematico fondamentale che non può essere definito in termini di concetti più semplici. In senso stretto, le formalizzazioni del concetto di algoritmo lo limitano in qualche modo. In ognuna di queste formalizzazioni viene data una definizione esatta di qualche classe all’interno della quale ognuno dei parametri può variare. Le varie formalizzazioni differiscono l’una dall’altra per la selezione di tali classi. Poiché i parametri definiscono senza ambiguità qualche algoritmo, una scelta dei domini dei parametri determina qualche classe di algoritmi. Tuttavia, tale scelta può pretendere di essere una formalizzazione del concetto intuitivo di algoritmo, solo se si può essere sicuri che per ogni algoritmo “intuitivo” esiste un algoritmo equivalente nella classe di algoritmi definita dalla scelta in esame. Questo requisito è formulato per ogni formalizzazione come un’ipotesi fondamentale, che, allo stato attuale delle conoscenze, non può essere dimostrata matematicamente.
Le prime formalizzazioni di questo tipo sono dovute a E.L. Post
e a A.M. Turing , le cui costruzioni hanno anticipato per molti aspetti le idee su cui si basano i moderni computer. Esistono anche versioni formulate da A.A. Markov ,
(cfr. Algoritmo normale) e da A.N. Kolmogorov , che ha basato l’approccio su complessi topologici costruttivi di un certo tipo, il che permette di esprimere più precisamente la proprietà di “essere locale” di una trasformazione. In ognuna di queste formalizzazioni l’ipotesi fondamentale è in soddisfacente accordo con la pratica. Un altro argomento a favore di questa ipotesi è il fatto che, come si può dimostrare, tutte le versioni formali (della calcolabilità effettiva) che sono state proposte sono equivalenti.
Come esempio, consideriamo la formalizzazione proposta da Turing. Nella sua forma originale, questa era una descrizione di qualche computer teorico che consisteva di 1) un nastro infinito, diviso in celle consecutive, ogni cella capace di contenere qualche simbolo dell'”alfabeto del nastro” della macchina; e 2) un “controllo finito”, che in ogni momento del tempo è in qualche “stato” (su una data lista finita di stati). Il controllo finito può muoversi lungo il nastro, una cella alla volta, e cambiare il contenuto delle celle che passa. Un programma che controlla il movimento del controllo finito costituisce l’algoritmo per le computazioni condotte su tale macchina (un “algoritmo di Turing”). Per una descrizione più esatta e dettagliata si veda Macchina di Turing. Qui viene data un’esposizione modernizzata della costruzione di Turing. Per definire un algoritmo di Turing, si specificano a) coppie di alfabeti disgiunti $ B, D, C $, con una lettera distinta $ \lambda $ in $ D $ e lettere distinte $ \alpha $ e $ \omega $ in $ C $; e b) un insieme di coppie della forma $ \langolo p \xi , \eta Tq \rangolo $ dove $ p, q \in C $, $ \xi , \eta \in B \cup D $, mentre $ T $ è uno dei tre simboli $ -, 0, + $; in questo insieme (che è chiamato programma) non ci sono due coppie con la stessa prima coordinata. I possibili ingressi e le possibili uscite sono parole su $ B $, mentre i possibili risultati intermedi sono parole su $ B \cup D \cup C $ che non contengono più di una lettera di $ C $. La regola di partenza è che la parola iniziale $ P $ viene convertita nella parola $ \lambda \alpha P \lambda $. La regola di fine è che un risultato intermedio che contiene $ \omega $ è finale. La regola per il recupero dell’output è che l’output è la sequenza di lettere nel risultato intermedio finale che segue $ \omega $ e precede la prima lettera non appartenente a $ B $. La regola di trasformazione che converte $ A $ in $ A ^ \primo $ è la seguente. La lettera $ \lambda $ viene scritta a sinistra e a destra di $ A $; nella parola così formata, la parte della forma $ \epsilon p \xi $, dove $ p \in C $, $ \epsilon \xi \in B \cup D $, viene sostituita da una parola $ Q $ secondo la regola: si cerca nel programma una coppia con il primo termine $ p \xi $; che il secondo termine di questa coppia sia $ \eta Tq $; se $ T $ è $ – $, $ Q = q \epsilon \eta $; se $ T = 0 $, $ Q = \epsilon q \eta $; se $ T $ è $ + $, $ Q = \epsilon \eta q $. La parola prodotta da questo scambio è $ A ^ \primo $. Per i riferimenti, vedere , , , , ,
di Algoritmi, teoria degli.
L’ipotesi fondamentale di cui sopra è solitamente chiamata tesi di Church-Turing o ipotesi di Turing. Questa tesi afferma che ciò che può essere efficacemente calcolato secondo la propria intuizione su ciò che costituisce un processo efficace, può anche essere calcolato da una macchina di Turing, cioè una nozione formalmente definita di algoritmo. Per la sua stessa natura di identificare una nozione intuitiva informale con una definizione formale precisa, la tesi di Church-Turing non può essere dimostrata formalmente.
Molte formalizzazioni si sono rivelate equivalenti, e nessuna formalizzazione si è rivelata strettamente più potente. Oltre alle formalizzazioni menzionate sopra, i seguenti riferimenti sono quelli più standard in Occidente: La formalizzazione di Church dei numeri e delle funzioni computabili mediante termini lambda, gli schemi ricorsivi generali di Kleene, e il modello di macchina a registro proposto da J.C. Shepherdson e H.E. Sturgis, che fu esteso in un modello di computer più realistico da S.A. Cook e R.A. Reckhow. Le versioni di Markov e Kolmogorov sono meno note. Per completezza sono riportati anche i riferimenti originali a Turing e Post.
| A.M. Turing, “On computable numbers, with an application to the Entscheidungsproblem” Proc. London Math.Soc. Ser. 2 , 42 (1936) pp. 230-265 | |
| A.M. Turing, “Correzioni a “On computable numbers, with an application to the Entscheidungsproblem” ” Proc. London Math.Soc. Ser. 2 , 43 (1937) pp. 544-546 | |
| A. Church, “An unsolvable problem of elementary number theory” Amer. J. Math. , 58 (1936) pp. 345-363 | |
| S.C. Kleene, “General recursive functions of natural numbers” Math. Ann. 112 (1936) pp. 727-742 | |
| E.L. Post, “Formal reductions of the general combinatorial decision problem” Amer. J. Math. , 65 (1943) pp. 197-268 | |
| J.C. Shepherdson, H.E. Sturgis, “Computability of recursive functions” J. Assoc. Comp. Mach. 10 (1963) pp. 217-255 | |
| S.A. Cook, R.A. Reckhow, “Time-bounded random access machines” J. Computer and System Sciences , 7 (1973) pp. 354-375 |