Category Archives: Gara Bazionale

Edizione XX

Problema 1

 


Problema 2

 


Problema 3

 


Problema 4

 


Problema 5

 


Problema 6

 


Problema 7

 


Problema 8

 


Problema 9


Problema 10

 

Edizione XIX

Problema 1 –  Inaugurazione

Nella piccola cittadina tedesca di Maschinestadt, in Turingia, sta per aprire un nuovo circolo culturale.
Il proprietario, Alan, ha invitato una serie di abitanti all’inaugurazione, e ha segnato su una lista una “S” per ogni invito accettato, e una “N” per ogni invito rifiutato.

Si scriva un programma per macchina di Turing che, ricevuta sul nastro di input una sequenza di simboli “S” e “N”, lasci sul nastro una sequenza di tante “S” quanti sono le “S” nella sequenza di input (la lunghezza della risposta corrisponderà al numero di persone che hanno accettato l’invito all’inaugurazione).


Problema 2 – Una misura di successo

Una inaugurazione di circolo a cui partecipano meno di 10 persone è un fallimento.

Si scriva un programma per macchina di Turing che, ricevuta sul nastro di input una sequenza di simboli sull’alfabeto {S, N} come nell’esercizio precedente, lasci sul nastro il solo simbolo “S” (per Successo) se la sequenza di input comprendeva almeno 10 “S”, e “F” (per Fallimento) in caso contrario.


Problema 3 – Più siamo più ci divertiamo

Alle feste di Alan partecipano sempre più persone. All’ingresso, viene segnata con una “X” su un nastro ogni persona entrata.
A fine serata, si vuole sapere quante persone hanno partecipato alle attività.

Si scriva un programma per macchina di Turing che, ricevuta sul nastro di ingresso una sequenza di “X”, lasci sul nastro il numero decimale corrispondente alla lunghezza della sequenza (ovvero, al numero di persone che sono entrate nella serata).
Per questo esercizio, è possibile che la sequenza di input sia vuota (ovvero, nessuno è entrato); in questo caso il programma deve lasciare sul nastro il numero 0.


Problema 4 – Il giusto mix

Si sa, una festa funziona meglio se c’è un giusto mix di ragazzi e ragazze.
Per questo motivo, il lunedì sera il club di Alan offre l’ingresso gratis ai rappresentanti del genere che in quel momento è minoritario.

Si scriva un programma per macchina di Turing che, ricevuta sul nastro di input una sequenza di simboli “M” (che indica l’ingresso di un ragazzo) e “F” (che indica l’ingresso di una ragazza), lascia sul nastro un simbolo “F” se deve essere offerto l’ingresso gratis alle ragazze, oppure “M” se deve essere offerto ai ragazzi.
In caso di parità, per cavalleria, è gratuito l’ingresso per le ragazze.


Problema 5 – Ingressi e uscite

Il martedì sera il circolo di Alan è ad ingresso libero: si svolgono dibattiti culturali sul tema dell’Entscheidungsproblem.
Per qualche motivo, questi sono meno popolari delle feste del lunedì; entrano tante persone, ma molte escono (qualcuna, visibilmente pallida in volto) dopo pochi minuti.
Alan chiede al personale all’ingresso di segnare con “M” e “F” gli ingressi, come nell’esercizio precedente, e con “N” e “E” le rispettive uscite.

Si scriva un programma per macchina di Turing che, ricevuta sul nastro di ingresso una sequenza di simboli in {M, F, N, E} (con la garanzia che per ogni genere le uscite non possono superare gli ingressi), lasci sul nastro come risultato la sequenza “MkFh” in cui k e h sono espressi come numeri decimali, e indicano quante persone per il corrispondente genere sono ancora dentro il circolo nel momento in cui si analizza la sequenza.


Problema 6 – Posti a tavola

Il mercoledì sera il circolo organizza una cena fra i soci, che siedono tutti a una grande tavola circolare (viene usato un nastro infinito per trasportare le vivande, sul modello dei ristoranti Kaiten-zushi).
Come al solito, la serata è più gradevole se ogni commensale uomo ha almeno un membro del gentil sesso accanto, e viceversa.
Ovviamente, non sempre questo è possibile: dipende dal numero dei commensali.

Si scriva un programma per macchina di Turing che, ricevuta sul nastro di input una sequenza di “M” e “F” che rappresentano gli ingressi come negli esercizi precedenti, lasci sul nastro la risposta “OK” se esiste una disposizione dei commensali al tavolo circolare che garantisce la proprietà di gradevolezza di cui sopra, e “KO” in caso contrario.


Problema 7 – Bingo binario

Il giovedì sera è dedicato agli anziani, e Alan organizza per loro un Bingo un po’ semplificato.
Ogni giocatore ha una cartella, composta da 4×4 caselle; in ogni casella è presente un simbolo “0” o “1”.
Viene poi estratta una sequenza di 4 simboli fra “0” e “1”.
Il giocatore che ha nella propria cartella l’esatta sequenza estratta, in orizzontale (da sinistra a destra), verticale (dall’alto al basso) o diagonale (da alto-sinistra a basso-destra) vince il premio per quella mano.

Si scriva un programma per macchina di Turing che, ricevuta sul nastro di ingresso una codifica della cartella (in cui le 4 righe di simboli sono riportate in sequenza, da sinistra a destra, iniziando dalla riga più in alto), seguita da un simbolo “#” e poi dalla sequenza di 4 simboli estratta; lasci sul nastro “SI” se la cartella è vincente, “NO” in caso contrario.


Problema 8 – Cinema, cinema!

Il venerdì sera è giorno di cineforum presso il club di Alan.
Il circolo è senza scopo di lucro, per cui il costo del biglietto viene calcolato dividendo il costo di noleggio del film per il numero di persone che partecipano alla serata.
Per semplicità, il costo è sempre un numero intero di euro, approssimando in alto la quota individuale. L’eventuale (piccolo) avanzo viene destinato a fondo cassa per altre iniziative.
Inoltre, il costo del biglietto è sempre inferiore a €10: se il numero di partecipanti non è sufficiente a garantire questa condizione, la serata viene annullata (e non si paga il noleggio).

Si scriva un programma per macchina di Turing che, ricevuto sul nastro di input il costo di noleggio espresso in euro, seguito da un simbolo “/” e poi dal numero di partecipanti, lasci sul nastro il costo del biglietto seguito dal simbolo “”%” e dal residuo di fondo cassa, oppure “NO” se la serata va annullata per via del costo del biglietto troppo alto.


Problema 9 –  Il Social Network

Per pubblicizzare le feste danzanti del sabato sera, Alan ricorre ai social network.
Il problema consiste nell’identificare le persone che hanno maggiore influenza (intesa come: numero di amici e di amici degli amici), e fornire loro un invito gratis a condizione che costoro pubblicizzino l’evento con un post sulla loro bacheca.
Diamo una rappresentazione del social network in cui gli abitanti dotati di presenza online sono indicati con una lettera dell’alfabeto fra “A” e “Z” (Maschinestadt è una città molto piccola).
Gli amici di una persona sono indicati, fra parentesi, subito dopo il nome della persona.
Così, per esempio, A(BF)B(CDEF)C(AEF) indica che A è amico di B e F, e B è amico di C, D, E e F, C è amico di A, E e F (si noti che la relazione di amicizia su questo social network non è simmetrica: A è amico di B, ma B non è amico di A).
Nel nostro esempio, A ha 2 amici (B,F); di questi, B ha 4 amici (C,D,E,F), e F nessuno; complessivamente quindi la cerchia (ovvero: amici e amici degli amici, escludendo la persona in questione) di A comprende (B,C,D,E,F) e la sua influenza è pari a 5.
Analogamente, B ha 4 amici (C,D,E,F); di questi, C ha 3 amici (A,E,F), e gli altri nessuno.
La cerchia di B comprende (A,C,D,E,F) e la sua influenza è quindi pari a 5.
Quanto a C, la sua cerchia comprende (A,B,E,F) e la sua influenza è dunque 4.

Si scriva un programma per macchina di Turing che, data in input la descrizione di un social network nel formato indicato sopra, lasci sul nastro il nome della persona di massima influenza fra quelle presenti nel social network.
In caso di parità, il programma deve lasciare su nastro il nome della persona fra gli ex-æquo che compare per prima nella descrizione in input.


Problema 10

 

Edizione XVIII

Problema 1

 


Problema 2

 


Problema 3

 


Problema 4

 


Problema 5

 


Problema 6

 


Problema 7

 


Problema 8

 


Problema 9


Problema 10

 

Edizione XVII

Problema 1 – Cambio di casacca

Nel Mondo dei Programmatori, la vita politica è molto intensa e piena di sorprese.
Nuove liste e partiti si formano e dissolvono di continuo, mentre i Programmatori discutono di quale sia il linguaggio migliore da utilizzare.

Per esempio, fino a qualche anno fa si contavano vari movimenti:

  • i Programmatori C Indipendenti (simbolo: c),
  • i Discreti & Continui (simbolo: d),
  • i Programmatori Strutturalisti (simbolo: s)
  • e i Programmatori Lisp Integralisti (simbolo: l).

Negli anni, questi raggruppamenti hanno cambiato molte volte nome, al punto che si è preferito numerarli per chiarezza.

Così,

  • i Programmatori C Indipendenti sono diventati il partito 0,
  • i Discreti & Continui sono diventati il partito 1,
  • i Programmatori Strutturalisti sono diventati il partito 2,
  • e i Programmatori Lisp Integralisti il partito 3.

Si scriva un programma per macchina di Turing che, ricevuta sul nastro una stringa sull’alfabeto {c, d, s, l}, in cui ogni simbolo rappresenta un elettore del corrispondente partito, lasci sul nastro gli stessi elettori, codificati però sull’alfabeto {0, 1, 2, 3}.

NASTRO INIZIALE NASTRO FINALE
dccsdlcdd 10021011
c 0
2012AD 100AT
dddd 1111
lcccl 30003

Problema 2 – Il Seggio Ben Ordinato

In tempo di votazioni, i Programmatori si mettono ordinatamente in fila al seggio (indicato dal simbolo S).
Un seggio è ben ordinato se la fila scorre in una unica direzione man mano che gli elettori votano (ovvero: tutti gli elettori sono, sul nastro, alla sinistra del seggio oppure tutti alla destra del seggio), mentre è mal ordinato in caso contrario.

Si scriva un programma per macchina di Turing che, ricevuto sul nastro una stringa sull’alfabeto {0, 1, 2, 3, s} rappresentate la fila degli elettori e il seggio, lasci sul nastro il solo simbolo B se il seggio era ben ordinato, M altrimenti.
Il seggio vuoto si considera ben ordinato.

NASTRO INIZIALE NASTRO FINALE
130201301123230S B
S0001 B
12321S3021 M
S B
1S12301202013302 M

Problema 3 – Calcolo dell’affluenza

Si scriva un programma per macchina di Turing che, ricevuto in ingresso una configurazione di seggio (ben ordinato o meno), lasci sul nastro un numero decimale rappresentante il numero totale di elettori presenti nella configurazione.

NASTRO INIZIALE NASTRO FINALE
S01200213 8
123001002S0123301 16
S 0
1S 1

Problema 4 – Caccia ai brogli!

Nel Mondo dei Programmatori il partito dei Programmatori C Indipendenti (il partito 0) ha fiducia assoluta nella fedeltà del proprio elettorato, e avendo ottenuto alle scorse elezioni meno voti di quelli previsti, sospetta che i partiti avversari abbiano trovato il modo di alterare il conteggio delle schede.

Si scriva un programma per macchina di Turing che, ricevuto in ingresso una sequenza di schede, ciascuna indicata con un simbolo fra 0 e 3, seguita dal simbolo ‘:‘ e poi dal numero di voti attesi espresso in decimale, lasci sul nastro la scritta OK se la votazione appare regolare, KO se si ritiene di poter contestare il risultato.

NASTRO INIZIALE NASTRO FINALE
011023001:2 KO
120113:1 OK
12312111:0 OK
0120000:5 OK
12334:12 KO
1022000320100300120030:12 OK

Problema 5 – Il sistema maggioritario

Nel Mondo dei Programmatori è in vigore il sistema maggioritario: il partito che ottiene più voti, vince (e impone a tutti i programmatori di usare il suo linguaggio preferito, fino alle prossime elezioni).

Si scriva un programma per macchina di Turing che, ricevuto sul nastro una configurazione di seggio come negli esercizi precedenti, termini lasciando come risposta sul nastro il simbolo del partito che aveva più elettori nella configurazione.
In caso di ex-aequo, il programma deve terminare lasciando sul nastro i simboli dei partiti maggioritari ex-aequo, in ordine numerico crescente.
In caso di seggio vuoto, il programma deve terminare lasciando il nastro vuoto.

NASTRO INIZIALE NASTRO FINALE
S
11111S222 1
1100021321001201S 1
S1122330032 23
321S 123

Problema 6 – Il Parlamento dei Programmatori

Il Parlamento dei Programmatori si organizza in gruppi che fanno riferimento a uno dei 4 partiti.
Come in altri consessi si formano ipotetici raggruppamenti di “destra” e “sinistra”, in base a dove i parlamentari seggono, così nel Parlamento dei Programmatori (gente notoriamente amante dell’ordine) si usa avere i partiti disposti in ordine numerico crescente, con il partito 0 seduto all’estrema sinistra e il partito 3 all’estrema destra.

Si scriva un programma per macchina di Turing che, data una sequenza di eletti (ciascuno rappresentato da un simbolo fra 0 e 3), faccia ordine e disponga i membri secondo l’ordine in cui essi siederanno in Parlamento, lasciando sul nastro la sequenza corrispondente.

NASTRO INIZIALE NASTRO FINALE
13321001000 00000111233
312212333 112223333
3 3
1230 0123
2221002012012 0000111222222

Problema 7 – Il sistema proporzionale

Dopo che una imprevista vittoria elettorale del Partito Programmatori Pensionati aveva obbligato tutti a scrivere programmi solo in COBOL e FORTRAN, si è deciso di passare al sistema proporzionale.
In questo sistema, vengono eletti quattro rappresentanti, distribuiti in maniera proporzionale rispetto al numero di elettori.
In particolare, ogni partito ottiene un rappresentante ogni 25% del voto raccolto (così, un partito che ottenga il 50% dei voti avrà due rappresentanti); per la parte residua, il rappresentante viene assegnato al partito che ha ottenuto più voti secondo il metodo dei cosiddetti “massimi resti”.

Si scriva un programma per macchina di Turing che, ricevuto sul nastro una configurazione di seggio, termini lasciando sul nastro i 4 simboli corrispondenti ai 4 rappresentanti eletti, in ordine numerico crescente, secondo il sistema proporzionale.
Per semplicità, si assuma che il numero di elettori presenti sia sempre un multiplo di 4, non superiore a 999, e che non si verifichino mai situazioni di ex-aequo.

Supponiamo che gli esiti della votazione siano i seguenti:

  • partito 0: 18 voti
  • partito 1: 12 voti
  • partito 2: 6 voti
  • partito 3: 8 voti.

Abbiamo un totale di 44 voti espressi, quindi il 25% corrisponde a 11 voti.
Il partito 0 ottiene subito un rappresentante (poiché 11 ≤ 18 < 22), come anche il partito 1; i partiti 2 e 3 non ne ottengono alcuno.

I voti corrispondenti ai rappresentanti assegnati vengono quindi sottratti al monte-voti di ciascun partito; questo ci lascia con i seguenti “resti”:

  • partito 0: 7 voti
  • partito 1: 1 voto
  • partito 2: 6 voti
  • partito 3: 8 voti.

I due rappresentanti mancanti vengono quindi assegnati al partito 3 (che ha un resto di 8 voti) e al partito 0 (che ha un resto di 7 voti), mentre il partito 2 con 6 voti di resto e il partito 1 con 1 voto di resto non ottengono altro.
L’esito dell’elezione è dunque: 0013.

NASTRO INIZIALE NASTRO FINALE
1111S 1111
01230S3320110 0123
S01230123012301230123 0123
21101S1131112 1112

Problema 8 – Rimborsi elettorali

Nel Mondo dei Programmatori, i diversi partiti ricevono un rimborso fisso per le spese elettorali, che è sempre un multiplo di 12, che va poi diviso fra i rappresentanti eletti.

Si scriva un programma per macchina di Turing che, ricevuto sul nastro l’esito di una elezione (ovvero, una sequenza di 4 simboli sull’alfabeto {1, 2, 3, 4}, come dato dall’esercizio precedente), seguito da un “:“, dal simbolo del partito per cui stiamo facendo i conti, un altro “:“, e infine la cifra del rimborso attribuito al partito in questione, lasci sul nastro il rimborso pro-quota per ciascuno eletto di quel partito.
Si assuma che il rimborso viene attributo solo se c’è almeno un eletto del partito in questione.

NASTRO INIZIALE NASTRO FINALE
1111:1:12000 3000
1123:1:12000 6000
0123:1:12000 12000
2233:2:144 72
2333:3:1440 480

Problema 9 – Al Ballottaggio!

Anche il sistema proporzionale ha i suoi difetti.
Alle ultime elezioni, è stato eletto esattamente un rappresentante per ciascun partito, e ovviamente i quattro non si sono messi d’accordo su quale linguaggio adottare.
Si decide allora di passare al sistema di voto con ballottaggio.
In questo sistema, si svolgono due turni di votazione.
Se al primo turno uno dei partiti ottiene più del 50% dei voti, l’elezione termina con la vittoria di quel partito.
Altrimenti, vengono riproposti al voto, nel secondo turno, i due partiti che hanno ottenuto il maggior numero di voti al primo turno.
In tutti i casi di parità, prevale il partito che ha per simbolo il valore numerico più alto.

Si scriva un programma per macchina di Turing che, ricevuta in input una configurazione di seggio, termini lasciando sul nastro il simbolo del partito vincitore, oppure i simboli dei due partiti che andranno al ballottaggio, in ordine numerico crescente.

NASTRO INIZIALE NASTRO FINALE
1100021321001201S 01
31010023021S321001201 01
S22022121222322 2
11100332S 13
31113S332201 13

Problema 10 – Politica 2.0

Tradizionalmente, i programmatori sono persone asociali, che non parlano facilmente di politica fra di loro.
Tuttavia, quest’anno va di gran moda un nuovo social network, chiamato Votebook, che consente a un programmatore in fila al seggio di scambiare opinioni, passando per dei server in Antartide, con le persone davanti a lui e con quelle dietro di lui nella fila.
Questi scambi di opinioni possono ovviamente influenzare il voto.
In particolare, se fra le due persone davanti e le due dietro all’elettore, ce ne sono almeno tre dello stesso partito, l’elettore viene convinto, e si adegua alla loro opinione (influenzando così l’esito finale della votazione).
Questo processo può essere espresso per passi come segue.
Si prenda una configurazione di seggio, anche mal ordinata.
Ad ogni passo, gli elettori immediatamente accanto al seggio esprimono il loro voto (che viene conteggiato), e lasciano la fila.
Tutti gli altri elettori hanno uno scambio di opinioni con gli elettori immediatamente precedenti e successivi nella fila, ed eventualmente cambiano opinione come descritto sopra.
Per l’elettore giunto all’inizio della fila (ovvero, accanto al seggio) si considera che gli elettori precedenti siano i primi della fila opposta, se presenti (altrimenti, il primo elettore non cambia opinione); gli elettori in fondo alla fila non hanno elettori successivi, e quindi non cambiano mai opinione.
Una volta terminato lo scambio di opinioni, il passo termina.
L’intera votazione si svolge in un numero di passi sufficiente a far votare tutti gli elettori.

Si scriva un programma per macchina di Turing che, presa in input una configurazione di seggio, lasci sul nastro i simboli del partito che ha ottenuto la maggioranza dei voti.
Si assuma che non vi saranno casi di ex-aequo.

Di seguito indichiamo la configurazione iniziale e i vari passi di una votazione (gli spazi intorno al seggio non sono significativi, e vengono mostrati solo per chiarezza):

132100101220121 S 12030121100200 voti espressi: 1,1 risultati parziali: 0, 2, 0, 0
13210010122012 S 2030121100200 cambi di opinione
13210000122022 S 2030111100000 opinioni modificate
13210000122022 S 2030111100000 voti espressi: 2,2 risultati parziali: 0, 2, 2, 0
1321000012202 S 030111100000 cambio di opinione
1321000012222 S 030111100000 opinioni modificate
1321000012222 S 030111100000 voti espressi: 2,0 risultati parziali: 1, 2, 3, 0
132100001222 S 30111100000 nessun cambio di opinione
132100001222 S 30111100000 voti espressi: 2,3 risultati parziali: 1, 2, 4, 1
13210000122 S 0111100000 nessun cambio di opinione
13210000122 S 0111100000 voti espressi: 2,0 risultati parziali: 2, 2, 5, 1
1321000012 S 111100000 cambio di opinione
1321000012 S 111100000 opinione modificata
1321000012 S 111100000 voti espressi: 2,1 risultati parziali: 2, 3, 6, 1
132100001 S 11100000 nessun cambio di opinione
132100001 S 11100000 voti espressi: 1,1 risultati parziali: 2, 5, 6, 1
13210000 S 1100000 cambio di opinione
13210000 S 0100000 opinione modificata
13210000 S 0100000 voti espressi: 0,0 risultati parziali: 4, 5, 6, 1
1321000 S 100000 cambio di opinione
1321000 S 000000 opinione modificata
1321000 S 000000 voti espressi: 0,0 risultati parziali: 6, 5, 6, 1
132100 S 00000 nessun cambio di opinione
132100 S 00000 voti espressi: 0,0 risultati parziali: 8, 5, 6, 1
13210 S 0000 nessun cambio di opinione
13210 S 0000 voti espressi: 0,0 risultati parziali: 10, 5, 6, 1
1321 S 000 nessun cambio di opinione
1321 S 000 voti espressi: 1,0 risultati parziali: 11, 6, 6, 1
132 S 00 nessun cambio di opinione
132 S 00 voti espressi: 2,0 risultati parziali: 12, 6, 7, 1
13 S 0 nessun cambio di opinione
13 S 0 voti espressi: 3,0 risultati parziali: 13, 6, 7, 2
1 S nessun cambio di opinione
1 S voti espressi: 1 risultati parziali: 13, 7, 7, 2
S fine votazione risultato finale: 13, 7, 7, 2
risposta: 0

Notate come nella configurazione iniziale, il partito 0 avesse 10 voti, ma in seguito agli scambi di opinioni ne ha avuti alla fine 13.
Il partito 1 aveva anch’esso 10 voti inizialmente, ma alla fine ha avuto soltanto 7 voti.
Il partito 2 ha mantenuto i suoi 7 voti, e il partito 3 ha mantenuto i suoi 2 voti iniziali.
Il programma deve quindi terminare lasciando sul nastro il solo simbolo “0”.

NASTRO INIZIALE NASTRO FINALE
1100021321001201S 01
31010023021S321001201 01
S22022121222322 2
11100332S 13
31113S332201 13

Edizione XVI

Problema 1 – Calendario AT

Alan Turing nacque il 23 giugno 1912.

Si consideri il 1912AD (Anno Domini) come anno 0AT (Anno Turingi), e si scriva un programma per Macchina di Turing che, ricevuto sul nastro un intero rappresentante un anno nella convenzionale notazione Gregoriana (fra il 1912 e il 9999), lasci sul nastro il corrispondente anno in notazione AT.

NASTRO INIZIALE NASTRO FINALE
1912AD 0AT
1913AD 1AT
2012AD 100AT
2013AD 101AT
4120AD 2208AT

Problema 2 – Compleanno di Turing

Si scriva un programma per macchina di Turing che, ricevuta in ingresso una data nel tradizionale formato gg/mm/aaaa

  • gg fra 01 e 31
  • mm fra 01 e 12
  • aaaa fra 1000 e 9999

lasci sul nastro la scritta HBAT (abbreviazione di Happy Birthday Alan Turing) se la data cade nel compleanno di Alan Turing, o NOaltrimenti.
Si considera compleanno anche una data precedente la nascita di AT.

NASTRO INIZIALE NASTRO FINALE
23/06/1912 HBAT
22/06/1912 NO
23/11/1912 NO
23/06/1012 HBAT
23/06/2012 HBAT
05/12/2012 NO

Problema 3 – Calcolo dell’età

Si scriva un programma per macchina di Turing che, ricevuto in ingresso una data nel formato dell’esercizio precedente, successiva o uguale alla data di nascita di AT, lasci sul nastro l’età che AT ebbe o avrebbe avuto nella data indicata, secondo la consueta convenzione per cui si incrementa l’età nel giorno stesso del compleanno.

NASTRO INIZIALE NASTRO FINALE
23/06/1912 0
14/11/1922 10
14/02/2012 99
15/08/2012 100

Problema 4 – La firma completa

Il nome completo di AT era Alan Mathison Turing.
Si scriva un programma per macchina di Turing che, ricevuta sul nostra una forma abbreviata o meno del nome di Turing, lasci sul nastro la forma espansa, in cui

  • un segmento “A.” è sostituito da “Alan
  • un segmento “M.” da “Mathison
  • un segmento “T.” da “Turing”.

La stringa in ingresso può contenere lettere alfabetiche, spazi (al più uno consecutivo), punti, virgole.
Tutti i caratteri non espansi devono essere copiati identici nel risultato.

NASTRO INIZIALE NASTRO FINALE
A. M. Turing Alan Mathison Turing
Dr. A. Turing Dr. Alan Turing
Turing, A. M. Turing, Alan Mathison
Prof. Turing Prof. Turing
A. T. Alan Turing

Problema 5 – Suona la campanella!

Nel 1926, a 14 anni, AT iniziò a frequentare le scuole superiori presso la Sherborne School, nel Dorset, a una certa distanza da Southampton, dove allora viveva.
Disgraziatamente, il primo giorno di lezioni coincise con il grande sciopero generale del 1926 che paralizzò la Gran Bretagna.
Il giovane AT era però particolarmente ostinato, per cui partì il giorno precedente per percorrere in bicicletta, da solo, i 97Km che separavano Southampton da Sherborne (fermandosi a dormire la notte in un ostello lungo la via), in modo da essere comunque presente al primo giorno di lezione.
Si scriva un programma per macchina di Turing che, ricevuto sul nastro un intero rappresentante un numero di giorni di lezione nel periodo dello sciopero (che durò in tutto 9 giorni), lasci sul nastro un altro intero rappresentante il numero di chilometri da percorrere (97 all’andata, 97 al ritorno) per frequentare le lezioni.
Nota: non risulta che AT abbia ripetuto l’exploit tutti i giorni!

NASTRO INIZIALE NASTRO FINALE
1 194
3 582
9 1746

Problema 6 – Battaglia fluviale

Com’è ormai noto, durante la seconda guerra mondiale AT lavorò per il servizio segreto di Sua Maestà Britannica, curando in particolare la decodifica dei messaggi cifrati della marina tedesca.
Possiamo immaginare che, nel tempo libero, si dilettasse nel gioco della Battaglia fluviale.
La Battaglia fluviale segue le regole della più nota battaglia navale, ma il gioco si svolge su un fiume (quindi, su una sequenza di caselle) anziché in mare (quindi, su una griglia di caselle).
In particolare, rappresenteremo con il carattere X una casella occupata da una nave, e con uno spazio una casella occupata da acqua; le caselle sono numerate da sinistra a destra, partendo da 1.

Si scriva un programma per macchina di Turing che, ricevuto sul nastro un intero k che rappresenta un numero di casella, seguito da un simbolo : e una rappresentazione del fiume (composta da X e spazi), di lunghezza non determinata, verifichi il contenuto della k-esima casella del fiume.
Se questa era occupata da una nave, il programma sovrascrive la casella con uno spazio, e lascia sul nastro una C (per colpito!) seguita da : e dalla rappresentazione del fiume.
Se invece la casella era occupata da acqua, lascia sul nastro una H (per H2O) seguita da : e dalla rappresentazione del fiume.

Per chiarezza, indichiamo gli spazi con –

NASTRO INIZIALE NASTRO FINALE
4:-XX–XXX H:-XX–XXX
3:-XX–XXX C:-X—XXX
2:-X—XXX C:—–XXX
12:-XX–XXX——XX H:-XX–XXX——XX
16:-XX–XXX——XX C:-XX–XXX——-X
8: H:

Problema 7 – La Battaglia dell’Atlantico

La grande Battaglia Navale a cui AT diede un impulso risolutivo fu la Battaglia dell’Atlantico, combattuta fra gli U-Boot del grand’ammiraglio Karl Dönitz (i cosiddetti branchi di lupi dell’Atlantico) e i convogli di navi militari e trasporti organizzati dall’Ammiragliato Britannico.

La vera Battaglia dell’Atlantico vide coinvolti circa 1200 sommergibili tedeschi (e qualche italiano) contro molte migliaia di navi di superficie alleate.
Per la nostra versione, però, ci accontenteremo di 8 unità, disposte (in maniera segreta) su una plancia di 8×8 caselle.
Le unità sono composte da:

  • 1 portarei (occupa 5 caselle, contenenti il codice 5)
  • 1 corazzata (occupa 4 caselle, contenenti il codice 4)
  • 1 cacciatorpediniere (occupa 3 caselle, contenenti il codice 3)
  • 5 sommergibili (occupano 1 casella, contenente il codice 1).

Le caselle sono identificate da un sistema di coordinate, in cui le righe sono denotate da una lettera (fra A e H) e le colonne da un numero (fra 1 e 8).
Sul nastro, l’Atlantico è rappresentato mettendo di seguito le 64 celle della plancia, riga per riga.

Negli esempi sottostanti, per chiarezza, andremo a capo ad ogni riga; sul nastro ovviamente non ci saranno a capo.
Inoltre, rappresentiamo con uno sfondo colorato la casella indicata dalle coordinate.

Si scriva un programma per macchina di Turing che, ricevuto sul nastro l’indicazione di una casella, seguita da “:” e da una rappresentazione della plancia, verifichi il contenuto della casella indicata;

  • se essa conteneva acqua, lasci sul nastro H seguito da : e dalla plancia;
  • se invece si trattava di una nave, lasci sul nastro A (per affondata) se il colpo ha completamente eliminato l’unità colpita, oppure C(per colpita) se l’unità è stata colpita, ma non affondata;
  • in entrambi i casi, nella casella indicata viene scritto uno spazio per indicare che ora contiene acqua, e la risposta è seguita dal codice del tipo di unità (15), da : e dal nuovo stato della plancia.
NASTRO INIZIALE NASTRO FINALE Commento
B4:
——4-
333—4-
—1–4-
2—–4-
2-1—–
—-1–1
1——-
-55555–
H:
——4-
333—4-
—1–4-
2—–4-
2-1—–
—-1–1
1——-
-55555–
acqua
D1:
——4-
333—4-
—1–4-
2—–4-
2-1—–
—-1–1
1——-
-55555–
C2:
——4-
333—4-
—1–4-
2—–4-
2-1—–
—-1–1
1——-
-55555–
colpita unità da 2
E1:
——4-
333—4-
—1–4-
——4-
2-1—–
—-1–1
1——-
-55555–
A2:
——4-
333—4-
—1–4-
——4-
–1—–
—-1–1
1——-
-55555–
affondata unità da 2
C4:
——4-
333—4-
—1–4-
——4-
–1—–
—-1–1
1——-
-55555–
A1:
——4-
333—4-
——4-
——4-
–1—–
—-1–1
1——-
-55555–
affondata unità da 1
H8:
——4-
333—4-
——4-
——4-
–1—–
—-1–1
1——-
-55555–
H:
——4-
333—4-
——4-
——4-
–1—–
—-1–1
1——-
-55555–
acqua

Problema 8 – La Bomba

Uno dei contributi principali di Turing alla decodifica del codice tedesco Enigma consistette nel perfezionamento della Bomba, una macchina elettromeccanica (originariamente concepita dai servizi segreti polacchi, anch’essi dotati di eccellenti matematici).
Il funzionamento della macchina era basato sulla disponibilità di un crib – ovvero, un frammento che si supponeva dovesse comparire nel testo decrittato.
Un esempio famoso di crib era Keine besonderen Ereignisse (equivalente a niente da segnalare), che come si immagina facilmente, compariva spesso nei più vari report militari.

La macchina Enigma utilizzata sostanzialmente un cifrario a sostituzione polialfabetico, ovvero un sistema in cui ogni lettera dell’alfabeto viene sostituita da un’altra, e la tabella di sostituzione è diversa in punti diversi del messaggio.
In questo sistema, la lettere A può essere sostituita da L in prima posizione, ma da Q in seconda posizione, da R in terza posizione, e così via – apparentemente, senza regolarità.
In realtà, la regolarità era data dal particolare intreccio di circuiti elettrici che si realizzava combinando vari componenti meccanici (rotori, tratti di cavi, ecc.) all’interno della macchina.

Noi illustreremo il funzionamento della Bomba affidandoci a un più semplice cifrario a sostituzione monoalfabetico in cui la tabella di sostituzione è fissata e uguale in tutte le posizioni: e anzi, come ulteriore semplificazione, useremo un cifrario ROTn in cui ogni lettera viene sostituita da quella che si trova n posizioni più avanti nell’alfabeto (modulo 26).
Il particolare caso del cifrario ROT3 è noto anche come Cifrario di Cesare, in quanto utilizzato da Caio Giulio Cesare (secondo la testimonianza di Svetonio) nelle guerre galliche.
In ROT3, ogni A è sostituita da D, ogni B da E, e così via.

Si realizzi dunque un programma per macchina di Turing che, ricevuto sul nastro un crib (testo in chiaro) seguito da “?=” e da un messaggio cifrato in ROTn (in cui n è ignoto, ma maggiore di 0), lasci sul nastro il testo decodificato secondo il più piccolo n per cui ilcrib compaia, in posizione qualunque, nel testo decodificato.
Il programma deve terminare scrivendo “?” se nessuna codifica ROTn è in grado di decodificare il messaggio in modo che emerga ilcrib.
Sia il crib che il messaggio cifrato usano l’alfabeto inglese az a 26 lettere.

NASTRO INIZIALE NASTRO FINALE Commento
alba?=dwwdffduhdoodoed attaccareallalba ROT3
port?=azcelpcptityiazcez portaereixinxporto ROT11
port?=pnzovnerlpvsenevb ?
cifra?=pnzovnerlpvsenevb cambiareycifrario ROT13
mai?=xfytktzytpdlfctep ucvqhqwvqmaiczqbm ROT3 – ko!
oni?=xfytktzytpdlfctep munizioniesaurite ROT11 – ok!
arma?=qqwzvxcibaedfasfwerflkejx ?

Problema 9 – Il problema della fermata

Uno dei primi contributi teorici di Turing fu legato al Problema della fermata (problema di cui forse già si era occupato attendendo l’autobus nei giorni del grande sciopero generale di cui all’esercizio 5): esiste una procedura che, dato un generico programma e il suo input, determina se il programma terminerà la sua computazione, oppure se continuerà a girare per sempre?
Turing dimostrò che il problema della fermata è indecidibile: non può esistere una tale procedura.

Tuttavia, se assumiamo un particolare meccanismo per eseguire un programma (per esempio: una macchina di Turing) e poniamo un limite k al numero di passi che esso può compiere, possiamo rispondere facilmente alla domanda correlata: il programma dato termina entro k passi?
La procedura è in questo caso semplice: basta eseguire passo-passo la macchina (simulandola), tenere il conteggio del numero di passi, e fermarsi se il programma termina (in questo caso, la risposta è SI), oppure se si raggiunge il numero di passi fissato k (in questo caso, la risposta è NO).
Notate che se un programma non è terminato entro k passi, potrebbe sempre terminare al passo k+1, se solo l’avessimo lasciato andare avanti ancora un po’… quindi, la non-terminazione entro k non dice nulla sulla non-terminazione tout court.

Sul simulatore troverete pre-caricato con il nome Problema 9 un interprete per una macchina di Turing, esso stesso scritto come macchina di Turing: si tratta della cosiddetta Macchina di Turing universale.
In questa macchina (semplificata), il programma è dato da quintuple scritte sul nastro nel formato <stato><input><stato><output><dir>

  • gli <stati> sono indicati da sequenze di S (S è lo stato 1, SS è lo stato 2, e così via);
  • l'<input> e l'<output> sono sull’alfabeto {0, 1, N} (in cui N rappresenta il blank);
  • lo spostamento della testina <dir> è codificato con 0 (= sposta a sinistra), 1 (= sposta a destra), N (= stai fermo).

Si può dimostrare che, anche con queste limitazioni, la macchina di Turing è in grado di calcolare qualunque cosa che la macchina senza limitazioni può calcolare: è una versione più complicata da programmare, ma non meno potente.

Per esempio, la tupla (sss, 0, s, 1, >) viene codificata in questo sistema con SSS0S11, mentre la tupla (sss, , ss, 0, ) diventa SSSNSS0N.
La macchina di Turing universale pre-caricata si attende sul nastro il programma e l’input, nel formato: B<tupla><tupla>…<tupla>IT<input> in cui

  • B indica l’inizio del programma,
  • I la sua fine,
  • e la T rappresenta la posizione della testina (che punta al simbolo che la segue: quindi, all’inizio, è posizionata sul primo simbolo dell’input).

Un esempio di input completo per la nostra MdT universale è dunque: BS0S11S1S01IT0100010100101 (per i curiosi: si tratta del programma che scambia 0 e 1 nell’input, con la stringa di input 0100010100101).

I commenti nel codice pre-caricato forniscono qualche indicazione su come la MdT universale funzioni: la si modifichi in modo che essa accetti un intero k prima del simbolo B iniziale del programma, che durante l’esecuzione del programma dato in input conti i passi della macchina simulata e che si arresti col messaggio NONT (per non termina) se la macchina non ha ancora terminato l’esecuzione dopo k passi, oppure con TERM se la macchina termina l’esecuzione in un numero di passi minore o uguale a k.

NASTRO INIZIALE NASTRO FINALE
1000BS0S11S1S01IT0100010100101 TERM
5BS0S11S1S01IT0100010100101 NONT
20BSNSS11SSNSSS01SSSNSSSS0NITN TERM
2000BSNSS11SSNSSS01SSSNSSSS0NITN TERM
2BSNSS11SSNSSS01SSSNSSSS0NITN NONT
5000BS0SS0S1S1NIT0 TERM
5000BS0SS0S1S1NIT1 NONT

Problema 10 – Filotassi Fibonacciana

Come molti altri personaggi dotati di menti inquiete, AT amava occuparsi dei problemi più disparati.
Oltre ai suoi lavori fondamentali per l’Informatica, ha lasciato importanti contributi in chimica e in genetica, quando ancora questa disciplina aveva appena iniziato la sua fioritura.
A proposito di fioritura, AT si occupò del rapporto fra la filotassi (la parte della Botanica che studia la disposizione geometrica delle piante) e la successione di Fibonacci.
In molte piante, la successione degli angoli o delle distanza fra petali, foglie, steli, segue infatti i rapporti dei termini consecutivi della successione di Fibonacci (il limite del rapporto fra due termini consecutivi è noto come rapporto aureo).

La successione di Fibonacci è definita classicamente come segue:

  • F(0) = 0
  • F(1) = 1
  • F(k) = F(k-1)+F(k-2), per k>1.

La Felce di Turing (Fibopteridoma Alanturingi) è una pianta infestante che cresce esclusivamente sui nastri delle macchine di Turing (pare si nutra di tuple, ma gli esperti non sono unanimi al riguardo).
Il seme della pianta è costituito da un numero intero j.
Innaffiando leggermente il nastro, la felce cresce in senso longitudinale, e nascono dei rami secondari, alternativamente a destra e a sinistra, distanziati fra di loro di una lunghezza di stelo pari all’h-esimo numero di Fibonacci.
La felce smette di crescere quando h è pari al seme iniziale j.
Sul nastro, il simbolo indica una unità di stelo, il simbolo / un ramo a sinistra, il simbolo \ un ramo a destra.
La cima della felce corrisponde a F(0), e corrisponde sempre a un ramo \.
La base della felce è sempre un ramo (che può essere / o \ a seconda dei casi).

Si scriva un programma per macchina di Turing che, ricevuto sul nastro di ingresso il seme j, lasci sul nastro di uscita la felce pienamente sviluppata.

NASTRO INIZIALE NASTRO FINALE
3 \–/-\-/\
6 /——–\—–/—\–/-\-/\
1 \-/\
7 /————-/——–\—–/—\–/-\-/\
0 /\

Edizione XV

Problema 1 – Stringhe pari

Si scriva un programma per macchina di Turing che, ricevuta in ingresso una stringa sull’alfabeto {A, …, G}, lasci sul nastro SI se la stringa era di lunghezza pari, NO se essa era di lunghezza dispari.

NASTRO INIZIALE NASTRO FINALE
ABC NO
AB SI
GGGGGGGG SI
ABAC SI
E NO

Problema 2 – Ripetizioni

Si scriva un programma per macchina di Turing che, ricevuta in ingresso una stringa composta da un numero decimale n fra 0 e 7, seguito da una lettera l fra A e G, lasci sul nastro una stringa composta da n ripetizioni di l.

NASTRO INIZIALE NASTRO FINALE
3A AAA
7C CCCCCCC
0E
1B B

Problema 3 – Raddoppi

Si scriva un programma per macchina di Turing che, ricevuto in ingresso un numero intero, lasci sul nastro il doppio del numero indicato.

NASTRO INIZIALE NASTRO FINALE
31 62
1 2
1651 3302
9 18

Problema 4 – Steganomusica

Nel sistema anglosassone di notazione musicale, le note sono indicate con delle lettere, secondo la corrispondenza:

Do=C, Re=D, Mi=E, Fa=F, Sol=G, La=A, Si=B.

Si scriva un programma per macchina di Turing che, ricevuta una stringa sull’alfabeto {A, …, Z}, lasci sul nastro soltanto la sottosequenza della stringa originale composta concatenando i soli simboli corrispondenti a note musicali presenti nella stringa di ingresso.

Nascondere un messaggio (in questo caso, un motivo musicale) mescolandolo con altri dati irrilevanti, che magari sembrano rappresentare qualcos’altro, è una tecnica crittografica nota col nome di steganografia.

NASTRO INIZIALE NASTRO FINALE
LAGAZZALADRA AGAAADA
ILBARBIEREDISIVIGLIA BABEEDGA
LENOZZEDIFIGARO EEDFGA
RHAPSODYINBLUE ADBE
IRIS

Problema 5 – Tempo, tempo!

Nella musica occidentale, la durata di una nota (chiamata valore) è espressa come una frazione (tipicamente, una potenza di due) di una unità fondamentale.

A queste durate si danno nomi convenzionali:

  • massima = 8,
  • lunga = 4,
  • breve = 2,
  • semibreve = 1,
  • minima = 1/2,
  • semiminima = 1/4,
  • croma = 1/8,
  • semicroma = 1/16,
  • biscroma = 1/32,
  • semibiscroma = 1/64,
  • fusa = 1/128.

Codifichiamo un brano musicale facendo seguire, al nome della nota secondo la notazione anglosassone, il suo valore (escludendo la massima e la lunga, ormai in disuso, e la breve) codificata da una cifra k, fra 0 e 7, che esprime la durata di 1/2^k.

La varie durate sono normalmente denotate con simboli particolari: per esempio nella figura accanto abbiamo, da sinistra a destra: semibreve, minima, semiminima, croma, semicroma; di ciascun valore viene dato in alto il valore, al centro il simbolo, e in basso la codifica numerica che useremo in questo esercizio (e nei successivi).
I simboli per la biscroma, semibiscroma, fusa sono analoghi a quelli della croma e semicroma, ma rispettivamente con 3, 4 e 5 code sul gambo.

Useremo inoltre una Z per indicare una pausa (ovvero, nessuna nota emessa), anch’essa seguita da una codifica della durata.
Così, A2 sarà la codifica di un La semiminima (durata 1/4), mentre Z0 indica una pausa semibreve (durata 1).

Si scriva un programma per macchina di Turing che, ricevuta in ingresso sul nastro una melodia codificata come sopra descritto, di lunghezza qualunque, lasci sul nastro la lunghezza totale del brano, espressa in unità, e approssimata in alto se necessario.

NASTRO INIZIALE NASTRO FINALE COMMENTO
A0B1C1D2A1D2 3 1+1/2+1/2+1/4+1/2+1/4
Z0Z0Z0Z0 4 1+1+1+1
C1D1C0D3F2D3Z1C0E1F2A2C3 6 1/2+1/2+1+1/8+1/4+1/8+1/2+1+1/2+1/4+1/4+1/8
A7 1 1/128
C7D4E5 1 1/128+1/16+1/32
A0B1C1D2A1D2 3 1+1/2+1/2+1/4+1/2+1/4

Problema 6 – La metà della metà

Sempre nella notazione musicale occidentale, si usa un “.” (detto punto di valore) per indicare che la durata della nota precedente deve essere aumentata della metà del suo valore.

Quindi,

  • un solo punto equivale a moltiplicare la durata per 3/2;
  • un doppio punto moltiplica per 7/4;
  • un triplo punto per 15/8,
  • ecc.

Si scriva un programma per macchina di Turing che, ricevuta sul nastro di ingresso una melodia codificata come nell’esercizio precedente, con la possibile aggiunta di un numero qualunque di punti dopo le durate (ma tale da non superare la grana minima di1/128 di durata), lasci sul nastro la stessa melodia, codificata senza fare uso di punti.

NASTRO INIZIALE NASTRO FINALE
A0B1C1D2A1D2 A0B1C1D2A1D2
A0. A0A1
C2A3..D2 C2A3A4A5D2
D6.Z2.D2.. D6D7Z2Z3D2D3D4
A0.A1…A4Z3 A0A1A1A2A3A4A4Z3
A0B1C1D2A1D2 A0B1C1D2A1D2
G0.B2 G0G1B2
C2A3..D2 C2A3A4A5D2

Problema 7 – Fuga in Do Maggiore per Macchina di Turing e Cervello Solo

Una fuga è una composizione musicale polifonica (cioè, con più voci o strumenti) in cui un dato tema (cioè, un frammento di melodia) viene presentato più volte, affidato a varie voci, alterato e ripetuto in vari modi.
Nella sua forma più semplice, le varie voci entrano una alla volta (le altre voci hanno soltanto pause fino alla loro entrata), ciascuna esponendo lo stesso soggetto, ovvero un breve tema musicale (si dice allora che la seconda voce entra con una risposta reale, identica al soggetto); dopo l’esposizione, le varie voci progrediscono in maniera differenziata, secondo le regole del contrappunto.

Noi codificheremo un brano musicale a più voci indicando ciascuna voce nella notazione vista sopra, data dal nome di una nota (AG) oppure Z per una pausa, seguita da una durata (07) e da zero o più punti.
Le varie voci saranno separate dal simbolo $.

Si scriva un programma per Macchina di Turing che, ricevuta sul nastro la codifica di una composizione musicale a un numero qualunque di voci, lasci sul nastro il solo soggetto, oppure lasci il nastro vuoto se la composizione non ha le caratteristiche della fuga in forma semplice presentate sopra.

NASTRO INIZIALE NASTRO FINALE
C1D1E1F1.E2D2$Z0C1D1E1F0.$Z0Z0C1D1E1A2 C1D1E1
A0B1C0..D3$Z0Z0A0B1E2.C0 A0B1
A0B1C0..D3$Z0Z0A0B1E2.C0$Z1A0C0D1 A0
A0.B1C0.D3$Z0.A0.B1C0.D3$Z0.Z1A0.B1C0. A0.B1C0.
A0.B1C0.D3$Z0.A1.B1C0.D3$Z0.Z1A0.B1C0.
C1D1E1F1.E2D2$Z0C1D1E1F0.$Z0Z0C1D1E1A2 C1D1E1

Problema 8 – Il Codice Parsons – indicizzazione

Il codice Parsons è stato inventato per permettere la ricerca approssimata di temi in database musicali.
Si basa su una semplice codifica, in cui ogni nota (ignorando le pause) è codificata in base alla sua altezza rispetto alla precedente.

Il codice utilizza soltanto i seguenti quattro simboli:

  • * = la prima nota del tema
  • u = la nota è più alta rispetto alla precedente
  • r = la nota ha la stessa altezza della precedente
  • d = la nota è più bassa rispetto alla precedente

Ai fini dell’esercizio, considereremo una sola ottava di musica, in cui A (=la) è la nota più bassa, mentre G (=sol) è la nota più alta.

Si scriva un programma per macchina di Turing che, data sul nastro una melodia (a una sola voce), codificata secondo le convenzioni di cui agli esercizi precedenti, lasci sul nastro come risultato il corrispondente codice Parsons.

NASTRO INIZIALE NASTRO FINALE
C1D1E1F1.E2D2 *uuudd
A0B1C0..D3 *uuu
E2F3F3Z0.F1B0Z1A1 *urrdd
G0..A2Z0G0..A2G2Z2G0 *dudur
C4E4F4C4C4E4F4C4E4F4G2 *uudruuduuu
C1D1E1F1.E2D2 *uuudd
A0B1C0..D3 *uuu
E2F3F3Z0.F1B0Z1A1 *urrdd

Problema 9 – Il Codice Parsons – ricerca

Si scriva un programma per macchina di Turing che, data sul nastro la codifica Parsons di una melodia cercata, seguita da un simbolo$ e poi da un brano musicale (a una voce) codificato come di consueto, lasci sul nastro il primo frammento di musica all’interno della melodia che corrisponde al codice Parsons fornito, oppure lasci il nastro vuoto se il brano non contiene nessun frammento che corrisponde al codice dato.

NASTRO INIZIALE NASTRO FINALE
*uuu$C1D1E1F1.E2D2 C1D1E1F1.
*udd$C1D1E1F1.E2D2 E1F1.E2D2
*urdd$E2F3F3Z0.F1B0Z1A1
*ruru$A0Z0C2C2D2D0.Z0E1F1D2 C2D2D0.Z0E1
*ruru$A0Z0A2C2C0.Z2G1F1D2 A0Z0A2C2C0.Z2G1
*uuu$F1D1E1F1.G2D2 D1E1F1.G2
*udd$C1D1E1F1.E2D2 E1F1.E2

Problema 10 – Tanti auguri a te

Nel giorno in cui scriviamo (22 Febbraio 2011) cade il 154° compleanno di Heinrich Rudolf Hertz, il fisico tedesco che ha dato il nome all’unità di misura della frequenza – l’Hertz appunto, abbreviato Hz.

Ogni nota musicale corrisponde a un suono a una determinata frequenza: per esempio, il La della cosiddetta “ottava centrale” (che è numerata per convenzione con il numero 4) corrisponde esattamente a 440 Hz.
Indicheremo questo La con la notazione 4A.

Ogni ottava è composta da 12 semitoni, corrispondenti ai tasti bianchi e neri del pianoforte, e va da Do a Do.
Due note consecutive saranno separate a volte da un semitono, a volte da un tono (ovvero, due semitoni), secondo lo schema mostrato in figura.
Le stesse note, ma all’ottava più grave, hanno esattamente la metà della frequenza della nota all’ottava superiore, quindi 3A ha frequenza 220 Hz, e 2A corrisponde a 110 Hz.
D’altra parte, 5A corrisponde a 880 Hz, e così via.
Fra un semitono e il successivo la frequenza aumenta di un fattore moltiplicativo pari alla radice 12-esima di 2 (è il cosiddetto temperamento equabile, a cui Johan Sebastian Bach – il cui 325° compleanno cadrà il prossimo 21 Marzo – dedicò il suoClavicembalo ben temperato).

Sciaguratamente, si tratta di un valore irrazionale, pari a 1.0594630943592952645618252949463417007792…

Così,

  • se 4A corrisponde a 440 Hz,
  • 4B (che è due semitoni sopra 4A) varrà 494 Hz,
  • 5C (che è un semitono sopra 4B) varrà 523 Hz,
  • 3B (che è un ottava esatta sotto 4B) varrà 247 Hz,
  • e così via.

Si scriva un programma per macchina di Turing che, ricevuto sul nastro di ingresso il nome di una nota preceduto dal numero dell’ottava, nell’intervallo 2A6G (per confronto: la maggior parte dei pianoforti hanno tasti da 0A a 8C; gli strumenti elettronici MIDI vanno da -1C a 9G), lasci sul nastro di uscita la sua frequenza calcolata come indicato sopra, approssimata all’intero più vicino.

Suggerimento: nell’effettuazione dei calcoli, si consiglia di usare una precisione sufficiente per il fattore di cui sopra, per esempio1.059463, onde evitare errori di approssimazione.

NASTRO INIZIALE NASTRO FINALE
6E 1319
4A 440
4B 494
4C 262
5C 525
3E 165
2A 110
6G 1568

Edizione XIV

Problema 1 – Numeri primi

Si scriva un programma per macchina di Turing che, ricevuto in ingresso sul nastro un numero decimale lasci sul nastro P se il numero era pari, D se era dispari.

NASTRO INIZIALE NASTRO FINALE
16 P
137 D
0 P
5173 D
2 P

Problema 2 – ZUDTQCSSON

Il Sistema Sbilenco di Numerazione (SSN) prevede che ogni cifra venga indicata con l’iniziale del suo nome in Italiano.
Quindi

0 Z
1 U
2 D

È semplice trasformare un numero decimale in un codice SSN, ma può essere complicato, dato un codice SSN, ricostruire il numero originale.

Si scriva un programma per macchina di Turing che, dato un codice SSN (senza Z iniziali), lasci sul nastro il numero decimale corrispondente, se unico, oppure X se non è possibile ricostruire il numero.

NASTRO INIZIALE NASTRO FINALE
DTZCO 23058
CCSU X
CZQDN 50429
NOSSN X

Problema 3 – Modulo tre

Si scriva un programma per macchina di Turing che, ricevuto in ingresso sul nastro un numero decimale lasci sul nastro il valore del numero modulo tre (ovvero, il resto della divisione per tre).

NASTRO INIZIALE NASTRO FINALE
30 0
7 1
29 2
5456423321 2

Problema 4 – Numeri ascendenti

Un numero si dice ascendente se ogni sua cifra ha un valore strettamente superiore a quello di ciascuna delle cifre che lo precedono.
Per esempio, 368 è un numero ascendente (infatti, 3 < 6 < 8).

Si scriva un programma per macchina di Turing che, ricevuto in ingresso sul nastro un numero decimale, lasci sul nastro A se il numero era ascendente, N in caso contrario.

NASTRO INIZIALE NASTRO FINALE
368 A
365 N
25789 A
204678 N
6 A

Problema 5 – Numeri discendenti

Similmente alla definizione data all’esercizio precedente, un numero si definisce discendente se ciascuna delle sue cifre è strettamente minore delle precedenti.
Per esempio, 8652 è un numero discendente.

Si scriva un programma per macchina di Turing che, ricevuto in ingresso sul nastro un numero decimale maggiore o uguale a 10, lasci sul nastro A se il numero era ascendente, D se era discendente, V altrimenti.

NASTRO INIZIALE NASTRO FINALE
550 V
2359 A
43 D
10 D
2543273 V
123456789 A

Problema 6 – La Sequenza Generalizzata Essaria di Fibonacci

La Sequenza Generalizzata di Fibonacci SGF(n,m) è la sequenza di numeri generati sommando i due precedenti elementi della sequenza, assumendo che i primi due elementi siano n e m.
Avremo quindi

  • SGF1(n,m)=n
  • SGF2(n,m)=m
  • SGF3(n,m)=n+m
  • SGF4(n,m)=m+(n+m)
  • SGF5(n,m)=(n+m)+(m+(n+m))
  • ecc.

La normale sequenza di Fibonacci è uguale a SGF(1,1), e genera i valori 1, 1, 2, 3, 5, 8, 13, 21, ecc.

La notazione essaria consiste nel denotare un numero non con la consueta notazione posizionale, ma semplicemente indicando il simbolo S tante volte quant’è il valore del numero.
Per esempio, la stringa SSSSS denota il numero 5, mentre SS rappresenta il numero 2.

Si scriva un programma per Macchina di Turing che, ricevuta su nastro una sequenza non vuota di numeri positivi in notazione essaria, separati da un singolo simbolo N, lasci sul nastro il simbolo T se la sequenza descrive una sottosequenza di una qualche SGF, o F in caso contrario.

NASTRO INIZIALE NASTRO FINALE
SSNSSSNSSSSS T
SSNSSNSSSSNSSSSSS T
SNSSSNSNSSS F
SNSNSSNSSSNSSSSS T
SSSNS T
SSSNSNSSSSSS F
S T
SNSNSNS F

Problema 7 – Steganografia

La steganografia è una tecnica per trasmettere un messaggio (anche non cifrato) nascondendolo all’osservatore non autorizzatoconfondendolo all’interno di altra informazione.
Per esempio, si può inviare una lunga missiva, con la convenzione che solo la quinta lettera di ogni paragrafo è parte del messaggiovero, mentre tutto il resto è solo materiale di copertura, destinato a confondere l’avversario-spione.
Per questo esercizio prenderemo in esame una forma semplice di steganografia, consistente nell’inviare una stringa quasi-simmetrica(intendendo che normalmente su un input di dimensione n, il simbolo alla posizione k-esima è uguale al simbolo in posizione (n-k+1)-esima), con l’intesa che solo i punti in cui la stringa non è simmetrica costituiscono il messaggio vero.

Si scriva quindi un programma per macchina di Turing che, ricevuta sul nastro una stringa quasi-simmetrica sull’alfabeto A-Z, contenente un messaggio steganografico dato dalle sole lettere non-simmetriche nella sequenza, lasci sul nastro il messaggio decodificato.
In caso di stringa di lunghezza dispari, il simbolo centrale si considera facente parte del messaggio da recuperare.

NASTRO INIZIALE NASTRO FINALE
APBBEACCARBBOA PERO
ZECCZMAAMEMCAZ ECZEMA
A A
DAMMADALADTAMAD MALTA
ORTIRITATATTAIATROITRO RITIRO
ANODITATACACIDONO ATTACCO

Problema 8 – I conti del SSN

Come si può comprendere facilmente, il SSN (introdotto nell’Esercizio 2) ha grossi problemi a far tornare i conti.

Si scriva un programma per macchina di Turing che, ricevuta sul nastro un’espressione nella forma n+m, in cui n e m sono numeri in notazione SSN (senza limiti di valore), lasci sul nastro l’espressione n+m=r (in cui r è il risultato della somma fra n e m espresso in SSN), se è possibile determinarlo univocamente, oppure il simbolo ? in caso contrario.

NASTRO INIZIALE NASTRO FINALE
C+T C+T=O
C+U C+U=S
C+D C+D=S
USS+Z USS+Z=USS
USS+U USS+U=?
SZT+DU SZT+DU=SDQ
SZDUT+SQCQ SZDUT+SQCQ=SSSSS
SUDUT+SQCS SUDUT+SQCS=?

Problema 9 – I conti del SSN – parte 2

Si scriva un programma per macchina di Turing che, ricevuta sul nastro un’espressione nella forma n+m=r in cui n, m e r sono numeri di esattamente tre cifre espressi in SSN, e con la garanzia che la somma sia corretta, lasci sul nastro la stessa espressione con i numeri in notazione decimale, se è possibile ricavarli, oppure X in caso contrario.

NASTRO INIZIALE NASTRO FINALE Commento
UDT+TTD=QCC 123+332=455
QTS+UZD=CTO 436+102=538
UUU+CCC=SSS 111+555=666
UUS+SSU=SSS 116+661=777
UUS+UUS=DTT X potrebbe essere 116+117=233 o 117+116=233
DZS+UUZ=TUS X potrebbe essere 206+110=316 o 207+110=317
DZS+UUU=TUO 207+111=318

Problema 10 – Numeri appaSSioNanti

Un numero in notazione SSN è detto appaSSioNante se è divisibile per S, ovvero se il resto della divisione per S è 0 – per una qualche interpretazione di S.
In altri termini, sono appaSSioNanti tutti i numeri SSN che hanno almeno una interpretazione decimale che è divisibile per 6 oppure per 7.

Per esempio, USO è appaSSioNante (si può interpretare come 168, che è divisibile per 6 e per 7), come anche SO (interpretabile come 78, che è divisibile per 6) o UZZU (1001, divisibile per 7).

Non sono invece appaSSioNanti NTC (935, non divisibile per 6 né per 7) o USZZ (interpretabile come 1600 o come 1700, nessuno dei quali è divisibile né per 6, né per 7).

Si scriva un programma per Macchina di Turing che, ricevuto in input un numero appaSSioNante in notazione SSN (di cui è quindi garantita la divisibilità per S), lasci sul nastro la sua interpretazione decimale di valore minore (che dovrà ancora essere divisibile perS).

NASTRO INIZIALE NASTRO FINALE Commento
UZZU 1001 Interpretazione univoca
S 6 Si può interpretare come 6 o come 7, entrambi divisibili per S, 6 è l’interpretazione minore.
QSD 462 Si può interpretare come 462 (divisibile per 6 e per 7) o 472 (non divisibile per 6 o 7, quindi non appaSSioNante).
CSS 567 Si può interpretare come 566, 567, 576, 577.
Di questi, 566 e 577 non sono appaSSioNanti; fra 567 e 576 che invece lo sono, il minore è 567.
USSSC 16765 Si può interpretare come 16665, 16675, 16765, 16775, 17665, 17675, 17765, 17775.
Fra questi, solo 16765 e 17675 sono appaSSioNanti, e 16765 è il minore.
UOZQQSS 1804467 Si può interpretare come 1804466, 1804467, 1804476, 1804477.
Fra questi, solo 1804467 e 1804476 sono appaSSioNanti, e 1804467 è il minore.

Edizione XIII

Problema 1 – La morra cinese

Nel gioco della Morra cinese due giocatori scelgono ciascuno un simbolo fra Carta, Forbice, Pietra (di solito, indicandolo in contemporanea con un gesto della mano):

  • Forbice vince su Carta
  • Carta vince su Pietra
  • Pietra vince su Forbice.

Si scriva un programma per macchina di Turing che, ricevuto in ingresso sul nastro una giocata composta da due simboli sull’alfabeto {C, F, P}, lasci in uscita

  • 1 se vince il primo giocatore (ovvero, se il primo simbolo vince sul secondo),
  • 2 se vince il secondo giocatore (ovvero, se il secondo simbolo vince sul primo),
  • 0 altrimenti.
NASTRO INIZIALE NASTRO FINALE
CF 2
FC 1
PP 0
FP 2
PC 2

Problema 2 – Pari e Dispari

Nel gioco Pari e Dispari, due giocatori puntano uno su Pari, l’altro su Dispari, e quindi scelgono ciascuno un numero compreso fra 0 e5 (di solito, indicandolo in contemporanea con le dita aperte di una mano).
Si scriva un programma per macchina di Turing che, ricevuto in ingresso sul nastro i numeri scelti dai due concorrenti, lasci in uscitaP se la somma è pari, D se la somma è dispari.

NASTRO INIZIALE NASTRO FINALE
40 P
00 P
53 P
14 D

Problema 3 – Testa o croce

Nel gioco Testa o Croce, due giocatori puntano uno su Testa, l’altro su Croce, e quindi lanciano una moneta un numero concordato di volte, scrivendo i risultati di ogni lancio sul nastro di una macchina di Turing.
Vince il concorrente che ha puntato sul simbolo uscito più volte.

Si scriva dunque un programma per macchina di Turing che, ricevuta in ingresso sul nastro una stringa sull’alfabeto {T, C} rappresentante gli esiti dei lanci, lasci sul nastro T se sono uscite più teste, C se sono uscite più croci, P se la partita è patta (sono uscite cioè tante teste quante croci).

NASTRO INIZIALE NASTRO FINALE
TTCTC T
TCTCCTCCCTT C
TC P
CCTCTTCTTC P

Problema 4 – Il baro

Un mazzo di carte napoletane contiene un totale di 40 carte, 10 per seme.
Esistono quindi esattamente 4 carte, di diverso seme, per ogni valore; i valori sono i numeri dall’1 al 7, il Fante, il Cavallo e il Re.

Si scriva un programma per macchina di Turing che, ricevuta in ingresso sul nastro una stringa sull’alfabeto {1, 2, 3, 4, 5, 6, 7, F, C,R}, dica se la stringa rappresenta una mano valida, ovvero se ogni valore compare al più 4 volte.
In caso di mano valida, la macchina deve lasciare sul nastro OK, altrimenti BARO.

NASTRO INIZIALE NASTRO FINALE COMMENTO
4457FR OK
11112 OK
FCRFFR1F5F BARO Ci sono 5 fanti
54R4C OK
11111 BARO Ci sono 5 assi

Problema 5 – Super Alan Bros

Nei videogiochi del genere platform, il personaggio controllato dal giocatore deve muoversi lungo un percorso, superando degli ostacoli di vario tipo, fino a raggiungere il premio finale del livello.

  • In Super Alan Bros, il giocatore (A) si trova inizialmente a sinistra di una piattaforma, composta da tratti di terreno (.) e da tratti di staccionata (#).
  • Il giocatore ha a disposizione solo due mosse: un passo verso destra (P), che lo porta nella successiva casella a destra, e un salto (S) che lo porta due caselle verso destra, saltando una casella.
  • Poiché non è possibile camminare attraverso una staccionata, questi tratti possono solo essere saltati.
  • Scopo del gioco è portare Alan nella posizione del tesoro (X), nel minor numero di mosse possibile.

Si scriva un programma per macchina di Turing che, ricevuto sul nastro una stringa descrivente il livello nella situazione iniziale, lasci sul nastro la sequenza di mosse di lunghezza minima che porta Alan sul tesoro di fine livello, senza mai camminare attraverso staccionate.

  • Alan ha un comportamento eager: tutte le volte che è possibile sia fare un passo che fare un salto (atterrando su terreno piano e senza superare il tesoro), Alan preferisce fare un salto.
  • È garantito che il livello di input sia risolubile (per esempio, non ci saranno lunghi tratti di staccionata come ### che non possono essere superati con un salto).
NASTRO INIZIALE NASTRO FINALE
A….X SSP
A#..#X SPS
A.#…#.#.X PSSSSP
AX P
A.X S
A#.X SP
A.#..#X PSPS

Problema 6 – Sette e mezzo

Nel gioco Sette e mezzo, ciascun giocatore riceve inizialmente una carta da un mazzo napoletano, e può poi chiedere ulteriori carte a sua discrezione.
Lo scopo è di avvicinarsi il più possibile al punteggio di 7 e mezzo (ogni carta vale il proprio punteggio nominale, mentre le figureFante, Cavallo, Re valgono ciascuna mezzo punto), senza superarlo.

Si scriva un programma per macchina di Turing che, ricevuto in ingresso sul nastro una stringa sull’alfabeto {1, 2, 3, 4, 5, 6, 7, F, C,R}, in cui ogni simbolo rappresenta una carta, dica se la giocata ha sballato superando il 7 e mezzo (lasciando sul nastro KO) o no (lasciando sul nastro OK).

NASTRO INIZIALE NASTRO FINALE COMMENTO
34 OK 7
145 KO 10
4RF OK 5
2R4C OK 7
411 OK 6
3R4 OK 7 e 1/2
1R16 KO 8 e 1/2

Problema 7 – Dadi

Le scommesse sui dadi hanno portato alla rovina più di un giocatore.
In una variante di questo gioco, il giocatore punta una cifra a sua discrezione (strettamente maggiore di 0) su un numero fra 1 e 6; vengono quindi lanciati tre dadi a 6 facce, e il giocatore incassa tante volte la posta quanti sono i dadi che hanno fornito il risultato su cui ha puntato.
Se nessun dado ha dato quel risultato, il giocatore perde la posta.

Si scriva un programma per macchina di Turing che, ricevuta sul nastro una sequenza composta da un numero rappresentante la puntata, un simbolo e infine i tre valori forniti dai dadi, lasci sul nastro la vincita da incassare.

NASTRO INIZIALE NASTRO FINALE
100/6/326 100
100/6/114 0
20/1/141 40
1300/6/666 3900
8320/2/422 16640
8320/2/153 0
1/1/111 3

Problema 8 – Black jack

Il gioco Black jack, simile al Sette e mezzo, usa un mazzo di carte francesi, dall’asso al re (13 carte per seme), che indicheremo con {A,2, 3, 4, 5, 6, 7, 8, 9, D, J, Q, K} (D=10, J=Jack, Q=Queen, K=King).

  • Nel Black jack, l’asso vale 1 o 11 punti a scelta del giocatore; J, Q e K valgono 10 punti, le carte dal 2 al 10 valgono ciascuna il proprio valore nominale.
  • Scopo del gioco è avvicinarsi il più possibile al 21, senza superarlo.
  • Il punteggio più ambito è ovviamente il black jack, dato da asso (con valore 11) e una figura (con valore 10), per un totale di 21.

Si scriva un programma per macchina di Turing che, data sul nastro di ingresso una serie di carte, lasci in uscita il valore numerico della giocata, scegliendo per l’asso il valore 1 o 11 a seconda di quale è più conveniente al giocatore.
Se il risultato supera il 21, il programma deve lasciare in uscita il solo simbolo S (superamento).

NASTRO INIZIALE NASTRO FINALE
478 19
5Q 15
KK 20
KKA 21
A8 19
AJ 21
4QD S
111AA 15

Problema 9 – Scopa

La Scopa si gioca con le carte napoletane.

  • A turno, i giocatori scartano una carta, e se sono presenti a terra una o più carte per cui la somma del valore coincide con la carta scartata, il giocatore prende la propria carta e quelle che assommano lo stesso valore; in caso contrario, la carta viene lasciata a terra.
  • Nella scopa, il Fante vale 8, il Cavallo vale 9, il Re vale 10, tutte le altre carte valgono il proprio valore nominale.
Si scriva un programma per macchina di Turing che riceva sul nastro in ingresso l’elenco di carte a terra, seguito da una / e dalla carta giocata dal giocatore, e lasci sul nastro in uscita l’insieme delle carte a terra dopo la giocata (e l’eventuale presa).
In caso siano possibili più prese, esse sono considerate tutte ugualmente accettabili.
NASTRO INIZIALE NASTRO FINALE COMMENTO
436/4 36 Prende il 4
165F/5 16F Prende il 5
165F/7 5F Prende 6+1=7
165F/3 165F3 Non prende
113R2/7 R Prende 1+1+3+2=7
46/R Prende 4+6=10, scopa!
46/1 461 Non prende
/F F Non prende, cala un fante

Problema 10 – Il Tris

Nel gioco del Tris, i concorrenti piazzano alternativamente un simbolo O (lettera O, non numero 0) o X in una casella di una scacchiera 3x3, spesso rappresentata come nelle figure sotto.

  • Vince il concorrente che allinea tre simboli uguali in orizzontale, verticale o diagonale.
  • Il gioco continua, con mosse alternate, finché ci sono caselle libere sulla scacchiera.

Si scriva un programma per macchina di Turing che, ricevuta sul nastro in ingresso una rappresentazione per righe di una scacchiera valida, in cui il simbolo . indica una casella vuota, lasci sul nastro il simbolo X o O se uno dei due giocatori ha vinto, P se è un pareggio, C se il gioco continua.

NASTRO INIZIALE NASTRO FINALE COMMENTO
XOX.XO..O C XOX
.XO
..O
Nessun tris, partita continua
XOO.XOXXO O XOO
.XO
XXO
Il giocatore O ha fatto tris
XOXXXOOXO P XOX
XXO
OXO
Nessun tris, partita patta
X.O.XO..X X X.O
.XO
..X
Il giocatore X ha fatto tris
C ...
...
...
Nessun tris, partita continua
….O…. C ...
.O.
...
Nessun tris, partita continua
XX..X.OOO O XX.
.X.
OOO
Il giocatore O ha fatto tris

Edizione XII

Problema 1 – Notazione unaria

Un numero intero n è rappresentato in notazione unaria da una sequenza di n simboli uguali, per esempio U.

Si scriva un programma per macchina di Turing che, ricevuto sul nastro un intero positivo in notazione decimale, lasci come risultato lo stesso numero, scritto in notazione unaria.

NASTRO INIZIALE NASTRO FINALE
4 UUUU
0
13 UUUUUUUUUUUUU
1 U

Problema 2 – Inversione

Si scriva un programma per macchina di Turing che, ricevuta in ingresso sul nastro una stringa sull’alfabeto {H, O, C} (attenzione: si tratta della lettera O, non della cifra 0), lasci sul nastro alla fine della computazione la stessa stringa, ma scritta in ordine inverso.

NASTRO INIZIALE NASTRO FINALE
OOOH HOOO
C C
HCCOH HOCCH
HOCCOCH HCOCCOH
OOO OOO

Problema 3 – Completezza

Si scriva un programma per macchina di Turing che, ricevuta in ingresso sul nastro una stringa sull’alfabeto {C, H, O}, lasci sul nastro la scritta SI se la stringa in ingresso conteneva ciascuno dei caratteri dell’alfabeto almeno una volta (la stringa in questo caso si dice completa rispetto all’alfabeto), NO in caso contrario.

NASTRO INIZIALE NASTRO FINALE
COO NO
HCCO SI
COCO NO
HHHHH NO
OHHHHC SI

Problema 4 – Ordinamento

Si scriva un programma per macchina di Turing che, ricevuta in ingresso sul nastro una stringa sull’alfabeto {H, O, C}, lasci sul nastro una stringa composta dagli stessi simboli presenti nell’input, ciascuno con lo stesso numero di occorrenze, ma ordinati in modo che tutte le H precedano le O, e tutte le O precedano le C.

NASTRO INIZIALE NASTRO FINALE
CHOO HOOC
COCCO OOCC
HHHOOCCC HHHOOCCC
COCHCOCH HHOOCCCC
O O

Problema 5 – La chimica di Turing I

Usiamo i caratteri H, O, C per rappresentare, rispettivamente, un atomo di idrogeno, ossigeno, carbonio.

  • Una sequenza di queste lettere può quindi rappresentare una molecola (ovviamente è anche possibile scrivere formule che non possono rappresentare una molecola stabile, ma per semplicità non ci poniamo il problema).
  • Nella chimica di Turing si usa una notazione compatta per scrivere queste formula, consistente in un numero decimale preceduto dalla lettera che identifica una molecola.
  • Per esempio, O2 (ossigeno molecolare) sta per OO, CH4 (metano) per CHHHH e H2O (acqua) per HHO.

Si scriva un programma per macchina di Turing che, ricevuto in ingresso una formula in notazione compatta, lasci sul nastro la stessa formula in notazione espansa.
Si assuma per semplicità che le quantità siano sempre espresse da una sola cifra decimale (da 2 a 9; l’assenza di un numero indica 1).

NASTRO INIZIALE NASTRO FINALE COMMENTO
CO2 COO Anidride carbonica
H2O2 HHOO Acqua ossigenata
CH4 CHHHH Metano
CH3CH3 CHHHCHHH Etano
CH2CH2 CHHCHH Etilene
O2 OO Ossigeno

Problema 6 – La chimica di Turing II

Come ulteriore forma di compressione, una formula in notazione compatta può essere preceduta da un numero decimale, che indica quante volte la formula è ripetuta.

  • Per esempio, 2H2O (due molecole di acqua) sta per HHOHHO, e 4CO2 (quattro molecole di anidride carbonica) sta perCOOCOOCOOCOO.

Si scriva un programma per macchina di Turing per effettuare il cambio di notazione, con l’assunzione che il numero iniziale (che rappresenta il numero di molecole) sia compreso fra 2 e 9 (estremi inclusi), oppure assente del tutto.

NASTRO INIZIALE NASTRO FINALE
4CO2 COOCOOCOOCOO
CO2H COOH
COOH COOH
3C2H2O CCHHOCCHHOCCHHOCCHHO

Problema 7 – Successione di Fibonacci

I numeri di Fibonacci sono definiti, per ricorrenza, dalla seguente equazione:

  • f(x)=1, se x <= 2
  • f(x)=f(x-1)+f(x-2), altrimenti

La successione di Fibonacci è formata dai numeri di Fibonacci consecutivi, partendo da f(1) (si noti che ogni termine della successione dopo i primi due è dato dalla somma dei due termini precedenti).

Si scriva un programma per macchina di Turing che, dato in ingresso un numero decimale n, lasci in uscita sul nastro i primi ntermini della successione di Fibonacci, separati esattamente da uno spazio.

NASTRO INIZIALE NASTRO FINALE
5 1 1 2 3 5
8 1 1 2 3 5 8 13 21
10 1 1 2 3 5 8 13 21 34 55
1 1

Problema 8 – Successione di Collatz

Si consideri la funzione

  • c(x)=3x+1, se x è dispari
  • c(x)=x/2, se x è pari

Si scriva un programma per macchina di Turing che, ricevuto sul nastro un intero x, lasci sul nastro la sequenza

x c(x) c(c(x)) c(c(c(x))) … 1 (con i valori separati da un singolo spazio).

Si noti che, benché i valori della successione così ottenuta crescano e decrescano in maniera apparentemente imprevedibile, esiste una congettura (non un teorema), detta Congettura di Collatz, secondo la quale per qualunque valore iniziale x, la successione raggiunge prima o poi il valore 1.
La lunghezza della sequenza è anch’essa molto variabile: per x=26, occorrono 11 passi per giungere a 1, ma per x=27 ne occorrono ben 111.
La congettura è stata verificata su calcolatore per tutti gli interi x fino a circa 2,88·10^18, ma manca una dimostrazione che ne garantisca la verità per qualunque x.
Sarete voi a trovarla?

NASTRO INIZIALE NASTRO FINALE
5 5 16 8 4 2 1
6 6 3 10 5 16 8 4 2 1
13 13 40 20 10 5 16 8 4 2 1
27 27 82 41 124 62 31 94 47 142 71 214 107 322 161 484 242 121 364 182 91 274 137 412 206 103 310 155 466 233 700 350 175 526 263 790 395 1186 593 1780 890 445 1336 668 334 167 502 251 754 377 1132 566 283 850 425 1276 638 319 958 479 1438 719 2158 1079 3238 1619 4858 2429 7288 3644 1822 911 2734 1367 4102 2051 6154 3077 9232 4616 2308 1154 577 1732 866 433 1300 650 325 976 488 244 122 61 184 92 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1
2 2 1
1 1

Problema 9 – La chimica di Turing III

Una formula stechiometrica di Turing è un’equazione, i cui termini sono separati dal simbolo =, e ciascuno dei termini è formato da una somma di molecole, in cui ogni addendo è una formula in notazione compatta (es.: 2H2O).
Una formula di questo tipo si dice bilanciata se il numero totale di occorrenze di ogni elemento a destra e a sinistra del segno di uguale è identico.

Per esempio,

  • 2H2O+O2+H+H=2O2+4H è bilanciata (sono presenti 4 atomi di ossigeno e 4 di idrogeno in entrambi i termini),
  • così come CH4+2O2=CO2+2H2O (che rappresenta la combustione del metano in presenza di ossigeno, e produce anidride carbonica e acqua),
  • mentre CO2+H2O=4CHO non lo è.

Si scriva un programma per macchina di Turing che, ricevuta in ingresso una stringa rappresentante una formula stechiometrica, lasci sul nastro la scritta SI se la formula è bilanciata, NO altrimenti.

NASTRO INIZIALE NASTRO FINALE
2H2O=O2H4 SI
2H2O+O2+2H=2O2+4H SI
H2O+2OH=CH4 NO
4O=2O2 SI
CH4+CO2+O2=2CO2+2H2O NO

Problema 10 – La chimica di Turing IV

In tempi di crisi energetica, si cerca di estrarre idrocarburi dalle fonti più variegate.
Siamo interessati in particolare al metano, che ha formula CH4.

Si scriva un programma per macchina di Turing che, ricevuta in input un termine di una formula stechiometrica (gli ingredienti), lasci sul nastro il numero di molecole di metano che sarebbe potenzialmente possibile estrarre dagli ingredienti.

Per esempio, 8CO2+8H2O contiene 8 atomi di carbonio e 16 di idrogeno (oltre a 24 di ossigeno, che però non ci interessano); sarebbe quindi possibile estrarre da questi ingredienti fino a 4 molecole di metano (ovvero, 4 atomi di carbonio e 16 di idrogeno).
Si noti che il numero di molecole di metano estraibili da una formula potrebbe richiedere più cifre decimali per essere espresso.

NASTRO INIZIALE NASTRO FINALE
8CO2+8H2O 4
6H2O+4CO2+COOH+4H2O 5
H2O+5CO2 0
6CH4 6
4O2+8H2O+4OH+4CO2+4C2H5 10

Edizione XI

Problema 1 – Moltiplicatore per 10

Si scriva un programma per Macchina di Turing che, ricevuto sul nastro un numero decimale, lasci sul nastro alla fine della computazione il risultato della moltiplicazione del numero di ingresso per 10.

NASTRO INIZIALE NASTRO FINALE
3 30
450 4500
123456 1234560
0 0

Problema 2 – Divisore per 10 (I)

Si scriva un programma per Macchina di Turing che, ricevuto sul nastro un numero decimale, lasci sul nastro alla fine della computazione il risultato della divisione del numero di ingresso per 10, approssimato in basso.

NASTRO INIZIALE NASTRO FINALE
145 14
534623 53462
10 1
0 0

Problema 3 – Riconoscimento numeri reali

Si scriva un programma per Macchina di Turing che, ricevuta sul nastro una stringa qualunque sull’alfabeto { 0-9, +, , . } lasci sul nastro la scritta SI se la stringa di ingresso rappresenta un numero reale in notazione decimale, definito come

[ + o - ] <sequenza di cifre> [ . <sequenza di cifre> ]

Se la stringa di ingresso non è un numero reale in notazione decimale, il programma deve lasciare sul nastro la stringa NO.

Si noti che, sotto l’assunzione che l’input sia finito, tutti i numeri esprimibili in questa notazione sono in realtà numeri razionali: come tutti i sistemi di elaborazione digitali, la Macchina di Turing può solo trattare approssimazioni razionali dei numeri reali.

NASTRO INIZIALE NASTRO FINALE
34 SI
-342.123 SI
-343-342 NO
234.234.23 NO
+12.45 SI
-38 SI
–34 NO
0 SI

Problema 4 – Divisore per 10 (II)

Si scriva un programma analogo a quello dell’esercizio 2, in grado però di operare su numeri reali (con opzionalmente segno e parti decimali) e approssimante verso lo 0.
Il segno va preservato nel risultato.

NASTRO INIZIALE NASTRO FINALE
145 14
-3017 -301
-3.1415926 0
31.415926 3
-100.5 -10

Problema 5 – Divisore per 10 (III)

Si scriva un programma analogo a quello dell’esercizio 4, che approssimi il risultato all’intero più vicino anziché verso lo 0.

NASTRO INIZIALE NASTRO FINALE
145 14
145.1 15
137.81 14
-218.0001 -22
5 0
6 1

Problema 6 – Conteggio di sottostringhe

Si scriva il programma di una Macchina di Turing che, date sul nastro due stringhe formate da lettere nell’alfabeto { A..J } separate da$, conta le occorrenze distinte della stringa a sinistra del $ all’interno di quella a destra del $.

Il programma deve lasciare sul nastro il numero di occorrenze trovate, espresso in notazione decimale.

NASTRO INIZIALE NASTRO FINALE
AB$ABBACCHIA 1
BA$BABA 2
AB$CABABBAABDABBBABABBBBE 6
AA$AAABBAA 2
F$ABCDE 0
AAA$AAABBAA 1

Problema 7 – Percentuale

Si scriva un programma per Macchina di Turing che, ricevuta in ingresso una stringa della forma a%b, in cui a e b sono numeri decimali e a è compreso fra 0 e 100 (inclusi), lasci sul nastro al termine della computazione il numero naturale corrispondente all’a%di b, approssimato in basso.

NASTRO INIZIALE NASTRO FINALE
10%50 5
25%100 25
33%1000 333
4%1890 75
0%3240 0
100%12 12
50%0 0

Problema 8 – Parole simili

Definiamo la distanza tra due parole composte di lettere A..Z come il numero di posizioni in cui le lettere corrispondenti nelle due parole differiscono.

  • Nel caso una parola sia più corta dell’altra, si assume che essa differisca in tutte le posizioni rimaste.
  • Per esempio, ABACO e ABATE sono a distanza 2, mentre ACANTO e ABATE sono a distanza 4.
  • Una nozione di distanza simile a questa (ma leggermente più complessa) è usata, fra l’altro, dai correttori ortografici forniti con i programmi di videoscrittura.

Si scriva il programma di una macchina di Turing che, dato sul nastro di input una parola seguita dal simbolo $ e una lista di parole separate da :, lasci sul nastro alla fine della computazione la parola della lista più “vicina” alla prima (ovvero, la cui distanza rispetto alla prima parola è minima).

Nel caso vi siano più parole con pari distanza minima, il programma dovrà restituire come risultato la prima della lista (ovvero, quella più a sinistra).
Si assuma che ciascuna parola sia lunga al più 9 caratteri.

NASTRO INIZIALE NASTRO FINALE
PEFA$PELO:PERA:PASSA PERA
PASSARE$FIUTARE:PASSATA:PASSARE PASSARE
NULLA$
SQUOLA$SQUALO:SCUOLA:STUOLO:STOLA SCUOLA

Problema 9 – La prova del 9

La prova del 9 è un metodo per verificare la correttezza di una moltiplicazione, basato sulle proprietà dell’aritmetica modulare.
Il metodo di prova si basa sul fatto che per ogni n, 10n mod 9 = 1; tecnicamente, diciamo che la somma delle cifre di un numero decimale mantiene l’equivalenza al numero in Z9 (l’anello degli interi modulo 9).

La forma tradizionale della prova del 9 è la seguente.
Innanzitutto si traccia una croce, che delimita quattro spazi che chiameremo A, B, C e D:

A B
C D

Nelle quattro zone si scrive (volendo verificare per esempio se è corretto il risultato 1902×1964=3735528):

  • In A: si sommano ripetutamente le cifre del moltiplicando, il primo fattore, finché non resta un numero ad una sola cifra:
    • 1902 => 1+9+0+2=12
    • 12 => 1+2=3
  • In B: si applica lo stesso procedimento con il moltiplicatore, il secondo fattore:
    • 1964 => 1+9+6+4=20
    • 20 => 2+0=2
  • In C: si moltiplicano i 2 numeri appena ottenuti e posti in alto sulla croce.
    Se il risultato della moltiplicazione ha più cifre, esse sono ripetutamente sommate come prima:

    • es. 3*2=6.
  • In D: si sommano le cifre del risultato presunto della moltiplicazione:
    • 3735528 => 3+7+3+5+5+2+8=33
    • 33 => 3+3=6

Nel caso del nostro esempio avremo dunque:

3 2
6 6

Quando, come in questo caso, i due numeri in basso sono uguali allora la prova ha esito positivo, altrimenti ha esito negativo.
Si noti però che:

  • se la prova ha esito negativo allora la moltiplicazione è sicuramente errata
  • se la prova ha esito positivo, il risultato trovato potrebbe essere errato, e differire dal risultato reale per un multiplo di 9. Infatti, se al risultato si sommasse o sottraesse 9 o un suo multiplo, il test sarebbe ancora superato (9 è infatti equivalente a 0 in Z9)!

Si scriva un programma per Macchina di Turing che, ricevuta sul nastro una moltiplicazione con un risultato presunto, nella formaa*b=c (con a, b e c numeri decimali) lasci sul nastro la stringa SI se la prova del 9 ha esito positivo, NO in caso contrario.
Come già osservato, il programma deve rispondere SI anche se la moltiplicazione è errata, ma la prova del 9 è superata.

NASTRO INIZIALE NASTRO FINALE
123*456=56088 SI
123*456=56089 NO
123*456=56097 SI
0*12=0 SI
150*30=4500 SI
150*30=9 SI
150*30=4300 NO

Problema 10 – Espressioni regolari

Una espressione regolare identifica un insieme di stringhe, ovvero un linguaggio.
Un’espressione regolare è denotata da un pattern, ovvero da una sequenza di caratteri, alcuni dei quali dotati di una particolare interpretazione, che indica quali stringhe appartengono all’insieme e quali no.
Ad esempio il pattern CIAO+ denota l’insieme di tutte le stringhe formate dai caratteri C, I, A e che terminano con una sequenza di uno o più caratteri O.
Ecco quindi che le stringhe CIAO, CIAOO, CIAOOOOO ecc. apparterranno all’insieme (si usa dire che esse soddisfano l’espressione regolare), mentre XX, CIA, CIAOA ecc. non vi apparterranno.

Consideriamo pattern formati da sequenze di caratteri da interpretare come segue:

  • Ogni carattere nell’alfabeto { A..Z } indica che nella stringa da verificare deve essere presente lo stesso carattere
  • Il carattere . indica che nella stringa da verificare deve essere presente un carattere qualsiasi
  • Se un carattere è seguito dal carattere * si intende che nella stringa da verificare il carattere precedente l’* può occorrere 0 o più volte (es. CI*AO indica le stringhe della forma CAO, CIAO, CIIAO, …)
  • Se un carattere è seguito dal carattere + si intende che nella stringa da verificare il carattere precedente il + può occorrere 1 o più volte (es. CI+AO indica le stringhe della forma CIAO, CIIAO, …). Si noti che per ogni carattere c, il pattern c+ è equivalente al pattern cc*.

Si scriva il programma di una Macchina di Turing che data sul nastro un pattern nel formato descritto, seguito dal simbolo $ di separazione e da una stringa (anche vuota) sull’alfabeto { A..Z }, lasci sul nastro

  • SI se la stringa soddisfa l’espressione regolare denotata dal pattern,
  • NO altrimenti.
NASTRO INIZIALE NASTRO FINALE
CIAO$CIAOO NO
CIAO$CIAO SI
C*I*A*O*$ SI
C*I*A*O*$IIAAA SI
C*I*A*O*$ICIAO NO
C+I*AO$CIAO SI
C+I*AO$CCIIIAO SI
C+I*AO$CIAOO NO
C.AO$CIAO SI
C.AO$CEAO SI
C.AO$EEAO NO
.*$ SI
.*$BUONLAVORO SI
.*A$BUONLAVORO NO