Decidibilità

Potrebbe mancare qualcosa

linee guida di martinenghi

Decidibilità

• un problema di decisione è tale se ha due sole possibili risposte: sì o no (1 o 0)
• Una domanda/problema chiuso è sempre decidibile

Semidecidibilità

• se c'è un algoritmo che dice di sì se la risposta è sì
• può andare in loop se la risposta è no

Insiemi ricorsivi

un insieme S è ricorsivo o decidibile se la sua funzione caratteristica

$c_s(x)$ è computabile.

$$c_s(x)=\{\begin{array}{ll}1& x\in S\\ 0& x\notin S\end{array}$$

Insiemi ricorsivamente enumerabili

S è RE o semidecidibile se e solo se:

• $S=\mathrm{\varnothing }$
• S è l'immagine di una funzione
  $g_S$ totale e computabile
  • $$S=I_{g_S}=\{x|x=g_s(y),y\in \mathbb{N}\}⟹S=\{g_s(0),g_s(1),g_s(2),...\}$$

L'equazione qui sopra giustifica il termine enumerazione. la semidecibilità deriva dal fatto che enumerando gli elementi di S, prima o poi si trova x e si riceve una risposta positiva. Per il caso

$x\notin S$ non si ha una risposta in tempo finito.

Teorema sulle funzioni totali

Per ogni

$S$, se

1. $i\in S$ implica che
   $f_i$ sia totale
2. per ogni funzione
   $f$ totale e computabile, esiste un
   $i\in S$ tale che
   $f=f_i$

allora S non è ricorsivamente enumerabile

Un caso specifico è

$S_{tot}=\{x|f_x\text{ è totale }\}$, che soddisfa le ipotesi del teorema e quindi non è ricorsivamente enumerabile.

Condizione necessaria e sufficiente per la RE

Un insieme S è ricorsivamente enumerabile se e solo se

1. $S=D_h$ per qualche funzioni parziale computabile
   $h$; ossia
   $S=\{x|h(x)\ne \mathrm{\perp }\}$

2. $S=I_g$ per qualche funzione parziale computabile
   $g$

Teorema 1/2 + 1/2 = 1

1. $S$ ricorsivo
   $⟹$
   $S$ ricorsivamente enumerabile
2. $S$ ricorsivo
   $⟺$ sia
   $S$ che
   $S^C$ sono RE (
   $S^C=\mathbb{N}-S$)

Teorema di Rice

sia

$F$ un insieme di funzioni computabili. L'insieme

$S$ degli indici delle TM che calcolano le funzioni di

$F$,

$S=\{x|f_x\in F\}$ è decidibile se e solo se

• $F=\mathrm{\varnothing }$
• F è l'insieme di tutte le funzioni computabili

Problemi risolvibili e irrisolvibili relativi ai linguaggi

Macchine di Turing

• non si può decidere se
  $x\in L(M)$ per una qualsiasi MT M ed una qualsiasi stringa
  $x\in V_T^{\ast }$
• Il problema di stabilire se un dato linguaggio è vuoto è indecidibile, se si considerano i linguaggi accettati dalle MT
  La dimostrazione segue dall'halting problem

Automi a stati finiti

• I linguaggi accettati dagli AF sono ricorsivi, cioè il problema dell'appartenenza è decidibile.

  Per ogni stringa

  $x$ e per ogni AF A è banale decidere se
  ${\delta }^{\ast }(q,x)\in F$. Basta far funzionare A fino a che
  $\delta$ non è più definita (caso 1) oppure la lettura di
  $x$ viene completata(caso 2).

• E' decidibile stabilire se, per un dato AF A, L(A) =

  $\mathrm{\varnothing }$

Automi a pila

• I linguaggi accettati dagli AP sono ricorsivi