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
Notice: This work is licensed under a BY-NC-SA. Permalink: Edizione XV

Comments are closed.