K non rispetta le funzioni

Tratto da: Degano: Domande Orale.

* Dimostrare che [tex]K[/tex] non è un insieme di indici che rispetta le funzioni (i.i.r.f).

Comments

  • MindFlyerMindFlyer Posts: 436
    edited February 2015
    caos wrote: »
    * Dimostrare che [tex]K[/tex] non è un i.i.r.f.

    Carino questo, come l'hai fatto?
  • caoscaos Posts: 9
    E' l'unico dove ho avuto difficoltà, in effetti la dimostrazione è stata un po' confusa.

    A freddo farei vedere che non vale (definizione di i.i.r.f.):
    [tex]\forall x \in K . \phi_x = \phi_y \Rightarrow y \in K [/tex]

    per fare questo si prenda la funzione:
    [tex]
    \varphi_k (y) = \psi (x, y) =
    \left\{
    \begin{array}{ll}
    42 & \mbox{if } y = k \\
    indefinita & \mbox{altrimenti}
    \end{array}
    \right.
    [/tex]
    dove [tex]k[/tex] è l'indice che viene fuori dall'applicazione del teorema s-1-1 (in effetti questo è un passo delicato, ma si passa prima per l'indice di [tex]\psi[/tex], poi si applica il teorema s-1-1) .

    A questo punto, per il padding lemma [tex]\exists z.\varphi_k = \varphi_z[/tex] e che diverge in [tex]z[/tex] per definizione di [tex]\varphi_k[/tex]. QED
  • Solo una domanda: come fai a garantire che il [tex]k[/tex] che usi nella funzione ([tex]y=k[/tex]) sia proprio l'indice di [tex]\varphi[/tex] in [tex]\varphi_k(y)[/tex]?
  • MindFlyerMindFlyer Posts: 436
    edited February 2015
    Ah ho capito, ci vuole una correzione. Cerco di mettere le cose in ordine.

    Definiamo

    [tex]
    \psi (x, y) =
    \left\{
    \begin{array}{ll}
    42 & \mbox{se } x = y \\
    \rm{indefinita} & \mbox{altrimenti.}
    \end{array}
    \right.
    [/tex]

    E' chiaro che [tex]\psi(x,y)[/tex] è calcolabile (parziale). Quindi, per il teorema di ricorsione di Kleene (anche detto secondo teorema di ricorsione di Kleene, che a sua volta si ottiene come corollario del primo applicando il teorema s-1-1), c'è un indice [tex]p[/tex] tale che [tex]\forall y, \varphi_p(y)=\psi(p,y)[/tex].

    Da qui si conclude come hai fatto tu: [tex]\varphi_p(p)=\psi(p,p)=42[/tex], e quindi [tex]p\in K[/tex]. D'altra parte, per il padding lemma esiste un indice [tex]q\neq p[/tex] tale che [tex]\varphi_p=\varphi_q[/tex], e tuttavia [tex]\varphi_q(q)=\varphi_p(q)=\psi(p,q)[/tex], che è indefinita. Quindi [tex]q\notin K[/tex], e dunque [tex]K[/tex] è un insieme di indici che non rispetta le funzioni.
  • caoscaos Posts: 9
    Controllando le mie note "cartacee" hai, ovviamente, ragione: ho commesso un typo in fase di digitalizzazione :)
    Siccome il secondo teorema di ricorsione di Kleene non l'abbiamo fatto a lezione, scrivo la mia dimostrazione (che al prof non ho dato e si è accontentato di una dimostrazione intuitiva), osservando che sono ovviamente sufficienti il primo teorema di ricorsione (quello di esistenza del punto fisso) e il teorema s-1-1 per ottenere tutto, infatti sia [tex]\psi(x, y)[/tex] definita come sopra:

    [tex] \varphi_{f(x)} (y) = \varphi_{s(p, x)} (y) = \varphi_p (x, y) = \psi(x,y) [/tex]

    dove, partendo dall'ultima uguaglianza a destra si è, prima, osservato che [tex]\psi[/tex] è calcolabile parziale (e che quindi ha un indice [tex]p[/tex]), poi che è possibile applicare il teorema s-1-1 e che la funzione che si ottiene dipende solo da [tex]x[/tex] e non da [tex]p[/tex] ([tex]p[/tex] è costante).
    Infine, osservando che esiste un punto fisso per [tex]f[/tex] (che è calcolabile totale ed iniettiva), sia esso [tex]k[/tex], otteniamo lo stessa sequenza di implicazioni di sopra :)
  • andreRondoandreRondo Posts: 25
    caos wrote: »
    Infine, osservando che esiste un punto fisso per [tex]f[/tex] (che è calcolabile totale ed iniettiva), sia esso [tex]k[/tex], otteniamo lo stessa sequenza di implicazioni di sopra :)

    Potete rispiegarmi gentilmente la conclusione?
  • MindFlyerMindFlyer Posts: 436
    caos ha solo detto che invece d'invocare il secondo teorema di Kleene lo si può dimostrare direttamente a partire dal primo teorema di Kleene e dal teorema s-1-1, come accennavo sopra e come spiega anche Wikipedia.

    Cioè ha ottenuto un k che fa esattamente le veci del p del mio messaggio precedente. Da lì poi la conclusione è come l'ho scritta sopra.
  • andreRondoandreRondo Posts: 25
    edited May 2017
    @MindFlyer a me Degano a ricevimento ha fatto vedere che si può dimostrare definendo una funzione psi_x (che è calcolabile e ha un indice p) = phi_p(z) = { 1 se z = 42 ; indefinita altrimenti } e poi usando il paddling lemma trovo y diverso da p t.c phi_y = phi_p (cioè calcolano la stessa cosa)
    A questo punto definisco phi_y(z) come fatto sopra (ipotizzando y=59) per phi_p(z) e ottengo che se y (abbiamo detto essere 59) è diverso da 42 allora y non appartiene a K. Quindi ho dimostrato che la definizione di i.i.r.f per K non vale.
  • MindFlyerMindFlyer Posts: 436
    Per far funzionare quel discorso vuoi anche che p sia in K (non solo che y non sia in K). Quindi vuoi che p=42, ma questo non è garantito.

    Il modo giusto di dire quella cosa è questo: voglio una funzione phi_p(z) = { 1 se z=p; indefinita altrimenti }. E per dimostrare che un tale p esiste uso di nuovo il teorema del punto fisso.

    Non penso che esistano approcci a questo problema svincolati da qualche teorema di punto fisso. Se Degano te l'ha "risolto" in altro modo, ha probabilmente sbagliato.
  • andreRondoandreRondo Posts: 25
    edited May 2017
    MindFlyer wrote: »
    Per far funzionare quel discorso vuoi anche che p sia in K (non solo che y non sia in K). Quindi vuoi che p=42, ma questo non è garantito.

    @MindFlyer In che senso non è garantito? Sicuramente hai ragione eh, ma volevo capire il perchè :)
  • MindFlyerMindFlyer Posts: 436
    Nel senso che di p sai solo che è l'indice di quella funzione. Molto probabilmente p non è 42. E per dire che è in K, vuoi che sia esattamente 42.
Sign In or Register to comment.