• 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
Mostra di più ( pagine)

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

In secondo luogo si ponga perciò l’at- tenzione sulla necessità di valutare tempestivamente i comportamenti da- toriali che appaiano inadeguati, ostili, vessatori o

Il problema si pu` o risolvere anche in un altro modo: a grandi linee: si trasforma l’insieme dato con operazioni che lasciano invariato lo spazio generato e in modo che dal

In quanti modi si possono colorare di rosso e di azzurro i quadretti di una riga di n quadretti in modo che ci siano esattamente c linee di confine fra una zona rossa e una

Ogni insieme può essere considerato un sottoinsieme di se stesso e l’insieme vuoto può essere ritenuto un sottoinsieme di qualsiasi insieme: per questo motivo, dato un insieme

Per me, poi non so voi, è difficile trovare un libro che non mi an- noi dopo le prime dieci pagine, ma se invece mi interessa mi sento un personaggio della sto- ria e quando

The archaeological site of Hierapolis (Denizli, Turkey), one of the great Hellenistic, Roman and Byzantine cities of southwestern Turkey, protected by UNESCO since 1988, was built

L’obiettivo del progetto è quello di fornire degli strumenti utili per la gestione dei clienti, in particolare nella gestione delle offerte fatte al cliente, con la

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

• Si presenti la costruzione dei numeri razionali a partire dai numeri interi (si scelga se fare una lezione o presentare il tutto in modo formale);2. • Si dimostri formalmente che

[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

Per avere però la complessità dell’algoritmo “globale” che, dato in input un intero n>1, calcoli la sua funzione di Eulero, si dovrebbe sommare anche la complessità di

Alla fine insieme ai bambini si sceglierà la proposta che più li convince, e tale eti- chetta sarà quella che poi si userà sempre in classe di fronte a questo tipo di problemi,

• Trovare matricola, nome e stipendio dei capi degli impiegati che guadagnano più di 40; per ciascuno, mostrare, matricola, nome e. stipendio

Table S5: Differentially expressed genes between Isotype and anti-ANXA2 antibody treated

Funzione di fuga: Il comportamento viene messo in atto per interrompere un’attività spiacevole o sgradita ed è mantenuto dal rinforzo negativo.. Le tipologie

• Quando un’ADT viene realizzato con una classe, che a sua volta implementa una o più strutture dati, l’invariante di struttura deve essere parte della post-condizione di tutti i

Il Protocollo di Kyoto è un accordo internazionale legato alla Convenzione delle Nazioni Unite sui Cambiamenti Climatici, che impegna le parti, fissando obiettivi vincolanti di