ESEMPI ELEMENTARI

Date due sequenze di 1 separate da *, scrive 1 se sono uguali, 0 altrimenti Esempi NASTRO INIZIALE NASTRO FINALE 11*11 1 11*111 0 Algoritmo Elimina un 1 a sinistra e un 1 a destra finché non rimane soltanto * Nei casi di errore cancella tutto e scrive 0 Codice Commenti (0,1,D,-,>) Elimina un 1 … Leggi tutto

Se sul nastro trova CIAO scrive 0, se sul nastro trova BYE scrive 1 Esempi NASTRO INIZIALE NASTRO FINALE CIAO 0 BYE 1 Algoritmo Ci sono due percorsi distinti di lettura controllata del nastro Input iniziale è CIAO allora scrive 0 input iniziale è BYE allora scrive 1 Codice Commenti (0,C,1,-,>) Inizia con C (1,I,2,-,>) … Leggi tutto

Se sul nastro trova 0 scrive CIAO, se trova 1 scrive BYE Esempi NASTRO INIZIALE NASTRO FINALE 0 CIAO 1 BYE Algoritmo Ci sono due percorsi distinti di scrittura su nastro Codice Commenti (0,0,1,C,>) Inizia con C (1,-,2,I,>) … (2,-,3,A,>) … (3,-,H,O,>) … (0,1,4,B,>) Inizia con B (4,-,5,Y,>) … (5,-,H,E,>) …

Scrivere CIAO con il nastro inizialmente vuoto Esempi NASTRO INIZIALE NASTRO FINALE   CIAO Algoritmo Codice Commenti (0,-,1,C,>) Scrive C (1,-,2,I,>) Scrive I (2,-,3,A,>) Scrive A (3,-,H,O,>) Scrive O

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 A A AA AB AAA ABA AAAA ABAB Algoritmo Codice Commento (0,A,1,A,>) A dispari (1,A,0,B,>) A pari diventa B

Aggiunge, a destra, il bit di parità a una sequenza binaria Esempi NASTRO INIZIALE NASTRO FINALE 1 11 0 00 11111 111111 11011 110110 Algoritmo Codice Commenti (0,0,0,0,>) Pari –> Pari (0,1,1,1,>) Pari –> Dispari (0,-,H,0,-) Scrive 0 (1,0,1,0,>) Dispari –> Dispari (1,1,0,1,>) Dispari –> Pari (1,-,H,1,-) Scrive 1

Se il numero di 1, in una sequenza unaria, è pari/dispari scrive EVEN/ODD Esempi NASTRO INIZIALE NASTRO FINALE 111 ODD 11 EVEN   EVEN Algoritmo Codice Commenti (0,1,1,-,>) Pari –> Dispari (0,-,2,E,>) Inizia a scrivere EVEN (2,-,3,V,>) (3,-,4,E,>) (4,-,H,N,>) (1,1,0,-,>) Dispari –> Pari (1,-,5,O,>) Inizia a scrivere ODD (5,-,6,D,>) (6,-,H,D,>)

Incrementare di 1 per sempre… Esempi NASTRO INIZIALE NASTRO FINALE 999 10001001… 118 119120… 0 12… Algoritmo Si sposta a destra, sull’ultima cifra Se incontra una cifra diversa da 9 scrive la cifra successiva e ritorna a destra Se incontra un 9 scrive 0 col riporto di 1… e continua a sinistra Codice Commenti (0,0123456789,0,0123456789,>) … Leggi tutto

Tratto dal sito ufficiale Scrivere un programma per macchina di Turing che, ricevuta sul nastro una stringa sull’alfabeto a-z, lasci il nastro vuoto alla fine della computazione se e solo se la stringa originale era palindroma. Si dicono palindrome le stringhe che si leggono identicamente da sinistra a destra o da destra verso sinistra. Esempi … Leggi tutto

Data un numero naturale incrementare di 1 il suo valore Esempi NASTRO INIZIALE NASTRO FINALE 0 1 109 110 999 1000 Algoritmo Codice Commenti (0,0123456789,0,0123456789,>) Vai a destra (0,-,S,-,<) Comincia… (S,012345678-,H,1234567891,>) Scrivi il successivo (S,9,S,0,<) Scrivi 0, col riporto di 1…