x1001

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.

È presente una B1

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 Tse la sequenza iniziale contiene almeno una B, una sola Faltrimenti.

Elimina Zeri1

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.

Palindroma1

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.

Maggiore A || B2

Indichiamo con AⁿB^m una sequenza del tipo AAABB.
Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza del tipo AⁿB^m, 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.

SCTC uguali! 2

Indichiamo con S e T due generiche sequenze formate da A e C.
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.

B consecutive2

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.

n div 22

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 8 div 2 è il numero 4.
Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza composta da n Aconsecutive (con n > 1), termina la sua esecuzione lasciando sul nastro la sequenza composta da n div 2 A consecutive.

Sostituisci le Doppie2

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.