Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Aniello Murano » 10.Mapping reducibility


Mapping Reducibility

Ridurre un problema A ad un problema B usando una mapping reducibility → esiste una funzione calcolabile che converte istanze del problema A in istanze del problema B.

Se abbiamo una tale funzione di conversione, chiamata riduzione, possiamo risolvere A risolvendo B.

Una qualsiasi istanza del problema A può essere risolta usando prima la riduzione per convertire A in una istanza di B e poi risolvendo B.

Funzioni calcolabili

Definizione:
una funzione f : Σ*→Σ* è una funzione calcolabile (computable function) se esiste qualche macchina di Turing M che, su ogni input w, si ferma con f(w) sul suo nastro.

Esempio:
Tutte le consuete operazioni aritmetiche sugli interi sono funzioni calcolabili. Per esempio, possiamo costruire una macchina che prende in input [m, n] e restituisce m+n, la somma di m e n.

Definizione formale di mapping reducibility

Definizione:
Un linguaggio A è mapping reducible ad un linguaggio B, si scrive Am B, se esiste una funzione calcolabile f : Σ*→Σ* , tale che per ogni w,

w A ↔ f (w) B.

La funzione f è chiamata una riduzione di A a B.

Mapping reducibility

  1. Una mapping reduction da A a B fornisce un modo per convertire il problema di testare l’appartenenza ad A nel problema di testare l’appartenenza a B.
  2. Per testare se wA, usiamo la riduzione f per mappare w con f(w) e testiamo se f(w)B.

Decidibilità e ≤m

Teorema:
Se AmB e B è decidibile, allora A è decidibile.

Dimostrazione:
Sia M un decisore per B e f una riduzione da A a B. Un decisore N per A è il seguente:

  • N = “Su input w:
    1. Calcola f(w).
    2. esegui M su input f(w) e restituisci l’output di M.”

Chiaramente, se wA, allora f(w)B perchè f è una riduzione da A a B. Dunque, M accetta f(w) se wA.

Corollario:
If A ≤mB e A è indecidibile, allora B è indecidibile.

Dimostrazione:
se A è indecidibile e B è decidibile allora si contraddice il precedente teorema.

Mapping reducibility e complementazione

Teorema:
Se A≤mB, allora anche per i complementi (∑*\A) ≤m (∑*\B)

Dimostrazione:
sia f la funzione di riduzione da A a B con w ∈ A ↔ f(w) ∈ B.
Per questa stessa funzione vale che w ∈ (∑*\A) ↔ f(w) ∈ (∑*\B), per ogni w ∈ ∑*

Mapping reducibility per HALTTM

Rivediamo alcune delle dimostrazioni che usano il metodo della riduzione per fare alcuni esempi di mapping riducibilità.
Cominciamo con l’indecidibilità di HALTTM attraverso la riduzione da ATM.
Possiamo dimostrare una mapping riduzione usando una funzione calcolabile f che prende un input di forma (M, w) e ritorna un output di forma (M’, w’), dove

[M, w] ∈ ATM se e solo se [M', w'] ∈ HALTTM.

La seguente macchina F calcola una riduzione f.
F = “su input [M, w]:
1. Si costruisce la seguente macchina M’, tale che:
M’= “Su input x:

  • si esegue M su x.
  • se M accetta, allora M’ accetta.
  • se M rifiuta, allora M’ entra in loop.”

2. Restituisci [M', w].”

Mapping reducibility per EQTM

Consideriamo ora l’indecidibilità di EQTM attraverso una riduzione da ETM
una mapping riduzione f da ETM a EQTM mappa gli input [M] con gli output [M, M1], dove M1 è la macchina che va in reject su tutti gli input.

[M] ETM se e solo se [M, M1]EQTM.

La seguente macchina F calcola una riduzione f.
F = “su input [M]:
1. Costruisce M1 che rifiuta tutti gli input.
2. Costruisce M‘ tale che
M‘ = “su input (M,M1):

  • se M accetta, accetta. (perché L(M)=L(M1) )
  • se M rifiuta, rifiuta.”

3. Restituisce [M', M1].”

Riconoscibilità and ≤m

Teorema
se Am B e B è Turing-riconoscibile, allora A è Turing-riconoscibile.
Dimostrazione:
sia M la TM che riconosce B e f la funzione di riduzione da A a B. Allora M su input w:

  1. Calcola f(w);
  2. Simula M su f(w) e restituisce lo stesso risultato.

Dalla definizione di f: w A è equivalente con f(w) B.
M “accetta” f(w) se w A, e
M “rifiuta” f(w)/non si ferma su f(w) se w∉A.

Corollario:
se Am B e A non è Turing-riconoscibile, allora B non è Turing-riconoscibile.
dimostrazione:
Il linguaggio A non è Turing-riconoscibile e se B fosse riconoscibile si contraddirebbe il teorema precedente.

Riconoscibilità e ≤m

Teorema:
se A≤mB e A non è co-Turing riconoscibile, allora B non è co-Turing-riconoscibile.

Dimostrazione:
Se A non è co-Turing-riconoscibile, allora il complemento (∑*\A) non è Turing-riconoscibile;
da A≤mB sappiamo che (∑*\A) ≤m (∑*\B).

Dal corollario precedente: (∑*\B) non è Turing-riconoscibile, quindi B non è co-Turing-riconoscibile.

EQTM

Teorema:
EQTM non è né Turing-riconoscibile né co-Turing-riconoscibile.

Dimostrazione:
Come prima cosa mostriamo che EQTM non è Turing-riconoscibile, per fare questo mostriamo che ATM m comp(EQTM).
(questo equivale a dimostrare che comp(ATM) m EQTM e noi sappiamo che comp(ATM) è co-Turing-riconoscibile).

La funzione di riduzione f è la seguente:
F = “su input [M, w] dove M è una TM e w una stringa:
1. Costruisce le seguenti 2 macchine M1 e M2.

  • M1 = “su ogni input:
    • 1. Rifiuta.”
  • M2 = “su ogni input:
    • 1. esegui M su w. se M accetta, accetta.”

2. ritorna [M1, M2].”

comp(EQTM) non è Turing-riconoscibile

Per mostrare che comp(EQTM) non è Turing-riconoscibile vediamo che ATMm EQTM.

La seguente G calcola la funzione di riduzione g:
G = “su input [M, w] dove M è una TM e w una stringa:
1. Costruisce le seguenti 2 macchine M1 e M2.

  • M1= “su ogni input:
    • 1. Accetta.”
  • M2= “su ogni input:
    • 1. esegui M su w. se M accetta, accetta.”

2. ritorna [M1, M2].”

Linguaggi senza mapping riduzione

L’indecidibilità di ETM mostrata nella precedente lezione, mostra invece la differenza tra la nozione formale di “mapping reducibility” e quella informale di riducibilità mostrata precedentemente.
La dimostrazione mostra che ETM è indecidibile tramite una riduzione da ATM.
Vediamo se riusciamo a trasformare questa riduzione in una mapping riduzione.
Dall’originale riduzione possiamo facilmente costruire una funzione f che prende in input (M, w) e restituisce (M1), dove M1 è la TM tale che L(M1) è non vuoto (L(M1) = {w}) iff w ∈ L(M).
Dunque f è una “mapping riduzione” da ATM a comp(ETM).
Questo dimostra ancora che ETM è indecidibile perché la decidibilità non è affetta dalla complementazione, ma f non è certamente una mapping reduction da ATM a ETM.
Infatti è possibile mostrare che una tale riduzione non può esistere:
Supponiamo per assurdo che ATM <m ETM tramite una riduzione f. Per definizione di mapping reducibility segue che comp(ATM)<mcomp(ETM) attraverso la stessa funzione di riduzione f.
Ma comp(ETM) è Turing-riconoscibile e comp(ATM) non è Turing-riconoscibile, contraddicendo il precedente teorema sulla turing-riconoscibilità nella slide 9.

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion