Halting theorem

Questo è un problema fondamentale, che abbiamo trattato anche in Fondamenti teorica#Halting problem, ma qui lo ritrattiamo, perché così lo rifacciamo per bene. In parte è stato trattato anche al corso di Logica.

Enunciato Halting theorem

Questo è molto simile a quanto presente sul (Sipser 2012). Ossia consideriamo il linguaggio

$$HALT=\left\{⟨x,y⟩\in {\Sigma }^{\ast }\times {\Sigma }^{\ast }:x=code(M),M\text{ si ferma su }x\right\}$$

Dimostrazione Halting theorem

La parte del sì è facile perché basta eseguirlo e vedere che si ferma (quindi abbiamo una La macchina di Turing#La macchina di Turing universale. Se si ferma appartiene al linguaggio, altrimenti è la parte in cui diverge.

Dimostrazione non decidibilità Supponiamo sia decidibile e dimostriamo l'assurdo. Se esiste una macchina $f$ tale per cui decida quel linguaggio,

$$\{\begin{array}{l}f(g,y)=1,g(y)\downarrow \\ \\ f(g,y)=0,g(y)\uparrow \end{array}$$

allora possiamo usare questa macchina per costruire un $h$ tale che per cui

$$\{\begin{array}{l}h(g)=1,f(g,g)=0\\ \\ h(g)=\uparrow ,f(g,g)=1\end{array}$$

Allora la computazione della funzione $h(h)$ genera un assurdo.

Il motivo è che $h(h)=1⟺f(h,h)=0⟺h(h)=\uparrow$ Questa cosa dovrebbe essere riscritta in modo $code$ per essere comprensibile da macchine di Turing.

Opposto di Halting theorem

Ossia vogliamo riconoscere il linguaggio

$$HAL{T}^{-}=\left\{⟨x,y⟩:x\ne code(M)\cup x=code(M)\cap M\text{ non si ferma su }x\right\}$$

Si può dimostrare che questo problema non è nemmeno riconoscibile da nessuno!

Dimostrazione complemento di halting theorem

Si ragiona anche qui per assurdo, se fosse riconoscibile, avremmo che Halting theorem principale sarebbe riconoscibile.

Mapping reducibility

Definizione mapping reducibility

Un linguaggio $L^{\prime }$ è riducibile a un altro linguaggio $L$ se esiste una funzione computabile totale $f:{\Sigma }^{\ast }\to {\Sigma }^{\ast }$ tale che valga

$$x\in L^{\prime }⟺f(x)\in L$$

E si scrive che $L^{\prime }\le L$ Ossia posso mappare qualunque parola in $L^{\prime }$ in una stringa in $L$. È molto importante che sia computabile, perché è un modo di dire che non stiamo barando nella dimostrazione, e mi appoggio soltanto all'espressività dei due linguaggi.

Proprietà di decidibilità basilari

• Se $L$ è decidibile, allora $\forall L^{\prime }:L^{\prime }\le L$ è decidibile.
• Se $L^{\prime }$ è indecidibile allora lo è anche $\forall L:L^{\prime }\le L$ perché altrimenti si avrebbe un assurdo
• Se $L$ è decidibile e $L^{\prime }$ no allora $L^{\prime }\nleqq L$ altrimenti assurdo per il primo punto.

Ogni linguaggio decidibile è semplice

Ossia se $L^{\prime }$ è decidibile allora per ogni $L$ tale che $L\ne \varnothing$ e $L\ne {\Sigma }^{\ast }$, ossia è un linguaggio finito, si ha che

$$L^{\prime }\le L$$

In altre parole, possiamo dire che i linguaggi decidibili sono mapping reducibili a qualunque altro linguaggio non banale, quindi sono le più semplici esistenti in altre parole.

Dimostrazione: Dato che $L^{\prime }$ è decidibile, esiste $g(x),\forall x\in {\Sigma }^{\ast }$ tale che decide se $x$ appartiene o meno a quel linguaggio. Dato che $L$ è finito, esiste un $\omega$ che non appartiene e un altro $v$ che appartiene. Allora costruisco la funzione $f$ così:

1. Runno $g$, se appartiene, mappo a $v$
2. Se non appartiene mappo a $\omega$. Ez.

Indecidibilità su nastro vuoto

NOTA: in ogni caso devo vedere se il codice della macchina è valido.

Definendo il linguaggio

$$ETH=\left\{x\in {\Sigma }^{\ast }:x=code(\mathcal{M})\text{ e }\mathcal{M}\text{ si ferma su }\epsilon \right\}$$

Per dimostrare ciò basta dimostrare che $HALT\le ETH$ Ossia dobbiamo costruire una funzione che mappa ogni stringa di $HALT$ in una di $ETH$. Questo è molto semplice, solo definire qualche dettaglio (non banale)

Indicibilità ogni input

Definiamo il linguaggio

$$FL=\left\{x\in {\Sigma }^{\ast }:x=code(\mathcal{M})\text{ e }\mathcal{M}\text{ ferma su ogni input}\right\}$$

Anche questo si può dimostrare in maniera simile al precedente, con una mapping reduction. Questo è anche più semplice: Se $\mathcal{M}$ non è il codice di nessuna macchina ritorno quello. Altrimenti: Per ogni input $⟨\mathcal{M},x⟩$ costruisco la seguente macchina

1. La macchina nuova prende un input $y$, la ignora per il momento, e simula $⟨\mathcal{M},x⟩$.
2. Se termina (e quindi appartiene a $HALT$) allora termino anche io ignorando l'input.
3. Altrimenti divergo, e quindi non appartengo. Questa nuova macchina è bona. Quindi funziona l'indicibilità

Quindi Se $\mathcal{M}$ non è codice ho già la risposta. Altrimenti

$$⟨y,x⟩\in HALT⟺\text{ macchina si ferma su }x⟺{\mathcal{M}}_{\mathcal{M},x}\text{ si ferma sempre}⟺f(⟨y,x⟩)=code({\mathcal{M}}_{\mathcal{M},x})\in FL$$

Equivalence problem decidability

$$EQ=\left\{⟨y,x⟩\in {\Sigma }^{\ast }\times {\Sigma }^{\ast }:x=code(\mathcal{M}),y=code({\mathcal{M}}^{\prime })\text{ e }\mathcal{M},{\mathcal{M}}^{\prime }\text{ hanno la stessa funzione parziale}\right\}$$

Anche in questo caso proviamo a ridurci al caso $FL$. Sempre come prima, per input $⟨\mathcal{M}⟩$ mi costruisco questa macchina La correttezza di questo è un po' più fine, però è giusto. Vedere qui.

Equivalence problem recognizability

Il linguaggio del problema di equivalenza non è nemmeno riconoscibile. Per fare ciò devo ridurre $HAL{T}^{-}$ a questo EQ. Dimostro la riduzione $HALT⟹E{Q}^{-}$

Nota sulla gerarchia

Cosa curiosa è che $HALT$ è il suo opposto non sono comparabili. Mentre ci aspetteremmo che HALT sia più semplice. Una altra cosa curiosa è che EQ non è riconoscibile, e nemmeno il suo opposto lo è. Quindi EQ non è nemmeno semi-decidibile.

Turing riducibilità

Definizione di oracolo

Dato un linguaggio $L$ e una stringa $x$, l'oracolo mi dice in tempo finito se $x\in L$.

Definizione Turing-riducibilità

Dato un $L^{\prime }$ , questo è Turing riducibile a $L$, quindi $L^{\prime }{\le }_{TM}L$, se dato un oracolo per $L$ possiamo decidere $L^{\prime }$

Mapping reducibility => Turing-riducibilità

Possiamo dimostrare in modo semplice che con Turing-riducibilità $HALT$ è riducibile a $HAL{T}^{-}$. Senza problemi. Mentre non posso farlo con Mapping reducibility. Questo mi dice che Turing riducibilità è una proprietà più forte della mapping reducibility, anche se non è propriamente una dimostrazione di questa proprietà.

Baker-Gill-Soloway (1975)

Questa sezione è solamente una nota filosofica, ma di poco conto per l'esame.

Prendiamo una macchina di Turing con oracolo, ossia possiamo chiedere se una stringa è parte dell'oracolo in tempo costante (come se fosse un dizionario con accesso diretto).

Esistono oracoli $O,O^{\prime }$ tali per cui $P=NP$ con una macchina di Turing che usi il primo oracolo, e anche che $P\ne NP$ usando il secondo oracolo. Questo teorema dice che la tecnica di diagonalizzazione di Cantor non può essere usata per risolvere NP = P. Questo dato è inutile per la maggior parte delle cose attuali credo. Oppure TM non sono buoni per risolvere questo problema (ha fatto nascere la branca con i circuiti booleani, non fatta qui).

References

[1] Sipser “Introduction to the Theory of Computation” Cengage Learning 2012