Cap 5

Fazer download em pdf ou txt
Fazer download em pdf ou txt
Você está na página 1de 32

Capı́tulo 5

Decidibilidade

Como já foi dito nos capı́tulos anteriores, existem vários problemas indecidı́veis, alguns
deles de formulação bastante simples. Neste capı́tulo serão apresentados alguns desses
problemas.
Este capı́tulo será iniciado pela apresentação da denominada tese de Church-Turing,
que afirma que a máquina de Turing é um formalismo que captura a noção de com-
putação efetiva. Em seguida, será visto como as instâncias de um problema de decisão
podem ser codificadas (representadas) de forma que possam ser alimentadas como en-
tradas para uma MT. Em seguida, na Seção 5.3, será mostrado que quaisquer MTs
podem ser codificadas e apresentadas como entrada para uma MT conhecida como
“máquina de Turing universal”, uma MT que simula qualquer MT fornecida como
entrada. O primeiro problema de decisão indecidı́vel será analisado na Seção 5.4: o
problema da parada para MTs. Será também apresentada uma linguagem que não é
LRE, assim como uma liguagem que é LRE mas não é recursiva. Na Seção 5.5 será
apresentada a técnica de redução de problemas, de forma que uma série de problemas
indecidı́veis sejam determinados como tais, por meio dessa técnica, na Seção 5.6.

5.1 A Tese de Church-Turing


No capı́tulo anterior, as MTs foram introduzidas como máquinas para reconhecimento
de linguagens. Mas, foi ressaltado, as MTs podem ser usadas para implementação de
funções em geral. Nesse caso, a MT recebe como entrada os argumentos e retorna a
saı́da na própria fita. A seguir, são esboçadas algumas considerações a respeito do poder
computacional das MTs com relação à computação de funções em geral. No restante
do capı́tulo, cujo propósito maior é a introdução ao mundo dos problemas insolúveis,
serão consideradas apenas as funções que retornam sim ou não, as quais podem ser
“programadas” por meio de MTs reconhecedoras de linguagens.
Mesmo antes do aparecimento dos primeiros computadores, os matemáticos já se
preocupavam com a noção de computação efetiva. Trabalhando a partir de uma noção
imprecisa (informal), na qual se especificava uma lista de atributos desejáveis para tal
conceito, como a possibilidade de execução mecânica, produção da mesma saı́da para as

243
244 Editora Thomson Introdução aos fundamentos da computação

mesmas entradas, execução em tempo finito etc., vários formalismos foram propostos
no intuito de capturar, de forma precisa (formal), o conceito de computação efetiva. A
partir de uma caracterização formal, seria possı́vel, então, mostrar que certos problemas
seriam computáveis, ou seja, existiriam algoritmos para eles, e que outros não seriam
computáveis.
É interessante observar que, já naquela época (final da década de 1930), vários
formalismos foram propostos que vieram a revelar a mesma expressividade, apesar das
suas diferentes “aparências”. Alguns desses formalismos são:
• máquinas de Turing;
• sistemas de Post;
• funções µ-recursivas;
• λ-cálculo.
Os computadores digitais, tanto os mais antigos quanto os mais modernos, foram
construı́dos com um conjunto de instruções que lhes dão um poder computacional
idêntico ao das máquinas de Turing e ao dos outros formalismos anteriormente cita-
dos.1 Mais modernamente, as linguagens de programação de alto nı́vel, como Java,
C, Pascal etc., com o mesmo poder expressivo, apareceram no intuito de facilitar a
tarefa de programação propriamente dita. Mas, não se deve perder de vista que tais
linguagens não apresentam maior expressividade do que, por exemplo, as MTs, embora
sejam, obviamente, muito mais adequadas do ponto de vista prático para a confecção
de algoritmos.
Entre os diversos formalismos matemáticos propostos, a máquina de Turing é um
dos mais aderentes aos computadores atuais, isto é, pode-se considerar que a máquina
de Turing captura a parte “essencial”, aquela responsável, em última análise, pelo
poder computacional dos computadores atuais. Já de um ponto de vista mais geral,
como os formalismos e linguagens já mencionados são equivalentes do ponto de vista
de expressividade, poder-se-ia dizer que a noção de “computação” seria o que existe de
comum entre todos eles, ou, por outro lado, cada um deles apresenta uma abordagem
diferente para o conceito de computabilidade.
A tese de Church-Turing pode ser assim enunciada:
Se uma função é efetivamente computável, então ela é computável por meio
de uma máquina de Turing.
Ou, equivalentemente: todo algoritmo pode ser expresso mediante uma MT.
A noção de computação efetiva não é definida formalmente. Portanto, não há
como provar que a tese de Church-Turing é correta. No entanto, a proliferação de
formalismos nunca mais expressivos que o da máquina de Turing constitui evidência em
seu favor. Dada a equivalência dos vários formalismos e linguagens, a tese de Church-
Turing, mesmo que implicitamente, equipara a classe das funções computáveis à classe
1
Estritamente falando, o poder computacional associado aos formalismos matemáticos citados é maior
que o de qualquer computador real, em virtude do fato de que um computador real tem uma memória
limitada.
Newton José Vieira Capı́tulo 2: Máquinas de estados finitos 245

de funções que podem ser expressas em qualquer um deles. Assim, por exemplo, a tese
implica que “se uma função for efetivamente computável, então ela será computável
por meio de um programa escrito na linguagem C”.
A tese de Church-Turing, quando particularizada para problemas de decisão, po-
deria ser assim enunciada: se um problema de decisão tem solução, então existe uma
MT que o soluciona. Dessa forma, para mostrar que um problema de decisão não tem
solução, basta mostrar que não existe MT que o soluciona. Por outro lado, dada a
equivalência dos diversos formalismos, um problema de decisão não tem solução se não
for possı́vel expressar uma solução em qualquer um dos mesmos. Assim, por exemplo,
se não existir um programa em C que seja uma solução para um problema de decisão,
então esse problema de decisão é insolúvel.
Uma caracterı́stica importante de qualquer um dos formalismos citados é o que
se denomina auto-referência. Por exemplo, é possı́vel ter MTs que manipulam MTs:
para isso, basta codificar (ou representar) a MT a ser manipulada, usando-se um al-
fabeto apropriado, antes de supri-la como entrada. No caso de uma linguagem de
programação, é possı́vel ter programas que manipulam programas: um programa em
Java pode receber como entrada um programa escrito em Java e manipulá-lo como
dado. Na Seção 5.2, vamos ver como isso pode ser feito para MTs.
A caracterı́stica mencionada no parágrafo anterior propicia a possibilidade de se
construir uma máquina universal, ou seja, uma MT (ou programa em uma linguagem
de programação) que seja capaz de simular uma MT (programa) qualquer suprida como
argumento. Na Seção 5.3, será apresentada uma máquina desse tipo: uma máquina de
Turing universal.
A possibilidade de auto-referência é uma caracterı́stica fundamental que levou à
descoberta de funções não computáveis. Um exemplo disso será visto na Seção 5.4:
não existe MT que determine se uma MT arbitrária vai parar ou não ao processar certa
entrada. Ou ainda, não existe programa em C que determine se um programa em C vai
parar ou não ao processr certa entrada. Na verdade, vários outros problemas similares,
que envolvem o processamento de MTs por MTs são insolúveis, como será mostrado
nos capı́tulos subsequentes.

5.2 Máquinas de Turing e Problemas de Decisão

Como já foi dito na Seção 1.4, a solução de um problema de decisão P é um algoritmo
que dá a resposta correta para cada instância p ∈ P . Dada a tese de Church-Turing,
a solução de P pode ser expressa por meio de uma máquina de Turing que, para cada
instância p ∈ P , se a resposta para p for “sim”, para em um estado final, e se a
resposta for “não”, para em um estado não final. Dessa forma, a máquina de Turing
deve reconhecer a linguagem recursiva que consta de todas as instâncias p para as quais
a resposta é “sim”.
246 Editora Thomson Introdução aos fundamentos da computação

Implı́cito no parágrafo anterior está o fato de que uma máquina que solucione um
problema P deve receber como entrada uma palavra que represente uma instância de
P . Assim, o primeiro passo para solucionar um problema de decisão P é projetar uma
representação para as instâncias de P utilizando-se um certo alfabeto Σ. Quando o PD
consta de uma única instância, na verdade ela não precisa ser representada, ou, por
outro lado, qualquer palavra serve para representá-la (λ, por exemplo). E mais, se o PD
consta de um número finito n de instâncias, nenhuma delas precisa ser representada,
ou, de outra forma, quaisquer n palavras servem para representar as n instâncias.
O problema da representação se torna importante quando o PD tem uma infinidade
de instâncias.2
Cada instância p de um PD P pode ser identificada com uma sequência v1 ,
v2 , . . . , vk de valores especı́ficos para os k parâmetros de P (e vice-versa). Assim,
a representação de p pode ser feita codificando-se a sequência v1 , v2 , . . . , vk , o que é
feito associando-se (pelo menos) uma palavra de Σ∗ a tal sequência. Essa associação
deve satisfazer os seguintes requisitos:

1. Para cada instância de P deve existir pelo menos uma palavra de Σ∗ que a
represente.
2. Cada palavra de Σ∗ deve representar no máximo uma instância de P .
3. Para cada palavra w ∈ Σ∗ , deve ser possı́vel determinar se ela representa ou não
alguma instância de P . Ou seja, o problema de determinar se w representa uma
instância deve ser decidı́vel.

Em outras palavras, a associação entre as instâncias de P e as palavras de Σ∗ pode ser


vista como uma função, não necessariamente total, de Σ∗ para P .

Exemplo 115 Seja o PD “determinar se um número natural n é primo”. Seguem duas


representações das instâncias deste problema:

a) Usando-se o alfabeto {1}, pode-se representar cada instância “determinar se j


é primo”, em que j é um número natural especı́fico, pela palavra 1j . Com isso,
os três requisitos enumerados anteriormente são satisfeitos:

i. Para cada instância, “determinar se j é primo”, existe uma palavra de {1}∗


que a representa: 1j .
ii. Cada palavra 1j ∈ Σ∗ representa uma instância: a instância “determinar se
j é primo”.
iii. Para cada palavra w ∈ {1}∗ , é possı́vel determinar se ela representa ou não
alguma instância: toda palavra representa uma instância.

b) Usando-se o alfabeto {0, 1}, pode-se representar cada instância na notação


binária convencional, com zeros à esquerda permitidos. Com isso:
2
Na verdade, em termos práticos, se um PD tem mais de uma instância, particularmente quando
possui muitas instâncias, pode ser conveniente representá-las explicitamente.
Newton José Vieira Capı́tulo 2: Máquinas de estados finitos 247

sim
Rhv1 , . . . , vn i M
não

Figura 5.1 Máquina de Turing para um problema de decisão.

i. Cada instância é representada por inúmeras palavras. Por exemplo, as pa-


lavras 0i , para i ≥ 1, representam “determinar se 0 é primo”; as palavras
0i 1, para i ≥ 0, representam “determinar se 1 é primo”; e assim por diante.
ii. Cada palavra de w ∈ Σ∗ representa no máximo uma instância: se w =
λ, não representa instância alguma; caso contrário, representa a instância
“determinar se η(w) é primo”, onde η(w) é o número representado em binário
por w. Por exemplo, 00110 representa “determinar se 6 é primo”, e apenas
essa instância.
iii. Para cada palavra w ∈ {0, 1}∗ , é possı́vel determinar se ela representa ou não
alguma instância: se w = λ, não representa instância alguma; caso contrário,
representa.

A notação Rhv1 , v2 , . . . , vn i será utilizada para designar qualquer palavra w que re-
presente a instância p correspondente à sequência de valores de parâmetros v1 , v2 ,. . . ,vn .
Uma máquina de Turing M que soluciona um PD, que receba como entrada v1 , v2 , . . . , vn ,
será representada esquematicamente como mostrado na Figura 5.1. Nessa figura,
mostra-se que uma entrada para M é qualquer representação Rhv1 , v2 , . . . , vn i para
uma instância do PD, e que a saı́da pode ser sim ou não. Acima das setas indicando
sim e não, para efeitos de clareza, pode-se colocar descrições do que significa a respec-
tiva resposta (veja, por exemplo, a Figura 5.2). Supondo que a representação para o
PD em questão seja feita a partir do alfabeto Σ, então para cada w ∈ Σ∗ , a máquina M
responde sim se (a) w representa alguma instância p (ou seja, se w é Rhv1 , v2 , . . . , vn i
para alguma sequência de parâmetros v1 , v2 ,. . . , vn ) e (b) M para em estado final ao
processar a entrada Rhv1 , v2 , . . . , vn i; e responde não se (a) w não representa qualquer
instância ou (b) se w representa alguma instância mas M para em estado não final ao
processar a mesma. Assim, a entrada para M , na Figura 5.1, pode ser qualquer w ∈ Σ∗ ,
porém a “entrada esperada” é da forma Rhv1 , v2 , . . . , vn i. No entanto, daqui para a
frente, com o objetivo de simplificar a exposição, vamos supor que a entrada esteja
realmente no formato Rhv1 , v2 , . . . , vn i (ou seja, que represente efetivamente alguma
instância).3

3
Tal suposição é coerente com o fato de que o teste para saber se w representa alguma instância pode
(e deve!) ser feito antes da ativação da MT relativa ao PD.
248 Editora Thomson Introdução aos fundamentos da computação

Exemplo 116 Considere o PD “determinar se uma gramática livre do contexto G gera


uma palavra w, para G e w arbitrários”.
Como ressaltado anteriormente, antes de se construir uma máquina de Turing que
solucione tal PD, deve-se conceber uma representação para suas instâncias. Para isso,
basta mostrar como codificar em um alfabeto Σ, que pode ser diferente do alfabeto de
G, os pares (G, w). Neste exemplo, será usado Σ = {0, 1}.
Seja uma GLC G = (V, Γ, R, P ), em que V = {X1 , X2 , . . . , Xn } e Γ = {a1 , a2 , . . . , ak }.
Cada variável Xi será representada pela palavra 1i , e cada terminal aj será represen-
tado pela palavra 1n+j . Assim, por exemplo, se V = {A, B, C} e Γ = {a, b}, tem-se a
seguinte codificação: A: 1, B: 11, C: 111, a: 1111, b: 11111. Uma regra de R pode ser
codificada colocando-se, em sequência, o código da variável do lado esquerdo seguido
dos códigos dos sı́mbolos da palavra do lado direito separados por 0. Dessa forma, para
o exemplo, a regra B → aAb pode ser assim codificada: 12 014 011 015 . Vamos assumir
que a variável de partida seja codificada por 1.
As codificações das regras são colocadas em sequência separadas por 00 (qualquer
sequência serve). A representação da gramática consta de 1n 01k 0, onde n é o número
de variáveis e k é o número de terminais, seguido da representação das regras. A
sequência que representa a gramática é separada da codificação da palavra de entrada
w por 000. Essa última é representada usando-se 0 para separar as codificações de seus
sı́mbolos. Segue um exemplo de representação de instância com base nessa codificação.
Seja a instância “determinar se aba ∈ L(H)” para a gramática livre do contexto
H = ({A, B, C}, {a, b}, R, A), em que R consta das regras:

A → aAa | B
B → aB | CC
C → b|λ

Usando os códigos já definidos, sejam Rhr1 i = 11 014 011 014 (código da regra A →
aAa), Rhr2 i = 11 012 (código da regra A → B) etc. Então uma representação para tal
instância, RhH, abai, seria:

13 012 0Rhr1 i00Rhr2 i00Rhr3 i00Rhr4 i00Rhr5 i00Rhr6 i00014 015 014 .

Observe que existem outras representações para essa mesma instância; por exemplo,
mude a ordem de apresentação das regras. Veja também que é possı́vel testar se qual-
quer palavra no alfabeto {0, 1} representa ou não uma instância. Ou seja, a linguagem

{z ∈ {0, 1}∗ | z é alguma RhG, wi para alguma GLC G e palavra w de G}

é recursiva (usando implicitamente a tese de Church-Turing).


Uma máquina de Turing que solucionasse o PD em questão seria representada esque-
maticamente como mostrado na Figura 5.2. Note que tal PD tem solução se, e somente
se, a linguagem {RhG, wi | w ∈ L(G)} é recursiva. Esta linguagem será referida como
uma linguagem associada ao PD. Portanto, um PD P é decidı́vel se e somente se uma
linguagem associada a P é recursiva.
Newton José Vieira Capı́tulo 2: Máquinas de estados finitos 249

w ∈ L(G)
sim
RhG, wi M
w 6∈ L(G)
não

Figura 5.2 Máquina de Turing para o PD do Exemplo 116.

Exercı́cios
1. Seja a seguinte representação de certa gramática G, utilizando-se a codificação
concebida no Exemplo 116:

RhGi = 1101101011101011100101100110111101101111001100.

Supondo que G tenha os terminais a, representado por 111, e b, representado por


1111, que linguagem é gerada por G?

2. Faça um algoritmo que, dada uma palavra w ∈ {0, 1}∗ , determine se a mesma re-
presenta ou não uma GLC de acordo com a representação criada no Exemplo 116.

3. Construa representações para os seguintes problemas de decisão:

a) Dados um vetor de números naturais V e um número n, determinar se n


ocorre em V .
b) Dados um grafo G e dois vértices v1 e v2 de G, determinar se existe um
caminho de v1 para v2 em G.
c) Dadas duas gramáticas regulares, determinar se elas são equivalentes.
d) Dado um AFD, determinar se ele reconhece uma linguagem infinita.
e) Dados um AFD M e uma palavra w, determinar se M reconhece w.

Utilize o alfabeto {0, 1}.

4. Para cada um dos problemas de decisão do Exercı́cio 3, mostrar como seria a


sua representação esquemática, como foi feito na Figura 5.2 para o problema de
decisão do Exemplo 116.

5. Exiba as linguagens associadas ao PD “determinar se n é um número par menor


do que 10” para as duas representações apresentadas no Exemplo 115.
250 Editora Thomson Introdução aos fundamentos da computação

Tabela 5.1 Representações dos estados e sı́mbolos do alfabeto

Estado Representação Sı́mbolo de Γ Representação


e1 = i 1 a1 = h 1
e2 11 a2 = ⊔ 11
.. .. .. ..
. . . .
en 1n ak 1k

5.3 Uma Máquina de Turing Universal


Uma caracterı́stica indicativa do poder computacional das máquinas de Turing é a
possibilidade de construir máquinas de Turing capazes de simular qualquer máquina de
Turing.4 Em particular, pode-se simular as máquinas de Turing que são reconhecedoras
de linguagens, como é o caso daquelas que solucionam PDs.
Como assinalado na Seção 5.2, o primeiro passo para se construir uma máquina
de Turing que solucione um PD é conceber uma representação para suas instâncias.
De forma semelhante, o primeiro passo para se construir uma máquina de Turing que
simule qualquer máquina de Turing é conceber uma representação para máquinas de
Turing. O exemplo a seguir mostra uma representação possı́vel.

Exemplo 117 A seguir, será mostrada uma possı́vel representação de MTs, de forma
que estas possam ser supridas como entrada para outras MTs. O alfabeto usado na
representação será {0, 1}. Seja uma MT qualquer M = (E, Σ, Γ, h, ⊔, δ, i, F ), onde
E = {e1 , e2 , . . . , en } e Γ = {a1 , a2 , . . . , ak }. Suponha que e1 = i, a1 = h,a2 = ⊔ e
lembre-se de que Σ ⊂ Γ. Na Tabela 5.1 encontram-se as representações para os estados
e sı́mbolos do alfabeto de fita. Com referência à direção de movimentação do cabeçote,
D será representada por 1 e E por 11. Supondo que F = {f1 , f2 , . . . , fp } e designando
por Rhxi a representação de x, seja x um estado, um sı́mbolo de Γ ou direção de
movimentação do cabeçote, a representação de M tem os seguintes componentes:
• F é representado por uma lista das representações dos estados finais separados
por 0, ou seja, RhF i = Rhf1 i0Rhf2 i0 · · · Rhfp i;
• cada transição t da forma δ(ei , aj ) = [e′i , a′j , d] é representada pela palavra
Rhti = Rhei i0Rhaj i0Rhe′i i0Rha′j i0Rhdi.
Finalmente, sendo t1 , t2 , . . . , ts as transições de M , uma representação de M é:
RhM i = RhF i00Rht1 i00Rht2 i00 · · · Rhts i.

Um exemplo de representação de MT, usando a representação concebida no Exem-


plo 117, vem a seguir.
4
Inclusive elas próprias!
Newton José Vieira Capı́tulo 2: Máquinas de estados finitos 251

Exemplo 118 Seja a MT cujo diagrama de estados está ilustrado na Figura 4.4b,
página 210, cuja especificação é aqui reproduzida:

M = ({0, 1}, {a, b}, {h, ⊔, a, b}, h, ⊔, δ, 0, {0, 1})

com δ contendo somente as duas transições:

t1 : δ(0, a) = [1, a, D]
t2 : δ(1, b) = [0, b, E].

Então, uma representação para M poderia ser obtida assim:

• Estados: Rh0i = 1, Rh1i = 11.


• Sı́mbolos: Rhhi = 1, Rh⊔i = 11, Rhai = 111, Rhbi = 1111.
• Direção: RhDi = 1, RhEi = 11.
• Transição 1: Rht1 i = Rh0i0Rhai0Rh1i0Rhai0RhDi
= 10111011011101.
• Transição 2: Rht2 i = Rh1i0Rhbi0Rh0i0Rhbi0RhEi
= 11011110101111011.
• Estados finais: RhF i = 1011.
• RhM i = RhF i00Rht1 i00Rht2 i
= 101100101110110111010011011110101111011.

Uma máquina de Turing universal, uma MT que simula qualquer MT M , deve


receber como entrada, além de uma representação de M , uma representação de uma
palavra de entrada de M ; ou seja, deve receber como entrada, RhM, wi, onde w é
uma palavra no alfabeto de M . Assim, para complementar a representação mostrada
no Exemplo 117, deve-se projetar uma representação para w, palavra de M , para,
finalmente, especificar como é RhM, wi. Usando as mesmas convenções do Exemplo 117,
e supondo que w = ai1 ai2 . . . aiu , uma possibilidade é ter RhM, wi = RhM i000Rhwi,
onde RhM i é como especificado no exemplo e Rhwi = Rhai1 i0Rhai2 i . . . 0Rhaiu i.
Para efeitos de clareza, será especificada uma MT universal, U , de três fitas, sendo
que a primeira receberá a entrada de U , ou seja RhM, wi, a segunda vai fazer o papel
da fita de M , e a terceira vai conter apenas a representação do estado atual de M . Um
algoritmo que mostra o comportamento de uma MT universal é exibido na Figura 5.3.
No passo 1, Rhwi é copiada da fita 1 para a fita 2, inicializando, assim, a fita a ser
usada para simulação de M . No passo 2, Rhii = 1 é copiado na fita 3. Depois
dessas inicializações, U entra em um ciclo no passo 3, onde, em cada passo simula o
processamento de uma transição de M . No passo 3.3 U pesquisa por Rhei0Rhai na
fita 1, onde Rhai é a representação sob o cabeçote da fita 2 e Rhei é a representação
sob o cabeçote da fita 3. Se encontrar, U terá acesso, em sequência, a Rhe′ i, Rha′ i
e Rhdi, que serão usados nos passos 3.4.1, 3.4.2 e 3.4.3 para simular o processamento
de uma transição. Se não encontrar, U verifica, no passo 3.5.1, se Rhei na fita 3 é a
252 Editora Thomson Introdução aos fundamentos da computação

1. copie Rhwi na fita 2 e posicione cabeçote no inı́cio;


2. escreva Rhii na fita 3 e posicione cabeçote no inı́cio;
3. ciclo
3.1 seja Rhai a representação sob o cabeçote da fita 2;
3.2 seja Rhei a representação sob o cabeçote da fita 3;
3.3 procure Rhei0Rhai0Rhe′i0Rha′ i0Rhdi na fita 1;
3.4 se encontrou então
3.4.1 substitua Rhei por Rhe′ i na fita 3
e volte cabeçote da fita 3 ao seu inı́cio;
3.4.2 substitua Rhai por Rha′ i na fita 2;
3.4.3 mova cabeçote da fita 2 na direção d
3.5 senão
3.5.1 se e é estado final então
pare em estado final
senão
pare em estado não final
fimse
fimse
fimciclo.

Figura 5.3 Uma MT universal.

representação de um estado final; para isso, basta pesquisar no inı́cio da fita 1. Se e


for estado final, há aceitação, caso contrário, não haverá.
Concluindo, a MT U aceita a linguagem

L(U ) = {RhM, wi | w ∈ L(M )}.

Se o critério de reconhecimento considerado for por parada, tem-se duas “simpli-


ficações”:
• estados finais estarão ausentes de RhM, wi;
• o passo 3.5.1 de U (veja a Figura 5.3) será simplesmente: pare em estado final.
Chamando-se essa nova MT de UP , ter-se-ia que:

UP aceita RhM, wi se, e somente se, M para ao processar w,

ou seja,
L(UP ) = {RhM, wi | M para ao processar w}.
Veja que L(UP ) é uma linguagem associada ao PD “dada uma MT M e uma palavra
w, determinar se M para ao processar w”. Na seção a seguir, será mostrado que tal
linguagem não é recursiva. A MT universal pode ser usada como base para a construção
de outras MTs que reconheçam linguagens associadas a PDs que recebam MTs como
entrada. Segue um exemplo.

Exemplo 119 Uma MT que reconhece a linguagem {RhM i | λ ∈ L(M )}, uma lin-
guagem associada ao PD “dada uma MT M , determinar se λ ∈ L(M )”, seria obtida
Newton José Vieira Capı́tulo 2: Máquinas de estados finitos 253

simplesmente alterando o passo 1 da MT universal (ver Figura 5.3) para deixar a fita
2 em branco (ou seja, elimina-se o passo 1, simplesmente).

O exemplo anterior mostra que {RhM i | λ ∈ L(M )} é uma LRE. Na Seção 5.5 será
visto que tal linguagem também não é recursiva e que, portanto, o problema ao qual é
associada não é decidı́vel.

Exercı́cios
1. Faça um algoritmo que determine se uma palavra de {0, 1}∗ é da forma RhM, wi,
supondo a representação do Exemplo 117, página 250.

2. Seja a representação de MTs mostrada no Exemplo 117, página 250, onde o


alfabeto usado na representação é {0, 1}. Seja o problema de representar o par
(M, w), onde M é uma MT com alfabeto de entrada {0, 1} e, portanto, w ∈
{0, 1}∗ . Pode-se fazer RhM, wi = RhM i000w? Justifique.

3. Mostre que a linguagem {RhM, wi | existe estado e tal que M passe duas vezes
por e ao processar w} é recursiva.

4. Mostre que a linguagem {RhM i | L(M ) 6= ∅} é LRE.

5. Seja E um conjunto enumerável de MTs de alfabeto de entrada Σ. Suponha


que exista um algoritmo (MT que sempre pare) que, recebendo como entrada
RhM, wi, em que M ∈ E e w ∈ Σ∗ , determine se w ∈ L(M ). Mostre que nem
toda linguagem recursiva de alfabeto Σ é reconhecida por alguma MT de E.

5.4 O Problema da Parada


Nesta seção, será mostrado que o célebre problema da parada não é decidı́vel, tanto para
máquinas de Turing quanto para linguagens do tipo Pascal, C, Java etc. Nesse último
caso, será lançada mão de uma pseudolinguagem que contém algumas construções que
todas as linguagens de programação usuais têm de uma forma ou de outra.
O problema da parada para MTs pode ser assim enunciado:

Dadas uma MT arbitrária M e uma palavra arbitrária w, determinar se a


computação de M para ao processar w.

A existência de uma MT universal UP , que simula M processando w, prova que a


linguagem L(UP ) é LRE. Ao ser mostrado que o problema da parada é indecidı́vel, ter-
se-á mostrado, então, que não existe uma MT que sempre pare e que seja equivalente
à MT UP delineada no final da Seção 5.3, ou, de forma equivalente, que L(UP ) não
é recursiva.
254 Editora Thomson Introdução aos fundamentos da computação

M para ao processar w
sim
RhM, wi P
M não para ao processar w
não

Figura 5.4 MT candidata a resolver o problema da parada.

M para ao processar w
loop
RhM, wi P′
M não para ao processar w
para

Figura 5.5 MT obtida a partir da MT P .

Teorema 40 O problema da parada para MTs é indecidı́vel.


Prova
Será feita uma prova por contradição. Suponha que o problema seja decidı́vel. Nesse
caso, seja uma MT P que solucionasse o problema. Essa máquina que, recebendo
como entrada RhM, wi, sempre para e dá a resposta correta (sim, se M para se a
entrada for w; não, se M entra em loop se a entrada for w), seria como mostrado na
Figura 5.4, utilizando a notação introduzida na Seção 5.2. Ora, a partir de tal MT
P , seria possı́vel construir uma MT P ′ cujo comportamento se dá como exposto na
Figura 5.5, ou seja, P ′ entra em loop se, e somente se, P para em um estado final,
ou ainda,

P ′ entra em loop se, e somente se, M para ao processar w.

Para isso, basta fazer, para cada par (f, a) tal que δ(f, a) seja indefinido, onde f é
estado final de P e a sı́mbolo de fita de P , δ(f, a) = [l, a, D], onde l é um novo estado.
Nesse último estado, faz-se a máquina entrar em loop assim: δ(l, a) = [l, a, D] para todo
sı́mbolo de fita a de P . Estas seriam as únicas transições a acrescentar a P para se
obter P ′ .
A partir de P ′ , pode-se obter outra máquina, D, conforme ilustra a Figura 5.6.5 A
figura ilustra que D tem transições para (nesta ordem), a partir de uma entrada RhM i:

5
O nome D foi escolhido para lembrar diagonal, visto que a MT D tem uma forte “afinidade” com
o argumento da diagonalização, como será visto após a prova deste teorema.
Newton José Vieira Capı́tulo 2: Máquinas de estados finitos 255

D M para ao processar RhM i



✟ loop
RhM, RhM ii
RhM i RR P′
❍ M não para ao processar RhM i
❍ para

Figura 5.6 A MT D.

1. obter uma representação de RhM i e produzir RhM, RhM ii (via uma sub-MT
RR); e
2. agir como P ′ sobre a palavra produzida anteriormente.
Agora, considere o que acontece se RhDi for submetida como entrada para a MT D: se
D entra em loop ao processar RhDi, é porque D para ao processar RhDi; e se D para
ao processar RhDi, é porque D não para ao processar RhDi. Ou seja,
D para ao processar RhDi
se e somente se
D não para ao processar RhDi.
Contradição! Mas, D pode ser construı́da a partir de P . Assim, P não pode existir e,
portanto, o problema da parada para MTs é indecidı́vel.
Segue uma explicitação do argumento da diagonalização para mostrar que a MT D
do Teorema 40 não pode existir. Ora, D é uma MT que para ao processar RhM i se, e
somente se, M não para ao processar RhM i. Se for considerado que o conjunto das MTs
pode ser enumerado, como de fato é, obtendo-se uma sequência RhM0 i, RhM1 i,RhM2 i,
. . . , isso quer dizer que
D para ao processar RhMi i se, e somente se, Mi não para ao processar RhMi i
para todo i ≥ 0. Veja, então, que D se comporta de forma diferente de Mi ao processar
RhMi i para todo i ≥ 0 (veja a Figura 5.7)!
A prova de que o problema da parada para as linguagens de programação procedu-
rais comuns6 é indecidı́vel segue as mesmas linhas que a prova do Teorema 40, como
pode ser observado a seguir. Será usada uma pseudolinguagem de aparência similar à
que tem sido utilizada até aqui na representação dos algoritmos.
Teorema 41 O problema da parada para as linguagens de programação procedurais
comuns é indecidı́vel.
Prova
Suponha que o procedimento P solucione o PD em questão, de forma que a chamada
P (x, w) retorne verdadeiro se, e somente se, o procedimento de texto x para ao processar
6
Algumas linguagens de programação procedurais “comuns”: Java, C, Pascal.
256 Editora Thomson Introdução aos fundamentos da computação

MT/repr RhM0 i RhM1 i RhM2 i ···


M0 s ou n s ou n s ou n ···
M1 s ou n s ou n s ou n ···
M2 s ou n s ou n s ou n ···
..
. s ou n s ou n s ou n ···

D difere de Mi para todo i na diagonal.

Figura 5.7 D difere de toda Mi para RhMi i.

a entrada (também texto) w. No que segue, todos os parâmetros de procedimentos serão


assumidos como “textos”, não havendo indicação explı́cita disso nas suas codificações.
Utilizando-se tal procedimento P , pode-se escrever o seguinte procedimento:7
procedimento D(x):
enquanto P (x, x) faça
fimenquanto
fim D.
Seja T esse texto do procedimento D. Então: se D(T ) para é porque P (T, T ) retorna
falso, o que significa que D(T ) não para; assim, se D(T ) para, então D(T ) não para!
Por outro lado, se D(T ) não para é porque P (T, T ) retorna verdadeiro, o que significa
que D(T ) para; assim, se D(T ) não para, D(T ) para! Contradição! Conclui-se que a
função P não pode existir, ou seja, o problema em questão é indecidı́vel.8

A partir da existência da MT universal e da indecidibilidade do problema da parada


para MTs, chega-se aos teoremas descritos a seguir, que se utilizam da linguagem
associada a P ,
LP = {RhM, wi | M para ao processar w}.

Teorema 42 A linguagem LP não é recursiva.


Prova
Segue da indecidibilidade do problema da parada (Teorema 40).

O teorema seguinte diz que LP é LRE, ou seja, o problema da parada é semidecidı́vel.


7
Tal procedimento corresponde à MT D do Teorema 40.
8
Um procedimento P ′ correspondente à MT P ′ do Teorema 40 seria:

procedimento P ′ (x, w):


enquanto P (x, w) faça
fimenquanto
fim P ′ .

(Veja o Exercı́cio 2, página 257.)


Newton José Vieira Capı́tulo 2: Máquinas de estados finitos 257

Teorema 43 A linguagem LP é recursivamente enumerável.


Prova
Segue diretamente da existência da MT universal UP concebida no final da Seção 5.3:
L(UP ) = LP .

Assim, tem-se como consequência de ambos os Teoremas 42 e 43 que o conjunto das


linguagens recursivas é subconjunto próprio do conjunto das LREs.
Utilizando-se esse último resultado (a existência de LRE que não é recursiva) e o
Teorema 39, pode-se provar que existem linguagens não recursivamente enumeráveis.

Teorema 44 A linguagem LP não é recursivamente enumerável.


Prova
Suponha que LP seja LRE. Como, pelo Teorema 43, LP é LRE, segue-se, pelo Teo-
rema 39, que LP é recursiva. Mas isso contraria o Teorema 42, que diz que LP não é
recursiva. Logo, LP não é LRE.

Note que a prova do Teorema 44 dá um exemplo de linguagem que não é LRE: LP .

Exercı́cios
1. Mostre que o problema da parada para MTs com alfabeto de entrada unitário
é indecidı́vel.

2. Modifique a prova do Teorema 41 para incluir na demonstração o uso do proce-


dimento P ′ , transcrito a seguir, de forma que ela se assemelhe mais com a prova
do Teorema 40.

procedimento P ′ (x, w):


enquanto P (x, w) faça
fimenquanto
fim P ′ .

3. Explicite o uso do argumento da diagonalização para mostrar que o procedimento


P do Teorema 41 não pode existir, de forma análoga ao que foi feito em seguida
à prova do Teorema 40.

4. Prove que {RhM i | M para em menos de 1000 passos ao processar alguma palavra}
é recursiva, ou seja, que o problema de determinar se uma MT para em menos
de 1000 passos ao processar alguma palavra é decidı́vel.
5. Seja a linguagem {RhM, wi | M não para ao processar w}. Prove que essa lin-
guagem não é recursivamente enumerável. Observe que essa linguagem é LP ,
excluı́das as palavras que não estejam na forma RhM, wi.

6. Mostre que se o problema da parada fosse decidı́vel, então toda LRE seria recursiva.
258 Editora Thomson Introdução aos fundamentos da computação

MT para P

sim
x R y MT para Q
não

Figura 5.8 Solução de P por redução a Q.

5.5 Redução de um Problema a Outro


Em consonância com o Exercı́cio 3 da Seção 1.4, página 25, define-se que um PD P
é redutı́vel a um PD Q, se existe um algoritmo R que, recebendo x como entrada,
produz um resultado y tal que a resposta de P ao processar a entrada x seja idêntica
ou complementar à resposta de Q ao processar a entrada y, qualquer que seja a entrada
x.9 Diz-se, com isso, que o algoritmo R pode ser usado para reduzir o problema P ao
problema Q.
Usando-se essa definição, supondo os algoritmos expressos por meio de MTs, o PD
P pode ser solucionado mediante o algoritmo R e um algoritmo para o PD Q como
mostra a Figura 5.8. Nessa figura, assume-se que a resposta de P ao processar x é
idêntica à de Q ao processar y. No caso em que a resposta de P ao processar x é
complementar à resposta de Q ao processar y, a seta superior saindo da MT para Q
deve se dirigir para a saı́da não e a seta inferior deve se dirigir para a saı́da sim. A
máquina redutora R, processando a entrada x, produz y, que é recebida como entrada
pela MT que soluciona o PD Q. A partir dessas duas MTs, obtém-se, sem dificuldade,
uma terceira que soluciona P .
A redução de problemas pode ser usada, tanto para provar que um problema é
decidı́vel quanto para provar que um problema é indecidı́vel:
• Se P for redutı́vel a um problema decidı́vel, então P será decidı́vel.
• Se um problema indecidı́vel for redutı́vel a um problema P , então P será indecidı́vel.10
Segue um exemplo do primeiro tipo.

Exemplo 120 Seja o problema de determinar se w ∈ L(r), em que r é uma expressão


regular arbitrária. Esse problema é decidı́vel, já que pode ser reduzido ao problema,
decidı́vel, de se determinar se w ∈ L(M ), onde M é um AFD. A prova do Teorema 14,
na página 104, mostra como fazer a redução, ou seja, como construir um AFD Mr , a
partir de uma expressão regular r, tal que w ∈ L(Mr ) se, e somente se, w ∈ L(r).
9
Esse tipo de redução é denominado redução por mapeamento ou redução muitos-para-um.
10
Por outro lado, se um PD P pode ser reduzido a um problema indecidı́vel, P pode ser decidı́vel ou
não. E se um problema decidı́vel pode ser reduzido a P , P pode ser decidı́vel ou não.
Newton José Vieira Capı́tulo 2: Máquinas de estados finitos 259

RhM, wi R RhM ′ i

Figura 5.9 Redução do problema da parada ao da fita em branco.

A seguir, um exemplo do segundo tipo, ou seja, uma prova de que um problema


é indecidı́vel pela redução de um problema indecidı́vel a ele. O problema da fita em
branco é o de se determinar se uma MT arbitrária para quando a fita começa em branco.
Em outras palavras, dada uma MT M , arbitrária, determinar se M para ao processar
λ.

Teorema 45 O problema da fita em branco é indecidı́vel.


Prova
O problema da parada tem dois parâmetros: uma MT e uma palavra. Aqui, o problema
possui apenas um parâmetro: uma MT. Deve-se determinar se esta MT para ou não
ao processar a entrada especı́fica λ.
O problema da parada será reduzido ao da fita em branco, estabelecendo-se, assim,
a indecidibilidade do problema da fita em branco. A MT redutora (veja a Figura 5.9)
produz RhM ′ i, a partir de RhM, wi, de forma que:
1. M ′ escreve w;
2. M ′ volta o cabeçote para o inı́cio da fita;
3. M ′ se comporta como M , isto é, o resto da função de transição de M ′ é idêntico
à função de transição de M .
Com isso, tem-se que:

M para ao processar w se e somente se M ′ para ao processar λ.

A seguir, novamente é usada redução do problema da parada a outro para mostrar


que este é indecidı́vel.

Teorema 46 O problema de se determinar se w ∈ L(G), para uma gramática irrestrita


arbitrária G, e w ∈ Σ∗ , onde Σ é o alfabeto de G, é indecidı́vel.
Prova
O problema da parada pode ser reduzido a este empregando-se a técnica do Teorema 35,
página 231. Na Figura 5.10 está descrito que o algoritmo (MT) de redução, a partir
de M e w (RhM, wi) obtém uma gramática G e a mesma palavra w (RhG, wi). Esse
260 Editora Thomson Introdução aos fundamentos da computação

RhM, wi R RhG, wi

Figura 5.10 Redução do problema da parada ao da geração por gramática.

algoritmo de redução é dado pela técnica referida do Teorema 35, devendo-se considerar
todos os estados de M como estados finais (ou reconhecimento por parada), de forma
que M aceita w se e somente se M para ao processar w. Com isso, a gramática G é tal
que:

M para ao processar w se e somente se G gera w.

Daqui até o final do capı́tulo, vamos assumir que o critério de reconhecimento,


para todas as MTs mencionadas, é o de parada, ou, equivalentemente, que todos os
estados das MTs são estados finais. Assim, L(M ) será o mesmo que LP (M ). Isso
não introduz restrição significativa, visto que os vários critérios de reconhecimento são
inter-redutı́veis, como mostrado no Teorema 33, na página 213.
Voltando ao problema da fita em branco, note que ele pertence a uma classe de
problemas de decisão a respeito de MTs, isto é, PDs cujo único parâmetro é uma MT.
Felizmente, toda uma classe de PDs em que o único parâmetro é uma MT arbitrária
pode ser provada como contendo apenas problemas indecidı́veis. Todos eles têm o
seguinte tipo de enunciado:

Dada uma MT M , determinar se L(M ) satisfaz à propriedade P .

Veja que tal PD é decidı́vel se, e somente se, {RhM i | L(M ) satisfaz P } (a linguagem as-
sociada) é recursiva. No caso do problema da fita em branco, por exemplo, o enunciado
é (considera-se reconhecimento por parada):

Dada uma MT M , determinar se λ ∈ L(M ).

Esse problema é decidı́vel se, e somente se, a linguagem associada {RhM i | λ ∈ L(M )}
é recursiva. Logo, pelo Teorema 45, essa linguagem não é recursiva.
Para que todos os PDs da classe referida sejam indecidı́veis, basta expurgar dois
tipos de PDs que são, trivialmente, decidı́veis: aqueles em que a propriedade P é sempre
verdadeira e aqueles em que P é sempre falsa, ou seja, aqueles em que a linguagem
{RhM i | L(M ) satisfaz P } é constituı́da de todas as representações de MTs, e aqueles
em que {RhM i | L(M ) satisfaz P } é ∅. Daı́, a definição a seguir.
Newton José Vieira Capı́tulo 2: Máquinas de estados finitos 261

Definição 64 Uma propriedade P de LREs é trivial se for satisfeita por toda LRE ou
por nenhuma.

Exemplos de PDs que envolvem linguagens com propriedades triviais e que, por-
tanto, são (trivialmente) decidı́veis:

• Determinar se L(M ) ⊆ Σ∗ , em que Σ é o alfabeto de entrada de M . Toda LRE


satisfaz tal propriedade.
• Determinar se L(M ) é enumerável. Toda LRE é enumerável (afinal, toda lingua-
gem é).
• Determinar se L(M ) não é reconhecı́vel por parada. Nenhuma LRE é não reco-
nhecı́vel por parada.
• Determinar se existe M ′ tal que M ′ 6= M e L(M ′ ) = L(M ). Toda LRE tem essa
propriedade (ser reconhecı́vel por mais de uma MT).

Já considerando o problema da fita em branco, a propriedade λ ∈ L(M ) não é trivial,


pois algumas LREs contêm λ e outras, não. Outros exemplos de PDs da classe em
consideração que, portanto, envolvem propriedades não triviais:

• Determinar se L(M ) contém alguma palavra.


• Determinar se L(M ) contém todas as palavras em Σ∗ .
• Determinar se L(M ) é finita.
• Determinar se L(M ) é regular.
• Determinar se L(M ) contém palavra começada com 0.

Antes de apresentar o Teorema de Rice, que mostra que tais problemas são in-
decidı́veis, assim como qualquer outro no formato geral apresentado anteriormente,
será mostrado à parte que o primeiro problema citado é indecidı́vel, utilizando-se uma
técnica que modifica um pouquinho aquela usada no problema da fita em branco.

Teorema 47 Não existe algoritmo para se determinar se a linguagem aceita por uma
MT arbitrária M não é ∅.
Prova
O problema da parada será reduzido a este de forma similar ao que foi feito para o
problema da fita em branco no Teorema 45. A MT redutora produz RhM ′ i, a partir
de RhM, wi, de forma que:

1. M ′ apaga a entrada;
2. M ′ escreve w;
3. M ′ volta o cabeçote para o inı́cio da fita;
4. M ′ se comporta como M (isto é, o resto da função de transição de M ′ é idêntico
à função de transição de M ).
262 Editora Thomson Introdução aos fundamentos da computação

Observe que a única diferença, com relação a M ′ produzida pela redução no Teorema 45,
é que aqui há um passo anterior: M ′ apaga a entrada que está na fita. Com isso, M ′
ignora qualquer entrada que seja submetida, e se comporta sempre como M com a
entrada w. Assim, tem-se que:
M para ao processar w se e somente se M ′ para ao processar alguma palavra.
É interessante notar que a mesma redução serve para provar o segundo PD citado
anteriormente, já que M ′ parando com alguma entrada, para com todas, e vice-versa:

M ′ para ao processar alguma palavra se, e somente se, M ′ para ao processar qual-
quer entrada.
Segue o Teorema de Rice.
Teorema 48 ( Teorema de Rice) Se P for uma propriedade não trivial de LREs, então
{RhM i | L(M ) satisfaz P } não será recursiva.
Prova
Seja P uma propriedade não trivial.
Caso 1 ∅ não satisfaz P . Seja uma MT MX tal que L(MX ) satisfaz P . Tal MT MX
existe, pois P é não trivial. Observe também que L(MX ) 6= ∅, pois ∅ não satisfaz P .
O problema da parada pode ser reduzido ao de se determinar se L(M ′ ) satisfaz P ,
por meio de uma MT que produz RhM ′ i a partir de RhM, wi, onde:
1. M ′ escreve w na fita, após a entrada para M ′ ; suponha, então, que a fita fique
assim: hx[w ⊔ . . ., onde “h” é o sı́mbolo de inı́cio de fita para M ′ , x refere-se à
palavra de entrada para M ′ , e “[” faz o papel de sı́mbolo de inı́cio de fita para a
simulação de M no passo a seguir;
2. M ′ se comporta como M sobre [w ⊔ . . .;
3. na situação em que M para, M ′ se comporta como MX sobre hx ⊔ . . ..
Observe que
L(M ′ ) satisfaz P se e somente se M para ao processar w,
pois:
• Se M para ao processar w, L(M ′ ) = L(MX ); portanto, L(M ′ ) satisfaz P .
• Se M não para ao processar w, L(M ′ ) = ∅; dada a suposição inicial desse caso,
então L(M ′ ) não satisfaz P .
Dessa forma, conclui-se que {RhM i | L(M ) satisfaz P e ∅ não satisfaz P } não é recur-
siva.
Caso 2 ∅ satisfaz P . Nesse caso, ∅ não satisfaz ¬P . E como P não é trivial, ¬P
também não é trivial. Pela argumentação do caso 1, {RhM i | L(M ) satisfaz ¬P } não
é recursiva. Como essa linguagem é o complemento 11 de {RhM i | L(M ) satisfaz P } e
as linguagens recursivas são fechadas sob complementação,12 segue-se que a linguagem
11
É o complemento com relação ao conjunto das palavras da forma RhM i, que é recursivo.
12
Mesmo relativa a conjunto recursivo, como pode ser facilmente verificado.
Newton José Vieira Capı́tulo 2: Máquinas de estados finitos 263

{RhM i | L(M ) satisfaz P e ∅ satisfaz P } não é recursiva.


Logo, se P é uma propriedade não trivial de LREs, então {RhM i | L(M ) satisfaz P }
não é recursiva.

Algumas linguagens da forma {RhM i | L(M ) satisfaz P }, em que P não é trivial,


são LREs e outras não são. Por exemplo, {RhM i | λ ∈ L(M )} é LRE (a MT universal
processando unicamente a palavra λ a reconhece). Já a linguagem {RhM i | λ 6∈ L(M )}
não é LRE (se fosse, a anterior seria recursiva pelo Teorema 39). Veja que uma maneira
de mostrar que uma linguagem associada a um PD não é LRE é mostrar que a linguagem
associada ao PD complementar é LRE não recursiva. Uma outra é reduzir um problema
cuja linguagem associada é sabidamente não LRE ao problema cuja linguagem associada
é a linguagem em questão.
Na próxima seção, vários problemas indecidı́veis relativos a GLCs serão apresenta-
dos. Antes, porém, o problema da parada será reduzido a um problema “intermediário”,
o qual servirá como ponto de partida para a abordagem daqueles PDs relativos a GLCs.
Tal problema é o denominado problema da correspondência de Post.

Definição 65 Um sistema de correpondência de Post (SCP ) é um par (Σ, P ), onde P


é uma sequência finita de pares (x, y) em que x, y ∈ Σ+ .

Uma solução para um SCP S = (Σ, P ) é uma sequência finita de pares de P tal que
a palavra formada pela concatenação dos primeiros elementos dos pares seja idêntica
àquela formada pela concatenação dos segundos elementos dos mesmos pares. Observe
que cada par pode aparecer várias vezes na sequência. Segue uma definição mais formal.

Definição 66 Seja um SCP S = (Σ, [(x1 , y1 ), (x2 , y2 ), . . . , (xn , yn )]). Uma solução
para S é uma sequência i1 , i2 , . . . , ik tal que

x i1 x i2 . . . x ik = y i1 y i2 . . . y ik ,

onde 1 ≤ ij ≤ n para 1 ≤ j ≤ k.

A seguir, um exemplo de SCP e soluções para o mesmo.

Exemplo 121 Seja o SCP ({0, 1}, [(10, 0), (0, 010), (01, 11)]). Esse SCP tem três pa-
res: (x1 = 10, y1 = 0), (x2 = 0, y2 = 010) e (x3 = 01, y3 = 11) . Uma solução seria
a sequência 2131, pois x2 x1 x3 x1 = y2 y1 y3 y1 : 0 10 01 10 = 010 0 11 0. Para maior
clareza, pode ser conveniente apresentar cada par (xi , yi ) na forma xyii . Nesse caso, a
solução referida pode ser apresentada assim:
0 10 01 10
.
010 0 11 0
Além destas, quaisquer quantidades de justaposições da sequência anterior formam
soluções. Exemplos: 21312131, 213121312131 etc.
264 Editora Thomson Introdução aos fundamentos da computação

parada PCPM PCP

RhM, wi R RhSi R′ RhS ′ i

Figura 5.11 Reduções para o PCP.

O PD a ser abordado, o problema da correspondência de Post (PCP), é: determinar


se um SCP arbitrário tem solução. Será demonstrado que esse problema é indecidı́vel
em dois passos: primeiramente, um PD similar ao PCP, denominado PCP modificado
(PCPM), será reduzido ao PCP; em seguida, o problema da parada será reduzido ao
PCPM. A Figura 5.11 esquematiza as reduções a serem feitas.
O problema da correspondência de Post modificado (PCPM), é: determinar se
um SCP arbitrário tem solução iniciada com 1. Ou seja, dado um SCP S =
(Σ, [(x1 , y1 ), (x2 , y2 ), . . . , (xn , yn )]), no PCPM a solução para S deve ser uma sequência
iniciada com 1: 1, i2 , . . . , ik , tal que

x 1 x i2 . . . x ik = y 1 y i2 . . . y ik ,

onde 1 ≤ ij ≤ n para 2 ≤ j ≤ k (observe que o par (x1 , y1 ) pode ser reutilizado).

Exemplo 122 Seja o SCP ({0, 1}, [(0, 010), (10, 0), (01, 11)]), obtido do SCP do Exem-
plo 121 invertendo-se o primeiro e o segundo pares. Uma solução para esse SCP, que
satisfaz os requisitos do PCPM, seria: 1232.
Já o SCP do Exemplo 121, ({0, 1}, [(10, 0), (0, 010), (01, 11)]), não tem solução que
satisfaça os requisitos do PCPM, pois no primeiro par uma palavra começa com 1 e a
outra com 0.

Teorema 49 O PCPM é redutı́vel ao PCP.


Prova
Seja um SCP S = (Σ, P ) com P = [(x1 , y1 ), (x2 , y2 ), . . . , (xn , yn )]. Seja “∗” um sı́mbolo
não pertencente a Σ, e sejam:

• x′i o resultado de colocar “∗” após cada sı́mbolo de xi . Por exemplo, se xi = 11010,
então xi = 1 ∗ 1 ∗ 0 ∗ 1 ∗ 0∗.
• yi′ o resultado de colocar “∗” antes de cada sı́mbolo de yi . Por exemplo, se
yi = 0100, então yi = ∗0 ∗ 1 ∗ 0 ∗ 0.
Seja “#” um sı́mbolo não pertencente a Σ, e seja o SCP S ′ = (Σ ∪ {∗, #}, P ′ ), onde P ′
é constituı́do por n + 2 pares:
Newton José Vieira Capı́tulo 2: Máquinas de estados finitos 265

• (∗x′1 , y1′ ) (a ser o primeiro par de uma solução);


• (x′i , yi′ ) para 1 ≤ i ≤ n; e
• (#, ∗#).

Será mostrado, conforme requerido, que S apresenta solução começada com (x1 , y1 ) se,
e somente se, S ′ tiver solução:
(→) Suponha que S tenha solução iniciada com (x1 , y1 ), e seja 1, i2 , . . . , ik uma solução
arbitrária de S, onde 1 ≤ ij ≤ n para 2 ≤ j ≤ k. Nesse caso, uma solução para S ′ seria
(mostrando-se os pares em vez de ı́ndices):

∗x′1 x′i2 x′i3 x′ik #


· · · .
y1′ yi′2 yi′3 yi′k ∗#

(←) Suponha que S ′ tenha solução. O único par de P ′ cujos elementos começam com o
mesmo sı́mbolo é (∗x′1 , y1′ ), e o único par de P ′ cujos elementos terminam com o mesmo
sı́mbolo é (#, ∗#). Assim, uma solução para S ′ só pode ter a forma

∗x′1 x′i2 x′i3 x′ik #


· · · .
y1′ yi′2 yi′3 yi′k ∗#

Além disso, existe uma solução dessa forma em que (∗x′1 , y1′ ) acontece apenas no inı́cio
e (#, ∗#) ocorre apenas no final. Assim,
x 1 x i2 x i3 xi
··· k
y 1 y i2 y i3 y ik

é uma solução para S, e esta, necessariamente, começa com (x1 , y1 ).

Para provar que o PCPM é indecidı́vel, no Teorema 50, o problema da parada


será reduzido a ele. Para isso, dada uma MT M qualquer e uma palavra w, deve-se
construir um SCP S que tenha solução iniciada por certo par se, e somente se, M para
ao processar w. A idéia a ser usada é construir S de forma que, havendo uma solução
para S,
x 1 x i2 xi
··· k,
y 1 y i2 y ik
ela seja tal que x1 xi2 · · · xik “represente” a computação de M para a palavra de entrada
w. Além disso, a solução deve existir somente se M parar ao processar w.

Teorema 50 Não existe algoritmo para o PCPM.


Prova
O problema da parada será reduzido ao PCPM. Seja uma MT M = (E, Σ, Γ, δ, i) e
uma palavra w ∈ Σ∗ . A partir destas, será produzido um SCP S = (∆, P ), onde:

• ∆ = E ∪ Γ ∪ {∗, #};
266 Editora Thomson Introdução aos fundamentos da computação

• o primeiro elemento de P é (∗, ∗hiw∗);


• os pares restantes de P são:

a) (c, c), para cada c ∈ Γ;


(∗, ∗).
b) Para cada a, b ∈ Γ e e, e′ ∈ E:
(ea, be′ ), se δ(e, a) = [e′ , b, D];
(e∗, be′ ∗), se δ(e, ⊔) = [e′ , b, D];
(cea, e′ cb), se δ(e, a) = [e′ , b, E], para cada c ∈ Γ;
(ce∗, e′ cb∗), se δ(e, ⊔) = [e′ , b, E], para cada c ∈ Γ.
c) (ea, #), se δ(e, a) é indefinido, para cada e ∈ E e a ∈ Γ;
(e∗, #∗), se δ(e, ⊔) é indefinido, para cada e ∈ E.
d) (c#, #) para cada c ∈ Γ;
(#c, #) para cada c ∈ Γ.
e) (∗#∗, ∗).

Pode-se mostrar que M para ao processar w se, e somente se, o SCP S tem solução
iniciada com (∗, ∗hiw∗).

A seguir, mostra-se um exemplo do uso da técnica desenvolvida na prova do


Teorema 50.

Exemplo 123 Seja a MT cujo diagrama de estados está representado na Figura 4.4b,
página 210, supondo o alfabeto de entrada como sendo {a, b}. A partir dela e da palavra
w = aab, pode-se construir, usando a técnica do Teorema 50, um SCP cujo primeiro
par é (∗, ∗h1aab∗) e os restantes são:

a) (h, h), (⊔, ⊔),(a,a),(b,b);


(∗, ∗).
b) (1a, a2),
(h2b, 1hb), (⊔2b, 1 ⊔ b), (a2b, 1ab), (b2b, 1bb).
c) (1h, #), (1⊔, #), (1b, #),
(2h, #), (2⊔, #), (2a, #),
(1∗, #∗), (2∗, #∗).
d) (h#, #), (⊔#, #), (a#, #), (b#, #),
(#h, #), (#⊔, #), (#a, #), (#b, #),
e) (∗#∗, ∗).

Uma solução para o SCP apresentado, espelhando uma computação de M com a palavra
aab, seria construı́da, passo a passo, assim:
Newton José Vieira Capı́tulo 2: Máquinas de estados finitos 267

• Começa-se com o par inicial:



∗h1aab∗
• Coloca-se o par (h, h), e, em seguida, (1a, a2):
∗h1a
∗h1aab ∗ ha2

• Colocam-se os pares (a, a), (b, b), (∗, ∗), (h, h) e (a, a):
∗h1aab ∗ ha
∗h1aab ∗ ha2ab ∗ ha

• Coloca-se o par (2a, #):


∗h1aab ∗ ha2a
∗h1aab ∗ ha2ab ∗ ha#
• Colocam-se os pares (b, b), (∗, ∗), (h, h) e (a, a):
∗h1aab ∗ ha2ab ∗ ha
∗h1aab ∗ ha2ab ∗ ha#b ∗ ha

• Coloca-se o par (#b, #):


∗h1aab ∗ ha2ab ∗ ha#b
∗h1aab ∗ ha2ab ∗ ha#b ∗ ha#

• Colocam-se os pares (∗, ∗) e (h, h):


∗h1aab ∗ ha2ab ∗ ha#b ∗ h
∗h1aab ∗ ha2ab ∗ ha#b ∗ ha# ∗ h

• Coloca-se o par (a#, #):


∗h1aab ∗ ha2ab ∗ ha#b ∗ ha#
∗h1aab ∗ ha2ab ∗ ha#b ∗ ha# ∗ h#

• Coloca-se o par (∗, ∗) e (h#, #):


∗h1aab ∗ ha2ab ∗ ha#b ∗ ha# ∗ h#
∗h1aab ∗ ha2ab ∗ ha#b ∗ ha# ∗ h# ∗ #

• Para finalizar, coloca-se o par (∗#∗, ∗):


∗h1aab ∗ ha2ab ∗ ha#b ∗ ha# ∗ h# ∗ #∗
∗h1aab ∗ ha2ab ∗ ha#b ∗ ha# ∗ h# ∗ #∗
268 Editora Thomson Introdução aos fundamentos da computação

Partindo-se da indecidibilidade do PCP, pode-se provar, com facilidade, que vários


problemas relativos a gramáticas livres do contexto são indecidı́veis. Esse é o assunto
da próxima seção.

Exercı́cios
1. Para cada PD a seguir, mostre que o mesmo é decidı́vel:

a) dada uma MT M , determinar se M escreve algum sı́mbolo diferente do


branco, ao processar λ;
b) dada uma MT M , determinar se M vai mover o cabeçote para a esquerda
alguma vez, ao processar λ.

2. Para cada PD a seguir, mostre que o mesmo é indecidı́vel:

a) dados uma MT M , uma palavra w e um estado e de M , determinar se a


computação de M ao processar w atinge o estado e;
b) dados uma MT M e um estado e de M , determinar se a computação de M
ao processar λ atinge o estado e;
c) dada uma MT M , determinar se a computação de M ao processar λ “volta”
ao estado inicial de M ;
d) dados uma MT M e um sı́mbolo a de M , determinar se a computação de
M ao processar λ escreve a na fita em algum momento;
e) dados uma MT M e uma expressão regular r, determinar se L(M )∩L(r) 6= ∅.

3. Mostre que é decidı́vel ou que não é: dada uma MT M , determinar se a com-
putação de M percorre alguma transição da forma δ(e, a) = [e, b, d] (um laço),
quando a fita é iniciada em branco.

4. Reduza o problema da parada para as linguagens de alto nı́vel (determinar se um


programa P para ao processar a entrada w) ao problema de se determinar se um
programa (sem entrada) para (determinar se um programa P para).

5. Seja o problema: dada uma MT M , determinar se x ∈ L(M ), onde x é uma


palavra especı́fica. (Observe que o único parâmetro desse problema é M .)

a) Pode-se usar o Teorema de Rice para mostrar que esse problema é inde-
cidı́vel? Justifique.
b) Reduza o problema da parada a este.
c) A linguagem Lx = {RhM i | x ∈ L(M )} é LRE? Justifique.

6. Mostre que os seguintes problemas são decidı́veis ou não:

a) Dada uma MT M , determinar se ela é a única que reconhece L(M );


b) Dada uma MT M , determinar se RhM i ∈ L(M );
Newton José Vieira Capı́tulo 2: Máquinas de estados finitos 269

c) Dadas MTs M1 e M2 , determinar se λ ∈ L(M1 ) ∪ L(M2 );


d) Dada uma MT M , determinar se L(M ) = {RhM i};
e) Dada uma MT M , determinar se há alguma palavra com menos de 100
sı́mbolos reconhecida por M ;
f ) Dada uma MT M , determinar se ela para ao processar algum palı́ndromo.

7. Pelo Teorema de Rice, as seguintes linguagens não são recursivas:

a) {RhM i | |L(M )| ≤ 2};


b) {RhM i | |L(M )| > 2};
c) {RhM i | |L(M )| = 2}.

Para cada uma delas mostre que ela é LRE ou que não é.

8. Seja a MT M = ({A, B, C}, {0, 1}, {h, ⊔, 0, 1}, h, ⊔, δ, A), onde δ é dada por:

δ(A, 0) = [A, 0, D], δ(B, 1) = [A, 1, D], δ(C, 1) = [C, ⊔, E],


δ(A, 1) = [B, 1, D], δ(B, ⊔) = [C, 1, E].

a) Construa um SCP a partir de M e w = 0011, como indicado na prova do


Teorema 50.
b) Mostre como é obtida uma solução para o SCP construı́do.

9. Prove que o PCP para SCPs com alfabeto de um único sı́mbolo é decidı́vel.

10. Dado um SCP S, seja L(S) a linguagem constituı́da de todas as soluções para
S. Ou seja, se S = (∆, P ), sendo P = [(x1 , y1 ), (x2 , y2 ), . . . , (xn , yn )], então
L(S) = {i1 i2 . . . ik | xi1 xi2 . . . xik = yi1 yi2 . . . yik }. Existe algoritmo que, dado um
SCP S arbitrário, seja capaz de produzir uma GLC G tal que L(G) = L(S)?

5.6 Alguns Problemas Indecidı́veis Sobre GLCs


A seguir, será mostrado como construir duas GLCs, Gx e Gy , a partir de qualquer
SCP, que são úteis para provar que alguns problemas de decisão relativos a GLCs não
têm solução. Assim, seja um SCP S = (Σ, P ), onde P tem n pares (x1 , y1 ), (x2 , y2 ),
. . . , (xn , yn ). Sejam também n sı́mbolos distintos s1 , s2 , . . . , sn , sendo que nenhum é
membro de Σ. Esses últimos servem para “indexar” os pares. Assim, s1 indexa (x1 , y1 ),
s2 indexa (x2 , y2 ) etc. Seguem as definições das duas GLCs:

• Gx = ({Px }, Σ ∪ {s1 , s2 , . . . , sn }, Rx , Px ), onde Rx consta das 2n regras:

Px → xi Px si , para cada 1 ≤ i ≤ n, e
Px → xi si , para cada 1 ≤ i ≤ n.

• Gy = ({Py }, Σ ∪ {s1 , s2 , . . . , sn }, Ry , Py ), onde Ry consta das 2n regras:


270 Editora Thomson Introdução aos fundamentos da computação

RhSi R RhGx , Gy i

Figura 5.12 Redução do PCP à disjunção de LLCs.

Py → yi Py si , para cada 1 ≤ i ≤ n, e
Py → yi si , para cada 1 ≤ i ≤ n.

Veja que se i1 i2 . . . ik é uma solução de S, então


∗ ∗
Px ⇒ xi1 xi2 . . . xik sik . . . si2 si1 e Py ⇒ yi1 yi2 . . . yik sik . . . si2 si1
e x i1 x i2 . . . x ik = y i1 y i2 . . . y ik .

e vice-versa. Conclui-se, então, que:

S tem solução se, e somente se, L(Gx ) ∩ L(Gy ) 6= φ.

Isso permite concluir o resultado a seguir.

Teorema 51 Não existe algoritmo para determinar se as linguagens de duas GLCs


são disjuntas.
Prova
O PCP pode ser reduzido a este, construindo-se Gx e Gy , conforme esquematizado na
Figura 5.12, de forma que um SCP S tenha solução se, e somente se, L(Gx )∩L(Gy ) 6= φ.

Embora as LLCs não sejam fechadas sob complementação, o fato é que existem
GLCs para L(Gx ) e L(Gy ) (veja o Exercı́cio 3 no final desta seção, página 271). Com
base nisso, segue o próximo teorema.

Teorema 52 Não existe algoritmo para determinar se L(G) = Σ∗ , para uma GLC G
arbitrária.
Prova
O PCP pode ser reduzido a este, construindo-se uma GLC para L(Gx ) ∪ L(Gy ), pois:

L(Gx ) ∪ L(Gy ) = Σ∗ se, e somente se, S não tem solução,

pois:
Newton José Vieira Capı́tulo 2: Máquinas de estados finitos 271

L(Gx ) ∪ L(Gy ) = Σ∗ ↔ L(Gx ) ∪ L(Gy ) = φ


↔ L(Gx ) ∩ L(Gy ) = φ
↔ S não tem solução.

Teorema 53 Não existe algoritmo para determinar se uma GLC arbitrária é ambı́gua.

Prova
O PCP pode ser reduzido a este, produzindo-se, a partir de um SCP S, a gramática

G = ({P, Px , Py }, Σ ∪ {s1 , s2 , . . . , sn }, Rx ∪ Ry ∪ {P → Px , P → Py }, P )

pois:

G é ambı́gua se, e somente se, L(Gx ) ∩ L(Gy ) 6= φ.

Exercı́cios
1. Mostre que é decidı́vel ou que não é:
a) Dados um conjunto finito F e uma GLC G, determinar se F ⊆ L(G);
b) Dadas uma GR R e uma GLC G, determinar se L(G) ⊆ L(R);
c) Dadas uma GR R e uma GLC G, determinar se L(R) ⊆ L(G);
d) Dada uma GR R, determinar se R é ambı́gua.
2. Construa as gramáticas Gx e Gy , como definidas no inı́cio da seção, correspon-
dentes ao SCP ({0, 1}, P ), onde P consta dos pares (01, 011), (001, 01), (10, 00).
3. Escreva uma gramática para a linguagem L(Gx ), onde Gx é a GLC definida no
inı́cio da seção.
4. Mostre que o seguinte problema é ou não decidı́vel: dadas uma GR GR e uma
GLC GL , determinar se L(GR ) ∩ L(GL ) = ∅.
5. Mostre que o seguinte problema é ou não decidı́vel: dadas duas GLCs G1 e G2 ,
cada uma com uma única variável, determinar se L(G1 ) ∩ L(G2 ) = ∅.
6. Mostre que o seguinte problema não é decidı́vel: dadas duas GLCs G1 e G2 ,
determinar se L(G1 ) ∩ L(G2 ) é finito.
7. Mostre que o seguinte problema não é decidı́vel: dada uma GLC G, determinar
se L(G) é finito.
8. Mostre que são indecidı́veis os problemas de se determinar, dadas duas GLCs G1
e G2 , que:
a) L(G1 ) = L(G2 );
b) L(G1 ) ⊆ L(G2 ).
272 Editora Thomson Introdução aos fundamentos da computação

5.7 Exercı́cios Adicionais


1. Um sistema de Post é uma quı́ntupla (V, ΣN , ΣT , R, A), onde:

• V é um alfabeto de variáveis;
• ΣN é um alfabeto de não terminais, disjunto de V;
• ΣT é um alfabeto de terminais, disjunto de ΣN e de V;
• R é um conjunto finito de regras; e
• A é um subconjunto finito de (ΣN ∪ ΣT )∗ cujos elementos são chamados
axiomas.

Cada regra é da forma u → v, onde u, v ∈ (V ∪ ΣN ∪ ΣT )∗ , nenhuma variável


acontece mais de uma vez em u, e cada variável em v deve ocorrer em u. Dada
uma palavra da forma (que pode ser uma axioma ou palavra já derivada):

x0 z0 x1 z1 . . . zn−1 xn , onde xi , zj ∈ (ΣN ∪ ΣT )∗ para cada i e j

e uma regra da forma:

x0 V0 x1 V1 . . . Vn−1 xn → v, onde Vj ∈ V para cada j,

pode-se derivar v ′ aplicando-se tal regra, ou seja, tem-se que:

x0 z0 z1 x1 . . . zn−1 xn ⇒ v ′

onde v ′ é o resultado de substituir em v cada ocorrência de Vj por zj , para


0 ≤ j < n. A linguagem gerada por um sistema de Post P = (V, ΣN , ΣT , R, A) é
definida como:

L(P ) = {w ∈ Σ∗T | x ⇒ w para algum x ∈ A}.

Por exemplo, sendo P = ({X}, ∅, {a, b}, {X → aXb}, {λ}), tem-se que L(P ) =
{an bn | n ≥ 0}, pois:

λ ⇒ ab ⇒ aabb ⇒ · · · ⇒ an bn .

a) Construa sistemas de Post que gerem:


i) {wwR | w ∈ {a, b}∗ };
ii) {an bn cn | n ≥ 0};
iii) {ww | w ∈ {a, b}∗ }.
b) Mostre que uma linguagem é LRE se, e somente se, existe um sistema de
Post que a gera.

2. Mostre que o seguinte problema é indecidı́vel: dada uma máquina de Turing M ,


determinar se M move seu cobeçote para o inı́cio da fita (local em que está o
sı́mbolo especial “h”) em algum momento.
Newton José Vieira Capı́tulo 2: Máquinas de estados finitos 273

3. Para cada PD a seguir, mostre que o mesmo é ou não é decidı́vel:


a) Determinar se L(A) ∩ L(P ) = ∅, para um AF A e um AP P .
b) Determinar se L(A) = L(P ), para um AF A e um AP P .
c) Determinar se L(A) ∩ L(M ) = ∅, para um AF A e uma MT M .
d) Determinar se L(A) = L(M ), para um AF A e uma MT M .
e) Determinar se existe uma MT M que reconhece L(r), para uma ER r.
f) Determinar se existe uma ER r que denota L(M ), para uma MT M .
4. Seja n uma constante. Seja Bn = {RhM i | M tem n estados e para ao processar
λ}. Determine se as linguagens a seguir são recursivas ou não:
a) Bn , para cada n ≥ 1;
b) ∪n>0 Bn .
5. Seja Bn como definido na questão 4. Seja t : N → N tal que t(n) é o número
de transições de uma MT de Bn de forma que nenhuma outra MT de Bn realize
mais transições quando a entrada for λ. Mostre que:
a) t(n) é definida para todo n;
b) t não é computável. Para isso, mostre que se existisse uma MT que calculasse
t(n) para todo n, ela poderia ser usada para resolver o problema da fita em
branco (página 259).
6. Seja o seguinte PD: dadas duas MTs M1 e M2 que entrem em loop ao processar λ,
determinar se existe um número natural n tal que a distância (número de células)
máxima entre os cabeçotes de M1 e M2 é n quando M1 e M2 processarem λ em
paralelo (ou seja, quando ambas efetuarem a k-ésima transição ao mesmo tempo
para todo k ≥ 1); veja figura abaixo. Mostre que tal PD é indecidı́vel.

M1 : h ···

distância atual: 8
M2 : h ···

(O conteúdo das fitas não é mostrado por ser irrelevante.)
7. Mostre que o PCP para SCPs com alfabeto de dois sı́mbolos é indecidı́vel. Para
isso, reduza o PCP a este problema.
8. Conclua a prova do Teorema 50, isto é, mostre que M para ao processar w se, e
somente se, o SCP S tem solução iniciada com (∗, ∗hiw∗).
9. Um sistema semi-Thue é um par S = (Σ, R), em que Σ é um alfabeto e R é um
conjunto de regras da forma u → v, onde u ∈ Σ+ e u ∈ Σ∗ . Seja o seguinte
problema associado a sistemas semi-Thue:
274 Editora Thomson Introdução aos fundamentos da computação

Dados um sistema semi-Thue S e duas palavras x ∈ Σ+ e y ∈ Σ∗ ,


determinar se y pode ser derivada a partir de x.
A noção de derivação aqui é similar àquela usada no contexto de gramáticas, em
que cada passo da derivação resulta da aplicação de uma regra. Mostrar que o
PD enunciado anteriormente é indecidı́vel, reduzindo:

a) o problema da parada para MTs a ele;


b) o problema de se determinar se uma gramática irrestrita G gera uma palavra
w a ele.

10. Seja Gx uma GLC obtida como mostrado no inı́cio da Seção 5.6, página 269.
Descreva APs para reconhecer:

a) L(Gx );
b) L(Gx ).

11. Pelo Teorema de Rice, as seguintes linguagens não são recursivas:


a) {RhM i | L(M ) aceita uma palavra de tamanho 10};
b) {RhM i | L(M ) 6= ∅};
c) {RhM i | L(M ) = ∅};
d) {RhM i | não existe palavra de prefixo 0 em L(M )};
e) {RhM i | L(M ) é finita};
f) {RhM i | L(M ) é infinita};
g) {RhM i | ambas L(M ) e L(M ) são infinitas};
h) {RhM i | L(M ) é regular}.

Elas são recursivamente enumeráveis?

5.8 Notas Bibliográficas


O primeiro autor a formular a denominada tese de Church-Turing foi Church (1936),
seguido por Turing (1936). Ainda nessa época (Turing, 1936), aparecem também as
máquinas de Turing universais e uma prova da indecidibilidade do problema da parada.
As funções recursivas, o λ-cálculo e os sistemas de Post, formalismos equivalentes
ao de MT em termos de expressividade, foram introduzidos por Kleene (1952), Church
(1941) e Post (1943), respectivamente.
Referências importantes sobre decidibilidade após o aparecimento dos primeiros
computadores são Davis (1958), Rogers (1967) e Minsky (1967).
O Teorema de Rice foi demonstrado por Rice (1953; 1956).
O problema da correspondência de Post foi mostrado ser indecidı́vel em Post (1946).
Várias propriedades indecidı́veis com relação a linguagens livres do contexto fo-
ram apresentadas por Bar-Hillel et al. (1961), Ginsburg e Rose (1963b) e Hartmanis e
Hopcroft (1968).

Você também pode gostar