Linguagem universal

Yuri Tavares dos Passos

Problemas

● Informalmente, um problema é uma questão sim/não sobre um conjunto infinito de possíveis instâncias

● Exemplo: “Um grafo G tem um ciclo hamiltoniano (ciclo que passa por cada nó exatamente uma vez)?– Cada grafo não-dirigido é uma instância do

“problema do ciclo hamiltoniano”.

Problemas

● Formalmente, um problema é uma linguagem.

● Cada string codifica alguma instância.● A string pertence a linguagem se e

somente se a resposta para aquela instância é “sim”.

Exemplo: Um problema sobre MT● Nós podemos pensar na linguagem Ld

como um problema.● “Dada uma MT, ela não aceita ela

mesma?”● Podemos pensar no problema como uma

pergunta sobre strings binárias– Como perguntaríamos Ld?

Problemas decidíveis

● Um problema é decidível se há um algoritmo para respondê-lo.– Um algoritmo, formalmente, é uma MT que

trava para qualquer entrada, aceitando ou não.

– “Problema decidível” = “Linguagem recursiva”.

● Caso contrário, o problema é indecidível.

LinguagensRE

(Decidíveis)

LinguagensRE

LinguagensNão-RE

Ld

Existe al-Guma lin-guagem aqui?

Linguagens

Do abstrato para o real

● Enquanto que o fato de que Ld é indecidível é interessante intelectualmente, não existe um impacto direto nos problemas do mundo real.

● Nós deveríamos desenvolver alguns problemas relacionados a MT que sejam indecídiveis, mas nosso objetivo é usar a teoria para mostrar que alguns problemas reais são indecidíveis.

Exemplos de problemas indecidíveis● Uma linha particular de código dentro de um programa

será executada?● Dada uma gramática livre de contexto, ela é ambígua?● Dada duas gramáticas livres de contexto, elas geram a

mesma linguagem?● Dada uma linguagem aceita por uma MT, ela é regular?● É possível verificar se um lgoritmo qualquer sempre irá

parar?

Técnicas para descobrir indecibilidade● Existem dois métodos convencionais:

– Análise do complemento da linguagem

– Redução a problemas/linguagens conhecidos(as)

● Um exemplo de problema conhecido será apresentado: a linguagem universal.

Complemento de linguagens RE e R● Dada uma linguagem L e seu

complemento L, quantos modos diferentes podemos inserir e no diagrama de linguagens R, RE e não-RE?

R

RE não R

Não RE

Possibilidade 1

R

RE não R

Não RE

L L

Possibilidade 2

R

RE não R

Não RE

L L

Possibilidade 3

R

RE não R

Não RE

L L

Possibilidade 4

R

RE não R

Não RE

L L

Possibilidade 5

R

RE não R

Não RE

L L

Possibilidade 6

R

RE não R

Não RE

L

L

Possibilidade 7

R

RE não R

Não RE

LL

Possibilidade 8

R

RE não R

Não RE

L

L

Possibilidade 9

R

RE não R

Não RE

L

L

Complemento de linguagens RE e R● Mas apenas 4 delas são válidas!● Veremos com os dois teoremas a seguir

Teorema 1

● Se L é uma linguagem recursiva, então L também é.

● Prova: Basta construir uma MT para L como na imagem a seguir.

Teorema 1

Teorema 2

● Se L e L são linguagens RE, então também L é recursiva.

● Prova: Considere L = L(M1) e L = L(M2).

● Construa uma MT M que usa M1 e M2 como na figura a seguir.

Teorema 2

Complemento de R e RE

● Com estes teoremas, apenas as seguintes combinações são possíveis:

– L e L são recursivas.

– L e L não são RE.

– L é RE mas não é recursiva e L não é RE.

– L é RE mas não é recursiva e L não é RE.

A linguagem universal

● Um exemplo de uma linguagem RE, mas não recursiva é a linguagem Lu da máquina de Turing universal (MTU).

● A MTU toma como entrada o código de alguma MT M e alguma string binária w e aceita somente se M aceita w.

A linguagem universal

● A linguagem universal (Lu) é definida como a linguagem dos pares (M,w) tais que M aceita w.

● Será apresentado uma MT que aceita Lu.

Como criar a MTU

● As entradas da fita serão da forma:– M 111 w

● Nota: Uma MT válida codificada em binário, nunca possui 111, logo podemos dividir M de w.

● A MT deve aceitar sua entrada se e somente se M é um código válido e M aceita w.

MTU

● A MTU possuirá várias fitas.● A fita 1 guarda a entrada M111w.● A fita 2 guarda a fita de M.

– MTU marca a cabeça de leitura como se fosse a cabeça de leitura de M.

● Fita 3 guarda o estado de M.

MTU

MTU

● Passo 1: A MTU verifica se M é um código válido.– Todos os movimentos devem ter cinco

componentes.

– Não há dois movimentos com o mesmo par (estado,símbolo).

● Se M não é válida, sua linguagem é vazia, então a MTU pára sem aceitar.

MTU

● Passo 2: A MTU examina M para verificar quantas células de sua fita são necessárias para representar um símbolo de M.

● Passo 3: Inicializa a fita 2 para representar a fita de M com a entrada w e inicializa a fita 3 para armazenar o estado inicial.

MTU

● Passo 4: Simula M.– Verifica o movimento na fita 1 que

corresponde ao estado na fita 3 e o símbolo de fita na cabeça de leitura da fita 2.

– Se encontrou, muda o símbolo e move a cabeça de leitura na fita 2 a muda para o estado na fita 3.

– Se M aceita, a MTU também aceita.

Pergunta

● No mundo real, existe algo semelhante a MTU?

O que é Lu?

● Lu = {(M,w)| M é uma MT codificada corretamente e M aceita w}

● não (A e B) = não A ou não B

● Lu = {(M,w)| M não é uma MT codificada corretamente ou M não aceita w}

Lu é RE mas não recursiva

● Uma MT para MTU foi descrita, logo ela é RE.

● Suponha que seja recursiva, isto é, uma MTU U sempre irá parar.

● Então, nós podemos rodar um algoritmo para Ld como segue.

Lu é RE mas não

recursiva● Ld é um caso especial de Lu.

● Ld = { w | w representa uma MT M e M não aceita w}

● Ld = Lu = {(w,w)| w não é uma MT codificada corretamente ou M não aceita w}– Nota: se w não é uma MT M codificada, L(M)= , ∅

logo M não aceita w e, portanto, w∈Ld.

Prova

● Dada uma entrada w, nós podemos decidir se está em Ld seguindo os seguintes passos.

– Verifica se w é um código para MT válida.● Se não é, então sua linguagem é vazia, logo w

pertence a Ld

– Se válido, usa-se U para decidir se w111w ∈ Lu

– Se w111w ∈ Lu, então w ∉ Ld. Senão, w ∈ Ld.

Prova

Prova

● Mas nós sabemos que Ld não é RE.

● Portanto, nossa suposição de que Lu é recursiva está errada.

● Logo, Lu é RE, mas não recursiva.

LinguagensRecursivas

=Decidíveis

LinguagensRE

LinguagensNão RE

Ld

Lu

Estas são indeci-díveis

Linguagens

Redução

● Uma redução de uma linguagem L para uma linguagem L' é um algoritmo (MT que sempre pára) que usa como entrada uma string w e a converte para uma string x, tal que:– x ∈ L' se e somente se w ∈ L.

Redução

Conversor MT para L'w xsim sim

MT para L

– x ∈ L' se e somente se w ∈ L.– Redução de L para L'

Redução

P1 se reduz a P

2

MT como um tradutor

● Até agora as MT foram consideradas aceitadores de palavras

● Mas, podemos adaptá-las de tal forma que elas possuam fitas de saída, onde uma string é escrita nesta fita apenas se ela parar.

● Dessa forma, a MT traduz sua entrada, escrevendo em sua saída.

Reduções

● Se reduzirmos L para L' e L' é decidível, então o algoritmo para L' junto com o algoritmo de redução mostram que L também é decidível

● A contrapositiva desta afirmação mostra que: Se L não é decidível, então L' não pode ser também.

Reduções

● Exemplo: Nós reduzimos Ld para Lu.

Reduções

● E chegamos a conclusão da contrapositiva, isto é:– Se Lu não é decidível, então, Ld também

não o é.

Exercícios

● Considere a linguagem– L5 = {M|M possui 5 estados}.

Esta linguagem/problema é decidível, indecidível ou não-RE? Justifique.

Exercícios

● Considere linguagem A contendo uma única cadeia, s, onde:– s = 0, se vida em Marte nunca será

encontrada.

– s = 1, se algum dia a vida em Marte será encontrada.

A linguagem A é decidível? Justifique. Assuma que a pergunta para questão da vida em Marte seja SIM ou NÃO.

Exercícios

● O problema/linguagem da parada é enunciado da seguinte forma:– Dada uma MT M, é o conjunto de pares (M,

w) tais que w está em H(M).● H(M) é a linguagem das palavras que são

aceitas por M por parada.

● Mostre que o problema da parada é RE mas não decidível. Dica: use redução.