Les màquines
Turing són semblants als autòmats finits/màquines d'estats finits, però tenen l'avantatge de la memòria il·limitada … Són capaços de simular ordinadors comuns; un problema que un ordinador comú pot resoldre (amb prou memòria) també es podrà resoldre amb una màquina de Turing, i viceversa.
Quina diferència hi ha entre la memòria RAM i la TM?
Una màquina de Turing no pot Una màquina de RAM pot fer aritmètica en O(1) (sota determinades restriccions). Una màquina de Turing no pot. Les màquines de Turing simulen polinomialment màquines RAM, és a dir, per a una constant c, qualsevol màquina RAM que funcioni en el temps O(nk) pot ser simulada per una màquina de Turing que funcioni en el temps O(nck).
La cinta d'una màquina de Turing és il·limitada?
A Turing Machine (TM) és una màquina d'estats que consta de dues memòries: una cinta il·limitada i una taula de control d'estats finits. La cinta conté dades com a símbols. La màquina té un conjunt molt reduït d'operacions adequades, 6 (llegir, escriure, moure's a l'esquerra, moure's a la dreta, canviar d'estat, aturar-se) a la cinta.
Per què la màquina de Turing és potent?
Quina potència tenen les màquines de Turing? Les màquines de Turing poden acceptar qualsevol llenguatge normal o sense context. Les màquines de Turing poden realitzar càlculs aritmètics bàsics … La tesi de Turing diu que qualsevol càlcul que es pugui dur a terme per “mitjans mecànics” pot ser realitzat per una màquina de Turing (ignorant els problemes d'eficiència).
Les màquines de Turing poden fer un bucle per sempre?
turing(turingDescrip) no pot aturar-se ni fer un bucle per sempre; no té sentit de cap manera.
