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 » 9.Problemi non decidibili e riducibilità - seconda parte


LBA – Linear bounded automaton

Definizione:
Le linear bounded automaton (LBA) sono Macchine di Turing con una sola limitazione:

la testina sul nastro non può muoversi oltre la porzione di nastro contenente l’input.

Se un LBA prova a muovere la sua testina oltre l’input, la testina rimane ferma in quel punto come accade nella Macchina di Turing classica quando la testina tenta di andare più a sinistra del primo simbolo in input (o il simbolo di start se utilizzato).

Un LBA è una Macchina di Turing con memoria limitata, com’è mostrato nella figura sottostante. Può risolvere solo problemi il cui input non superi la capienza del nastro.

Usando un alfabeto del nastro più ampio dell’alfabeto di input si ha che la memoria disponibile viene incrementata di un fattore costante. Perciò per un input di lunghezza n, la quantità di memoria disponibile è lineare in n. Da questo deriva il nome di questo modello.


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={anbncn} e L={an!}.

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


ALBA

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,

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

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

ALBA è decidibile.
La dimostrazione della decidibilità di ALBA è 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,
  • gn 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 qngn.

Decidibilità di ALBA

Teorema
ALBA è 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 ALBA

Dimosgtrazione:
L’Algoritmo che decide ALBA è 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 qngn 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 qngn 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 ELBA

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:

ELBA ={| 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 C1, C2, …, Cl dove:

  • C1 è la configurazione di partenza di M su w,
  • Cl è una configurazione accettante,
  • ogni Ci segue Ci-1 secondo le regole di M.

Una CH non accettante è simile ad una CH accettante tranne che Cl è 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 ELBA è indecidibile

Riduciamo ATM a ELBA.
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 ATM.
  • Viceversa se L(B) non è vuoto allora M accetta w e dunque (M,w) è in ATM.

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 ATM, 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 ELBA implica un decisore per ATM. Sappiamo però che ATM è indecidibile, quindi non esiste un decisore per ELBA.

PCP – POST CORRESPONDENCE PROBLEM

Il fenomeno dell’indecidibilità non è un problema che riguarda solo gli automi. Per mostrare un esempio, consideriamo un problema indecidibile riguardante una “semplice” manipolazione di stringhe: il Post correspondence problem (PCP).

Il PCP fu introdotto e provato indecidibile per la prima volta da E.L.Post in “A variant of Recursivley Unsolvable problem”, Bull. Amer. Math. Soc.52 (1946)

Possiamo descrivere questo problema paragonandolo ad un tipo di puzzle. Iniziamo con un insieme di domini, ognuno contenente due stringhe, ognuna su un lato.

Un pezzo singolo del domino è rappresentato nella figura in alto.

Mentre un insieme di domini sarà come indicato nella figura al centro.

L’obbiettivo è quello di costruire una lista di questi domini (le ripetizioni sono ammesse) in modo che la stringa dei simboli scritti nella parte superiore dei domini è uguale a quella dei simboli inferiori. Questa lista è chiamata un match.

Ad esempio la lista nella figura in baso è un match per questo puzzle:


PCP(segue)

Leggendo l’inizio della stringa otteniamo “abcaaabc”, che è uguale alla stringa sotto. Possiamo anche rappresentare questo match deformando i domini in modo che creiamo la corrispondenza da sopra a sotto la linea.

Per alcuni insiemi di domini non è sempre possibile trovare un match. Per esempio l’insiemeindics6to nella figura in basso non può contenere un match perché ogni stringa che si trova sopra è più lunga rispetto alla stringa che si trova sotto.

Il Post correspondence problem riguarda la possibilità di determinare se una collezione di domini ha un match. Questo problema non è risolvibile con algoritmi. Prima di dare la definizione formale di questo teorema con la sua definizione, formuliamo precisamente il problema e in seguito definiamo il suo linguaggio.


Indecidibilità delPCP

Un instanza del PCP è un insieme P di domini,  come indicato in figura.

Un match è una sequenza di interi i1, i2,…, il, dove ti1, ti2,…tin = bi1, bi2,…, bin.
Nota: la stessa coppia può apparire più volte, ovvero, può essere che per certi m≠j, si ha che ij = im.

Il problema del PCP è quello di determinare se P ha un match.

Il linguaggio corrispondente al problema è

PCP={<P>| P è un istanza del Post Correspondence Problem con un match}

TEOREMA: PCP è indecidibile


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 1. Inizializzazione

Dati <M, w>, costruiamo il primo domino dell’insieme P come corrispondente alla configurazione iniziale è q0w nel modo indicato in figura

Il simbolo # è un nuovo simbolo non appartenente all’alfabeto del nastro di M e serve come marcatore


Prova di ind. per PCP: Step2. transizione

Ad ogni passo di computazione di M facciamo corrispondere dei domino in P in modo da poter copiare la configurazione corrente di M dalla parte di sotto dei domino (delimitata tra #) nella parte superiore e sostituiamo nella parte sottostante corrispondente la prossima configurazione.

Per fare questo, abbiamo bisogno di fare più passi elementari nel modo indicato nella figura in alto:
Una configurazione racchiusa tra # avrà sempre la forma del tipo αbqcβ.
Per calcolare la prossima configurazione, occorre copiare _ sia nella parte superiore che inferiore
Copiare bqc sulla parte superiore e la prossima configurazione sulla parte inferiore
Copiare β sia nella parte superiore che inferiore.

Per copiare α e β, aggiungiamo il sequente domino in P, per ogni a in Γ, come indicato nella figura in basso.

Nelle slide successive indichiamo come trattare le transizioni.


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 qaccept


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


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 qaccept##/ # = ⋆qaccept# ⋆ #/#
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.

  • 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