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

Comments are closed.