Partiamo dal principio. Cos’è una macchina di Turing? All’apparenza è una macchina molto semplice composta da una testina che si può spostare a sinistra e a destra su un nastro infinito. Le sue operazioni consistono nel leggere un valore dal nastro (detto simbolo) e, in base a delle regole ben definite (il programma) e a […]