Macchina di Turing

[pigi1]

Buona sera a tutti!!

Sono interessato alla Macchina di Turing (MdT); so che vi sono delle semplici MdT che eseguono le operazioni aritmetiche di base, come vi sono anche MdT + ricche di prestazioni e di risorse le quali consentono di descrivere elaborazioni + complesse. In particolare sono interessato a quelle riguardanti i grafi... qualcuno potrebbe consigliarmi delle fonti di qualsiasi natura su cui approfondire?

Grazie a tutti... buona serata

[pigi1]

grazie e... buona domenica

[akiross1]

Ciao,
Io le MdT le ho studiate su 2 libri: il primo (migliore e piu' dettagliato per quanto concerne le MdT) e' "Teoria della computabilita' e della complessita'", di Toffalori, Corradini, Leonesi e Mancini, Ed. McGraw-Hill.
L'altro e' il piu' classico "Automi, linguaggi e calcolabilita'", Hoproft, Ullman e Motwani, ed. Addison-Wesley.

Comunque vorrei ricordare che la MdT si basa su un solo modello che ne descrive le capacita' in senso assoluto. Tutti gli altri modelli, sebbene piu' comodi, non sono piu' potenti.

Quindi, per quel che so, non e' vero che ne esistono altre "piu' ricche di prestazioni e di risorse" (anche perche' una mdt ha storage infinito). Al massimo esistono quelle a piu' nastri, che pero' sono solo piu' comode da usare, ma equipotenti.

Oltre a questo non ho mai sentito altro, relativamente ad operazioni aritmetiche e grafi... Ma suppongo siano solo altre astrazioni costruite sulla mdt per agevolare lo studio di certi argomenti.

Ciao