V edizione

Sostituzione di caratteri1

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.

Parentesi bilanciate2

Una sequenza di parentesi quadre e graffe annidate si dice bilanciata secondo la seguente definizione:
  1. la sequenza vuota è bilanciata;
  2. 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.

Schedina3

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.

Divisione x23

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.

Raddoppio di sequenza2

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.

Divisibilità x63

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.

Espressioni booleane5

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