admin

Sostituzione di caratteri Programmare una macchina di Turing che, dato un nastro iniziale contenente una sequenza arbitraria di simboli A e B, sostituisca ogni occorrenza di due simboli consecutivi AB con due simboli CD. Nastro iniziale Nastro finale 1° AABABBBAABAAABAABAA ACDCDBBACDAACDACDAA 2° BBBBAAA BBBBAAA 3° AABB ACDB Diagramma di stato Tabella delle transizioni di stato … Leggi tutto

Numeri Trini Un numero intero si dice trino se è divisibile per 3.Se n è trino, n+1 si dice strino e n+2 distrino. Si scriva un programma che, dato in input un numero decimale, lasci sul nastro una delle tre stringhe TRINO, STRINO o DISTRINO a seconda dei casi. NASTRO INIZIALE NASTRO FINALE 3 TRINO 5 DISTRINO … Leggi tutto

Problema 1 – Musica, musica! Tradizionalmente, le sette note della scala musicale vengono denominate in Italia do, re, mi, fa, sol, la, si. Le stesse note nel sistema anglosassone vengono indicate con le prime lettere dell’alfabeto: A, B, … G, con do C re D … … sol G la A si B Si scriva un … Leggi tutto

Si vuole realizzare l’odometro di Erone da Alessandria, ovvero un contatore a cifre decimali a lunghezza fissa che incrementa di uno il numero N.Quando raggiunge il valore massimo 99…9, ritorna a 00…0. Programmare una macchina di Turing che, dato un nastro iniziale contenente un numero decimale N, termini la sua esecuzione lasciando sul nastro l’incremento di N con l’odometro. Esempi Nastro … Leggi tutto

Addizione unaria Nei sistemi di numerazione posizionale, il valore denotato da un numero è ottenuto moltiplicando ogni cifra per la corrispondente potenza di una base.Nel caso della notazione decimale, la base è 10; la cifra più a destra è moltiplicata per 100=1, quella successiva per 101=10, la terza da destra per 102=100, e così via.Nella numerazione con base 1 (unaria), ciascuna … Leggi tutto

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: Negli anni, questi raggruppamenti hanno cambiato … 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 Tabella delle transizioni di stato 1 2 … 9 A – 0 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 Diagramma 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 –  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