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