API 2022 04 09

Page 1

Algoritmi e Principi dell’Informatica 9 Aprile 2022, prima prova in itinere Esercizio 1 Si denoti, come di consueto, con fy la funzione calcolata dalla macchina di Turing con indicey. Per ciascuna delle seguenti funzioni si dica se ` e computabile, motivando opportunamente la risposta: a) g1(y) = { 1 se f10(10)> 10 0 altrimenti b) g2(y) = { 1 se f10(10)> 10 ⊥ altrimenti c) g3(y) = { 1 se fy(10)> 10 0 altrimenti d) g4(y) = { 1 se fy(10)> 10 ⊥ altrimenti e) g5(y,x ) = { 1 se fy(10)>x 0 altrimenti f) g6(y,x ) = { 1 se fy(10)>x ⊥ altrimenti Soluzione a) S` ı: la condizionef10(10)> 10 ` e una domanda chiusa. b) S` ı: come sopra. c) No per Rice: l’insieme di funzioni F ={fy|fy(10)> 10} non ` e n´ e l’insieme vuoto, n´ e l’insieme di tutte le funzioni computabili. Ad esempio, la funzione costante f(x) = 11 appartiene ad F, mentre la funzione costante g(x) = 9 no. d) S` ı: basta mettere in esecuzione la macchina y-esima con l’ingresso 10 (recuperandone il suo diagramma degli stati con l’enumerazione di G¨ odel). Se termina, ce ne si accorge in tempo finito e si pu` o confrontare l’esito con 10 (restituendo 1 se l’esito ` e maggiore ed entrando in un ciclo infinito negli altri casi); se non termina, questo ` e compatibile con la definizione della funzione g4. e) No: il problema di stabilire se fy(10)>x ` e una generalizzazione di quello del caso della funzione g3, quindi se sapessimo risolverlo, sapremmo valutare anche il test della funzione g3, che per` o non ` e calcolabile. f) S` ı: in modo analogo al caso della funzione g4. 1/2 Esercizio 2 (7 punti) Si considerino i linguaggi Ls ={anb2m|n,m≥ 0} e Ld ={ε,a,aa}. Si realizzi un traduttore a potenza minima che calcoli la seguente traduzione da Ls a Ld: τ(anb2m) =an mod 3, dovex mody indica il resto della divisione intera x/y.…