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:
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 (A–G) oppure Z per una pausa, seguita da una durata (0–7) 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 2A–6G (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 |