Problemi e Applicazioni MdT

Question 1

Funzione parziale?

Answer 1

Quando dominio è relazione R\sube N^k

R\sube N^k -> N

Question 2

Funzione parziale computabile

Answer 2

o tau-ric. quando esiste algoritmo che Vx\inN^k
- f(x) se x\in R
- altrimenti non termina

Question 3

Tesi di Church estesa (per funzioni parziali τ-ricorsive)

Answer 3

la classe delle funzioni parziali computabili coincide con la classe delle funzioni parziali tau -ricorsive

Question 4

Unicità funzione parziale k-aria calcolata da M

Answer 4

data mdt esiste una sola funzione parziale k-aria computabile calcolata da M.

codifico input in 111…111…
Leggo output su stringa 111… (1 sparsi)

Question 5

Codifica binaria di MdT

Answer 5

codifico stati qi=11111(#i+1 1)
lettere alfabeto ai=1111…(#i+1 1)
simboli spostamento=(D=11…(#s+2), S=11…1(#s+3))
1 zero = separo simboli
2 zeri = separa transizioni
3 zeri = inizio e fine codifica MdT
transizione = cod(stato)0cod(lettera)0cod(spostamento)0cod(nuovo stato)

Question 6

Insieme di MdT è enumerabile

Answer 6

Usando rappresentazione binaria.
genero tutte le stringhe binarie, effettuo controllo sintattico

Ogni MdT in M1, M2, …, Mn, … ha funzione parziale computabile univoca

Question 7

M_a(a) è semidecidibile

Answer 7

Sia K insieme di numeri a tale che M_a(a) termina.
Dim
algoritmo di semidecisione, dato a eseguo algoritmo di enumerazione per trovare M_a (mdt sono enumerabili)
Esegue M_a(a) se termina allora a apparteiene a K

Per assurdo K decidibile
Per Church esiste M MdT che decide K
creo phi definita come
- f_n+1 se x in R
- 0 altrimenti
phi è computabile (f_n per enumerazione MdT mentre K è decidibile, quindi dire se n sta in K o no è decidibile)
phi computabile -> compare nella lista delle funzioni computabili unarie
perciò phi=f_h per n opportuno
- calcolo se h\in K phi(h)=f_h(h)+1 assurdo
- se h not in K phi(h) = 0 pero per def di K (MdT non terminano) assurdo

Question 8

Teorema dell’arresto

Answer 8

Data MdT M e stringa w, determinare se M termina o no

Questo problema non è decidibile

Def R={(n,m)\in N^2| M_n(m) termina}
R non è decidibile (lo sia per assurdo allora anche K sarebbe decidibile n=m)

Question 9

Cos’è una MdT universale

Answer 9

prende in input MdT e k-upla e simula il comportamento di MdT su input k-upla

Esiste

Question 10

Gödelizzazione di MdT

Answer 10

Sia a_1,…,a_s alfabeto
godelizzazione
ogni stringa in Sigma^* diventa
P1^{indice nell’alfabeto +1} . P2^{indice 2a lettera +1) …
dove Pn sono primi diversi in ordine crescente

Question 11

Cos’è una riduzione da un linguaggio ad un altro?

Answer 11

Sia L1\sube \Sigma1^, L2\sube \Sigma2^
f da \Sigma1^* a \Sigma2^* si dice riduzione quando
- f computabile
- per ogni parola in \Sigma^* w\in L1 <->w\in L2

Cioè ogni parola in L1 viene tradotta in parola in L2, mentre ogni parola not in L1 viene tradotta in parola not in L2

Question 12

L_1 rid a L_2, L_2 dec → L_1 dec (utile per dimostrazioni)

Answer 12

Ho f riduzione da L1 a L2, M2 algoritmo di decisione -> voglio M1 algoritmo di decisione

w -> f(w) -> M2(f(w)) = M1(w)

Viceversa se L1 riducibile a L2, L1 indecidibile -> L2 indecidibile (contronominale)

Question 13

Problema del nastro vuoto

Answer 13

Dato MdT determinare se M termina su nastro vuoto

Question 14

BTP è indecidibile

Answer 14

Riduzione da Lhalt a Lbtp
1. Controllo sintassi input (=R(MdT)w)
2. Input: R(MdT)w, voglio R(M’) tale che M’ termini
M’ scrive w sul nastro ed esegue M su w
M termina su w <-> M’ termina su nastro vuoto

Question 15

Quali proprietà di linguaggi semidecidibili

Answer 15

➢ 𝜀∈𝐿(𝑀)? Ovvero: 𝑅(𝑀)∈{𝑅(𝑁) | 𝜀∈𝐿(𝑁)}? ➢ 𝐿(𝑀)=∅? Ovvero: 𝑅(𝑀)∈{𝑅(𝑁) | 𝐿(𝑁)=∅}?
➢ 𝐿(𝑀) è regolare? Ovvero: 𝑅(𝑀)∈{𝑅(𝑁) | 𝐿(𝑁) è 𝑟𝑒𝑔𝑜𝑙𝑎𝑟𝑒}?
➢ 𝐿(𝑀)=Σ∗? Ovvero: 𝑅(𝑀)∈{𝑅(𝑁) | 𝐿(𝑁)=Σ∗}?

Question 16

L_{Σ^*} è indecidibile

Answer 16

Ricordiamo L_{Σ^}={R(M)|L(M)=Σ^}

Question 17

Cos’è una proprietà banale?

Answer 17

P si dice banale quando ogni linguaggio semidecidibile soddisfa P oppure nessuno lo soddisfa

Question 18

Enunciato teorema di Rice

Answer 18

Se P è proprietà non banale -> Lp = {R(M)|L(M) soddisfa P} e indecidibile

Question 19

Teorema di Rice (dim p1)

Answer 19

1. Suppongo linguaggio vuoto non soddisfa P
   Per hp P è non banale -> Sia L semidecidible t.c L soddisfa P (L!= /0)
   Sia Ml MdT che accetta L

Riduzione da Lhalt a Lp
Descriviamo comportamento su M.
R(M)w —> R(M’)
1. Dato input y, scrivo w a destra di y (nastro diventa yw)
2. Eseguo M su w
se non termina -> M’ non termina
se termina su w vado all’inizio

Oss. Se M termina su w, M’ ha lo stesso comportamento su ogni stringa.
Dunque L(M’)=L(Ml)=L e L soddisfa P (R(M’) in Lp)

Question 20

Teorema di Rice (dim p1)

Answer 20

Supponiamo linguaggio vuoto soddisfa P -> linguaggio vuoto non soddisfa not p

Sappiamo da punto 1 che L_notP è indecidibile
L_notP indecidibile -> Lp U {tutto cio che non è codifica di MdT} non è decidibile (complementare)
-> Lp non è decidibile (per contronominale di sotto)

Lp decidibile -> LP U {MdT} è decidibile
1. Controllo se codifica MDT
2. Se lo è uso algoritmo di decisione di Lp

Question 21

Applicazioni teorema di Rice

Answer 21

Si può usare se dire se una proprietà di un linguaggio è decidibile

1. Determinare se è proprietà non banale DEL LINGUAGGIO (NO MDT) (trovare esempio che non soddisfa ed esempio che soddisfa)
2. Per il teorema di Rice L1 è indecidibile

Question 22

Ogni funzione mu-ricorsiva è tau-ricorsiva (dim)

Answer 22

Procediamo per induzione strutturale su funzioni mu-ricorsive

Possono essere
- funzioni iniziali
- costruttori: composizione, ricorsione primitiva, minimalizzazione funzione regolare

Per ognuna creao mdt che lo calcola