Programmare con la macchina di Turing!
Sezione di VALCON.IT
admin Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza di A e B, termina la sua esecuzione lasciando sul nastro una sola T se la sequenza iniziale contiene almeno una B, una sola F altrimenti. Esempi Nastro iniziale Nastro finale 1° BABBAB T 2° B T 3° AAA F Diagramma di … Leggi tutto
Programmare una Macchina di Turing che, dato un nastro iniziale contenente la rappresentazione decimale di un numero intero positivo n, <> 0, termina la sua esecuzione lasciando sul nastro la rappresentazione decimale di n*100. Esempi Nastro iniziale Nastro finale 1° 431 43100 2° 6 600 Diagramma di stato Si posiziona a destra.Scrive due volte 0. … Leggi tutto
Date due sequenze di 1 separate da *, scrive 1 se sono uguali, 0 altrimenti Esempi Nastro iniziale Nastro finale 1° 11*11 1 2° 11*111 0 Algoritmo Quintuple (0,1,D,-,>) Elimina un 1 a sinistra (0,*,F,-,>) (F,-,H,1,>) (F,1,FF,-,>) (FF,-,H,0,>) (D,1*,D,1*,>) Va a destra (D,-,DD,-,<) (DD,1,S,-,<) (DD,*,SS,-,<) (SS,1,SS,-,<) (SS,-,H,0,<) (S,1*,S,1*,<) Elimina un 1 a destra (S,-,0,-,>) Va … Leggi tutto
Se sul nastro trova CIAO scrive 0, se sul nastro trova BYE scrive 1 Esempi Nastro iniziale Nastro finale 1° CIAO 0 2° BYE 1 Diagramma di stato Ci sono due percorsi distinti di lettura controllata del nastro Tabella delle transizioni di stato A B C E I O Y 0 — 4, -, > … Leggi tutto
Se sul nastro trova 0 scrive CIAO, se trova 1 scrive BYE Esempi Nastro iniziale Nastro finale 1° 0 CIAO 2° 1 BYE Diagramma di stato Ci sono due percorsi distinti di scrittura su nastro Tabella delle transizioni di stato 0 1 – 0 1, C, > 4, B, > — 1 — — 2, … Leggi tutto
Scrivere CIAO con il nastro inizialmente vuoto Esempi Nastro iniziale Nastro finale 1° CIAO Diagramma di stato Tabella delle transizioni di stato – 0 1, C, > 1 2, I, > 2 3, A, > 3 H, O, > H — Quintuple
Tratto dal sito ufficiale Consideriamo una macchina che modifica una sequenza di A rimpiazzando ogni A in posizione dispari con una B.La prima A ha posizione pari uguale a 0. Esempi Nastro iniziale Nastro finale 1° A A 2° AA AB 3° AAA ABA 4° AAAA ABAB Diagramma di stato Quintuple
Aggiunge, a destra, il bit di parità a una sequenza binaria Esempi Nastro iniziale Nastro finale 1° 1 11 2° 0 00 3° 11111 111111 4° 11011 110110 Diagramma di stato Tabella delle transizioni di stato 0 1 – 0 0, 0, > 1, 0, > H, 0, – 1 1, 0, > 0, 0, … Leggi tutto
Se il numero di 1, in una sequenza unaria, è pari/dispari scrive P/D Esempi Nastro iniziale Nastro finale 1° 111 D 2° 11 P 3° P Diagramma di stato Tabella delle transizioni di stato 1 – 0 D, -, > H, P, – 1 0, -, > H, D, – H — — Quintuple … Leggi tutto
Incrementare di 1 per sempre… Esempi Nastro iniziale Nastro finale 1° 999 10001001… 2° 118 119120… 3° 0 12… Diagramma di stato Tabella delle transizioni di stato 0 1 … 8 9 – 0 0, 0, > 0, 1, > … 0, 8, > 0, 9, > 1, -, < 1 0, 1, > 0, … Leggi tutto