IV edizione

Pari || Dispari1

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.

Sequenza 0n1n0n1

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.

Raddoppia 11

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.

Sequenza 101102

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.

Raddoppia 12

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.

Moltiplicazione x112

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).

Sequenza ripetuta x22

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.

Sequenza xSyRz2

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.

EspandiSequenza xAyBzC2

Programmare una macchina di Turing che, data una sequenza del tipo n1xn2yn3z ... con ciascun numero ni > 0 rapsubsentato 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.

MdT Universale30

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:

nastro iniziale nastro finale  
BSNSS11SSNSSS01SSSNSSSS0NITN BSNSS11SSNSSS01SSSNSSSS0NI10T0 Scrive 100
BS0S11S1S01IT0100010100101 NSBS0S11S1S01I1011101011010TN scambia 1 con 0 e viceversa
Soluzione