macchina di Turing

Una macchina di Turing (termine spesso abbreviato con MdT) è una macchina formale, cioè un sistema formale che può descriversi come un meccanismo ideale, ma in linea di principio realizzabile concretamente, che può trovarsi in stati ben determinati, opera su stringhe in base a regole ben precise e costituisce un modello di calcolo. 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 meccanicistiche piuttosto intuitive. D'altra parte essa ha la portata computazionale (potere computazionale) che si presume essere la massima: si dimostra infatti che essa è equivalente, ossia in grado di effettuare le stesse elaborazioni di tutti gli altri modelli di calcolo di più ampia portata. 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.
Per saperne di più visita Wikipedia.org...

Dispositivo funzionale logico, basato su semplici componenti (una unita' di lettura-scrittura, una unita' di memoria, un nastro), capace di eseguire automaticamente qualsiasi procedura e di simulare qualsiasi elaborazione di dati. La macchina ha lo scopo di studiare le potenzialita' ed i limiti dei moderni elaboratori elettronici. E' stata inventata da A. M. Turing nel 1936 e rappresenta il primo modello teorico di elaboratore programmabile a istruzioni memorizzate.