ESERCIZI di GARA

Programmare una macchina di Turing che, dato un nastro iniziale contenente una sequenza arbitraria di 0 e 1, termina la sua esecuzione lasciando sul nastro il bit di parità.Tale bit è 1 se e solo se vi sono un numero dispari di 1 nella sequenza iniziale; altrimenti vale 0. Esempi Nastro iniziale Nastro finale 1011100010 1 0001100101 0 0000 0 Diagramma di stato … Leggi tutto

Programmare una macchina di Turing che, dato un nastro iniziale contenente un numero intero n compreso tra 1 e 9, termina la sua esecuzione lasciando sul nastro A…A (n consecutive). Esempi Nastro iniziale Nastro finale 1° 1 A 2° 5 AAAAA 3° 9 AAAAAAAAA Diagramma di stato Quintuple #1 (0,A,0,A,<) Si posiziona a sinistra (0,1,1,-,>) Per ogni cifra da 1 a 9… (0,2,1,1,>) … Leggi tutto

Programmare una Macchina di Turing che, dato un nastro iniziale contenente la rappresentazione decimale di un numero intero positivo k, termina la sua esecuzione lasciando sul nastro la sola sequenza SI se k è un numero pari, la sola sequenza NO altrimenti. Esempi Nastro iniziale Nastro finale 1° 148 SI 2° 2763 NO Algoritmo #1 … Leggi tutto

Problema 1   Problema 2   Problema 3   Problema 4   Problema 5   Problema 6   Problema 7   Problema 8   Problema 9 Problema 10  

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 … Leggi tutto

Problema 1   Problema 2   Problema 3   Problema 4   Problema 5   Problema 6   Problema 7   Problema 8   Problema 9 Problema 10  

Problema 1 – Cambio di casacca Nel Mondo dei Programmatori, la vita politica è molto intensa e piena di sorprese.Nuove liste e partiti si formano e dissolvono di continuo, mentre i Programmatori discutono di quale sia il linguaggio migliore da utilizzare. Per esempio, fino a qualche anno fa si contavano vari movimenti: i Programmatori C Indipendenti … Leggi tutto

Problema 1 – Calendario AT Alan Turing nacque il 23 giugno 1912. Si consideri il 1912AD (Anno Domini) come anno 0AT (Anno Turingi), e si scriva un programma per Macchina di Turing che, ricevuto sul nastro un intero rappresentante un anno nella convenzionale notazione Gregoriana (fra il 1912 e il 9999), lasci sul nastro il corrispondente … Leggi tutto

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 … Leggi tutto

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 … Leggi tutto