• Non ci sono risultati.

Come affrontare un problema di decidibilità/computabilità

N/A
N/A
Protected

Academic year: 2021

Condividi "Come affrontare un problema di decidibilità/computabilità"

Copied!
6
0
0

Testo completo

(1)

Come affrontare un problema di decidibilità/computabilità

Linee guida

(2)

Casi immediati

• C’è una domanda di tipo booleano la cui risposta non dipende da alcun parametro esterno?

Si tratta di una domanda chiusa --> problema decidibile

(anche se non sappiamo rispondere alla domanda!)

• La funzione in questione consiste di un numero finito di casi, tutti singolarmente decidibili/calcolabili?

La funzione è calcolabile

(3)

Caso del programmatore

• Sapremmo scrivere un programma (in C, Java, …) che risolve il problema dato?

La funzione è calcolabile

• NB: questo vuol dire che so scrivere un programma che, per ogni

possibile ingresso, è in grado di calcolare il valore corretto dell’uscita

• NB: se, per qualche valore dell’ingresso, l’uscita non è definita, basta far entrare il programma in un loop infinito

(4)

Riduzioni

• Conosco un problema indecidibile che è un caso particolare del mio problema

--> il mio problema è indecidibile

• Conosco un problema decidibile di cui il mio problema è un caso particolare

--> il mio problema è decidibile

(5)

Teorema di Rice (funzioni)

• Devo verificare se un programma/TM/algoritmo

ha una data proprietà (relativa alla funzione da esso calcolata)?

calcola una funzione tra quelle di un insieme dato?

• In questi casi posso utilizzare il teorema di Rice

• Se l’insieme di funzioni identificato (cioè quelle che hanno la data proprietà o che appartengono al dato insieme) è non banale, il

problema è indecidibile, altrimenti è decidibile

• Un insieme di funzioni è banale se

È vuoto, oppure

È l’insieme di tutte le funzioni computabili

(6)

Ricorsività di un insieme S di numeri naturali

S è finito:

S è certamente ricorsivo

S è infinito:

La funzione caratteristica di S (cioè quella che determina se un generico elemento appartiene a S) è computabile

--> S è ricorsivo

(altrimenti S non è ricorsivo)

S può essere espresso come insieme di indici di TM con una proprietà comune relativa alla funzione che calcolano

Posso usare il teorema di Rice

S può essere espresso come insieme di indici di TM con una proprietà comune che non riguarda però la funzione che calcolano

Questo significa che posso trovare due TM, una con la proprietà e una senza, che calcolano la stessa funzione

Non posso usare il teorema di Rice

Riferimenti

Documenti correlati

[r]

[r]

Tutoraggio Analisi

Se tale problema di PL ha regione ammissibile vuota, che cosa possiamo dire per il problema di PLI..

Si dimostri che in tal caso ogni incremento del termine noto di un vincolo che lasci invariata la base ottima non pu´ o diminuire il valore ottimo del problema (3 punti).. un

Quindi, per il teorema di esistenza e unicit`a locale, il problema di Cauchy dato ammette esattamente una soluzione.. (b) Le soluzioni stazionarie si ottengono risolvendo

Determinare il tipo di convergenza della serie e scrivere l’identit` a

Corso di Laurea in Scienze Fisiche Prova finale del