Edizione V

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

Problema 2 – Parentesi bilanciate

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.

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

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

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

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

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

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

Problema 9 – Sequenza prefissa

Una sequenza di simboli A, B, e C si dice prefissa secondo la seguente definizione:

1. la sequenza composta di un solo simbolo (A, B oppure C) è prefissa;
2. 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).

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

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

esegua il crivello di Eratostene e termini l’esecuzione lasciando sul nastro la sequenza di M simboli

in cui ciascuna P corrisponde a un numero primo q <= M.