Macchina Di Turing Esercizio Somma Uno a Un Numero Dato

TESTO ESERCIZIO

implementare una macchina di turing che dato in input un numero, lasci sul nastro il numero sommato di uno

Esercizio sulla macchina di Turing - Analisi

Questa Macchina di Turing implementa un sommatore. La somma binaria è definita secondo le solite regole. Nel caso della macchina di turing le operazioni da fare (che corrisponderanno ai vari stati della macchina) sono

ISCRIVITI AL CANALE YOUTUBE
...
  • posizionarsi a destra della stringa scritta sul nastro
  • leggere il primo elemento, scorrendo a sinistra:
    • Se il numero è zero, scrive 1 e termina
    • Se il numero è 1 cambia stato (sta sommando e deve registrarlo nello stato).
  • Se sta sommando con riporto e legge 0 scrive 1 e termina
  • Se sta sommando con riporto e legge 1, scrive 0 e continua

Utilizzando la sitassi del simulatore della Macchina di turing si ha la macchina seguente:

; scrorre a destra la stringa
0 * * r 0
0 _ _ l 1 

; stato 1 (sta sommando senza riporto)
1 0 1 * halt-end
1 1 0 l 2

; stato 2 (sta sommando con riporto)
2 0 1 * halt-end
2 1 0 l 2
2 _ 1 * halt-end

Altre lezioni in: Teoria sugli Algoritmi

Altre lezioni in: informatica

Avatar
Prof. Andrea Pollini
Docente di Ruolo Informatica (A41) Docente Universitario corso di Sistemi Operativi e Architettura degli Elaboratori

Matematico e Informatico. Ammiro il mondo, penso e immagino un futuro di innovazione. Mi adopero per formare alla creatività e all’imprenditorialità le nuove generazioni. Risolvo problemi complessi per le aziende.

comments powered by Disqus