Esercizi di Gara della II edizione
Se non specificato altrimenti,
negli esercizi le sequenze iniziali si intendono non vuote, ovvero
contenenti almeno un simbolo.
-
Programmare una Macchina di
Turing che, dato un nastro iniziale contenente la rappresentazione decimale
di un numero intero positivo k, termina la sua esecuzione lasciando sul
nastro la sola sequenza SI
se k è un numero pari, la sola sequenza NO
altrimenti.
Esempi
nastro iniziale
|
nastro finale
|
148
|
SI
|
2763
|
NO
|
-
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 contiene la sottosequenza ABA,
la sola sequenza NO
altrimenti.
Esempi
nastro iniziale
|
nastro finale
|
AABAB
|
SI
|
ABBA
|
NO
|
BA
|
NO
|
-
Programmare una Macchina di
Turing che, dato un nastro iniziale contenente una sequenza di A
e B
di lunghezza dispari, termina la sua esecuzione lasciando sul nastro il
simbolo in posizione centrale della sequenza iniziale.
Esempi
nastro iniziale
|
nastro finale
|
AABAB
|
B
|
AAA
|
A
|
B
|
B
|
-
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 ottenuta rovesciando
quella iniziale.
Esempi
nastro iniziale
|
nastro finale
|
AABAB
|
BABAA
|
ABA
|
ABA
|
A
|
A
|
-
Programmare una Macchina di
Turing che, dato un nastro iniziale contenente una sequenza di sole A,
termina la sua esecuzione lasciando sul nastro una sequenza di A
e B
intercalate, di lunghezza doppia rispetto alla sequenza iniziale.
Esempi
nastro iniziale
|
nastro finale
|
AA
|
ABAB
|
AAA
|
ABABAB
|
A
|
AB
|
-
Programmare una Macchina di
Turing che, dato un nastro iniziale contenente una sequenza, eventualmente
vuota, contenente un numero pari di A,
termina la sua esecuzione lasciando sul nastro la sequenza ottenuta da
quella iniziale inserendo al centro della stessa la sequenza BB.
Esempi
nastro iniziale
|
nastro finale
|
AA
|
ABBA
|
AAAA
|
AABBAA
|
|
BB
|
-
Programmare una Macchina di
Turing che, dato un nastro iniziale contenente una sequenza di A,
B
e
C
termina la sua esecuzione lasciando sul nastro la sequenza ottenuta da
quella iniziale rimpiazzando ogni sottosequenza ABC
con ACB.
Esempi
nastro iniziale
|
nastro finale
|
AABCC
|
AACBC
|
ABCABCA
|
ACBACBA
|
ACAB
|
ACAB
|
-
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 sequenza contenente
lo stesso numero di A
e lo stesso numero di B
della sequenza iniziale, in cui però tutte le A
precedono tutte le B.
Esempi
nastro iniziale
|
nastro finale
|
ABBAB
|
AABBB
|
BABAAA
|
AAAABB
|
AAB
|
AAB
|
-
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 contiene un numero pari di A
e un numero dispari di B,
la sola sequenza NO
altrimenti.
Esempi
nastro iniziale
|
nastro finale
|
ABBAB
|
SI
|
BBABAA
|
NO
|
BABA
|
NO
|
BBB
|
SI
|
-
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 A
se, nella sequenza iniziale, il numero di A
è maggiore o uguale del numero di B,
una sola B
altrimenti.
Esempi
nastro iniziale
|
nastro finale
|
ABABA
|
A
|
BBAA
|
A
|
BABBA
|
B
|
BB
|
B
|
|
|
|
|