Phenquestions
La macchina di Turing è il costrutto teorico centrale nell'informatica. La macchina di Turing è un modello matematico astratto di calcolo. L'uso delle macchine di Turing aiuta a spiegare cos'è il calcolo delimitando le cosiddette "funzioni calcolabili"."
Le prime ricerche di Alan Turing sulla logica si concentrarono su un famoso problema irrisolto noto come Entscheidungsproblem. L'Entscheidungsproblem (tradotto approssimativamente dal tedesco come il problema della decisione) è stato proposto dal filosofo e matematico David Hilbert nel 1928. Il problema chiedeva se esistesse un algoritmo che decidesse ogni affermazione in un linguaggio formale.
Un linguaggio formale è un sistema di assiomi e regole di inferenza come quelli dell'aritmetica o della logica del primo ordine. Gli assiomi possono essere qualsiasi simbolo e le regole di inferenza possono essere qualsiasi elenco di regole per manipolare quei simboli. "Decidere ogni affermazione" significava emettere se l'affermazione era vera/falsa o se l'affermazione era derivabile/sottovalutabile. Il teorema di completezza di Kurt Godel ha dimostrato che un algoritmo che decide per la validità è equivalente a una procedura efficace che decide per la derivabilità. L'articolo del 1936 di Alan Turing "On Computable Numbers, with an Application to the Entscheidungsproblem", ha dimostrato un risultato negativo, che era impossibile decidere algoritmicamente ogni affermazione in un sistema formale.
Alan Turing
Per dimostrare un risultato negativo per l'Entscheidungsproblem, Turing aveva bisogno di formalizzare la nozione di algoritmo. La formalizzazione di un algoritmo da parte di Turing era un modello matematico di calcolo che in seguito divenne noto come la macchina di Turing. Una macchina di Turing ha un insieme finito di stati in cui la macchina può essere in. La macchina di Turing ha un nastro infinitamente lungo che è diviso in quadrati. Su ogni quadrato del nastro c'è un simbolo tratto da un insieme finito di simboli. In qualsiasi momento del calcolo, la macchina di Turing sta leggendo il simbolo su un quadrato del nastro. La macchina di Turing può sostituire quel simbolo con un altro simbolo e spostarsi sul quadrato a destra o sul quadrato a sinistra. L'azione intrapresa dalla macchina di Turing è determinata automaticamente dallo stato in cui si trova la macchina. Dopo che il simbolo di sostituzione e l'azione di spostamento in un quadrato diverso hanno avuto luogo, la macchina di Turing può passare a uno stato diverso. Ogni diverso stato ha un diverso insieme di regole su come sostituire i simboli e in quale direzione muoversi.
Una rara implementazione fisica del design della macchina di Turing (senza un nastro infinito)
La formulazione canonica della macchina di Turing consiste solitamente in un alfabeto binario composto esclusivamente da 0 e 1. Questa formulazione corrisponde all'intuizione dei moderni programmatori di computer, dato che tutti i computer moderni usano il binario. Le macchine di Turing, infatti, sono neutre rispetto alle dimensioni dell'alfabeto dei simboli. Una macchina di Turing può anche utilizzare qualsiasi simbolo, sia numerico che tratto da qualsiasi altro tipo di alfabeti come i simboli pittorici o l'alfabeto latino. Qualsiasi formulazione di ogni possibile alfabeto finito è dimostrabilmente riducibile a una macchina di Turing binaria.
Le macchine di Turing presumono che sia disponibile una quantità infinita di memoria. Nessuna macchina reale istanziata fisicamente può soddisfare questo requisito di essere una macchina di Turing. Una macchina di Turing presuppone inoltre che possa essere impiegato un tempo potenzialmente infinito per calcolare la funzione. Queste assunzioni sono state fatte per generare la classe più ampia di possibili funzioni per la definizione di funzioni calcolabili di Turing. Le funzioni calcolabili di Turing sono tutte le funzioni che possono essere calcolate da una macchina di Turing. Molte di queste funzioni calcolabili potrebbero non essere mai calcolabili da nessuna macchina istanziata fisicamente perché richiedono troppo tempo o memoria.
La tesi di Church-Turing afferma l'equivalenza di funzioni calcolabili e funzioni che possono essere calcolate da una macchina di Turing. Ciò implica che tutte le funzioni non calcolabili dalle macchine di Turing non possono essere calcolate con nessun altro metodo. David Hilbert si aspettava una risposta positiva all'Entscheidungsproblem, il che significherebbe che tutti i problemi sono calcolabili. Il risultato di Turing ha portato alla scoperta di molti problemi non calcolabili.
Il problema non computabile più famoso è il problema dell'arresto. L'Halting Problem è il problema di creare un algoritmo che può, nel caso generale, decidere se un programma per computer con il suo input si fermerà o andrà avanti all'infinito. Sebbene ci siano casi specifici in cui il problema di Halting può essere risolto, non può essere risolto per ogni programma per computer con qualsiasi input. Questo risultato ha avuto importanti conseguenze per la programmazione dei computer, poiché i programmatori di computer devono essere consapevoli della possibilità di cicli infiniti e dell'impossibilità di rilevare tutti i cicli infiniti prima di eseguire i loro programmi.
Un'altra implicazione della macchina di Turing è la possibilità di macchine di Turing universali. Implicito nel design di Turing è il concetto di memorizzare il programma che modifica i dati insieme ai dati che modifica. Ciò ha suggerito la possibilità di computer di uso generale e riprogrammabili. I computer moderni sono tipicamente macchine di Turing universali, nel senso che possono essere programmati per eseguire qualsiasi algoritmo. Ciò ha eliminato la necessità di hardware diverso per ogni potenziale programma per computer e ha introdotto la distinzione hardware/software.
Il modello della macchina di Turing ha portato direttamente all'invenzione dei computer, ma non è lo stesso progetto utilizzato per progettare i computer moderni. L'architettura von Neumann utilizzata come progetto per i computer moderni utilizza il concetto di programma memorizzato implicito nel modello della macchina di Turing, ma è diversa dal resto del modello della macchina di Turing in molti modi importanti. Le maggiori differenze sono che l'architettura von Neumann non utilizza una testina di lettura-scrittura e include invece più registri, memoria ad accesso casuale, bus dati, un piccolo set di istruzioni macchina di base e capacità di elaborazione di bit multipli. L'architettura von Neumann consente anche esplicitamente dispositivi di input e output specializzati come tastiere e monitor monitor.
Il modello della macchina di Turing è stato il primo modello matematico di calcolo. Ha portato direttamente all'invenzione dei computer fisici. I computer fisici hanno tutte le stesse capacità delle macchine di Turing, assumendo una memoria limitata e vincoli di tempo sul calcolo effettivo. La formulazione di Turing gioca ancora un ruolo centrale nello studio della computazione. Gli informatici sono ancora attivamente coinvolti nella ricerca se funzioni specifiche sono calcolabili dalle macchine di Turing.
