PROBLEMI RISOLUBILI E COMPUTABILITÀ

Secondo la Tesi di Church-Turing, non esiste un formalismo “più potente” della Macchina di Turing, ossia capace di risolvere una classe più ampia di problemi.

Dunque...

PROBLEMI RISOLUBILI E COMPUTABILITÀ

se neanche la macchina di Turing riesce a risolvere un problema, quel problema non è risolubile!

Secondo la Tesi di Church-Turing, non esiste un formalismo “più potente” della Macchina di Turing, ossia capace di risolvere una classe più ampia di problemi.

Dunque...

QUALCHE DEFINIZIONE

PROBLEMA RISOLUBILE

• Un problema la cui soluzione può essere espressa da una Macchina di Turing o formalismo equivalente.

QUALCHE DEFINIZIONE

PROBLEMA RISOLUBILE

• Un problema la cui soluzione può essere espressa da una Macchina di Turing o formalismo equivalente.

La macchina di Turing calcola funzioni, quindi occorre un modo (semplice) per associare a un problema una funzione.

QUALCHE DEFINIZIONE

FUNZIONE CARATTERISTICA DI UN PROBLEMA• Dato un problema P, l’insieme X dei suoi dati di ingresso, l’insieme Y delle risposte corrette, si dice funzione caratteristica del proble- ma P la funzione:

fP: X Y

che associa a ogni dato d’ingresso la corri- spondente risposta corretta.

QUALCHE DEFINIZIONE

FUNZIONE CARATTERISTICA DI UN PROBLEMA• Perché questo artificio?

• Perché grazie a questa funzione, decidere se un problema è risolubile equivale a chiedersi se la funzione fP è computabile

QUALCHE DEFINIZIONE

FUNZIONE CARATTERISTICA DI UN PROBLEMA• Perché questo artificio?

• Perché grazie a questa funzione, decidere se un problema è risolubile equivale a chiedersi se la funzione fP è computabile

D’ora in poi parleremo quindi solo di funzioni computabili, sapendo che ciò equivale a parlare di problemi risolubili.

QUALCHE DEFINIZIONE

FUNZIONE COMPUTABILE

• Una funzione f: AB per la quale esiste una Macchina di Turing che

– data sul nastro una rappresentazione di xA

dopo un numero finito di passi – produce sul nastro una rappresentazione del

risultato f(x)B

QUALCHE DEFINIZIONE

Attenzione• Nel seguito considereremo solo funzioni

f: N N• questo non è limitativo perché

– ogni informazione è necessariamente finita, – quindi può essere codificata in una collezione

di numeri naturali– la quale collezione può essere a sua volta

espressa con un unico numero naturale mediante il procedimento di Gödel.

IL PROCEDIMENTO DI GÖDEL

“Data una collezione di numeri naturali, esprimerla con un unico numero naturale.”

Procedimento: • Siano N1, N2, … Nk i numeri naturali dati

• e siano P1, P2, … Pk i primi k numeri primi• Il nuovo numero R definito come

R ::= P1N1 · P2

N2 · … · PkNk

• rappresenta univocamente la collezione N1, … Nk grazie all’unicità della scomposi-zione in fattori primi.

COMPUTABILITÀ

È noto dall’analisi matematica che l’insieme F = { f: N N }

non è enumerabile (cardinalità del continuo)

COMPUTABILITÀ

È noto dall’analisi matematica che l’insieme F = { f: N N }

non è enumerabile (cardinalità del continuo)

Invece, l’insieme delle Macchine di Turing (e quindi delle funzioni computa-bili) è enumerabile.

Infatti, poiché il numero di simboli di ingresso, di uscita e di stati di una TM è finito, ogni Macchina di Turing può essere associata a un numero naturale con il procedimento di Gödel.

COMPUTABILITÀ

CONSEGUENZA:

la maggioranza delle funzioni NON può essere calcolata!!!

COMPUTABILITÀ

Però…a pensarci bene, le sole funzioni che davvero ci interessano sono quelle che possiamo definire

COMPUTABILITÀ

Però…a pensarci bene, le sole funzioni che davvero ci interessano sono quelle che possiamo definire

ma per definire qualcosa ci vuole un linguaggio…

COMPUTABILITÀ

Però…a pensarci bene, le sole funzioni che davvero ci interessano sono quelle che possiamo definire

ma per definire qualcosa ci vuole un linguaggio…

.. e quindi un alfabeto…

COMPUTABILITÀ

Però…a pensarci bene, le sole funzioni che davvero ci interessano sono quelle che possiamo definire

ma per definire qualcosa ci vuole un linguaggio…

.. e quindi un alfabeto… ..che è fatto di un numero finito di simboli!

COMPUTABILITÀ

CONSEGUENZA:

le funzioni che possiamo realmente defi-nire sono molte di meno, e costituiscono un insieme enumerabile!

COMPUTABILITÀ

CONSEGUENZA:

le funzioni che possiamo realmente defi-nire sono molte di meno, e costituiscono un insieme enumerabile!

Ergo, potremmo sperare che almeno queste si potessero calcolare tutte…

COMPUTABILITÀ

Ergo, potremmo sperare che almeno queste si potessero calcolare tutte…… E INVECE NO!!

CONSEGUENZA:

le funzioni che possiamo realmente defi-nire sono molte di meno, e costituiscono un insieme enumerabile!

FUNZIONI NON COMPUTABILI

È facile dimostrare che esistono funzioni definibili ma non computabili

e, quindi, problemi non risolubili.

FUNZIONI NON COMPUTABILI

È facile dimostrare che esistono funzioni definibili ma non computabili

e, quindi, problemi non risolubili.

ESEMPIO: Problema dell’ halt della macchina di Turing.

Dire se una data macchina di Turing T, con un generico ingresso X, si ferma oppure no.

FUNZIONI NON COMPUTABILI

Questo problema è perfettamente definito, ma non è computabile (nel caso generale).

FUNZIONI NON COMPUTABILI

Questo problema è perfettamente definito, ma non è computabile (nel caso generale).

Dimostrazione• Sia M l’insieme di tutte le Macchine di Turing• e X l’insieme di tutti i possibili ingressi.

Sia poi:– x X un generico dato di ingresso– m Muna generica Macchina di Turing.

FUNZIONI NON COMPUTABILI

La funzione caratteristica fH di questo problema può essere così definita:

fH (m,x) =

1, se m con ingresso x si ferma

0, se m con ingresso x non si ferma

FUNZIONI NON COMPUTABILI

La funzione caratteristica fH di questo problema può essere così definita:

fH (m,x) =

1, se m con ingresso x si ferma

0, se m con ingresso x non si ferma

Dimostreremo che questa funzione è definita ma non computabile, in quanto tentare di calcolarla conduce a un assurdo.

FUNZIONI NON COMPUTABILI

Se fH è computabile, deve esistere una Macchina di Turing TF capace di calcolarla.

FUNZIONI NON COMPUTABILI

Se fH è computabile, deve esistere una Macchina di Turing TF capace di calcolarla.

Definiamo allora una nuova funzione gH come segue:

dove n è il numero naturale che rappresenta una data Macchina di Turing (procedimento di Gödel).

gH (n) =

1, se fH (n,n) = 0

, se fH (n,n) = 1

FUNZIONI NON COMPUTABILI

In pratica, con un dato ingresso n:

g si ferma e risponde 1quando f non si ferma

g non si ferma e entra in un ciclo infinito quando invece f si ferma.

gH (n) =

1, se fH (n,n) = 0

, se fH (n,n) = 1

FUNZIONI NON COMPUTABILI

Come caso particolare, sia ora n = ng,

ossia prendiamo come ingresso proprio quel particolare numero che rappresenta la Macchina di Turing TG che calcola gH.

FUNZIONI NON COMPUTABILI

Come caso particolare, sia ora n = ng,

ossia prendiamo come ingresso proprio quel particolare numero che rappresenta la Macchina di Turing TG che calcola gH.

Questo significa dare come ingresso a TG, come caso particolare, la sua stessa descrizione.

FUNZIONI NON COMPUTABILI

Sostituendo si ottiene:

che è assurdo, in quanto afferma che:se g vale 1 (e quindi TG si ferma), f vale 0 (e quindi TG non si ferma)

se invece g è indefinita (cioè TG non si ferma), f vale 1 (perciò TG si ferma).

gH (ng) =

1, se fH (ng, ng) = 0

, se fH (ng, ng) = 1

FUNZIONI NON COMPUTABILI

Conclusione:

il problema di decidere se una data Macchina di Turing T, con un generico ingresso X, si ferma oppure no non è computabile:

È UN PROBLEMA INDECIDIBILE.