Cosa è la macchina di Turing?

Risponde Pierluigi Crescenzi del Dipartimento di Matematica e Informatica ‘Ulisse Dini’ Una macchina di Turing è un dispositivo che può trovarsi in un certo numero di stati, ha a disposizione un foglio a quadretti grande a piacere e, in ogni istante, si trova posizionato su un quadretto specifico, in cui c’è scritto un simbolo. Sulla…