Esercizi di Gara della III edizione
- 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.
Esempi
|
nastro iniziale |
nastro finale |
|
1 |
A |
|
5 |
AAAAA |
|
9 |
aaaaaaaaa |
- 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.
Esempi
|
nastro iniziale |
nastro finale |
|
A |
1 |
|
AAAAAA |
6 |
|
AAAAAAAAAAA |
11 |
- 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.
Esempi
|
nastro iniziale |
nastro finale |
|
9-4 |
5 |
|
13-6 |
7 |
|
302-3 |
299 |
- 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.
Esempi
|
nastro iniziale |
nastro finale |
|
ABcAB |
CBB |
|
BBABC |
ABC |
|
BA |
|
- 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.
Esempi
|
nastro iniziale |
nastro finale |
|
AADA |
AA |
|
AADAAA |
AAA |
|
AADAA
DA |
AA
A |
- 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.
Esempi
|
nastro iniziale |
nastro finale |
|
ABADBAA |
SI |
|
BABADABBA |
SI |
|
ABBDBAA
ABADABB |
NO
NO |
- 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.
Esempi
|
nastro iniziale |
nastro finale |
|
3 |
SI |
|
27 |
SI |
|
81 |
SI |
|
20 |
NO |
|
7676585 |
NO |
- Una sequenza di parentesi si dice bilanciata secondo la seguente definizione induttiva:
- la sequenza vuota è bilanciata,
- 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.
Esempi
|
nastro iniziale |
nastro finale |
|
BEBE |
SI |
|
BBBEEE |
SI |
|
BBEBEE
BBBEBEEBEE |
SI
SI |
|
BEE |
NO |
|
BBEEEB |
NO |