Utente:Davide0402/Sandbox

In informatica una macchina di Turing (o più brevemente MdT) è una macchina ideale che manipola i dati contenuti su un nastro di lunghezza potenzialmente infinita, secondo un insieme prefissato di regole ben definite. In altre parole, è un modello astratto che definisce una macchina in grado di eseguire algoritmi e dotata di un nastro potenzialmente infinito su cui può leggere e/o scrivere dei simboli.

È un potente strumento teorico che viene largamente usato nella teoria della calcolabilità e nello studio della complessità degli algoritmi, in quanto è di notevole aiuto agli studiosi nel comprendere i limiti del calcolo meccanico. La sua importanza è tale che oggi, per definire in modo formalmente preciso la nozione di algoritmo, si tende a ricondurlo alle elaborazioni effettuabili con macchine di Turing.

La MdT come modello di calcolo è stata introdotta nel 1936 da Alan Turing per dare risposta all'Entscheidungsproblem (problema di decisione) proposto da Hilbert nel suo programma di fondazione formalista della matematica.

Essa ha la particolarità di essere retta da regole di natura molto semplice, ovvero di potersi descrivere come costituita da meccanismi elementari molto semplici; inoltre è possibile presentare a livello sintetico le sue evoluzioni mediante descrizioni meccaniche piuttosto intuitive. D'altra parte, essa ha la portata computazionale (potere computazionale) che si presume essere la massima: si dimostra, infatti, che essa è in grado di effettuare tutte le elaborazioni effettuabili dagli altri modelli di calcolo noti all'uomo. Tra questi modelli di calcolo ricordiamo le funzioni ricorsive di Jacques Herbrand e Kurt Gödel, il lambda calcolo di Alonzo Church e Stephen Kleene, la logica combinatoria di Moses Schönfinkel e Haskell Curry, gli algoritmi di Markov, i sistemi di Thue, i sistemi di Post, le macchine di Hao Wang e le macchine a registri elementari o RAM astratte di Marvin Minsky. Di conseguenza si è consolidata la convinzione che per ogni problema calcolabile esista una MdT in grado di risolverlo: questa è la cosiddetta congettura di Church-Turing, la quale postula in sostanza che per ogni funzione calcolabile esista una macchina di Turing equivalente, ossia che l'insieme delle funzioni calcolabili coincida con quello delle funzioni ricorsive.

Gli algoritmi che possono essere implementati da una MdT si dicono "algoritmi Turing-computabili". Caratteristiche

Nel 1936 venne pubblicato un articolo di Alan Mathison Turing intitolato On computable numbers, with an application to the Entscheidungsproblem, in cui l'autore risolveva negativamente l'Entscheidungsproblem o problema della decidibilità lanciato nel 1900 da David Hilbert e Wilhelm Ackermann.

La questione era stata posta da Hilbert nei seguenti termini: «esiste sempre, almeno in linea di principio, un metodo meccanico (cioè una maniera rigorosa) attraverso cui, dato un qualsiasi enunciato matematico, si possa stabilire se esso sia vero o falso?»

I vantaggi derivanti dal possedere un tale metodo sono enormi e meritano tutta l'enfasi che Hilbert e molti altri al suo seguito, diedero alla questione: un tale algoritmo sarebbe in grado di risolvere tutti i problemi matematici e, molto di più, sarebbe possibile ridurre ogni ragionamento umano a mero calcolo meccanizzabile. Una prima forte risposta la diede il matematico boemo Gödel in occasione della conferenza sull'epistemologia delle scienze esatte di Könisberg (1931), in cui espresse per la prima volta pubblicamente le idee racchiuse nel suo più celebre lavoro sull'incompletezza dei sistemi formali coerenti (primo teorema di incompletezza); Gödel dimostrò che la semplice coerenza di un sistema formale non può garantire che ciò che in esso viene dimostrato sia vero oppure falso. Il sogno di Hilbert stava già sfumando quando Turing pubblicò il suo articolo, in cui dimostrò l'insolubilità dell'Entscheidungsproblem.

"Un giovane sconosciuto di nome Alan Turing risolse il quesito quasi per gioco. Con una macchina immaginaria."[1].

La soluzione proposta da Turing consiste nell'utilizzo di un modello matematico capace di simulare il processo di calcolo umano, scomponendolo nei suoi passi ultimi. La macchina è formata da una testina di lettura e scrittura con cui è in grado di leggere e scrivere su un nastro potenzialmente infinito partizionato, in maniera discreta, in caselle. Ad ogni istante di tempo t1, la macchina si trova in uno stato interno s1 ben determinato, risultato dell'elaborazione compiuta sui dati letti.

Lo stato interno, o configurazione, di un sistema è la condizione in cui si trovano le componenti della macchina ad un determinato istante di tempo t. Le componenti da considerare sono:

• il numero della cella osservata
• il suo contenuto
• l'istruzione da eseguire

Tra tutti i possibili stati, si distinguono:

   una configurazione iniziale, per t=t0 (prima dell'esecuzione del programma)
   una configurazione finale, per t=tn (al termine dell'esecuzione del programma)
   delle configurazioni intermedie, per t=ti (prima dell'esecuzione dell'istruzione oi)

Implementare un algoritmo in questo contesto significa effettuare una delle quattro operazioni elementari

   spostarsi di una casella a destra
   spostarsi di una casella a sinistra
   scrivere un simbolo preso da un insieme di simboli a sua disposizione su una casella
   cancellare un simbolo già scritto sulla casella che sta osservando
   oppure fermarsi

Eseguire un'operazione o1, tra gli istanti di tempo t1 e t2, vuol dire passare dallo stato interno s1 al s2. Più formalmente questo si esprime in simboli come: {s1,a1,o1,s2} da leggersi come: nello stato interno s1 la macchina osserva il simbolo a1, esegue l'operazione o1 e si ritrova nello stato interno s2. Turing poté dimostrare che un tale strumento, dalle caratteristiche così rigidamente definite, è in grado di svolgere un qualsiasi calcolo, ma non si fermò qui; egli capì che la calcolabilità era parente stretta della dimostrabilità e dunque, così come Gödel aveva distrutto i sogni di gloria dei Principia Mathematica di Russell e Whitehead, così le sue macchine potevano definitivamente chiudere la questione dell'Entscheidungsproblem.