Completamenti calcolabili di funzioni incalcolabili

Calcolabilità, modelli di calcolo, complessità, linguaggi formali.

Completamenti calcolabili di funzioni incalcolabili

Messaggioda Nihilus il mar 20 gen 2015, 17:25

Data una funzione parziale $\phi$, diciamo che essa ha un completamento calcolabile sse esiste una funzione calcolabile totale $f$ tale che $(\forall x \in \mathbb N ) [\phi(x) \downarrow \; \Rightarrow f(x) = \phi(x)]$.


Esibire una funzione parziale non calcolabile che ammette un completamento calcolabile.
Cadi e non c'è nulla cui aggrapparti; cadi e la libertà è non trattenersi. Che perfezione...
Avatar utente
Nihilus
 
Messaggi: 102
Iscritto il: sab 22 set 2012, 14:05

Messaggioda fry il gio 22 gen 2015, 19:45

Nihilus ha scritto:Esibire una funzione parziale non calcolabile che ammette un completamento calcolabile.

Tra i tanti modelli equivalenti del concetto di computabilità, scegliamo di intendere ogni funzione calcolabile $f : \mathbb{N} \to \mathbb{N}$ come un programma che preso in ingresso un naturale $x \in \mathbb{N}$, o termina e restituisce un naturale $y \in \mathbb{N}$, in tal caso scriviamo $f(x)\! \downarrow$ e $f(x) = y$, oppure non termina, in tal caso scriviamo $f(x) \!\uparrow$. Inoltre osserviamo che esiste una biezione calcolabile, con inversa calcolabile, tra l'insieme delle coppie funzione calcolabile-ingresso $(f,x)$ e l'insieme dei naturali $\mathbb{N}$, pertanto identifichiamo questi due insiemi e diciamo che $c \in \mathbb{N}$ termina, risp. non termina, se la biezione associa $c$ ad una coppia $(f,x)$ tale che $f(x) \!\downarrow$, risp. $f(x) \!\uparrow$.

È ben noto che la funzione
$$H : \mathbb{N} \to \mathbb{N} : x \mapsto \begin{cases} 1 & \text{ se } x \text{ termina} \\ 0 & \text{ se } x \text{ non termina} \end{cases}$$
non è calcolabile. Definiamo la funzione parziale $\phi := H \upharpoonright H^{-1}[0]$, ovvero $\phi(x) = 0$ per ogni $x \in \mathbb{N}$ tale che $H(x) = 0$ e $\phi$ non è definita per ogni altro argomento. Chiaramente la funzione costante $\mathbb{N} \to \mathbb{N} : x \mapsto 0$ è un completamento calcolabile di $\phi$. Proviamo che $\phi$ non è calcolabile. Se per assurdo $\phi$ fosse calcolabile allora per ogni $x \in \mathbb{N}$ potremmo calcolare $H(x)$ come segue: eseguiamo in parallelo i programmi $\phi(x)$ e $x$, necessariamente uno dei due deve terminare, se termina $\phi(x)$ allora $H(x) = 0$, se termina $x$ allora $H(x) = 1$. Ma $H$ non è calcolabile, assurdo.
"Hey. They laughed at Louis Armstrong when he said he was gonna go to the moon. Now he's up there, laughing at them."
Avatar utente
fry
 
Messaggi: 1122
Iscritto il: ven 20 giu 2008, 19:06

Re: Completamenti calcolabili di funzioni incalcolabili

Messaggioda Nihilus il dom 1 feb 2015, 12:56

Giusto!
Sostanzialmente è la stessa soluzione che ho pensato io, ma per dare un'idea di come può venire in mente la scrivo. Ho sempre trovato molto istruttive le dimostrazioni che partono dalla conclusione e risalgono passo passo alle premesse.

Cerchiamo di trovare la funzione "più facile" che soddisfi i requisiti: le funzioni calcolabili più facili sono le costanti quindi è ragionevole condensare l'incalcolabilità della funzione parziale nel suo dominio, cercandola costante là dove è definita.

Un teorema ci assicura che i domini delle funzioni parziali ricorsive sono tutti e soli gli insiemi ricorsivamente enumerabili. Quindi non ci serve altro che trovare l'esempio più facile di insieme non ricorsivamente enumerabile.

Il cosiddetto "teorema di complementazione" stabilisce un legame tra insiemi ricorsivi e ricorsivamente enumerabili: $A \subseteq \mathbb N$ è ricorsivo se e solo se $A$ ed il suo complementare $\mathbb N \setminus A $ sono ricorsivamente enumerabili.
Quindi basta trovare l'esempio più facile di insieme ricorsivamente enumerabile non ricorsivo e considerare il complementare.

È ben noto che l'insieme più facile che soddisfa questi requisiti è il cosiddetto "halting set" $K=\{ \langle i, x \rangle \, | \, \mbox{il programma } i \mbox{ si arresta sull'input } x \}$, ergo $\mathbb N \setminus K$ è l'insieme cercato.
Cadi e non c'è nulla cui aggrapparti; cadi e la libertà è non trattenersi. Che perfezione...
Avatar utente
Nihilus
 
Messaggi: 102
Iscritto il: sab 22 set 2012, 14:05


Torna a Fondamenti dell'Informatica

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite

cron