Aniello Murano » 9.Problemi non decidibili e riducibilità - seconda parte

Potenza espressiva degli LBA

Nonostante questi vincoli sulla memoria, gli LBA sono piuttosto potenti in termini di accettori di linguaggi. Ad esempio, i decisori per ADFA e EDFA sono tutti LBA.

Gli LBA sono strettamente più potenti dei PDA. Infatti, si può provare che ogni CFL può essere deciso da un LBA. Inoltre esistono linguaggi accettati da LBA che non sono context-free come ad esempio L={anbⁿcⁿ} e L={a^n!}.

Gli LBA sono anche meno potenti delle Macchine di Turing (si pensi a qualsiasi linguaggio che ha bisogno di memoria “non constante” in aggiunta all’input per poterlo processare)

I linguaggi accettati dagli LBA sono generati da grammatiche denominate “context-sensitive“.

Problema aperto: La versione deterministica degli LBA è meno potente?

Gerarchia di Chomsky estesa

A_LBA

Come accennato, gli LBA sono piuttosto potenti in termini di accettori di linguaggi. Vediamone un esempio:

ALBA è il problema di determinare se un LBA accetta il suo input.
Formalmente,

A_LBA ={ | M è un LBA che accetta una stringa w}

Ricordiamo che il problema analogo per le MT, ovvero A_TM, è indecidibile

A_LBA è decidibile.
La dimostrazione della decidibilità di A_LBA è semplice qualora si possa asserire che il numero di configurazioni possibili è limitato, come mostrato dal Lemma che presentiamo nella prossima diapositiva.

Particolarità di un LBA

Lemma:
Preso un LBA M con q stati e g simboli nell’alfabeto del nastro. Ci sono esattamente qngn configurazioni distinte di M per un nastro di lunghezza n.

Dimostrazione:
Ricordando che una configurazione di M è come uno “snaphshot” nel mezzo di una computazione.
Una configurazione consiste dello stato di controllo, posizione della testina e il contenuto del nastro.
Per quanto riguarda le “grandezze” degli oggetti coinvolti nelle configurazioni, notiamo che:

• M ha q stati,
• la lunghezza del nastro è n, cosi la testina può essere al più in n posizioni differenti,
• gⁿ sono le possibili stringhe di simboli del nastro che si possono trovare sul nastro.

Il prodotto di queste tre quantità è il numero totale di configurazioni differenti di M con un nastro di lunghezza n, ovvero qngⁿ.

Decidibilità di A_LBA

Teorema
A_LBA è decidibile

Idea per la dimostrazione
Prima di tutto per decidere se un LBA M accetta l’input w, simuliamo M su w con una MdT M’
Durante il corso della simulazione, se M si ferma e accetta o rigetta, allora la prova termina perché M’ si ferma. La difficoltà nasce se M gira all’infinito su w.
Questo si può ovviare individuando quando la macchina va in loop, cosi possiamo fermarci e rifiutare.
L’idea per capire quando M va in loop è questa:

• Quando M computa su w, M passa da una configurazione ad un’altra. Se M ripete più volte una stessa configurazione significa che è entrata in un loop.
• Poiché M è un LBA, sappiamo che la capienza del nastro è limitata. Attraverso il lemma visto nella precedente slide, sappiamo che M può avere solo un numero limitato di configurazioni in base alla capienza del suo nastro.
• Quindi M ha un limite di volte prima di entrare in qualche configurazione che ha già fatto precedentemente. Come conseguenza del lemma, possiamo dire che se M non si ferma dopo un certo numero di passi significa che è in loop. Questo M’ è in grado di rilevarlo.

Dimostrazione della decidibilità di A_LBA

Dimosgtrazione:
L’Algoritmo che decide A_LBA è il seguente.

M’:=”Su input , dove M è un LBA e w è una stringa:

1. Simula M su w finché non si ferma o, alternativamente, per qngⁿ passi.
2. Se M si ferma, abbiamo i seguenti casi:

• Se M accetta allora M’ accetta
• Se M rifiuta allora M’ rifiuta

3. Se M non si ferma, allora M’ rifiuta.”

Domanda: Perché l’algoritmo può rifiutare se la macchina non si ferma in qngⁿ passi?

Risposta: Per il lemma precedente, M deve aver incontrato almeno una volta una configurazione precedentemente incontrata, dunque si trova in un loop.

Il linguaggio E_LBA

Abbiamo visto un problema decidibile per un LBA ma che non lo è per una Macchina di Turing classica.
Esistono tuttavia problemi indecidibili per le TM che rimangono tali anche per le LBA. Un esempio è il seguente linguaggio:

E_LBA ={| M è un LBA dove L(M)=ø}

Per la dimostrazione di indecidibilità, dobbiamo prima introdurre il concetto di “computation histories“.

Computation Histories

Una Computation Historie (CH) di una MdT M è la sequenza finita di configurazioni che M attraversa per decidere un input.

Sia M una MdT e w un ingresso per M. Una CH accettante per M su w è una sequenza di configurazioni C₁, C₂, …, C_l dove:

• C₁ è la configurazione di partenza di M su w,
• C_l è una configurazione accettante,
• ogni C_i segue C_i-1 secondo le regole di M.

Una CH non accettante è simile ad una CH accettante tranne che C_l è una configurazione non accettante.

Nota: Le MdT deterministiche hanno una sola CH per un dato input, mentre le MdT non deterministiche ne possono avere diverse.

Prova che E_LBA è indecidibile

Riduciamo A_TM a E_LBA.
Per ogni MdT M e ingresso w, definiamo un LBA B tale che

L(B)={CH | CH è accettante per una data MdT M e un dato ingresso w}

• Se L(B) = Ø vuol dire che M non accetta w e dunque (M,w) non è in A_TM.
• Viceversa se L(B) non è vuoto allora M accetta w e dunque (M,w) è in A_TM.

Per verificare che ogni sequenza in ingresso per B è una CH accettante devono essere verificate le condizioni descritte in precedenza.
Costruiamo il decisore S per A_TM, supponendo che esiste un decisore R per L(B). S := su ogni ingresso ,

• costruisce un LBA B da (M,w) come definito sopra.
• esegue R su ingresso (B)
• se R accetta → S rifiuta (L(B) è vuoto → M non accetta w)
• se R non accetta → S accetta (L(B) è non vuoto → M ha una CH accettante per w)

Quindi, l’esistenza di un decisore per E_LBA implica un decisore per A_TM. Sappiamo però che A_TM è indecidibile, quindi non esiste un decisore per E_LBA.

PCP è indecidibile

Per la prova riduciamo ATM al PCP attraverso le Computation Histories.
Dati <M, w>, costruiamo un insieme P di domino nel modo seguente.
Iniziamo con un domino che ha nella parte di sotto la configurazione iniziale di M e sopra una stringa vuota.
Aggiungiamo a P dei domino la cui parte superiore corrisponde alla configurazione corrente e la parte inferiore è la configurazione successiva.
Questi domino devono anche tenere conto di

• Il movimento della testina.
• Aumentare lo spazio del nastro con degli spazi vuoti (quando richiesto).
• Forzare ad usare come primo domino della soluzione del match quello corrispondente alla configurazione iniziale di M.

Per semplicità, assumiamo che ogni soluzione possibile deve sempre inizialre con il primo domino.
Chiameremo il PCP con questa regola aggiuntiva “modified PCP” o semplicemente MPCP.
Successivamente vedremo che questa non è una limitazione e che può essere rimossa.

Prova di ind. per PCP: Step 3. transizione R

Prova di ind. per PCP: Step 4. transizione L

Prova di ind. per PCP: Step 5. matching con q_accept

Prova di ind. per PCP: Step 6. Chiusura con q_accept

Esempio: Step 1, Step 2 + Step 3

Esempio: Step 2+3, Step 2+4

Esempio: Step 2+4, Step 2+5

Esempio: Step 6

Da MPCP a PCP

Per completare la dimostrazione, dobbiamo forzare il fatto che il primo domino deve essere il primo ad essere usato in ogni possibile soluzione del PCP.
Sia “⋆” un nuovo simbolo (cioè non presente in Γ U {#}).
Per ogni stringa s, sia⋆s la stringa ottenuta inserendo il simbolo “⋆”
Prima di ogni simbolo in s. Per esempio, _(abc) = ⋆a ⋆ b ⋆ c.
Analogamente, definiamo s⋆ e ⋆s⋆ come la stringa ottenuta aggiungendo solo dopo, oppure sia prima che dopo, ogni simbolo di s il simbolo ⋆
Dato l’insieme di domino P costruiti precedentemente, si sostituiscano i domino nel modo seguente:
t1/b1 = t1⋆/ ⋆ b1⋆
ogni altro ti/bi= ⋆ ti / b1⋆
il domino finale q_accept##/ # = ⋆q_accept# ⋆ #/#
In questo modo, il primo domino deve essere assolutamente il primo altrimenti non ci sarà matching.

Esercizio

Provare che il seguente problema è indecidibile.

Problema del domino
Dato un insieme finito di colori e un insieme di piastrelle quadrate con i quattro lati colorati di un qualche colore tra quelli a disposizione, trovare, se esiste, un modo per piastrellare una parete infinita in lunghezza e larghezza assicurando che i lati adiacenti delle piastrelle abbiano lo stesso colore.