Decidibilità
===

::: warning
Potrebbe mancare qualcosa
:::

[linee guida di martinenghi](https://martinenghi.faculty.polimi.it/courses/api/Decidib.pdf)

## 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{cases} 1 & x \in S \\ 0 & x \notin S \end{cases}$$

## Insiemi ricorsivamente enumerabili
S è RE o semidecidibile se e solo se:
- $S = \emptyset$
- S è l'immagine di una funzione $g_S$ totale e computabile
- $$S = I_{g_S} = \{x | x = g_s(y), y \in \mathbb{N}\} \implies 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) \neq \bot \}$

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

## Teorema 1/2 + 1/2 = 1
1. $S$ ricorsivo $\implies$ $S$ ricorsivamente enumerabile
2. $S$ ricorsivo $\iff$ 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 = \emptyset$
- 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^*$
- 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^*(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) = $\emptyset$

### Automi a pila
- I linguaggi accettati dagli AP sono *ricorsivi*