Ricevimento 26/10/2020

Rispondi
Enrico Tomasi
Messaggi: 1
Iscritto il: 15/07/2020, 14:41

Elementi di calcolabilità
1 - Riguardo a EXT, come dimostro che non è nè R nè R.E? Ha qualcosa a che vedere con il fatto che le sue funzioni si possono estendere a TOT?

-Basta descrivere una funzione che vale 1 se x=0 ed è indefinita altrimenti, dimostro che non è R tramite il teorema di Rice e che non è R.E con una riduzione da K segnato a EXT

2 - EXT è un I.I.R.F?
- Dal teorema di Rice, ne consegue che lo è perché EXT non è vuoto nè uguale ad N

3 - I = {x | n < x < 2n e Phi_x = Phi_n} sono R, R.E? Com'è la loro unione?
- E' un insieme finito, quindi ricorsivo, se uniamo i due insiemi al variare di n sono ricorsivi

4 - Sappiamo dal Padding Lemma che esiste una funzione che restituisce indici di macchine equivalenti, ne può esistere una che li restituisce tutti?
- Una funzione che è praticamente tutto N (?)

5 - K segnato si riduce a TOT

- E' meglio ridurre K a TOT segnato, in tal caso però mettere come valore restituito dalla Psi 1/2 se x€K non vale perché 1/2 non è N

6 - L'unione finita di insiemi ricorsivi è R o R.E? L'unione infinita invece è R o R.E?

- Unione finita di insiemi ricorsivi : Basta definire la loro funzione caratteristica relativamente all'unione di questa oppure che restituisce il massimo tra {Caratt.A,Caratt.B}

- Unione infinita di insiemi ricorsivi:
Se prendo I0 = {x | Phi_x converge in zero passi}
I1 = {x | Phi_x converge in un passo}
...
In = {x | Phi_x converge in n passi}
La loro unione per i€N è proprio K, che non è ricorsivo (ma è ricorsivamente numerabile)

- Unione finita di insiemi ricorsivamente numerabili : Se faccio andare una macchina in un procedimento a coda di colomba alternativamente per dire se un elemento appartiene ad un insieme A oppure ad un insieme B con A e B € RE oppure dire "MAI" se non converge, allora genero un insieme ricorsivamente numerabile (vedere Teorema 1.10.4 in merito)

- Unione infinita di insiemi ricorsivamente numerabili : Se l'unione finita di insiemi ricorsivi non è ricorsiva e non è detto che quella di insiemi ricorsivamente numerabili sia ricorsivamente numerabile

7 - Esiste f calcolabile totale t.c per ogni x. Dom(Phi_f(x)) = N e per ogni y Phi_z(y) = z => Phi_f(x)(y) = z?
- Esiste, basta prendere come f una funzione costante f = ly.z

8 - Proprietà di I = { x | x € Imm(f) e Dom(g)} con f,g calcolabili totali
- Se g è calcolabile totale, il dominio di g = N e se inoltre x€Imm(f), allora l'insieme I è immagine di una funzione
calcolabile e quindi è ricorsivamente numerabile

9 - Proprietà di A = {i | Phi_i = Phi_2i}
-Utilizzando il teorema del punto fisso, possiamo dire che è infinito, ma non sappiamo dire se è un I.I.R.F

10 - In quali casi A si riduce ad A segnato?
- Certamente non quando è vuoto o Infinito, ma se A si riduce ad A segnato allora A segnato si riduce ad A, e questo
può avvenire se e solo se entrambi gli insiemi sono ricorsivi

11 - Proprietà dell'insieme I = {x | Esiste y t.c Phi_x(y) converge <=> Phi_x+2y converge}
-Se è RE dipende dal'enumerazione, non è vuoto e per il teorema del punto fisso possiamo dire che è infinito, non
sappiamo se è un I.I.R.F


12 - Co-NP è sinonimo di NP?
-No, ma coincidono
Rispondi

Torna a “[ECC] Elementi di calcolabili e complessità”