Macchina di Turing: differenze tra le versioni

Contenuto cancellato Contenuto aggiunto
Nessun oggetto della modifica
m Annullate le modifiche di 80.68.181.66 (discussione), riportata alla versione precedente di 2001:760:2C00:6:15CE:DE29:3A35:2011
Riga 2:
[[File:Turing Machine.png|thumb|upright=1.4|Una rappresentazione grafica della macchina di Turing]]
 
In [[informatica|inform]] 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 [[algoritmo|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 [[Algoritmo#Modelli formali|definire in modo formalmente preciso]] la nozione di algoritmo, si tende a ricondurlo alle elaborazioni effettuabili con macchine di Turing.