Please enable JavaScript.
Coggle requires JavaScript to display documents.
Macchine di Turing - Coggle Diagram
Macchine di Turing
E' un
modello matematico
di un computer
Venne proposto da
Alan Turing
nel 1936
Serve a descrivere cosa può calcolare un algoritmo
Se un problema è risolvibile da un computer, allora lo è anche da una MdT (viceversa)
E' più potente di un
automa finito
Perché ha una
memoria molto più ampia
Lavora su un solo
nastro
Utilizza una
testina di lettura e scrittura
Le 4 differenze fondamentali. con gli automi finiti
Un automa finito legge soltanto
La MdT legge e scrive sul nastro (modificando la memoria)
Una MdT può muovere la testina a sinistra o destra
Una MdT ha un nastro infinito con
memoria illimitata
Una MdT non deve leggere per forza tutta la parola
Si ferma subito quando entra in uno stato di accettazione o rifiuto
Il nastro è la
memoria della macchina
Contiene all'inizio la stringa di input
In tutte le altre celle continue, ha il simbolo blank
La
testina
Legge il simbolo corrente
Può scrivere un nuovo simbolo
Si sposta a sinistra o destra