Nozioni di Calcolabilità
- Materiale didattico delle note, disponibili nella pagina del programma.
- Definizione Formale di Linguaggio. Appartenenza a Linguaggi come “Problemi Decisionali”, Problemi di Calcolo di una funzione come problema decisionale: per una opportuna funzione di codifica, se $$L_f = \{ cod(y) \;|\; y=f(x) \}$$ allora calcolare $$y=f(x)$$ è equivalente a decidere se data la coppia $$x,y \in N$$ si ha $$y \in L$$. Ad esempio:
- Se il problema è decidere se un intero è primo, avremo come input un intero cioè $$n \in N$$, e come linguaggio: PRIMES = $$ \subset N = \{ p \;|\; p $$ è primo $$\}$$.
- Se il problema è la soluzione di un sistema lineare, $$Ax = b$$, allora, esiste una codifica $$cod: (R^{\,m,n},R^n) \to \{0,1\}^*$$, tale che $$L_{A,b} = \{ cod(x) \;|\; Ax = b \}$$ è il linguaggio delle stringhe binarie che rappresentano le soluzioni del sistema. Il problema di trovare una soluzione $$x$$ del sistema, è equivalente al problema decisionale che data una stringa qualunque di {0,1} decide se essa appartiene a $$L_{A,b}$$.
- Algoritmi come sistemi di transizione terminanti, esempio di modello di calcolo (come sistema di transizione): Macchine di Turing.
- Esistenza della macchina di Turing Universale: programmi come “codifiche” di una Macchina di Turing, per il nastro della macchina universale.
- Macchina Universale come Interprete del formalismo delle macchine di Turing.
- Esistenza di problemi non calcolabili (secondo Turing): problema della fermata.
- Esistenza di problemi non calcolabili: dimostrazione per cardinalità, cioè, l’insieme di tutte le macchine di Turing è numerabile. Mentre le funzioni dai naturali ai naturali hanno la cardinalità del continuo.
Riferimenti:
- Dimostrazione diagonale.
- libro: Per una trattazione più approfondita si rimandano gli studenti a leggere il libro disponibile online. In particolare:
- Nella sezione 1.1.6 per la dimostrazione diagonale (ma tutto il primo Capitolo sarebbe un buon ripasso/studio di concetti di base). Sezione 1.3 per la definizione di linguaggio formale, fino a 1.3.3 (facoltativo se vi piace l’algebra). Sezione 1.3.4 per la cardinalità dei linguaggi.
- Alla fine del Capitolo 2, Definizione 2.10, 2.11.
- Quindi nel Capitolo 5, definizione ed esempi di macchina di Turing, in particolare l’esempio con il grafo che modella la funzione di transizione vi farà capire meglio come in pratica sono fatte le MdT.
- Sezione 5.1.2 computazione: Definizione 5.6 e 5.7, verificate che queste definizioni dicono sostanzialmente qualcosa di simile a quello che nelle note è definito un sistema di transizione e un algoritmo.
- Sezione 5.2 e 5.3 calcolabilità di funzioni.
- Per il problema della fermata è preferibile: un video molto simpatico.