ESERCIZI

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 Quintuple (0,0,0,0,>) Pari –> Pari (0,1,D,1,>) Pari –> Dispari (0,-,H,0,-) Scrive 0 (D,0,D,0,>) Dispari –> Dispari (D,1,0,1,>) Dispari –> Pari (D,-,H,1,-) Scrive 1

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 Quintuple (0,1,D,-,>) Pari –> Dispari (0,-,H,P,-) Scrive P(ari) (1,1,0,-,>) Dispari –> Pari (1,-,H,D,-) Scrive D(ispari)

Incrementare di 1 per sempre… Esempi Nastro iniziale Nastro finale 1° 999 10001001… 2° 118 119120… 3° 0 12… Diagramma di stato Quintuple #1 (0, 0, 0, 0, >)(0, 1, 0, 1, >)…(0, 9, 0, 9, >) Va a destra (0, -, 1, -, <) Si posiziona sulla prima cifra e calcola il successivo (1, … 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 1° 0 1 2° 109 110 3° 999 1000 Diagramma di stato Quintuple #1 (0, 0, 0, 0, >) Vai a destra (0, 1, 0, 1, >) (0, 2, 0, 2, >) (0, 3, 0, 3, >) (0, 4, 0, … Leggi tutto

Data una sequenza binaria incrementare di 1 il suo valore Esempi Nastro iniziale Nastro finale 1° 0 1 2° 101 110 3° 111 1000 Diagramma di stato Quintuple #1 (0, 0, 0, 0, >) Va a destra (0, 1, 0, 1, >) … (0, -, 1, -, <) Successivo? (1, 0, H, 1, -) Scrive … Leggi tutto

Or logico di una sequenza di bit Esempi Nastro iniziale Nastro finale 1° 00100 1 2° 00000 0 Diagramma di stato Quintuple (0,0,0,-,>) Il bit 0 non cambia stato (0,1,V,-,>) Il primo bit 1 cambia stato in V (0,-,H,0,-) Finisce con falso, scrive 0 (V,0,V,-,>) Elimina (V,1,V,-,>) (V,-,H,1,>) Finisce con vero, scrive 1

And logico di una sequenza di bit Esempi Nastro iniziale Nastro finale 1° 1110111 0 2° 111 1 Diagramma di stato Quintuple (0,0,F,-,>) Il primo bit 0 porta nello stato F (0,1,0,-,>) Il bit 1 non cambia lo stato (0,-,H,1,-) La sequenza finisce con vero (F,0,F,-,>) Elimina (F,1,F,-,>) … (F,-,H,0,>) La sequenza finisce con falso

And logico tra 2 bit Esempi Nastro iniziale Nastro finale 1° 00 0 2° 01 0 3° 10 0 4° 11 1 Diagramma di stato Quintuple #1 (0, 0, 0X, -, >) Il primo bit è 0 (0, 1, 1X, -, >) Il primo bit è 1 (0X, 0, H, 0, -) 00 -> 0 … Leggi tutto

Complementare un bit Esempi Nastro iniziale Nastro finale 1° 0 1 2° 1 0 Diagramma di stato Legge il bit, scrive il suo complemento e si ferma… Quintuple (0, 0, H, 1, -) O -> 1 (0, 1, H, 0, -) 1 -> 0