Computer Engineering - Algoritmi e Principi dell'Informatica

First partial exam

Algoritmi e Principi dell'Informatica 9 Aprile 2022, prima prova in itinere Esercizio 1 Si denoti, come di consueto, conf yla funzione calcolata dalla macchina di Turing con indice y. Per ciascuna delle seguenti funzioni si dica se e computabile, motivando opportunamente la risposta: a)g 1( y) =( 1 sef 10(10) >10 0 altrimenti b)g 2( y) =( 1 sef 10(10) >10 ?altrimenti c)g 3( y) =( 1 sef y(10) >10 0 altrimenti d)g 4( y) =( 1 sef y(10) >10 ?altrimenti e)g 5( y; x) =( 1 sef y(10) > x 0 altrimenti f )g 6( y; x) =( 1 sef y(10) > x ?altrimenti Soluzione a)S: la condizionef 10(10) >10 e una domanda chiusa. b)S: come sopra.c)No per Rice: l'insieme di funzioniF=ff yj f y(10) >10gnon e ne l'insieme vuoto, ne l'insieme di tutte le funzioni computabili. Ad esempio, la funzione costantef(x) = 11 appartiene adF, mentre la funzione costanteg(x) = 9 no. d)S: basta mettere in esecuzione la macchinay-esima con l'ingresso 10 (recuperandone il suo diagramma degli stati con l'enumerazione di Godel). Se termina, ce ne si accorge in tempo nito e si puo confrontare l'esito con 10 (restituendo 1 se l'esito e maggiore ed entrando in un ciclo in nito negli altri casi); se non termina, questo e compatibile con la de nizione della funzioneg 4. e)No: il problema di stabilire sef y(10) > xe una generalizzazione di quello del caso della funzione g3, quindi se sapessimo risolverlo, sapremmo valutare anche il test della funzione g 3, che pero non e calcolabile. f )S: in modo analogo al caso della funzioneg 4. 1/2 Esercizio 2 (7 punti) Si considerino i linguaggiL s= fan b2 m jn; m0geL d= f"; a; aag. Si realizzi un traduttore a potenza minima che calcoli la seguente traduzione daL sa L d: (an b2 m ) =an mod 3 ; dovexmodyindica il resto della divisione interax=y. Soluzioneq 0q 1aq 0aq 2aq 3q 4a=a a="b=" a=" a="a="a=aa=aaa="b="b=" 2/2