K non rispetta le funzioni

[InformateciBot]

Tratto da: Degano: Domande Orale.

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

[LorenzoBuonanno]

caos
la dimostrazione è stata un po' confusa.

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

per fare questo si prenda la funzione:
[math]
\varphi_k (y) = \psi (x, y) =
\left\{
\begin{array}{ll}
42 & \mbox{if } y = k \\
indefinita & \mbox{altrimenti}
\end{array}
\right.

dove [math]k è 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 [math]\psi, poi si applica il teorema s-1-1) .

A questo punto, per il padding lemma [math]\exists z.\varphi_k = \varphi_z e che diverge in [math]z per definizione di [math]\varphi_k. QED

MindFlyer
Solo una domanda: come fai a garantire che il [math]k che usi nella funzione ([math]y=k) sia proprio l'indice di [math]\varphi in [math]\varphi_k(y)?

Ah ho capito, ci vuole una correzione. Cerco di mettere le cose in ordine.

Definiamo

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


E' chiaro che [math]\psi(x,y) è 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 [math]p tale che [math]\forall y, \varphi_p(y)=\psi(p,y).

Da qui si conclude come hai fatto tu: [math]\varphi_p(p)=\psi(p,p)=42, e quindi [math]p\in K. D'altra parte, per il padding lemma esiste un indice [math]q\neq p tale che [math]\varphi_p=\varphi_q, e tuttavia [math]\varphi_q(q)=\varphi_p(q)=\psi(p,q), che è indefinita. Quindi [math]q\notin K, e dunque [math]K è un insieme di indici che non rispetta le funzioni.

caos
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 [math]\psi(x, y) definita come sopra:

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

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

andreRondo

Infine, osservando che esiste un punto fisso per [math]f (che è calcolabile totale ed iniettiva), sia esso [math]k, otteniamo lo stessa sequenza di implicazioni di sopra

Potete rispiegarmi gentilmente la conclusione?

MindFlyer
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.

andreRondo
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.

MindFlyer
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.

andreRondo
In che senso non è garantito? Sicuramente hai ragione eh, ma volevo capire il perché

MindFlyer
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.