Universidade Federal de Campina Grande – UFCGUniversidade Federal de Campina Grande – UFCGCentro de Engenharia Elétrica e Informática – CEEICentro de Engenharia Elétrica e Informática – CEEIDepartamento de Sistemas e Computação – DSCDepartamento de Sistemas e Computação – DSC

Teoria da Computação 2005.1

Decidibilidade e Decidibilidade e IndecidibilidadeIndecidibilidade

Problemas Decidíveis ( LR )

Problemas computacionais relacionados a AF’s :

saber se um AF aceita uma palavra

saber se a linguagem de um AF é vazia

saber se dois AF’s são equivalentes

etc.

Linguagens Regulares

Problemas Decidíveis ( LR )

Podemos formular problemas computacionais em termos de teste de pertinência em uma linguagem.

Por exemplo:

Saber se um dado AFD B aceita uma dada entrada w pode ser expresso como o problema:

Saber se <B,w> é um membro da linguagem:

AAFD= {<B,w> : B é um AFD que aceita w}.

Mostrar que a linguagem é decidível implica em mostrar que o problema computacional é decidível

Representação do problema

Problemas Decidíveis ( LR )

Teorema 18 :

AAFD é uma linguagem decidível.

Prova:

M = “Com entrada <B, w>, onde B é um AFD e w é uma palavra:

1. Simular B para a entrada w. 2. Se a simulação termina num estado final de B, aceitar. Se termina num estado não final,

rejeitar.”

Problemas Decidíveis ( LR )

AAFND = { <B,w> : B é um AFND que aceita w} é decidível. 

Prova:

N = “Com entrada <B, w>, onde B é um AFND e w uma palavra:

1. Converter B para um AFD equivalente C

2. Executar MT M com entrada <C,w>.

3. Se M aceita a entrada, aceitar. Caso contrário, rejeitar.”

Teorema 19:

Problemas Decidíveis ( LR )

Teorema 20:

EAFD = { <A> : A é um AFD e L(A) = Ø} é decidível.

T = “Com entrada <A>, onde A é um AFD:

1. Marcar o estado inicial de A.

2. Repetir até que nenhum novo estado seja marcado

3. Marcar todo o estado que tenha uma transição chegando de qualquer estado já marcado

4. Se nenhum estado final estiver marcado, aceitar. Caso contrário, rejeitar.”

Prova:

Problemas Decidíveis ( LR )

Teorema 21:

EQAFD = {<A,B> : A e B são AFDs e L(A) = L(B) } é decidível.

Prova:

F = “Com entrada <A, B>, onde A e B são AFDs:

L(C)= ( L(A) L(B) ) ( L(A) L(B) )

1. Construir o AFD C como descrito.2. Executar MT T com entrada <C>.

3. Se T aceita <C>, aceitar. Caso contrário, rejeitar.”

Problemas Decidíveis ( LLC )

Linguagens Livre-de-contexto

O problema de saber se um string é um membro de uma linguagem livre de contexto é relacionado com o problema de reconhecimento e compilação de programas em uma linguagem de programação.

AGLC = { <G, w> | G é uma GLC que gera a cadeia w}

Problemas Decidíveis ( LLC )

Teorema 22:

AGLC é uma linguagem decidível.

Prova:

S = “Com entrada <G, w>, onde G é uma GLC e w uma cadeia:

1. Converter G em uma gramática equivalente G’ na Formal Normal de Chomsky.

2. Listar todas as derivações com 2n-1 passos, onde n é o comprimento de w.

3. Se alguma destas derivações gera w, aceitar. Senão, rejeitar.”

Problemas Decidíveis ( LLC )

Teorema 23:

EGLC = {<G> | G é uma GLC e L(G) = } é decidível.Prova:

R = “Com entrada <G>, onde G é uma GLC:

1. Marcar todos os símbolos terminais de G.

2. Repetir até que nenhuma variável seja marcada:

3. Marcar cada variável A de G aparecendo em uma regra do tipo A U1U2...Uk onde cada símbolo U1, ... Uk já tenha sido marcado.

4. Se o símbolo inicial não estiver marcado, aceitar. Senão, rejeitar.”

Problemas Decidíveis ( LLC )

Teorema 24:

Toda linguagem livre de contexto é decidível.

Prova:

Seja G uma GLC para a linguagem:

MG = “Com entrada w:

1. Executar a MT S com entrada <G, w>

2. Se S aceita, aceitar. Senão, rejeitar.”

Indecidibilidade

Teorema 25:

AMT não é decidível

Prova:

Vamos assumir que AMT é decidível e chegar a uma contradição

Supor que H é uma MT que decide AMT :aceite se M aceita w

rejeite se M não aceita wH(<M, w>) =

Indecidibilidade

Vamos construir uma outra MT D que usa H da seguinte forma :

D recebe como entrada uma MT M e chama H para determinar o que M faz quando tem como entrada sua própria descrição <M>. Uma vez D tenha determinado isso, ela faz o oposto: ela rejeita se M aceita e aceita se M rejeita.

Indecidibilidade

D = “com entrada<M>, onde M é uma MT:

1. Execute H para a entrada <M, <M>>.

2. Retorne o contrário do que H retorna, isto é, se H aceita, rejeitar, se H rejeita, aceitar.”

ou seja :

aceite se M não aceita <M>

rejeite se M aceita <M>D(<M>) =

Indecidibilidade

O que acontece quando executamos D com sua própria descrição <D> como entrada ?

CONTRADIÇÃO !!!!!!!!!!!!!!!!!!!

Portanto, nem MT D nem MT H podem existir.

Esse problema é uma versão do Problema da Parada

aceite se D não aceita <D>

rejeite se D aceita <D>D(<D>) =

Decidibilidade

Teorema 26:

Uma linguagem é decidível se e somente se ela e seu complemento são Turing -reconhecíveis

) Se A é decidível, podemos ver facilmente que tanto A quanto seu complemento são Turing- reconhecíveis, visto que qualquer linguagem decidível é Turing-reconhecível e o complemento de uma linguagem decidível é também decidível.

Prova:

Decidibilidade

) Se ambas, A e seu complemento são Turing- reconhecíveis , então sejam M1 e M2

reconhecedores para elas, respectivamente. Então :

M = “ com entrada w”

1. Executar simultaneamente M1 e M2 com entrada w.

2. Se M1 aceita, aceitar; se M2 aceita, rejeitar.

Indecidibilidade

Corolário:

O complemento de AMT não é Turing-reconhecível

Prova:

AMT é Turing-reconhecível. Se o seu complemento fosse Turing-reconhecível, pelo teorema 26, AMT seria decidível o que contraria o teorema 25.

Redução

O problema A é redutível ao problema B implica em que uma solução para B leva a uma solução para A.

Em termos da Teoria da Computação:

Se A é redutível a B e B é decidível, então A é decidível.

Se A é indecidível e redutível a B, então B é indecidível

O Problema da Parada (versão 2)

HaltMT = {<M,w> : M é uma MT e M pára para w}

Prova:

Vamos mostrar que AMT é redutível a HaltMT.

Vamos assumir que HaltMT é decidível. Então seja R a MT que decide HaltMT.

Se R existe, podemos construir uma MT que decide AMT:

Teorema 27:

HaltMT é indecidível

O Problema da Parada (versão 2)

S =“ com entrada <M,w>, onde M é uma MT e w string:

1. Executar R com entrada <M,w>

2. Se R rejeitar, rejeitar.

3. Se R aceitar, simular M com w até parar.

4. Se M aceitar, aceitar; senão rejeitar “.

Se R decide HaltMT então S decide AMT. Como AMT é indecidível, HaltMT também deve ser, ou seja, R não pode existir.

Redução

EMT = {<M> : M é uma MT e L(M) = }

Teorema 28:

EMT é indecidível.

Prova:

Vamos assumir que EMT é decidível e então mostrar que isso leva a conclusão que AMT é decidível !!!!

Redução

Seja R uma MT que decide EMT.

Idéia para S:

1. Rodar R com entrada <M> e ver se ela é aceita.

Se ela aceita, sabemos então que L(M) =Ø e portanto M não aceita w. Mas, se R

rejeita<M>, tudo que sabemos é que L(M) Ø e portanto aceita algum string não necessariamente w.

Como mostrar que a existência de R leva a existência de S que decide AMT?

Redução

2. Em vez de rodar R com <M>, rodar R com uma modificação de M:

Modificamos M para garantir que ela rejeita todos os strings exceto w, e com entrada w, ela trabalha normalmente.

Então usamos R para testar se a máquina modificada reconhece a linguagem vazia. O único string que a máquina pode aceitar agora é w. Então a linguagem será não nula se e somente se ela aceita w.

Redução

M1 = “ com entrada x : ”

S = “ com entrada<M,w>, M MT e w string:

1. Construir M1, a partir de M e de w;

Se R é um “decider” para EMT ,S seria um “decider” para AMT . Um “decider” de AMT não pode existir, então também não existe um para EMT.

1. Se x w, rejeitar;2. Se x = w, executar M com entrada w e aceitar se M aceita.

2. Executar R com entrada <M1>;3. Se R aceita, rejeitar; se R rejeita, aceitar.

Redução

REGULARMT ={<M> : M é MT e L(M) é regular}

Teorema 29

REGULARMT é indecidível

Prova:

Redução de AMT.

Vamos assumir que temos uma MT R que decide REGULARMT .

Vamos usar R para construir S que que decide AMT.

Vamos modificar M de tal forma que a resultante M2 reconheça uma linguagem regular se e somente se aceita w:

Redução

( M2 reconhece a linguagem não-regular { 0n1n: n>0} se M não aceite w e reconhece a linguagem regular Σ* se M aceita w )

S = “ com entrada <M,w>:1. Construa a seguinte MT M2.M2 = “ com entrada x :

1. Se x tem a forma 0n1n, aceitar.2. Se x não tem essa forma, rodar

M com entrada w e aceitar se M aceita w.”

2. Rodar R com entrada <M2>3. Se R aceita, aceitar. Se R rejeita, rejeitar.”

Redução

LIVRE-DE-CONTEXTOMT = { <M> : M é MT e L(M) é livre de contexto}

DECIDÍVELMT ={<M> : M é MT e L(M) é decidível}

FINITOMT ={<M> : M é MT e L(M) é finito}Teorema 30:

LIVRE-DE-CONTEXTOMT,DECIDIVELMT e FINITOMT são indecidíveis.

Teorema de Rice:

Qualquer propriedade de linguagem reconhecidas por Máquinas de Turing é indecidível.

Redução

EQMT={<M1, M2> :M1 e M2 são MT’s e L(M1) = L(M2) }

Teorema 31:

Prova:

Então, se R decide EQMT, S decide EMT. Como EMT é indecidível, então EQMTtambém é.

EQMT é indecidível.

Redução de EMT.Vamos supor que temos MT R que decide EQMT.Vamos construir S para decidir EMT:S =“com entrada <M>, onde M é uma MT:

1. Rodar R com entrada <M,M1>, onde M1 é uma MT que rejeita todas as entradas.

2. Se R aceita, aceitar. Se R rejeita, rejeitar.”

Redução

Seja M uma MT e w um string de entrada

Uma história da computação de aceitação, para M com w é uma sequência de configuração c1, c2, ..., cl, onde:- C1 é a configuração inicial de M com w

- Cl é uma configuração de aceitação- cada Ci segue de Ci-1 de acordo com a resposta de M

Uma história da computação de rejeição para M com w é definida simultaneamente, exceto que Cl é uma configuração de rejeição.

Redução

Histórias da computação são seqüências finitas.

Se M não pára para w, não existe história da computação para M com w.

Máquinas determinísticas tem no máximo uma história da computação para qualquer dada entrada.

Redução

ALBA = { <M,w> : M é LBA e aceita w }

Teorema 32:

ALBA é decidível

Redução

Lema 3:

Seja M um LBA com q estados e g símbolos no alfabeto da fita. Existem qngn distintas configurações de M para uma fita de comprimento n.

Prova:

Uma configuração consiste do estado do controle, da posição do cabeçote e do conteúdo da fita:

M tem q estados.

O comprimento da fita é n, então o cabeçote pode estar em uma das n posições e gn possíveis strings podem estar na fita. Então o número total de diferentes configurações é q.n.gn .

Redução

O lema estabelece que um LBA pode ter apenas um número limitado de configuração quando um string de comprimento n é a entrada.

Redução

Retornando :

ALBA = { <M,w> : M é LBA aceita w }

Prova:

Teorema 33:

ALBA é decidível

Se M repete uma configuração M vai repetir e repetir entrando em loop.

Quando M computa com w, ela vai de configuração em configuração.

Redução

Como para um LBA apenas um número finito de configuração é possível (lema), basta simular M para um número máximo de passos (dado pelo lema) :

L = “ com entrada <M,w>, onde M é um LBA :

1. Simular M com entrada w para qngn passos ou até que pare.

2. Se M tem parado, aceitar se ele aceitou e rejeitar se ele rejeitou.

Se M não parou, rejeitar . “

Redução

ELBA = {<M> : M é um LBA e L(M) = Ø }

Teorema 34:

ELBA é indecidível.

Prova:

Redução de ALBA

Para uma MT M e uma entrada w, podemos determinar se M aceita w pela construção de um certo LBA B e pelo teste então se L(B) é vazio

Redução

Construimos B para aceitar sua entrada x se x é uma história da computação aceitante para M com w.

MT S que decide AMT na suposição de termos a máquina R que decide ELBA.

S = “ com entrada <M,w>, onde M é MT e w string:

## ## #

C1 C2 C3 Cl

... #

1. Construir LBA B de M e w como descrito.2. Rodar R com entrada <B>

3. Se R rejeita, aceitar. Se R aceita, rejeitar.”

Redução por Mapeamento

Reduzir um problema A para um problema B usando uma redução por mapeamento significa que existe uma função computável que converte instâncias do problema A para instâncias do problema B.

Definição formal:

A linguagem A é redutível por mapeamento para a linguagem B (A < B) se existe uma função compatível f : Σ* Σ* onde para todo w, w є A f(w) є B.

Se temos uma tal conversão (função de ), chamada uma redução, podemos resolver A com um resolvedor (solucionador) para B.

A função f é chamada a redução de A para B.

Redução por Mapeamento

Teorema 35:

Se A < B e B é decidível, então A é decidível.

Prova :

Seja M uma MT que decide B e f uma redução de A para B.

N = Entrada w

1. Computar f(w)

2. Executar M para entrada f(w). Se M aceita, aceitar. Se não, rejeitar.

Redução por Mapeamento

Corolário:

Se A < B e A é indecidível, então B é indecidível.

Teorema 36:

Se A < B e B é Turing-reconhecível, então A também é Turing-reconhecível.

Corolário:

Se A < B e A não é Turing-reconhecível, então B não é Turing-reconhecível.

Auto Referência (Self-Reference)

Vamos construir uma MT que ignore sua entrada e imprime (na fita) como saída sua própria descrição (SELF).

Lema 4:

Existe uma função computável q: Σ* Σ* tal que para qualquer string w, q(w) é a descrição de uma MT Pw que imprime w e

então pára.

Auto Referência (Self-Reference)

Prova:

A seguinte MT computa q:

Q = “ Entrada string w:

1. Construir a seguinte MT Pw:

Pw = “Entrada qualquer:

1. Apagar entrada2. Escrever w na fita3. Parar”

2. Escrever Pw na fita

Se M é uma MT e <M> sua descrição, q(<M>) = <P<M>>

Auto Referência (Self-Reference)

Vamos construir SELF como a função de 2 máquinas A e B <SELF> = <AB>

A parte A roda primeiro e depois passa o controle para a parte B.

O resultado da execução de A é escrever na fita uma descrição de B, e o resultado da execução de B é escrever convenientemente na fita uma descrição de A.O resultado final então é escrever na fita uma descrição de SELF.

Auto Referência (Self-Reference)

A = P<B> e

B = “ Entrada <M>, onde M é uma MT:

Obs : q(<B>) = <P<B>> = <A>

1. computar q(<M>)2. combinar o resultado com <M> para ter uma descrição de uma MT.

3. escrever uma descrição e parar.”

Teorema da Recursão

Seja T uma MT que computa uma função t: Σ*x Σ* Σ*.Existe uma MT R que computa uma função r: Σ* Σ* onde para todo w, r(w) = t(<R>,w)

Teorema 37:

Teorema da Recursão

R = “entrada w”

Prova:

2. Computar t(<R>,w)1. obter <R>

obter <R>:

A = P<BT>

B = “Entrada <M>1. Computar q(<M>)

2. Combinar remetido com <M>

3. Escrever na fita.