Problemi indecidibili

Obiettivo: presentare un problema irrisolvibile

Problema

• input: MdT $M$, stringa $w$
• domanda: $M$ accetta $w$?

Linguaggio corrispondente $A_{TM}= \{ \langle M,w \rangle | M \text{ è una MdT che accetta la parola } w\}$

Teorema

Il linguaggio $A_{TM}= \{ \langle M,w \rangle | M \text{ è una MdT che accetta la parola } w\}$ non è decidibile

Cardinalità

Due insiemi hanno la stessa cardinalità se è possibile stabilire una corrispondenza tra i loro elementi

Metodo della diagonalizzazione

Due insiemi finiti hanno la stessa cardinalità se gli elementi dell’uno possono essere messi in corrispondenza uno a uno con quelli dell’altro → esteso anche agli insiemi infiniti

Funzioni

Una funzione $f: X \to Y$ è una relazione input-output

• $X$ è l’insieme dei possibili input (dominio)
• $Y$ è l’insieme dei possibili output (codominio)

Per ogni input $x \in X$ esiste un solo output $y = f(x) \in Y$

$f:X \to Y$ è iniettiva se $\forall x, x' \in X$ $x \neq x' \Rightarrow f(x) \neq f(x')$

$f: X\to Y$ è suriettiva se $\forall y \in Y$ si ha $y = f(x)$ per qualche $x \in X$

Una funzione $f: X \to Y$ è una funzione biettiva di $X$ su $Y$ se $f$ è iniettiva e suriettiva