Riduzione di K complemento a TOT

Salve a tutti,
Rileggendo le dispense di Degano ho trovato ke si può eseguire la riduzione da K complemento a TOT(insieme di indici di macchine che calcolano funzioni totali), tuttavia non ne dà una dimostrazione.
Qualcuno di voi sa che riduzione usare?

Comments

  • MindFlyerMindFlyer Posts: 436
    Sì, è una tipica domanda da esame, quindi non ti rispondo in modo diretto perché è più utile pensarci prima un po'.
    Scrivi un approccio di soluzione, poi se ti blocchi la sistemiamo insieme.
  • goblin92goblin92 Posts: 15
    edited May 2015
    Avevo pensato di definire una funzione [tex]\psi(x,y)[/tex]che se [tex]x \in K= indefinita[/tex], altrimenti gli assegnavo un valore costante.
    Ma penso che questo non sia possibile visto che se [tex]x \notin K [/tex],allora la macchina non si arresta...
  • MindFlyerMindFlyer Posts: 436
    Ok, allora facciamo così.

    Dobbiamo fare una riduzione da [tex]\overline K[/tex] a [tex]TOT[/tex], ovvero vogliamo una funzione calcolabile [tex]f[/tex] (la riduzione) tale che, per ogni indice di funzione calcolabile [tex]n[/tex],

    [tex]n\in K \iff f(n)\notin TOT[/tex].

    Dunque, se [tex]\varphi_n(n)[/tex] si arresta in un numero finito di passi, vogliamo produrre una funzione [tex]\varphi_{f(n)}[/tex] che non è totale.
    Invece, se [tex]\varphi_n(n)[/tex] non si arresta in un numero finito di passi, vogliamo produrre una funzione [tex]\varphi_{f(n)}[/tex] che è totale.

    Impostando le cose così ce la possiamo fare abbastanza facilmente.
    Cosa deve fare [tex]f[/tex]? Si prende in input un [tex]n[/tex], e costruisce una funzione calcolabile (immaginala come un programma) [tex]\varphi_{f(n)}[/tex] che farà questo: prende un input [tex]m[/tex], e simula [tex]\varphi_n(n)[/tex] per [tex]m[/tex] passi. In base a questa simulazione, calcolerà un certo [tex]\varphi_{f(n)}(m)[/tex]...

    In che modo? Qui ti lascio il compito di concludere. :P
  • MindFlyerMindFlyer Posts: 436
    Tutto tace, quindi concludo io. Se hai dubbi sulla soluzione, chiedi.

    Se [tex]\varphi_n(n)[/tex] termina in meno di [tex]m[/tex] passi, [tex]\varphi_{f(n)}(m)[/tex] cicla all'infinito. Altrimenti, [tex]\varphi_{f(n)}(m)[/tex] termina con un output qualsiasi.

    Quindi, se [tex]n\in K[/tex], prima o poi [tex]\varphi_n(n)[/tex] termina, e [tex]\varphi_{f(n)}(m)[/tex] comincia ad essere indefinita da un certo [tex]m[/tex] poi. Dunque [tex]f(n)\notin TOT[/tex]. Se invece [tex]n\notin K[/tex], [tex]\varphi_n(n)[/tex] non termina mai, e [tex]\varphi_{f(n)}(m)[/tex] è definita per ogni [tex]m[/tex]. Dunque [tex]f(n)\in TOT[/tex].
  • cgiorgia_93cgiorgia_93 Posts: 10
    edited October 2016
    vedevo nelle dispense del turini che lui faceva una riduzione di K¯(segnato) a TOT¯(segnato)..ma cosi facendo non dimostro che TOT è r.e. giusto ?
  • MindFlyerMindFlyer Posts: 436
    edited October 2016
    Così facendo dimostri che [tex]\overline{TOT}[/tex] non è r.e., e questo di per sé non implica nulla sulla ricorsiva enumerabilità di [tex]TOT[/tex].

    (Di solito il teorema che si usa per dimostrare in modo indiretto la non ricorsiva enumerabilità è quello che dice che se un insieme e il suo complementare sono r.e., allora sono ricorsivi. Dunque, se [tex]A[/tex] è non ricorsivo e [tex]\overline{A}[/tex] è r.e., allora [tex]A[/tex] non è r.e. Nel caso di [tex]TOT[/tex] il teorema non si applica, perché sia [tex]TOT[/tex] che il complementare non sono r.e.)
Sign In or Register to comment.