Dimostrare che FIN è non-RE

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 :#

Comments

  • MindFlyerMindFlyer Posts: 436
    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...
  • andreRondoandreRondo Posts: 25
    edited May 2017
    @MindFlyer 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..
  • andreRondoandreRondo Posts: 25
    @MindFlyer 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?
  • MindFlyerMindFlyer Posts: 436
    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.
  • andreRondoandreRondo Posts: 25
    @MindFlyer 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?
  • MindFlyerMindFlyer Posts: 436
    edited May 2017
    andreRondo wrote: »
    quindi phi_x di cui parlavi prima, termina se simulato per infiniti y passi

    Questa cosa non ha senso.
  • andreRondoandreRondo Posts: 25
    @MindFlyer scritto così in effetti non ha senso.. Intendevo dire che phi_x termina in quanto sappiamo che x appartiene a K..
  • MindFlyerMindFlyer Posts: 436
    edited May 2017
    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:
    http://informateci.org/discussion/755/riduzione-di-tot-a-inf
  • andreRondoandreRondo Posts: 25
    edited May 2017
    @MindFlyer
    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ì?
  • MindFlyerMindFlyer Posts: 436
    No. Rincontrolla la definizione di K.
Sign In or Register to comment.