III Edizione

ScriviA1

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

ContaA1

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.

DifferenzaXY2

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

SostituisciAorBruntime2

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.

MaggioreSeqA2

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.

Sequenza SDT1

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.

Divisibile x32

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.

Sequenza bilanciata2

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