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 A ≤_m 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.

Decidibilità e ≤_m

Teorema:
Se A ≤_mB 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 w∈A, allora f(w)∈B perchè f è una riduzione da A a B. Dunque, M accetta f(w) se w∈A.

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 HALT_TM

Rivediamo alcune delle dimostrazioni che usano il metodo della riduzione per fare alcuni esempi di mapping riducibilità.
Cominciamo con l’indecidibilità di HALT_TM attraverso la riduzione da A_TM.
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] ∈ A_TM se e solo se [M', w'] ∈ HALT_TM.

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 EQ_TM

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

[M] ∈ E_TM se e solo se [M, M₁] ∈ EQ_TM.

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

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

3. Restituisce [M', M₁].”

Riconoscibilità and ≤_m

Teorema
se A ≤_m 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 A ≤_m 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.

EQ_TM

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

Dimostrazione:
Come prima cosa mostriamo che EQ_TM non è Turing-riconoscibile, per fare questo mostriamo che A_TM ≤_m comp(EQ_TM).
(questo equivale a dimostrare che comp(A_TM) ≤_m EQ_TM e noi sappiamo che comp(A_TM) è 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 M₁ e M₂.

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

2. ritorna [M₁, M₂].”

comp(EQ_TM) non è Turing-riconoscibile

Per mostrare che comp(EQ_TM) non è Turing-riconoscibile vediamo che A_TM ≤_m EQ_TM.

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.

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

2. ritorna [M₁, M₂].”

Linguaggi senza mapping riduzione

L’indecidibilità di E_TM 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 E_TM è indecidibile tramite una riduzione da A_TM.
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 (M₁), dove M₁ è la TM tale che L(M1) è non vuoto (L(M₁) = {w}) iff w ∈ L(M).
Dunque f è una “mapping riduzione” da A_TM a comp(E_TM).
Questo dimostra ancora che E_TM è indecidibile perché la decidibilità non è affetta dalla complementazione, ma f non è certamente una mapping reduction da A_TM a E_TM.
Infatti è possibile mostrare che una tale riduzione non può esistere:
Supponiamo per assurdo che A_TM <_m E_TM tramite una riduzione f. Per definizione di mapping reducibility segue che comp(A_TM)<_mcomp(E_TM) attraverso la stessa funzione di riduzione f.
Ma comp(E_TM) è Turing-riconoscibile e comp(A_TM) non è Turing-riconoscibile, contraddicendo il precedente teorema sulla turing-riconoscibilità nella slide 9.