Dimostrare che FIN è non-RE

Rispondi
Avatar utente
InformateciBot
Messaggi: 314
Iscritto il: 30/09/2018, 16:33

Salve a tutti, qualcuno può darmi una mano a risolvere questo esercizio?
La mia idea è quella di ridurre Ksegnato a FIN e quindi dimostrare che FIN è non-RE.
Ho definito quindi psi(x,y) = phi_f(x) (y) = ....... ?
Non so proprio da dove partire per definire questa funzione e in generale per definire funzioni che permettano di dimostrare altre riduzioni da Ksegnato a un insieme.. Help
LorenzoBuonanno
Messaggi: 29
Iscritto il: 10/02/2019, 23:23

MindFlyer:
Non so cosa vuoi fare con quella psi, quella phi, e quella f, né come siano definite, né che senso abbia impostare le cose così.

Tutto quello che vuoi fare è una riduzione da K a INF, che è una cosa abbastanza facile da fare (dato che FIN è molto più di non-RE). Cioè, dato un x, devi calcolare un indice di funzione calcolabile f(y) che sia definita per infiniti y se e solo se phi_x termina su input x. Il modo più ovvio di farlo è simulare phi_x per y passi...

andreRondo:
Scusa ma proprio non ci sono..
K è r.e. completo e se riesco a ridurlo a INF, posso sapere al massimo che è r.e. ... Essendo INF il complementare di FIN, cosa me ne faccio di sapere che INF è al massimo r.e. ?(non potrei sfruttare il fatto che INF è non r-e e andare avanti per quella strada, se proprio voglio utilizzare INF ? )
So che è una cosa facile, però davvero mi ci perdo in queste dimostrazioni..

ah aspetta.. Per il fatto che K e INF sono rispettivamente i complementari di Ksegnato e FIN, allora riduco K a INF perché per la proprietà di riduzione, A<B sse Asegnato<Bsegnato?

MindFlyer:
Non avevo voglia di scrivere "K segnato" perché c'è un momentaneo problema di LaTeX nel forum, quindi ho scritto la cosa equivalente, ovvero riduzione da K a INF. Tutto qua.

andreRondo:
quindi phi_x di cui parlavi prima, termina se simulato per infiniti y passi e quindi K si riduce a INF e quindi Ksegnato si riduce a FIN e si deduce che FIN è non-RE.. Giusto?

MindFlyer:
« quindi phi_x di cui parlavi prima, termina se simulato per infiniti y passi »
Questa cosa non ha senso.

andreRondo:
Intendevo dire che phi_x termina in quanto sappiamo che x appartiene a K..

MindFlyer:
Tu devi dire come si calcola phi_f(x) (y) in modo che sia definita per un numero infinito di y se e solo se phi_x(x) termina. Il suggerimento è di simulare phi_x(x) per y passi. Manca la conclusione... Cosa deve restituire phi_f(x) (y)?

Comunque questi esercizi si fanno tutti nello stesso modo. Qui ce n'è un altro molto simile: [url=https://www.informateci.it/viewtopic.php?f=29&t=667&p=668]Riduzione di TOT a INF[/url]

andreRondo:
Costruisco φf(x) in questo modo.
φf(x)(y)=ψ(x,y)={ 42 if x∈K and ∀z<y.φx(z)↓ indefinita altrimenti

In questo modo se x∈K⇒φf(x) calcola la funzione costante y=42.
Perciò f(x)∈INF.
Altrimenti se x∉K⇒∃k∈N.φx(k)↑. Quindi in questo caso la macchina φf(x)diverge quando ha come input valori maggiori di k, dove k è il minimo numero t.c la φx(k)↑.

Pertanto dom(φf(x))={0,...,k}, che è finito e quindi f(x)∉INF

Ok così?

MindFlyer:
No. Rincontrolla la definizione di K.

Lucac:
So che è il post è di più di un anno fa ma sto preparando ora l'esame ed ero interessato anche io a questa dimostrazione.
Nella soluzione che è stata proposta è sbagliata la condizione ∀z<y.φx(z)↓ ?
O c'è qualcos'altro che non va?


mizipolo:
Credo un po' tutta la riduzione sia un po' insensata, forse scopiazzata da quell'altra da [math] a [math]. MindFlyer ne suggerisce una moooolto più semplice

Lucac:
Io per K che si riduce a INF avevo pensato di costruire φf(x) così:
[math]

Se x∈K⇒φf(x) = 1 e f(x)∈INF.
Altrimenti φf(x) è indefinita e f(x)∉INF

Però sinceramente ho qualche dubbio al riguardo

mizipolo:
Va bene!
Lucac:
Grazie!!
Rispondi

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