Monthly Archives: gennaio 2016

Edizione IV – Problema 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’;
  • <dir> è 0 (sinistra), 1 (destra) oppure N (stai fermo).

Seguono alcuni esempi di quintuple e della loro codifica corrispondente:

Quintupla Codifica
 (sss, 0, s, 1, >) SSS0S11
(sss, -, ss, 0, -)  SSSNSS0N
(s, -, ss, -, <) SNSSN0

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:

Quintupla Codifica
(s,0,s,1,>) S0S11
(s, 1, s, 0, >) S1S01

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.

NASTRO INIZIALE NASTRO FINALE
BSNSS11SSNSSS01SSSNSSSS0NITN BSNSS11SSNSSS01SSSNSSSS0NI10T0
BS0S11S1S01IT0100010100101 NSBS0S11S1S01I1011101011010TN

Osserva

  • Scrive 100
  • Scambia 1 con 0 e viceversa

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.

Soluzione ufficiale

# Stato iniziale
(0, B, init, B, <)
(init, -, start, S, >)

# Va a leggere i simboli
(start, B, gord, B, >)
(gord, S, gord, S, >)
(gord, 0, gord, 0, >)
(gord, 1, gord, 1, >)
(gord, N, gord, N, >)
(gord, I, gord, I, >)
(gord, T, rd, T, >)

# Legge i simboli
(rd, 0, rd0, 0, <)
(rd, 1, rd1, 1, <)
(rd, N, rdN, N, <)
(rd, -, rd, N, -)

# Memorizza il simbolo all'estremità sinistra della stringa
(rd0, T, rd0, T, <)
(rd0, 1, rd0, 1, <)
(rd0, 0, rd0, 0, <)
(rd0, I, rd0, I, <)
(rd0, S, rd0, S, <)
(rd0, N, rd0, N, <)
(rd0, B, rd0, B, <)
(rd0, -, gom, 0, >)

(rd1, T, rd1, T, <)
(rd1, 1, rd1, 1, <)
(rd1, 0, rd1, 0, <)
(rd1, I, rd1, I, <)
(rd1, S, rd1, S, <)
(rd1, N, rd1, N, <)
(rd1, B, rd1, B, <)
(rd1, -, gom, 1, >)

(rdN, T, rdN, T, <)
(rdN, 1, rdN, 1, <)
(rdN, 0, rdN, 0, <)
(rdN, I, rdN, I, <)
(rdN, S, rdN, S, <)
(rdN, N, rdN, N, <)
(rdN, B, rdN, B, <)
(rdN, -, gom, N, >)

# Inizia a fare il match dei simboli
(gom, S, gom, S, >)
(gom, B, gomS, B, >)
(gomS, S, msa, A, <)

# Stati di match
(msa, S, msa, S, <)
(msa, N, msa, N, <)
(msa, 1, msa, 1, <)
(msa, 0, msa, 0, <)
(msa, B, cs, B, <)
(cs, S, cs, S, <)
(cs, X, mark, X, >)
(cs, 0, mark, 0, >)
(cs, 1, mark, 1, >)
(cs, N, mark, N, >)

(mark, S, marked, X, >)
(mark, B, fvfy, B, <)
(marked, S, marked, S, >)
(marked, N, marked, N, >)
(marked, 1, marked, 1, >)
(marked, 0, marked, 0, >)
(marked, B, marked, B, >)
(marked, A, next, S, >)

# Prossimo match
(next, S, msa, A, <)

(next, 0, vrfy0, Z, <)
(next, 1, vrfy1, U, <)
(next, N, vrfyN, M, <)

(vrfy0, S, vrfy0, S, <)
(vrfy0, 1, vrfy0, 1, <)
(vrfy0, 0, vrfy0, 0, <)
(vrfy0, N, vrfy0, N, <)
(vrfy0, B, vfy0, B, <)

(vrfy1, S, vrfy1, S, <)
(vrfy1, 1, vrfy1, 1, <)
(vrfy1, 0, vrfy1, 0, <)
(vrfy1, N, vrfy1, N, <)
(vrfy1, B, vfy1, B, <)

(vrfyN, S, vrfyN, S, <)
(vrfyN, 1, vrfyN, 1, <)
(vrfyN, 0, vrfyN, 0, <)
(vrfyN, N, vrfyN, N, <)
(vrfyN, B, vfyN, B, <)

(vfy0, X, vfy0, X, <)
(vfy0, S, fvfy, S, <)
(vfy0, 0, apply, -, >)
(vfy0, 1, fail, 1, >)
(vfy0, N, fail, N, >)

(vfy1, X, vfy1, X, <)
(vfy1, S, fvfy, S, <)
(vfy1, 0, fail, 0, >)
(vfy1, 1, apply, -, >)
(vfy1, N, fail, N, >)

(vfyN, X, vfyN, X, <)
(vfyN, S, fvfy, S, <)
(vfyN, 0, fail, 0, >)
(vfyN, 1, fail, 1, >)
(vfyN, N, apply, -, >)

# Fallisce
(fvfy, S, fvfy, S, <)
(fvfy, X, fvfy, S, <)
(fvfy, 1, fail, 1, >)
(fvfy, 0, fail, 0, >)
(fvfy, N, fail, N, >)

(fail, X, fail, S, >)
(fail, S, fail, S, >)
(fail, B, fail, B, >)
(fail, 0, fail, 0, >)
(fail, 1, fail, 1, >)
(fail, N, fail, N, >)

(fail, U, nrule, 1, >)
(fail, Z, nrule, 0, >)
(fail, M, nrule, N, >)
(fail, A, failS, S, >)

(failS, S, failS, S, >)
(failS, 0, nrule, 0, >)
(failS, 1, nrule, 1, >)
(failS, N, nrule, N, >)

# Prossima tupla
(nrule, S, nrule, S, >)
(nrule, N, nrules, N, >)
(nrule, 0, nrules, 0, >)
(nrule, 1, nrules, 1, >)
(nrules, 0, nrules, 0, >)
(nrules, 1, nrules, 1, >)
(nrules, N, nrules, N, >)
(nrules, S, msa, A, <)
(nrules, I, STOP, I, -)

# Applica la tupla
(apply, X, apply, -, >)
(apply, B, apply, B, >)
(apply, S, apply, S, >)
(apply, 0, apply, 0, >)
(apply, 1, apply, 1, >)
(apply, N, apply, N, >)

(apply, U, sets, 1, >)
(apply, Z, sets, 0, >)
(apply, M, sets, N, >)

# Prossimo stato
(sets, S, gow, X, <)
(gow, S, gow, S, <)
(gow, N, gow, N, <)
(gow, B, gow, B, <)
(gow, 0, gow, 0, <)
(gow, 1, gow, 1, <)
(gow, -, gowb, S, >)

(gowb, S, gowb, S, >)
(gowb, N, gowb, N, >)
(gowb, B, gowb, B, >)
(gowb, 0, gowb, 0, >)
(gowb, 1, gowb, 1, >)
(gowb, X, sets, S, >)

(sets, 0, s0d?, 0, >)
(sets, 1, s1d?, 1, >)
(sets, N, sNd?, N, >)

(s0d?, 0, s0d0, 0, >)
(s0d?, 1, s0d1, 1, >)
(s0d?, N, s0dN, N, >)
(s1d?, 0, s1d0, 0, >)
(s1d?, 1, s1d1, 1, >)
(s1d?, N, s1dN, N, >)
(sNd?, 0, sNd0, 0, >)
(sNd?, 1, sNd1, 1, >)
(sNd?, N, sNdN, N, >)

# Aggiorna il nastro
(s0d0, S, s0d0, S, >)
(s0d0, N, s0d0, N, >)
(s0d0, I, s0d0, I, >)
(s0d0, 0, s0d0, 0, >)
(s0d0, 1, s0d0, 1, >)
(s0d0, T, ws0d0, T, >)
(ws0d0, 0, gd0, 0, <)
(ws0d0, 1, gd0, 0, <)
(ws0d0, N, gd0, 0, <)

(s0d1, S, s0d1, S, >)
(s0d1, N, s0d1, N, >)
(s0d1, I, s0d1, I, >)
(s0d1, 0, s0d1, 0, >)
(s0d1, 1, s0d1, 1, >)
(s0d1, T, gd1, 0, >)

(s0dN, S, s0dN, S, >)
(s0dN, N, s0dN, N, >)
(s0dN, I, s0dN, I, >)
(s0dN, 0, s0dN, 0, >)
(s0dN, 1, s0dN, 1, >)
(s0dN, T, ws0dN, T, >)
(ws0dN, 0, rd0, 0, <)
(ws0dN, 1, rd0, 0, <)
(ws0dN, N, rd0, 0, <)

(s1d0, S, s1d0, S, >)
(s1d0, N, s1d0, N, >)
(s1d0, I, s1d0, I, >)
(s1d0, 0, s1d0, 0, >)
(s1d0, 1, s1d0, 1, >)
(s1d0, T, ws1d0, T, >)
(ws1d0, 0, gd0, 1, <)
(ws1d0, 1, gd0, 1, <)
(ws1d0, N, gd0, 1, <)

(s1d1, S, s1d1, S, >)
(s1d1, N, s1d1, N, >)
(s1d1, I, s1d1, I, >)
(s1d1, 0, s1d1, 0, >)
(s1d1, 1, s1d1, 1, >)
(s1d1, T, gd1, 1, >)

(s1dN, S, s1dN, S, >)
(s1dN, N, s1dN, N, >)
(s1dN, I, s1dN, I, >)
(s1dN, 0, s1dN, 0, >)
(s1dN, 1, s1dN, 1, >)
(s1dN, T, ws1dN, T, >)
(ws1dN, 0, rd1, 1, <)
(ws1dN, 1, rd1, 1, <)
(ws1dN, N, rd1, 1, <)

(sNd0, S, s1d0, S, >)
(sNd0, N, s1d0, N, >)
(sNd0, I, s1d0, I, >)
(sNd0, 0, s1d0, 0, >)
(sNd0, 1, s1d0, 1, >)
(sNd0, T, ws1d0, T, >)
(wN1d0, 0, gd0, N, <)
(wN1d0, 1, gd0, N, <)
(wN1d0, N, gd0, N, <)

(sNd1, S, s1d1, S, >)
(sNd1, N, s1d1, N, >)
(sNd1, I, s1d1, I, >)
(sNd1, 0, s1d1, 0, >)
(sNd1, 1, s1d1, 1, >)
(sNd1, T, gd1, N, >)

(sNdN, S, s1dN, S, >)
(sNdN, N, s1dN, N, >)
(sNdN, I, s1dN, I, >)
(sNdN, 0, s1dN, 0, >)
(sNdN, 1, s1dN, 1, >)
(sNdN, T, wsNdN, T, >)
(wsNdN, 0, rdN, N, <)
(wsNdN, 1, rdN, N, <)
(wsNdN, N, rdN, N, <)

# Sposta a sinistra
(gd0, T, gd0, T, <)
(gd0, 0, w0, T, >)
(gd0, 1, w1, T, >)
(gd0, N, wN, T, >)
(w0, T, rd0, 0, <)
(w1, T, rd1, 1, <)
(wN, T, rdN, N, <)

# Sposta a destra
(gd1, 0, rd, T, >)
(gd1, 1, rd, T, >)
(gd1, N, rd, T, >)

Edizione IV

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

NASTRO INIZIALE NASTRO FINALE
1011100010 1
0001100101 0
0000 0

Problema 2

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

NASTRO INIZIALE NASTRO FINALE
000111000 1
0011100 0
00100 0

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

NASTRO INIZIALE NASTRO FINALE
0010110101 0011011110110110
1001 110011
0000 0000

Problema 4

Sia fissata a priori la sequenza binaria 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.

NASTRO INIZIALE NASTRO FINALE
0100101101101 1
100010100 0
0100101101101010 1

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

NASTRO INIZIALE NASTRO FINALE
20230321020320002301 00000000112222223333
001223 001223
322100 001223

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

NASTRO INIZIALE NASTRO FINALE
48273 531003
0 0
12 132

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

NASTRO INIZIALE NASTRO FINALE
01110111 1
11011011 0
101101 1

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

NASTRO INIZIALE NASTRO FINALE
1S0R12212 02202
02S10R02201 10011
10S02R10012 22222

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

NASTRO INIZIALE NASTRO FINALE
3A2B1A AAABBA
1C2B1C3A CBBCAAA
10C CCCCCCCCCC

Problema 10

Vedi discussione…

Edizione III

Problema 1

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 A…A (n consecutive).

NASTRO INIZIALE NASTRO FINALE
1 A
5 AAAAA
9 AAAAAAAAA

Problema 2

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.

NASTRO INIZIALE NASTRO FINALE
A 1
AAAAAA 6
AAAAAAAAAAA 11

Problema 3

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 0<y<=9, termina la sua esecuzione lasciando sul nastro soltanto la differenza tra x e y.

NASTRO INIZIALE NASTRO FINALE
9 4 5
13 6 7
302 3 199

Problema 4

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.

NASTRO INIZIALE NASTRO FINALE
ABCAB CBB
BBABC ABC
BA

Problema 5

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.

NASTRO INIZIALE NASTRO FINALE
AADA AA
AADAAA AAA
AADAA AA
DA A

Problema 6

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.

NASTRO INIZIALE NASTRO FINALE
ABADBAA SI
BABADABBA SI
ABBADBAA NO
ABADABB NO

Problema 7

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.

NASTRO INIZIALE NASTRO FINALE
3 SI
27 SI
81 SI
20 NO
7676585 NO

Problema 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 ed E, termina la sua esecuzione lasciando sul nastro la sola sequenza SI se la sequenza è bilanciata, la sola sequenza NO altrimenti.

NASTRO INIZIALE NASTRO FINALE
BEBE SI
BBBEEE SI
BBBEEE SI
BBBEBEEBEE SI
BEE NO
BBBEEB NO

Edizione II

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

NASTRO INIZIALE NASTRO FINALE
148 SI
2763 NO

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

NASTRO INIZIALE NASTRO FINALE
AABAB SI
ABBA NO
BA NO

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

NASTRO INIZIALE NASTRO FINALE
AABAB B
AAA A
B B

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

NASTRO INIZIALE NASTRO FINALE
AABAB BABAA
ABA ABA
A A

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

NASTRO INIZIALE NASTRO FINALE
AA ABAB
AAA ABABAB
A AB

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

NASTRO INIZIALE NASTRO FINALE
AA ABBA
AAAA AABBAA
BB

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

NASTRO INIZIALE NASTRO FINALE
AABCC AACBC
ABCABCA ACBACBA
ACAB ACAB

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

NASTRO INIZIALE NASTRO FINALE
ABBAB AABBB
BABAAA AAAABB
 AAB AAB

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

NASTRO INIZIALE NASTRO FINALE
 ABBAB SI
BBABAA NO
BABA NO
BBB SI

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

NASTRO INIZIALE NASTRO FINALE
 ABABA A
 BBAA A
 BABBA B
 BB B

Edizione I – Problema 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ù consecutive con una sola B.

Esempi

NASTRO INIZIALE NASTRO FINALE
ABAABBBA ABABA
BBAABBBAB ABAB
AAA A
BB B

0109Algoritmo

  • Riconosce una sequenza di A (B) terminata da una B (A)
  • Va a destra e scrive X (Y)
  • Ritorna a sinistra e ricomincia
  • Quando le A e le B sono finite trasforma le X in A e le Y in B.

Codice

(0,A,A,-,>)
(A,A,A,-,>)
(A,BXY,X,BXY,>)
(X,ABXY,X,ABXY,>)
(X,-,S,X,<)
(0,B,B,-,>)
(B,B,B,-,>)
(B,AXY,Y,AXY,>)
(Y,ABXY,Y,ABXY,>)
(Y,-,S,Y,<)
(S,ABXY,S,ABXY,<)
(S,-,0,-,>)
(0,XY,0,AB,>)
Inizia una sequenza di A
Continua...
La sequenza di A è finita
Va a destra per scrivere X
Scrive X
Inizia una sequenza di B
Continua...
La sequenza di B è finita
Va a destra per scrivere Y
Scrive Y
Torna a sinistra
e ricomincia
Trasforma le X e le Y in A e B

Edizione I – Problema 8

Dato un numero intero positivo n, (n div 2) è il quoziente della divisione intera.
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.

Esempi

NASTRO INIZIALE NASTRO FINALE
AAAA AA
AAAAA AA
AAA A
AA A

0108Algoritmo

  • Se legge due A consecutive va a destra, scrive X e ritorna a sinistra
  • Altrimenti traduce le X in A e si ferma

Codice

(0,A,1,-,>)
(0,X,0,A,>)
(1,A,2,-,>)
(1,X,1,A,>)
(2,AX,2,AX,>)
(2,-,R,X,<)
(R,AX,R,AX,<)
(R,-,0,-,>)
Ha letto la prima A
Traduce le X in A
Ha letto la seconda A
Traduce le X in A
Va a destra per scrivere X

Ritorna a sinistra
Ricomincia

Edizione I – Problema 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.

Esempi

NASTRO INIZIALE NASTRO FINALE
ABAABA BB
BAAABABB BBBB
BBB BBB

0107Algoritmo

  • Se incontra una A la cancella
  • Se incontra una B la cancella ma la riscrive a destra come X e ricomincia
  • Quando le A e B finiscono traduce le X in B

Codice

(0,A,0,-,>)
(0,B,B,-,>)
(0,X,0,B,>)
(B,ABX,B,ABX,>)
(B,-,R,X,<)
(R,ABX,R,ABX,<)
(R,-,0,-,>)
Elimina le A
Elimina una B e va nello stato B
Traduce le X in B
Salta ABX per andare a destra
Scrive X e ritorna
Salta ABX per andare a sinistra
Ricomincia

Edizione I – Problema 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.

Esempi

NASTRO INIZIALE NASTRO FINALE
ABACABAC SI
BBBCBBBC SI
BABACBBAC NO
BBBCABC NO

0106Algoritmo

  • Elimina la prima lettera a sinistra, si sposta a destra dopo la C in cerca della stessa lettera che diventa una C
  • Torna a sinistra e ripete
  • Se sul nastro rimangono solo C scrive SI
  • Nei casi di errore cancella tutto e scrive NO

Codice

(0,A,A,-,>)
(0,B,B,-,>)
(0,C,C,-,>)
(A,AB,A,AB,>)
(A,C,AA,C,>)
(AA,C,AA,C,>)
(AA,A,S,C,<)
(AA,B-,X1,B-,<)
(B,AB,B,AB,>)
(B,C,BB,C,>)
(BB,C,BB,C,>)
(BB,B,S,C,<)
(BB,A-,X1,A-,<)
(S,ABC,S,ABC,<)
(S,-,0,-,>)
(C,C,C,-,>)
(C,-,SI,S,>)
(C,AB,X2,-,>)
(SI,-,H,I,>)
(X1,ABC,X1,ABC,<)
(X1,-,X2,-,>)
(X2,ABC,X2,-,>)
(X2,-,NO,N,>)
(NO,-,H,O,>)
...

Edizione IX – Problema 2

Numeri Trini

Un numero intero si dice trino se è divisibile per 3.
Se n è trino, n+1 si dice strino e n+2 distrino.

Si scriva un programma che, dato in input un numero decimale, lasci sul nastro una delle tre stringhe TRINO, STRINODISTRINO a seconda dei casi.

NASTRO INIZIALE NASTRO FINALE
3 TRINO
5 DISTRINO
82 STRINO
0 TRINO

ix0201Algoritmo 1

  1. A seconda della cifra letta passa attraverso gli stati 0, 10, 20
  2. Quando l’input finisce scrive la risposta corrispondente allo stato in cui si trova

Codice

(0,[0369],0 ,-,>)
(0,[147] ,10,-,>)
(0,[258] ,20,-,>)
(0,-,1,T,>)
(1,-,2,R,>)
(2,-,3,I,>)
(3,-,4,N,>)
(4,-,H,O,>)
(10,[0369],10,-,>)
(10,[147] ,20,-,>)
(10,[258] ,0 ,-,>)
(10,-,11,S,>)
(11,-,12,T,>)
(12,-,13,R,>)
(13,-,14,I,>)
(14,-,15,N,>)
(15,-,H ,O,>)
(20,[0369],20,-,>)
(20,[147] ,0 ,-,>)
(20,[258] ,10,-,>)
(20,-,21,B,>)
(21,-,22,I,>)
(22,-,23,S,>)
(23,-,24,T,>)
(24,-,25,R,>)
(25,-,26,I,>)
(26,-,27,N,>)
(27,-,H ,O,>)
 n Mod 3 = 0
...
...
Scrive TRINO
...
...
...
...
n Mod 3 = 1
...
...
Scrive STRINO
...
...
...
...
...
n Mod 3 = 2
...
...
Scrive DISTRINO
...
...
...
...
...
...
...

ix0202Algoritmo 2

  • Come prima ma scrive la risposta a pezzi DISTRINO per risparmiare stati e quintuple

Codice

(0,[0369],0 ,-,>)
(0,[147] ,10,-,>)
(0,[258] ,20,-,>)

(0,-,1,T,>)
(1,-,2,R,>)
(2,-,3,I,>)
(3,-,4,N,>)
(4,-,H,O,>)

(10,[0369],10,-,>)
(10,[147] ,20,-,>)
(10,[258] ,0 ,-,>)

(10,-,0,S,>)

(20,[0369],20,-,>)
(20,[147] ,0 ,-,>)
(20,[258] ,10,-,>)

(20,-,21,D,>)
(21,-,10,I,>)
n Mod 3 = 0
 ...
 ...
 ...
 Scrive TRINO
 ...
 ...
 ...
 ...
 ...
 n Mod 3 = 1
 ...
 ...
 ...
 Scrive STRINO
 ...
 n Mod 3 = 2
 ...
 ...
 ...
 Scrive DISTRINO
 ...

Edizione XII – Problema 3

Completezza

Si scriva un programma per macchina di Turing che, ricevuta in ingresso sul nastro una stringa sull’alfabeto {C, H, O}, lasci sul nastro la scritta SI se la stringa in ingresso conteneva ciascuno dei caratteri dell’alfabeto almeno una volta (la stringa in questo caso si dice completa rispetto all’alfabeto), NO in caso contrario.

Esempi

NASTRO INIZIALE NASTRO FINALE
COO NO
HCCO SI
COO NO
HHHHH NO
OHHHHC SI

Algoritmo

  • Il nome dello stato, C, H, O, CH, CO, HOCHO, indica le lettere diverse incontrate fino a quel momento.
  • Se l’input finisce e si trova nello stato CHO scrive SI
  • Se si trova in un qualsiasi altro stato scrive NO

1203_

Codice

(0,C,C,-,>)
(0,H,H,-,>)
(0,O,O,-,>)
(C,C,C,-,>)
(C,H,CH,-,>)
(C,O,CO,-,>)
(H,C,CH,-,>)
(H,H,H,-,>)
(H,O,HO,-,>)
(O,C,CO,-,>)
(O,H,HO,-,>)
(O,O,O,-,>)
(CH,[CH],CH,-,>)
(CH,O,CHO,-,>)
(CO,[CO],CO,-,>)
(CO,H,CHO,-,>)
(HO,[HO],HO,-,>)
(HO,C,CHO,-,>)
(C,-,NO,N,>)
(CH,-,NO,N,>)
(CO,-,NO,N,>)
(H,-,NO,N,>)
(HO,-,NO,N,>)
(O,-,NO,N,>)
(NO,-,F,O,>)
(CHO,[CHO],CHO,-,>)
(CHO,-,SI,S,>)
(SI,-,F,I,>)
0: nessun carattere letto
...
...
C: ha letta almeno una C
...
...
H: ha letta almeno una H
...
...
O: ha letta almeno una O
...
...
CH: ha letta almeno una C e almeno una H
...
CO: ha letta almeno una C e almeno una O
...
HO: ha letta almeno una H e almeno una O
...
Se l'input finisce prima di aver letto i tre caratteri scrive NO
...
...
...
...
...
...
finisce l'input dopo aver letto sia C che H che O
...
...