admin

Edizione patrocinata dal Rotary Club di Pisa e aperta alle scuole della provincia di Pisa. Problema 1 – Ababa NO Scrivere un programma per macchina di Turing che, ricevuta in ingresso sul nastro una stringa composta di A e B, lasci sul nastro la scritta SI se la sequenza conteneva un numero uguale di A e … Leggi tutto

Problema 1 – 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 … 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 re mi fa sol la si C D E F G A B Si scriva … Leggi tutto

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

Problema 1 – 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 AABABBBAABAAABAABAA ACDCDBBACDAACDACDAA BBBBAAA BBBBAAA AABB ACDB Problema 2 – Parentesi bilanciate Una sequenza di parentesi quadre … Leggi tutto

Programmare una macchina di Turing che simuli il comportamento di una versione semplificata di macchina di Turing rappresentata come segue. La macchina si programma con quintuple, gli stati sono rappresentati da sequenze di ‘S’, mentre i simboli accettati sono 1, 0 e N (che rappresenta il blank o spazio). Una quintupla descritta da <stato><car><stato><car><dir> viene … Leggi tutto

Problema 1 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. NASTRO INIZIALE NASTRO … Leggi tutto

Problema 1 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). NASTRO INIZIALE NASTRO FINALE 1 A 5 AAAAA 9 AAAAAAAAA Problema 2 Programmare una macchina di Turing che, dato un nastro iniziale contenente … Leggi tutto

Problema 1 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. NASTRO INIZIALE NASTRO FINALE 148 SI 2763 NO Problema 2 Programmare … Leggi tutto

Programmare una Macchina di Turing che, dato un nastro iniziale contenente una sequenza di A e B, termina la sua esecuzione lasciando sul nastro la sequenza che si ottiene da quella iniziale rimpiazzando due o più A consecutive con una sola A e due o più B consecutive con una sola B. Esempi Nastro iniziale Nastro … Leggi tutto