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…