Si richiede una MdT che calcoli il resto della divisione per 2.

2

Si richiede una MdT che riconosca i multipli di 100.

Si richiede una MdT che conti gli zeri che compaiono in un numero di tre cifre.

Si richiede una MdT che, data una parola di sole vocali, riconosca, se ci sono vocali uguali consecutive.

Scrivere un programma di quintuple per una macchina di Turing che sommi due numeri naturali * 1.

Alfabeto consigliato {|, *, spazio}.

Non è richiesta la copia dei dati di partenza.

All'inizio la testina è posizionata sulla barra più a destra e così deve essere alla fine. Commentare le quintuple.

Progettare una macchina di Turing che determini il successivo di un numero naturale n scritto in notazione decimale. (La macchina partirà dall'esame della cifra meno significativa e ad essa aggiungerà 1, il che significa che se la cella esaminata contiene una cifra minore di 9 aggiunge 1 e si ferma, altrimenti scrive zero e passa alla casella successiva, aggiunge 1 e si ferma).

Data una stringa composta da 1 e 0 e terminante con il simbolo * (es. 11011*), costruire una macchina di Turing che scriva 1 se la stringa contiene un numero dispari, altrimenti scriva 0.

Progettare una macchina di Turing che calcoli la differenza di due numeri naturali denotati da due stringhe di barre separate da *.

1

Programmare una Macchina di Turing che, dato un nastro iniziale contenente la rappresentazione decimale di un numero intero positivo n (diverso da 0), termina la sua esecuzione lasciando sul nastro la rappresentazione decimale di n.

2

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.

3

Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza di cifre decimali, termina la sua esecuzione lasciando sul nastro la sequenza che si ottiene eliminando tutte le cifre 0 alla sinistra della cifra diversa da 0 più a sinistra. Se la sequenza iniziale è composta da sole cifre 0, la macchina deve lasciare sul nastro un solo 0.

4

Una sequenza si dice palindroma se la sua lettura da sinistra verso destra è uguale alla sua lettura da destra verso sinistra. Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza di A e B, termina la sua esecuzione lasciando sul nastro la sola sequenza SI se la sequenza iniziale è palindroma, la sola sequenza NO altrimenti.

5

Indichiamo con AnBm una sequenza del tipo

Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza del tipo AnBm , con n > 0 e m > 0, termina la sua esecuzione lasciando sul nastro una sola A se n>m, una sola B se m>n, una sola C se n=m.

6

Indichiamo con S e T due generiche sequenze formate da A e B . Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza del tipo SCTC, termina la sua esecuzione lasciando sul nastro la sequenza SI se S e T sono uguali, la sequenza NO altrimenti.

7

Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza di A e B, con almeno una B, termina la sua esecuzione lasciando sul nastro la sequenza di sole B consecutive (cioè non separate da alcuno spazio) che si ottiene da quella iniziale eliminando tutte le A .

8

Dato un numero intero positivo n, n div 2 è il numero se n è pari, se n è dispari. Ad esempio, 6 div 2 è il numero 3, mentre 9 div 2 è il numero 4. Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza composta da n A consecutive (con n > 1), termina la sua esecuzione lasciando sul nastro la sequenza composta da n div 2 A consecutive.

9

Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza di A e B, termina la sua esecuzione lasciando sul nastro la sequenza che si ottiene da quella iniziale rimpiazzando due o più A consecutive con una sola A e due o più B consecutive con una sola B .

1

Programmare una Macchina di Turing che, dato un nastro iniziale contenente la rappresentazione decimale di un numero intero positivo k, termina la sua esecuzione lasciando sul nastro la sola sequenza SI se k è un numero pari, la sola sequenza NO altrimenti.

Esempi

2

Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza di A e B, termina la sua esecuzione lasciando sul nastro la sola sequenza SI se la sequenza iniziale contiene la sottosequenza ABA, la sola sequenza NO altrimenti.

Esempi

3

Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza di A e B di lunghezza dispari, termina la sua esecuzione lasciando sul nastro il simbolo in posizione centrale della sequenza iniziale.

Esempi

4

Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza di A e B termina la sua esecuzione lasciando sul nastro la sequenza ottenuta rovesciando quella iniziale.

Esempi

5

Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza di sole A, termina la sua esecuzione lasciando sul nastro una sequenza di A e B intercalate, di lunghezza doppia rispetto alla sequenza iniziale.

Esempi

6

Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza, eventualmente vuota, contenente un numero pari di A, termina la sua esecuzione lasciando sul nastro la sequenza ottenuta da quella iniziale inserendo al centro della stessa la sequenza BB.

Esempi

7

Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza di A, B e C termina la sua esecuzione lasciando sul nastro la sequenza ottenuta da quella iniziale rimpiazzando ogni sottosequenza ABC con ACB.

Esempi

8

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 sequenza contenente lo stesso numero di A e lo stesso numero di B della sequenza iniziale, in cui però tutte le A precedono tutte le B.

Esempi

9

Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza di A e B termina la sua esecuzione lasciando sul nastro la sola sequenza SI se la sequenza iniziale contiene un numero pari di A e un numero dispari di B, la sola sequenza NO altrimenti.

Esempi

10

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 A se, nella sequenza iniziale, il numero di A è maggiore o uguale del numero di B, una sola B altrimenti. 

Esempi

1

Programmare una macchina di Turing che, dato un nastro iniziale contenente un numero intero n>0, termina la sua esecuzione lasciando sul nastro il numero n-1.

Esempi

2

Programmare una macchina di Turing che, dato un nastro iniziale contenente un numero intero n compreso tra 1 e 9, termina la sua esecuzione lasciando sul nastro n A consecutive.

Esempi

3

Programmare una macchina di Turing che, dato un nastro iniziale contenente una sequenza di n A consecutive (con n>0), termina la sua esecuzione lasciando sul nastro il numero n. 

Esempi

4

Programmare una macchina di Turing che, dato un nastro iniziale contenente due numeri interi positivi x e y separati da una cella vuota tali che x>y e 9>=y>0, termina la sua esecuzione lasciando sul nastro soltanto la differenza tra x e y. 

Esempi

5

Indichiamo con S una sequenza formata da A, B o C ed indichiamo con x e y un simbolo che sia A o B. Programmare una macchina di Turing che, dato un nastro iniziale contenente una sequenza del tipo xyS termina la sua esecuzione lasciando sul nastro la sequenza ottenuta da S rimpiazzando tutte le occorrenze di x con y. 

Esempi

6

Programmare una macchina di Turing che, dato un nastro iniziale contenente due sequenze di A separate da una D, termina la sua esecuzione lasciando sul nastro la sequenza che contiene il maggior numero di A. 

Esempi

7

Indichiamo con S e T due sequenze non vuote e della stessa lunghezza formate da A o B. Programmare una macchina di Turing che, dato un nastro iniziale contenente una sequenza del tipo SDT, termina la sua esecuzione lasciando sul nastro nastro la sola sequenza SI se T è un anagramma di S, la sola sequenza NO altrimenti. 

Esempi

8

Programmare una macchina di Turing che, dato un nastro iniziale contenente un numero intero (arbitrariamente grande), termina la sua esecuzione lasciando sul nastro la sola sequenza SI se il numero è divisibile per 3, la sola sequenza NO altrimenti. 

Esempi

9

Una sequenza di parentesi si dice bilanciata secondo la seguente definizione induttiva:

1. la sequenza vuota è bilanciata,  

2. se S e T sono sequenze bilanciate allora anche la sequenza ( S ) T è bilanciata.

Rappresentando ( con B e ) con E, programmare una macchina di Turing che, dato un nastro iniziale contenente una sequenza di B ed E, termina la sua esecuzione lasciando sul nastro la sola sequenza SI se la sequenza è bilanciata, la sola sequenza NO altrimenti.

Esempi

1

Programmare una macchina di Turing che, dato un nastro iniziale contenente una sequenza arbitraria di 0 e 1, termina la sua esecuzione lasciando sul nastro il bit di parità. Tale bit è 1 se e solo se vi sono un numero dispari di 1 nella sequenza iniziale; altrimenti vale 0. 

Esempi

2

Programmare una macchina di Turing che, dato un nastro iniziale contenente una sequenza arbitraria di 0, 1 e 2, termina la sua esecuzione lasciando sul nastro un bit uguale a 1 se e solo se la sequenza è del tipo 0n1n0n, ovvero ci sono n simboli 0, poi n simboli 1 e infine n simboli 0, per un qualche intero n > 0. Altrimenti, il bit lasciato sul nastro è 0. 

Esempi

3

Programmare una macchina di Turing che, dato un nastro iniziale contenente una sequenza arbitraria di 0 e 1, termina la sua esecuzione lasciando sul nastro una sequenza finale ottenuta da quella iniziale raddoppiando gli 1. 

Esempi

4

Sia fissata a priori la sequenza binaria P = 10110. Programmare una macchina di Turing che, dato un nastro iniziale contenente una sequenza arbitraria di 0 e 1, termina la sua esecuzione lasciando sul nastro un bit uguale a 1 se e solo se la sequenza iniziale contiene P. Altrimenti, il bit lasciato sul nastro è 0. 

Esempi

5

Programmare una macchina di Turing che, dato un nastro iniziale contenente una sequenza di simboli 0, 1, 2 e 3, termina la sua esecuzione lasciando sul nastro la sequenza finale contenente gli stessi elementi ordinati in maniera non decrescente. 

Esempi

6

Programmare una macchina di Turing che, dato un nastro iniziale contenente un intero X rappresentato con cifre decimali, termina la sua esecuzione lasciando sul nastro il risultato della moltiplicazione di X per 11 (in cifre decimali).

Esempi

7

Programmare una macchina di Turing che, dato un nastro iniziale contenente una sequenza arbitraria di 0 e 1, termina la sua esecuzione lasciando sul nastro un bit uguale a 1 se e solo se la sequenza iniziale è della forma xx, ovvero è una sequenza ripetuta due volte. Altrimenti, il bit lasciato sul nastro è 0. 

Esempi

8

Programmare una macchina di Turing che, dato un nastro iniziale contenente una sequenza del tipo xSyRz (in cui x, y e z sono sequenze di simboli 0, 1 e 2, con x e y di uguale lunghezza), termina la sua esecuzione lasciando sul nastro la sola sequenza z in cui ciascun carattere di x è stato sostituito, ordinatamente, con il corrispondente carattere di y. 

Esempi

9

Programmare una macchina di Turing che, data una sequenza del tipo n1xn2yn3z ... con ciascun numero ni > 0 rappresentato con cifre decimali, termini lasciando sul nastro una sequenza di n1 simboli x seguiti da n2 simboli y, da n3 simboli z ecc. Si assuma che i simboli x y e z siano A, B o C. 

Esempi

10

Programmare una macchina di Turing che simuli il comportamento di una versione semplificata di macchina di Turing rappresentata come segue. La macchina si programma con quintuple, gli stati sono rappresentati da sequenze di 'S', mentre i simboli accettati sono 1, 0 e N (che rappresenta il blank o spazio). Una quintupla descritta da

<stato><car><stato><car><dir>

viene codificata su nastro come segue: <stato> è una sequenza lunga a piacere di 'S'; <car> è uno dei simboli '0', '1' e 'N'; infine,<dir> è 0 (sinistra), 1 (destra) oppure N (stai fermo). Seguono alcuni esempi di quintuple e della loro codifica corrispondente:

Indicata con <quintupla> la codifica di una quintupla nel formato appena descritto, un programma sarà espresso come segue:

B<quintupla><quintupla>...<quintupla>I

Ad esempio il programma che scambia 0 con 1 e viceversa può essere realizzato tramite due quintuple:

Viene quindi codificato come: BS0S11S1S01I

L'input della macchina di Turing così codificata si trova subito dopo la 'I' e può essere composto solo da '0', '1' e 'N'. La testina, indicata col simbolo 'T', precede il carattere che indica.

Un nastro contenente una macchina di Turing e il suo input potrebbe essere il seguente: 0001101N0T10010NN10

Si assuma che l'input della macchina simulata possa espandersi solo a destra. Quando l'input ha la testina come ultimo carattere, viene aggiunta una 'N' in fondo:

01010100010010T 01010100010010TN

La macchina inizialmente si trova nello stato 'S' e la testina segue il simbolo 'I'. La computazione deve terminare sempre con la testina sul simbolo 'I'. Un esempio di input è quindi il seguente:

BS0S11S1S01IT0100010100101

Si scriva un programma che interpreti una tale descrizione di macchina di Turing, rispettando l'input proposto. Inoltre seguendo l'algoritmo codificato dalle quintuple sul nastro, esegua il programma sul nastro di input.

Suggerimento: si segua il seguente algoritmo.

Lo stato corrente della macchina viene messo prima della `B` che indica l'inizio del programma. Subito prima dello stato si trova il carattere indicato dalla testina 'T'. Il nastro a un certo punto del calcolo potrebbe essere il seguente:

0SBS0S11S1S01IT0100010100101

Lo stato attuale della macchina simulata è 'S' e 0 è il simbolo che segue 'T'. L'interprete funziona come segue:

1. Scrive lo stato iniziale 'S' prima del simbolo 'B'.

2. Legge il simbolo corrente dopo la 'T' e scrive nel primo carattere bianco a sinistra dello stato corrente.

3. Posiziona la testina del simulatore sulla prima regola da controllare.

4. Confronta lo stato corrente con quello della regola corrente:

   • Lo stato coincide. Verifica che il carattere dopo lo stato sia uguale a quello corrente:

     • Coincide anche il simbolo. Applica la regola sostituendo allo stato corrente quello indicato dalla regola e andando a scrivere il nuovo simbolo dopo il carattere T. Sposta la testina come indicato nella regola. Legge il nuovo simbolo corrente e si ricomincia col passo 1.

     • Il simbolo non coincide. Va al passo 4.

   • Lo stato non coincide. Esamina la prossima regola. Va al passo 4.

    

5. Si trova l'inizio della prossima regola oppure il simbolo 'I'. Nel primo caso si torna al passo 3. Nel secondo caso, la computazione termina.

Esempi:

1

[Sostituzione di caratteri]. Programmare una macchina di Turing che, dato un nastro iniziale contenente una sequenza arbitraria di simboli A e B, sostituisca ogni occorrenza di due simboli consecutivi AB con due simboli CD.

Esempi

2

[Parentesi bilanciate]. Una sequenza di parentesi quadre e graffe annidate si dice bilanciata secondo la seguente definizione: (i) la sequenza vuota è bilanciata; (ii) se S e T sono sequenze bilanciate allora anche le due sequenze { S } T e [ S ] T sono bilanciate. Programmare una macchina di Turing che, dato un nastro iniziale contenente una sequenza (non vuota) di parentesi quadre e graffe, termini la sua esecuzione lasciando sul nastro la sola sequenza SI se la sequenza iniziale è bilanciata e la sola sequenza NO altrimenti.

Esempi

3

[Schedina]. Una colonna di schedina S è una sequenza simboli 1, 2 e X. Data la colonna vincente V, anch'essa costituita da una sequenza di altrettanti simboli scelti tra 1, 2 e X, si vuole verificare che S sia vincente, ovvero ci siano almeno 12 risultati indovinati tra quelli riportati in V. Programmare una macchina di Turing che, dato un nastro iniziale contenente le sequenze S e V separate dal simbolo *, termini la sua esecuzione lasciando sul nastro la sola sequenza SI se S è vincente e la sola sequenza NO altrimenti.

Esempi

4

[Divisione per due]. Programmare una macchina di Turing che, dato un nastro iniziale contenente un numero pari decimale N, termini la sua esecuzione lasciando sul nastro il risultato della divisione di N per 2.

Esempi

5

[Raddoppio di sequenza]. Programmare una macchina di Turing che, dato un nastro iniziale contenente una sequenza arbitraria S di simboli A, B e C, termini la sua esecuzione lasciando sul nastro la sequenza SS, cioè la sequenza originale duplicata.

Esempi

6

[Divisibilità per sei]. Programmare una macchina di Turing che, dato un nastro iniziale contenente un numero decimale N, termini la sua esecuzione lasciando sul nastro la sola sequenza SI se N è divisibile per 6 e la sola sequenza NO altrimenti.

Esempi

7

[Espressioni booleane]. Si vogliono applicare ripetutamente le seguenti regole di sostituzione, dove la sequenza di due o tre simboli (in neretto) a sinistra di ogni freccia va sostituita con il simbolo corrispondente a destra della freccia:

• Sostituzioni NOT: !0 -> 1, !1 -> 0

• Sostituzioni AND: *00 -> 0, *01 -> 0, *10 -> 0, *11 -> 1

• Sostituzioni OR: +00 -> 0, +01 -> 1, +10 -> 1, +11 -> 1

Una sequenza S di simboli 0, 1, !, * e + si dice risolvibile se applicando ripetutamente le sostituzioni suddette, in qualunque ordine, si ottiene alla fine un unico simbolo, chiamato soluzione, ovvero il simbolo 0 oppure il simbolo 1. Per esempio, se S è la sequenza +*1+01*0!*01, si possono applicare le sostituzioni riportate sotto, ottenendo 1 come soluzione (si noti che, nel caso in cui più sostituzioni siano applicabili, l'ordine di applicazione non è rilevante):

+*1+01*0!*01 -> +*11*0!*01

+*11*0!*01 -> +1*0!*01

+1*0!*01 -> +1*0!0

+1*0!0 -> +1*01

+1*01 -> +10

+10 -> 1

Programmare una macchina di Turing che, dato un nastro iniziale contenente una sequenza S risolvibile, termini la sua esecuzione lasciando sul nastro la soluzione di S. Non importa come le sostituzioni vengano realizzate ed eseguite sulla macchina di Turing; è sufficiente che la soluzione finale calcolata (0 oppure 1) sia corretta.

Esempi

8

[Somma]. Programmare una macchina di Turing che, dato un nastro iniziale contenente due numeri decimali N e M, separati dal simbolo +, termini la sua esecuzione lasciando sul nastro la somma di N e M.

Esempi

9

[Sequenza prefissa]. Una sequenza di simboli A, B, e C si dice prefissa secondo la seguente definizione: (i) la sequenza composta di un solo simbolo (A, B oppure C) è prefissa; (ii) se S è una sequenza prefissa allora anche le sequenze SSA, SSB e SSC, costruite duplicando S e aggiungendo un simbolo in fondo, sono sequenze prefisse. Per esempio, A, AAA, AAC, AACAACC e AACAACCAACAACCA sono prefisse, mentre AA, ABA, AABA e ABAABAC non lo sono (ABAABAC non è prefissa perché ABA non è prefissa). Programmare una macchina di Turing che, dato un nastro iniziale contenente una sequenza di simboli A, B, e C, termini la sua esecuzione lasciando sul nastro la sola sequenza SI se la sequenza è prefissa e la sola sequenza NO altrimenti.

Esempi

10

[Crivello di Eratostene]. Un intero q > 1 si dice primo se è divisibile solo per 1 e per se stesso. Per esempio, 2, 3, 5, 7, 11, 13, 17 e 19 sono primi. Dato un numero decimale M, si vogliono individuare tutti i numeri primi q <= M usando il seguente algoritmo, che rappresenta una versione semplificata del "crivello di Eratostene". Si marcano inizialmente come primi tutti i numeri da 2 a M. Sia q l'ultimo numero primo trovato (inizialmente q = 2). Si marcano come "non primi" tutti i numeri maggiori di q che sono multipli di q. Per esempio, se q = 2, si marcano 4, 6, 8, 10, 12, 14, ecc. Quindi, si pone q uguale al successivo numero che risulta marcato come primo, e si ripete la marcatura finché non ci sono ulteriori primi da esaminare. Usando il simbolo P per marcare un primo e il simbolo N per un "non primo", i numeri che rimangono marcati con P alla fine del crivello sono i numeri primi. Per esempio, per M = 20, il crivello esegue i seguenti passi:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

N P P P P P P P P  P  P  P  P  P  P  P  P  P  P  P

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20      q = 2

N P P N P N P N P  N  P  N  P  N  P  N  P  N  P  N

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20       q = 3

N P P N P N P N N  N  P  N  P  N  N  N  P  N  P  N

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20       q = 5,7,11,13,17,19

N P P N P N P N N  N  P  N  P  N  N  N  P  N  P  N

Per M >= 2, sia data una sequenza formata da un simbolo N seguito da M - 1 simboli P, dove l'i-esimo simbolo (P o N) corrisponde al numero 1 <= i <= M. Programmare una macchina di Turing che, dato un nastro iniziale contenente la suddetta sequenza di M simboli NPPPPPPPPPPPPPPP..., esegua il crivello di Eratostene e termini l'esecuzione lasciando sul nastro la sequenza di M simboli NPPNPNPNNNPNPNNNPNPN... in cui ciascuna P corrisponde a un numero primo q <= M.

Esempi

1

Si vuole realizzare l’odometro di Erone da Alessandria, ovvero un contatore a cifre decimali a lunghezza fissa che incrementa di uno il numero N. Quando raggiunge il valore massimo 99…9, ritorna a 00…0. Programmare una macchina di Turing che, dato un nastro iniziale contenente un numero decimale N, termini la sua esecuzione lasciando sul nastro l’incremento di N con l’odometro. Per questo esercizio, i numeri possono contenere zeri iniziali.

Esempi

2

Esempi

3

Esempi

4

Esempi

5

Esempi

6

Esempi

7

Esempi

8

Esempi

9

Esempi

10

Esempi

1

Esempi

2

Esempi

3

Esempi

4

Esempi

5

Esempi

6

Esempi

7

Esempi

8

Esempi

9

Esempi

10

Esempi