Teoria della computazione

Note

Formalizziamo un calcolo come un problema per capire se , o di calcolare . Queste due formulazioni sono definite come:

  • Sapendo , definisco e .
  • Avendo una MT che risolve , definisco , poi per tutte le possibili stringhe chiedo a se . Se è definita, prima o poi la macchina risponderà positivamente.
Tesi di Church-Turing

Nel 1933, Gödel e Herbrand individuano un insieme di funzioni sugli interi che appaiono definire ciò che può essere calcolato manualmente.

Nel 1936, Alonso Church definisce un altro sistema basato su funzioni ricorsive, il -calcolo, anch'esso in grado di descrivere tutte le funzioni "calcolabili operativamente".
Sempre nel 1936, Turing definisce quella che è la MT a nastro singolo tentando di fornire un formalismo per rappresentare tutto ciò che è "effettivamente calcolabile".
Kleene, Turing e Church dimostrano che i tre formalismo citati sono equivalenti, cioè definiscono lo stesso insieme di problemi.

Di conseguenza, tutti i problemi calcolabili operativamente sono descritti da una MT.

Turing definisce computable una funzione che può essere calcolata da una procedura eseguita da una macchina, senza necessità di intervento esterno, e che dà risultato in tempo finito.

Enumerazione algoritmica

Note

Definiamo la enumerazione di un insieme, cioè la corrispondenza biunivoca tra i suoi elementi e quelli di , è quindi una mappa: . Diciamo che è effectively computable se esiste un algoritmo (o una MT) che la calcola.

Dimostrazione

Consideriamo le MT a nastro singolo, con alfabeto ␢ e . Osserviamo quali sono le possibili di queste MT. È possibile contare il numero di possibili e sapere quante MT a strati e lettere di alfabeto esistono.

In generale ho funzioni . Facendo i conti con abbiamo che, con e ci sono possibili funzioni per MT a stati e lettere.

Scegliendo un ordine arbitrario per l'insieme , e allo stesso modo ordino le MT. Numerando gli insiemi uno dopo l'altro ottengo un'enumerazione .

Si ha che è algoritmica, e quindi è possibile scrivere un programma che, data mi fornisce il suo numero.

Definiamo è detto numero di Gödel di , e è detta gödelizzazione.
Definiamo inoltre come la funzione calcolata dall'-esima MT. Si ha quindi che se e solo se non si ferma quando riceve in ingresso .

Macchina di Turing universale

Note

Si ha che esiste almeno una Macchina di Turing Universale (MTU) per ogni calcolo, cioè una MT che calcola .

La MTU non sembra essere dello stesso tipo delle altre , questo perché è funzione di una variabile, mentre di due, tuttavia è possibile provare il contrario ricordando che è enumerabile. È quindi possibile riformulare tale per cui . La MTU lascia sul nastro termina la computazione su .

Definizione e risoluzione dei problemi

Note

Si ha che , e quindi che: Sappiamo anche che . Quindi esistono almeno funzioni, tuttavia esistono solo MT, e quindi gran parte delle funzioni non è risolvibile algoritmicamente.

Si ha inoltre che un problema definito su un linguaggio, a sua volta è definito sull'alfabeto , che a sua volta è sottoinsieme di , che è numerabile. Sappiamo quindi che:

Data una funzione , con finiti o effettivamente numerabili, essa si dice computabile se esiste una MT che la calcola, e quindi .

Halting problem

Consideriamo la funzione: Si ha che non esiste una MT che calcola , e quindi, nella pratica seguono conseguenze come:

  • Inesistenza di un compilatore che possa dirci che il nostro programma andrà in loop su un dato input
  • Inesistenza dell'antivirus definitivo che sia in grado di capire a priori se un programma è malevolo
  • Impossibilità di "creare un programma per tentativi ciechi" controllando solo a posteriori che sia quello corretto
Dimostrazione

Supponiamo che esista, e sia calcolabile una: Allora è calcolabile anche un: Se è calcolabile, esiste una tale che . A questo punto calcoliamo .
Se , dato che si ha che . Tuttavia per la definizione di abbiamo che , ma quindi per definizione di , che è assurdo.
Se , dato che si ha che . Tuttavia per la definizione di abbiamo che , ma quindi per definizione di , che è assurdo.

Intuitivamente, se ho un programma in grado di dire se un generico altro programma termina, posso usarlo per costruire un altro programma che fa sempre sbagliare nel determinare se quest'ultimo termina.

Teorema di Cantor

Si ha che:

Dimostrazione

Dimostriamo che esiste una iniettiva, ma non suriettiva. Esiste una iniettiva, per esempio mappa in . Non esiste una suriettiva, consideriamo . Supponiamo per assurdo, che esista una suriettiva, e quindi dato che per costruzione: Che è assurdo.

Nel contesto della calcolabilità: posso sapere che esiste una MT che risolve il problema, anche se non sono in grado di dire quale sia tra le possibili. Supponiamo di avere una funzione di cui non siamo in grado di trovare un algoritmo che la calcola. Un modo di dimostrare che è calcolabile senza eseguire un algoritmo è:

  • mostrare che appartiene ad un insieme di funzioni
  • mostrare che per ogni elemento di esiste una MT che lo calcola

Computazione di problemi binari

Note

Dato un problema con input l'istanza del problema, e come output la scelta binaria "si" o "no", diciamo che:

  • è decidibile se esiste una MT che avendo in input la codifica dell'istanza stampa la risposta corretta del problema. Inoltre il problema è deciso se la macchina è realizzabile. (basta una descrizione ad alto livello)
  • è semidecidibile se esiste una MT che se la risposta è "si" termina sempre e stampa "si".
  • è indecidibile altrimenti.

Il complementare del problema scambia le risposte "si" e "no".

Nei casi in cui non sono presenti variabili in input in un problema , il problema è decidibile.

Decidibilità e semidecidibilità

Note

Considerando un problema con risposta binaria, quindi quelli che richiedono di calcolare una certa , la interpretiamo come funzione caratteristica di : Definiamo come ricorsivo o decidibile se e solo se la sua funzione caratteristica è calcolabile.
Definiamo come ricorsivamente enumerabile (RE) o semidecidibile se e solo se:

  • è l'insieme vuoto
  • è l'immagine di una funzione totale e calcolabile
  • cioè da cui il nome ricorsivamente enumerabile

Analizzando l'insieme direttamente, se , è ricorsivo se esiste una MT tale che, ricevendo in input , termina sempre e stampa "si" se , "no" se .

Se esiste una MT che termina e stampa "si" se , allora è ricorsivamente enumerabile (RE).

Dimostrazione

Se è vuoto, allora è RE per definizione. Assumendo , e costruendo una funzione totale e calcolabile di cui è immagine, , definiamo come: Si ha che è calcolabile, totale e , e quindi è RE.

Proprietà della della decidibilità

Si ha che àà. Si ha inoltre che è ricorsivo se e solo se sono ricorsivamente enumerabili sia che il suo complemento . Si ha quindi che gli insiemi decidibili sono chiusi rispetto al complemento.

Tip

È equivalente dire che:

  • è ricorsivamente enumerabile
  • è il dominio di una funzione parziale calcolabile
  • è il codominio di una funzione parziale calcolabile

Il termine semidecidibile deriva dal fatto che:

  • Se , enumerando gli elementi di prima o poi trovo un valore di tale per cui
  • se , non sono mai certo di poter rispondere " non appartiene a " enumerando, potrei non aver ancora trovato tale per cui

Consideriamo , cioè il dominio della funzione che è calcolabile e parziale. Abbiamo quindi che è RE, e la sua indicatrice: Non è calcolabile, e dunque non è decidibile.

Si ha quindi che:

Definizione delle calcolabili e totali

Note

Dato un insieme per cui, se , allora è calcolabile e totale, e se è totale e calcolabile allora , allora non è ricorsivamente enumerabile

Dimostrazione

Ipotizziamo che calcolabile. Definiamo . Ho che . è calcolabile, ma diversa da tutte le calcolabili, che è assurdo.

Non è possibile, con un formalismo RE, definire l'insieme di tutte e sole le calcolabili totali. Non posso in nessun modo descrivere com'è fatto l'insieme di tutti e soli i programmi che terminano sempre.

Teorema di Kleene

Note

Sia una funzione totale e calcolabile. È sempre possibile trovare una tale che . La funzione è detta punto fisso di .

Dimostrazione

Dato un parametro definiamo una MT che calcola sull'ingresso :

  • Calcola
  • Se e quando il calcolo precedente termina, calcola

La definizione è effettiva, quindi esiste una MT che la calcola. Costruita , ne calcoliamo il suo numero di G̈ödel. Chiamiamo la funzione che costruisce e calcola il numero di Gödel. Abbiamo quindi: Sappiamo che, data la totale e calcolabile di cui sopra, e data una totale e calcolabile, anche la composizione lo è. Chiamiamo il numero di Gödel di . Costruiamo ora , cioè come prima, per il caso , ottenendo: Ricordando che è totale e calcolabile, otteniamo che . Sostituendo con al secondo membro abbiamo . Quindi è il punto fisso di .

Teorema di Rice

Note

Sia l'insieme di funzioni computabili e l'insieme degli indici delle MT che calcolano le funzioni di , si ha che è decidibile se e solo se o è l'insieme di tutte le funzioni computabili.

Dimostrazione

Supponiamo, per assurdo, che sia decidibile, e sia non vuoto e diverso dall'insieme di tutte le funzioni computabili. Consideriamo: Essa è calcolabile per l'ipotesi appena fatta. Quindi possiamo calcolare:

  • Il più piccolo tale che , cioè
  • Il più piccolo tale che , cioè

Per quanto detto, è a sua volta calcolabile e totale. Applicando il teorema di Kleene alla funzione totale e calcolabile otteniamo che esiste un punto fisso tale per cui . Arriviamo alla contraddizione, assumendo:

  • : per definizione di abbiamo che , ma da quanto appena detto per il teorema di Kleene, da cui, per come definito , , che è assurdo.
  • : per definizione di abbiamo che , ma da quanto appena detto per il teorema di Kleene da cui, per come definito , , che è assurdo.

Un altro enunciato per il teorema di Rice è il seguente:
Sia una proprietà semantica non banale dei linguaggi accettati da MT. Allora il linguaggio: àÈ indecidibile.

Non banale significa che esiste almeno una macchina tale che ha , e una tale che non ha .

Semantica significa che riguarda il linguaggio accettato , cioè l'insieme delle stringhe accettate, non la struttura del codice della macchina.

Tip

Dire se un generico problema è (semi)decidibile o meno è un problema indecidibile. Tuttavia il teorema di Rice ci consente di mostrare che un teorema non è decidibile.

Come conseguenze del teorema di rice possiamo dire che, non possiamo decidere se una MT:

  • Accetta .
  • Accetta un linguaggio finito.
  • Accetta un linguaggio regolare.

Tecnica di riduzione

Note

Siano e (sottoinsiemi o codificabili in ) due problemi di decisione, cioè due insiemi di cui si vorrebbe risolvere il problema dell'appartenenza. Allora una funzione , tale che è totale (definita su tutto il dominio) e computabile, e con , , allora è una riduzione da a .

Se è una riduzione allora:

  • Se è ricorsivo allora lo è anche
  • Se non è ricorsivo allora non lo è neanche