XI edizione

Moltiplicatore per 103

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.

Divisore per 10 (I)5

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.

Riconoscimento numeri reali10

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 - ] [ . ]
  • 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.

    Divisore per 10 (II)12

    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.

    Divisore per 10 (III)15

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

    Conteggio di sottostringhe25

    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.

    Percentuale25

    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.

    Parole simili30

    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.

    La prova del 942

    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:
    ab
    cd

    Nelle quattro zone si scrive (volendo verificare per esempio se è corretto il risultato 1902×1964=3735528):
    1. In A: si sommano ripetutamente le cifre del moltiplicando, il primo fattore, finché non resta un numero ad una sola cifra: es. 1902 => 1+9+0+2=12; 12 => 1+2=3
    2. In B: si applica lo stesso procedimento con il moltiplicatore, il secondo fattore: es. 1964 => 1+9+6+4=20; 20 => 2+0=2
    3. 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.
    4. In D: si sommano le cifre del risultato presunto della moltiplicazione: es. 3735528 => 3+7+3+5+5+2+8=33; 33 => 3+3=6
    Nel caso del nostro esempio avremo dunque:
    32
    66

    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:
    1. se la prova ha esito negativo allora la moltiplicazione è sicuramente errata
    2. 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 forma a*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.