tema 5 1 - Decidibilidade

Prévia do material em texto

Decidibilidade
Apresentação
O termo “determinável” refere-se a um problema de tomada de decisão, isto é, se existe um 
método eficaz para determinar a correlação em um conjunto de fórmulas. Se a relevância 
do conjunto de fórmulas logicamente válidas pode ser determinada com eficácia, então o sistema 
lógico é decidível. Se houver um algoritmo eficaz para determinar se alguma fórmula pertence a ele, 
então uma teoria em um sistema lógico fixo (um conjunto de fórmulas fechadas sob um resultado 
lógico) pode ser determinada, embora muitas questões importantes não possam sê-lo, o que torna 
um sistema indecidível. A decidibilidade ou solução de um problema de decisão requer que as 
respostas sejam retornadas para qualquer instância do problema. Portanto, pode-se definir uma 
solução parcial como um processo que retorna “sim” para todas as instâncias reais, mas, no caso de 
uma instância de erro, pode retornar “não” ou deixar de produzir uma resposta.
Nesta Unidade de Aprendizagem, você entenderá os conceitos em torno dos problemas de decisão, 
compreenderá a diferença entre decidibilidade e indecidibilidade, bem como aplicá-la a máquinas 
de Turing, além de ser capaz de definir problemas de parada e outras linguagens relacionadas a ela. 
Bons estudos.
Ao final desta Unidade de Aprendizagem, você deve apresentar os seguintes aprendizados:
 Definir formalmente os problemas de decisão. 
 
•
Introduzir o conceito de decidibilidade e indecidibilidade via máquinas de Turing.•
Conceituar o problema da parada e outras linguagens indecidíveis ou irreconhecíveis por 
máquina de Turing.
•
Laiane
Laiane
Desafio
A máquina de Turing (MT) pode ser utilizada para resolver diversos problemas, empregando uma 
técnica específica para determinar quais serão as decisões tomadas, visando a um resultado e 
determinando uma solução para cada caso. Além disso, a tese de Church-Turing pode ser definida 
como o uso de máquinas para reconhecimento de linguagens. Assim, se um problema de decisão 
tem solução, existe uma máquina de Turing que o soluciona. E se, por exemplo, não existir uma 
linguagem que seja uma solução para um problema de decisão, esse problema de decisão 
é insolúvel.
Considerando essas informações, tenha em vista o seguinte cenário:
Aponte a câmera para o código e acesse o link do conteúdo ou clique no código para acessar.
https://statics-marketplace.plataforma.grupoa.education/sagah/51eb9f1b-0e60-4186-8e7b-0e7deda115ad/6ce777ed-9400-4dfe-8376-f5d73c4e9dee.jpg
A partir do cenário apresentado, os desafios propostos em relação à MT criada são: 
a) Após a implementação da MT, é necessário definir qual a relação entre a decidibilidade e a 
computação para o exemplo proposto. 
b) Sabendo que o algoritmo apresentado também apresenta o poder de decisão, você precisa 
explicar aos alunos o conceito da MT utilizada em um problema de decisão e a maneira como deve 
ser aplicado. É necessário identificar de que forma o programa seria capaz de reconhecer que o 
problema é insolúvel?
Laiane
Padrão de resposta esperadoa) Nesse exemplo, a decidibilidade é representada por meio do problema de parada, em que uma decisão deve ser tomada sobre a soma de dois números, representando na saída o resultado final e sempre uma parada quando isso acontecer.b) Quando os conceitos de Turing são considerados para definir um problema de decisão, têm-se os seguintes fatores:- se o problema de decisão tiver uma solução, pode-se usar uma MT para resolver qualquer problema, principalmente com algoritmos e linguagem; no caso apresentado, o problema é decidível;- se for impossível expressar uma solução em qualquer problema de decisão, então não há solução para o problema de decisão. Portanto, por exemplo, se não houver um programa em qualquer linguagem que resolva o problema de decisão, este não poderá ser resolvido.Nesse caso, o resultado esperado era a soma dos números; assim, quando os dois números forem somados, apresentando o resultado na saída, o programa parará.
Infográfico
A decidibilidade define recursos utilizados para que se possa tomar uma decisão. Já a máquina de 
Turing tem diversas funções atribuídas, como calcular, resolver problemas e até mesmo raciocinar 
para facilitar a execução de tarefas. De acordo com a teoria de Turing, qualquer máquina de 
computação é uma máquina de Turing, cujo principal propósito era simular a função do 
pensamento humano. Considerando esses conceitos, vale dizer que a resolução de problemas é 
fundamental para as teorias em todos os campos. As proposições nesses campos podem ser 
estudadas com base em um número limitado de axiomas (proposições que podem ser aceitas sem 
apresentação para melhor compreender e aprender matemática e geometria), dando origem a 
problemas de tomada de decisão. 
Neste Infográfico, você vai conhecer alguns eventos relacionados ao surgimento das máquinas de 
Turing e a aplicação do problema de decisão relacionado ao conceito de decidibilidade.
Laiane
Aponte a câmera para o 
código e acesse o link do 
conteúdo ou clique no 
código para acessar.
https://statics-marketplace.plataforma.grupoa.education/sagah/9868f5fc-136f-4829-a825-c029ed0c2361/9e1721e3-eab2-4a72-8919-a202363a5858.jpg
Conteúdo do livro
Muito antes de os computadores modernos terem sido inventados, a teoria da computação já havia 
sido iniciada e estava em desenvolvimento. Matemáticos de todo o mundo buscavam resolver 
problemas por meio de processos com um número finito de passos que pudessem sempre retornar 
resultados corretos para uma mesma questão. Como solução, a máquina de Turing não apenas 
desenvolveu a teoria da decidibilidade, mas também um modelo de cálculo semelhante ao 
dos autômatos finitos, embora sua função seja mais poderosa e amplamente usada para propósitos 
gerais para ajudar a resolver problemas com o uso da computação. 
Em relação à decidibilidade, ainda que existam várias teorias, para definir esse conceito, pode-se 
considerar qualquer teoria inconsistente, já que toda fórmula será uma consequência lógica e, 
portanto, membro da teoria. A linguagem baseada na máquina de Turing e os problemas de decisão 
e parada podem estar relacionados à computação, à lógica e a diversas teorias de decibilidade.
No capítulo Decidibilidade, base teórica desta Unidade de Aprendizagem, você verá alguns 
exemplos e conceitos que definem a decibilidade, sua relação com a máquina de Turing e de que 
maneira essas teorias podem estar relacionadas a linguagens indecidíveis, problema da parada 
e computação.
Boa leitura. 
Laiane
Laiane
Laiane
LINGUAGENS 
FORMAIS E 
AUTÔMATOS
OBJETIVOS DE APRENDIZAGEM
 > Definir formalmente os problemas de decisão.
 > Introduzir o conceito de decidibilidade e indecidibilidade via máquinas 
de Turing.
 > Conceituar o problema da parada e outras linguagens indecidíveis ou 
irreconhecíveis por máquina de Turing.
Introdução
Vários fundamentos da computação foram desenvolvidos e aperfeiçoados a 
partir dos anos 1930 (FONSECA FILHO, 2007), com importantes contribuições de 
personagens como Alan Turing, Alonzo Church e Stephen Kleene. Usualmente 
chamada “teoria da computabilidade”, essa área do conhecimento envolve 
perguntas essenciais, tais como: Quais funções matemáticas são computáveis? 
Qual é o conceito de algoritmo? Quais problemas podem ser resolvidos pelo 
uso de um computador?
Neste capítulo, abordaremos essas questões por meio do estudo da má-
quina de Turing (MT) e de sua aplicação nos chamados “problemas de decisão”. 
Você poderá compreender os principais conceitos de problemas de decisão, 
o modo como a decidibilidade e a indecidibilidade são caracterizadas, além 
da maneira como se dão problemas específicos, como o problema de parada 
e outros problemas que envolvem as linguagens indecidíveis e decidíveis. 
Ao final, deveremos ter uma visão mais clara do que podemos considerar 
computável (problemas que podem ser solucionados via algoritmos) e do que 
seria incomputável (problemas que não podem ser resolvidos via algoritmos).Decidibilidade
Fernanda Rosa da Silva
Laiane
Problemas de decisão
Com o surgimento dos computadores, diversas questões foram levantadas 
em relação ao poder da tecnologia e à forma como os computadores seriam 
capazes de solucionar problemas. Além disso, questionou-se até que ponto 
esses problemas seriam considerados computáveis, dúvida essa que deu 
origem a diversos contextos que caracterizam a teoria da computação.
Na literatura, podemos encontrar diferentes visões para o conceito de 
problema de decisão. Uma delas é mais próxima dos trabalhos de máquinas 
reconhecedoras de linguagens (HOPCROFT; MOTWANI; ULLMAN, 2002; DIVERIO; 
MENEZES, 2011; SIPSER, 2007), ao passo que outra está mais relacionada com 
a construção de funções matemáticas (DIVERIO; MENEZES, 2011) e, até mesmo, 
da satisfatibilidade de fórmulas lógicas (FERREIRA, 2019; DIVERIO; MENEZES, 
2011). De todo modo, podemos dizer informalmente que um problema de 
decisão é qualquer tipo de questionamento para o qual a resposta seja “sim” 
ou “não” (de forma equivalente a “verdadeiro” ou “falso”). Uma ilustração 
desse fluxo de problema de decisão pode ser vista na Figura 1.
Figura 1. Representação de fluxo do 
problema de decisão.
Decidibilidade2
Laiane
Laiane
Um exemplo simples de problema de decisão é descobrir se um 
número pertencente a um determinado conjunto é ou não é primo. 
O problema é definido a partir do seguinte questionamento: “Dado um número 
inteiro x, esse x é um número primo?”. A resposta para essa pergunta pode ser 
“sim” ou “não” e depende dos valores que a variável x assume em cada instância 
do problema. Quando a entrada é definida pelo número 7, por exemplo, a resposta 
gerada na saída é “sim”; já para a instância 8, a resposta é “não”.
No estudo de máquinas (HOPCROFT; MOTWANI; ULLMAN, 2002), o problema 
de decisão está relacionado à questão decisória de se uma dada palavra 
pertence ou não pertence a uma linguagem — a qual nada mais é do que 
um conjunto de palavras formadas pela concatenação de símbolos de um 
determinado alfabeto. Será esse o nosso foco de trabalho.
Tomemos como exemplo a linguagem expressa pela expressão regular 
0(0 + 1)*0, ou seja, a linguagem de números binários que começam e terminam 
com símbolos 0, L = {00, 000, 010, 0000, 0010, …}, sobre o alfabeto Σ ={0, 1}. 
Essa linguagem pode ser aceita por meio de diferentes tipos de autômatos 
(como o autômato finito determinístico ou o autômato de pilha), mas vamos 
analisar o funcionamento de uma MT (Figura 2), que processa uma palavra w 
de entrada e sempre responde “sim” (ou aceita) se a palavra pertence a L e 
responde “não” (ou rejeita) se a palavra não pertence a L.
Para a palavra w = 010, a MT terminará o seu processamento no estado 
q3 e, portanto, será aceita. Já para a palavra w = 011, a MT terminará o seu 
processamento no estado q1 e, portanto, será rejeitada. É importante com-
preender que, para qualquer palavra, a MT da Figura 2 sempre vai parar e 
responder “sim” ou “não”.
Figura 2. MT reconhecedora da linguagem 0(0 + 1)*0.
Decidibilidade 3
Laiane
Laiane
Formalmente, podemos enunciar (HOPCROFT; MOTWANI; ULLMAN, 2002; 
DIVERIO; MENEZES, 2011; SIPSER, 2007): se Σ é um alfabeto e L ⊆ Σ* é uma 
linguagem sobre Σ, então o problema de decisão L é, dada uma palavra 
w ∈ Σ*, decidir se w ∈ L ou w ∉ L.
Sendo assim, o problema de decisão é um problema que determina se um 
elemento específico faz parte ou não faz parte de um conjunto específico ou, 
de modo equivalente, se satisfaz a uma determinada propriedade (DIVERIO; 
MENEZES, 2011).
O conceito de problema de decisão, conhecido em alemão como 
Entscheidungsproblem, foi proposto por David Hilbert, em 1928. 
Hilbert queria encontrar um procedimento mecânico (ou algoritmo) para verificar 
se uma determinada fórmula na lógica de predicados de primeira ordem seria 
válida ou não. Church e Turing provaram que tal algoritmo não existe.
Para saber mais sobre esse tópico, sugerimos a leitura do artigo “O problema 
da decisão e a máquina universal de Turing”, de Ferreira (2019).
A partir do conceito de problema de decisão, é possível classificar os pro-
blemas em algumas classes (Figura 3) com relação à decidibilidade, conforme 
apresentamos a seguir (DIVERIO; MENEZES, 2011).
 � Problema solucionável, ou decidível: se existe uma máquina que sempre 
para respondendo “sim” ou “não”.
 � Problema não solucionável, ou indecidível: se não existe uma máquina 
que sempre para respondendo “sim” ou “não”.
 � Problema parcialmente solucionável, ou computável: se existe uma 
máquina que para quando a resposta para o problema é “sim”, mas, 
quando a resposta esperada é “não”, a máquina pode parar ou entrar 
em um loop infinito de processamento.
 � Problema completamente insolúvel, ou não computável: se não existe 
uma máquina que para quando a resposta esperada para o problema 
é “sim”.
Decidibilidade4
Laiane
Laiane
Laiane
Laiane
Laiane
Figura 3. Classificação de problemas.
Fonte: Diverio e Menezes (2011, p. 251).
Considerando a mesma teoria, Sipser (2007) afirma que, mesmo em ca-
sos em que um problema é decidível, ele pode ser considerado não solúvel 
por necessitar de uma quantidade excessiva de recursos, como memória, 
além de muito tempo para ser solucionado, dando origem à complexidade 
computacional.
É importante frisar que essa classificação dos problemas está intimamente 
relacionada com o uso da MT como reconhecedora de linguagens. Assim 
sendo, podemos estabelecer uma associação entre o conjunto das linguagens 
recursivas e das linguagens recursivamente enumeráveis e a classificação de 
problemas via decidibilidade. Apresentaremos esse assunto na próxima seção.
Decidibilidade e máquina de Turing
Como nos apresenta Menezes (2011), a MT é um modelo abstrato de computação 
criado com o objetivo de explorar os limites da capacidade da solucionabi-
lidade de problemas. Sendo assim, ela é uma proposta de definição formal 
para o conceito intuitivo de algoritmo.
A partir do formalismo da MT, são definidas as classes de linguagens 
apresentadas a seguir (MENEZES, 2011; DIVERIO; MENEZES, 2011; HOPCROFT; 
MOTWANI; ULLMAN, 2002; SIPSER, 2007).
 � Linguagem recursiva: conjunto de linguagens decididas por uma MT, 
ou seja, para as quais existe uma máquina (Figura 4a) que sempre 
para indicando se uma palavra pertence ou não pertence à linguagem.
 � Linguagem recursivamente enumerável: conjunto de linguagens aceitas 
por uma MT, ou seja, para as quais existe uma máquina (Figura 4b) capaz 
de determinar se uma palavra pertence à linguagem. Caso a palavra 
Decidibilidade 5
Laiane
Laiane
Laiane
Laiane
Laiane
Laiane
não pertença à linguagem, a máquina pode parar ou ficar processando 
indefinidamente.
Figura 4. (a) Linguagem recursiva e (b) linguagem recursivamente enumerável.
Fonte: Adaptada de Menezes (2011).
a b
A relação entre as linguagens recursivas e as linguagens recursivamente 
enumeráveis está resumida na Figura 5. Com base no que apresentamos, 
é possível concluir que a classe dos problemas solucionáveis, ou decidíveis, 
é equivalente à classe das linguagens recursivas. Assim, de acordo com 
Diverio e Menezes (2011) e Hopcroft, Motwani e Ullman (2002), a questão da 
solucionabilidade de um problema pode ser traduzida em uma investigação 
acerca de se a linguagem associada é recursiva (problema solucionável) ou 
recursivamente enumerável (problema parcialmente solucionável).
Figura 5. Relação entre o conjunto de linguagens as-
sociadas à MT.
Decidibilidade6
Laiane
Laiane
Na Figura 5, pode-se constatar a presença de um conjunto muito maior que 
os outros, o qual foi nomeado “universo de todas as linguagens”. Isso significa 
que há linguagens para as quais não existe qualquer MT que as reconheça. 
Trata-se de um resultado importantíssimo na teoria da computabilidade, e, 
na literatura da área, há diversos exemplos de problemas não computáveis.
Alan Turing contribuiu para resolver o problema de decisão por meio 
dos conceitos relacionadosao problema de parada, o qual é um dos mais 
importantes problemas não solucionáveis. A seguir, vamos analisar as suas 
características e apresentar alguns exemplos.
Problema da parada e outras linguagens
Esta seção se concentra em apresentar diferentes problemas e classificá-los 
de acordo com a Figura 3. Nosso principal objetivo será definir pelo menos 
um problema para cada um dos seguintes casos: problema associado a uma 
linguagem recursiva que não seja recursivamente enumerável, problema 
associado a uma linguagem recursivamente enumerável que não seja re-
cursiva, problema associado a uma linguagem que não seja recursivamente 
enumerável.
Antes de apresentarmos exemplos de linguagens e problemas associados 
à Figura 5, convém introduzirmos o conceito de codificação de máquinas em 
palavras de uma linguagem. A ideia é semelhante à do funcionamento de 
um compilador que traduz um programa escrito em uma linguagem de alto 
nível (como C) para uma linguagem de baixo nível (código de máquina). Assim, 
existem algoritmos que traduzem a descrição completa de uma MT M em 
palavras 〈M〉 (notação utilizada por Sipser, 2007) pertencentes a um alfabeto 
(usualmente um alfabeto binário).
Diferentes algoritmos de codificação para máquinas podem ser 
encontrados na página 252 da obra Teoria da computação: máquinas 
universais e computabilidade, de Diverio e Menezes (2011); e na página 397 da 
obra Introdução à teoria de autômatos, linguagens e computação, de Hopcroft, 
Motwani e Ullman (2002).
Decidibilidade 7
Laiane
Laiane
Os exemplos que apresentaremos na sequência se baseiam em dois 
conceitos importantes: MT universal (Figura 6) e princípio da redução (Figu-
ras 7 e 8). Desse modo, vamos analisar cada um desses conceitos antes de 
prosseguirmos.
A MT universal (HOPCROFT; MOTWANI; ULLMAN, 2002; SIPSER, 2007; DIVERIO; 
MENEZES, 2011) U é uma MT capaz de simular a execução de qualquer outra 
MT M recebida como uma entrada codificada 〈M〉 e uma palavra w a ser reco-
nhecida. A ideia é a mesma de um computador (a MT universal) executando 
um programa qualquer (uma MT qualquer) com dados de entrada (a palavra 
a ser reconhecida).
Figura 6. MT universal.
O princípio da redução tem múltiplas aplicações na computação (DIVERIO; 
MENEZES, 2011; HOPCROFT; MOTWANI; ULLMAN, 2002; SIPSER, 2007). Ele pode ser 
usado para construir a solução de um problema desconhecido reutilizando-se 
a solução de um problema conhecido (sendo esse uso bastante comum na área 
de construção de algoritmos), bem como para investigar a solucionabilidade 
de um problema a partir de outro, sendo essa a forma com que aplicaremos 
o princípio.
Conforme aponta Sipser (2007), a redutibilidade sempre evolve dois pro-
blemas, denominados A e B; e, como destacam Hopcroft, Motwani e Ullman 
(2002), a direção da redução é importante, ou seja, dizer que o problema A se 
reduz ao problema B produz resultados diferentes dos obtidos ao dizer que 
o problema B se reduz ao problema A. A Figura 7 mostra a visão da redução 
de A para B, em que o problema B é utilizado para resolver o problema A. Já a 
Figura 8 mostra como a redução de A para B pode ser utilizada para investigar 
a solucionabilidade de A, uma vez que se conhece a solucionabilidade de B 
(e vice-versa).
Decidibilidade8
Figura 7. Resolvendo um problema A via redução para um problema B.
Fonte: Adaptada de Hopcroft, Motwani e Ullman (2002).
Figura 8. Princípio da redução de A para B.
Fonte: Diverio e Menezes (2011, p. 249).
O princípio da redução apresentado na Figura 8 pode ser aplicado à questão 
da solucionabilidade da forma descrita a seguir (DIVERIO; MENEZES, 2011).
 � Quando existem dois problemas de decisão, é possível modificar o 
problema A por meio do princípio da redução, permitindo que ele se 
comporte como se fosse o problema B.
 � Se o problema A for insolúvel (respectivamente indecidível ou não 
computável), será possível concluir que, como os dois são semelhantes, 
o problema B acaba se tornando insolúvel (respectivamente indecidível 
ou não computável).
 � Se o problema B for solucionável (respectivamente decidível ou par-
cialmente solucionável), o problema A também poderá ser solucionável 
(respectivamente decidível ou parcialmente solucionável).
Decidibilidade 9
Laiane
Laiane
Laiane
Além disso, é correto afirmar que o princípio da redução consiste em fa-
cilitar a solução de problemas a partir das características de outro problema 
que tenha sido resolvido por meio de uma classe conhecida de soluções, 
considerando condições em comum entre eles.
Um exemplo de problema decidível é proposto por Sipser (2007). O chamado 
“problema da aceitação de autômatos finitos determinísticos” é definido 
como um problema de decisão para a pergunta “Dado um autômato finito 
determinístico AFD e uma palavra w, AFD aceita w?”. Ao traduzirmos o problema 
como linguagem, obtemos:
LAFD = {〈AFD, w〉|AFD aceita a palavra w}
A linguagem LAFD é uma linguagem recursiva e não recursivamente enume-
rável, portanto, decidível. A ideia da prova formal é que podemos criar uma 
MT M que decide a linguagem mediante a simulação dos passos de execução 
do autômato finito determinístico sobre os símbolos da palavra de entrada.
Neste momento, podemos pensar que todos os problemas práticos da 
computação são decidíveis e que apenas exemplos teóricos sem aplicação 
prática estariam no conjunto de problemas indecidíveis. Não poderíamos estar 
mais enganados. Diverio e Menezes (2011) explicam que existem problemas 
não solucionáveis (indecidíveis) bastante práticos e que dois deles, descritos 
a seguir, são bem conhecidos do nosso dia a dia.
 � Detector universal de loops: dado um programa e qualquer entrada, 
nenhum algoritmo geral pode verificar se o programa, considerando 
a entrada, será finalizado. Esse problema é frequentemente referido 
como o “problema da parada”.
 � Equivalência de compiladores: não é possível criar um algoritmo univer-
sal capaz de identificar se dois compiladores diferentes para a mesma 
linguagem de programação, cuja gramática é classificada como livre 
de contexto, são equivalentes ou não.
O problema de parada pode ser definido como um problema de decisão e 
foi comprovado como indecidível, por mais que os recursos computacionais 
fossem suficientes para tratar da situação apresentada. A importância histó-
rica do problema da parada se deve ao fato de ter sido o primeiro problema 
Decidibilidade10
Laiane
Laiane
considerado indecidível, comprovado pelas teorias de Turing e a máquina 
universal — apesar de isso ter ocorrido após Alonzo Church lançar, no mesmo 
ano de 1936, como prova da indecidibilidade, um problema representado 
pelo cálculo lambda.
Dessa forma, o problema da parada foi definido considerando-se as pro-
priedades de uma máquina universal de Turing M e uma palavra w qualquer. 
O problema da parada é, então, caracterizado pelo seguinte problema de 
decisão, de acordo com Diverio e Menezes (2011):
LP = {〈M, w〉|w ∈ ACEITA(M) ∪ REJEITA(M)}
onde:
 � LP é a linguagem associada ao problema;
 � 〈M〉 é uma codificação bijetora de programas em um número natural.
Considerando-se uma máquina universal qualquer e utilizando-se uma 
palavra qualquer como entrada, geralmente existe um algoritmo que verifica 
se a máquina em questão está aceitando ou rejeitando a entrada processada. 
Um programa mais complexo pode ser mais difícil de se analisar. O programa 
pode rodar por um tempo fixo, e, se ele não parar, não há um jeito de saber 
se eventualmente ele vai parar ou se vai continuar rodando para sempre. 
Turing provou que não há um algoritmo que pode ser aplicado a qualquer 
programa arbitrário, com uma entrada, para decidir se o programa para ou 
não para com essa entrada. Em termos de linguagem, LP é uma linguagem 
recursivamente enumerável, mas não recursiva.
Posteriormente ao problema da parada, muitos outros problemas foram 
descritos. Além disso, a técnica da redução do problema da parada a esses 
problemas foi essencial para provar quetais problemas são indecidíveis. 
Hopcroft, Motwani e Ullman (2002) apresentam uma lista de problemas in-
decidíveis sobre MTs:
1. determinar se a linguagem aceita por uma MT é vazia;
2. determinar se a linguagem aceita por uma MT é finita;
3. determinar se a linguagem aceita por uma MT é linguagem regular;
4. determinar se a linguagem aceita por uma MT é linguagem livre de 
contexto.
Decidibilidade 11
Laiane
Outros problemas de decisão definidos pela 
máquina de Turing
Além do problema da parada, que representa o principal problema de decisão, 
há outros problemas que podem ser aplicados considerando-se os conceitos 
e as características da MT. A seguir, vamos analisar alguns deles.
Problema da parada da palavra vazia
O problema da parada apresenta uma variação: o problema da parada da 
palavra vazia. Nesse caso, sempre que a linguagem ou o algoritmo recebe 
uma entrada, essa entrada é vazia ou não existe. Segundo Diverio e Menezes 
(2011), ela pode ser definida com o seguinte questionamento: Considerando 
uma máquina universal, pode-se aplicar um algoritmo para definir se a en-
trada vazia, ao ser processada, deve ser aceita ou não; é possível que essa 
definição seja realizada?
A Figura 9 demonstra de forma genérica como o teorema pode ser apre-
sentado e representa a prova de que o problema da parada da palavra vazia 
é não solucionável, considerando-se a seguinte linguagem:
Lε = {〈M〉|ε ∈ ACEITA(M) ∪ REJEITA(M)}
A ideia de redução do problema da parada da palavra vazia é representada 
graficamente na Figura 9. Nela, é possível observar que, uma vez provado que 
o problema da parada é indecidível e que ele pode ser reduzido ao problema 
da parada da palavra vazia, o problema da parada da palavra vazia também 
é indecidível.
Figura 9. Representação do problema da 
parada da palavra vazia.
Fonte: Diverio e Menezes (2011, p. 260).
Decidibilidade12
Laiane
Problema da totalidade
O problema da totalidade, de acordo com Diverio e Menezes (2011), pode ser 
definido por meio do seguinte questionamento: Dada uma máquina universal M 
qualquer, existe um algoritmo que verifica se M para, aceitando ou rejeitando, 
ao processar qualquer entrada?
O problema da totalidade é não solucionável e pode ser representado 
pela linguagem que traduz o problema da totalidade como não recursiva da 
seguinte forma:
LT = {〈M〉|LOOP(M) = ∅}
A Figura 10 representa graficamente a ideia de redução do problema da 
totalidade.
Figura 10. Representação do problema da 
totalidade.
Fonte: Menezes (2011, p. 260).
Problema da equivalência
De acordo com Diverio e Menezes (2011), o problema de equivalência de MTs 
é utilizado para decidir se duas máquinas reconhecem a mesma linguagem. 
A linguagem que traduz o problema da equivalência não é recursiva e pode 
ser representada pela seguinte expressão:
LE = {〈M1, M2〉|ACEITA(M1) = ACEITA(M2) e REJEITA(M1) = REJEITA(M2)}
Decidibilidade 13
Laiane
A ideia de redução do problema da equivalência é representada grafica-
mente na Figura 11.
Figura 11. Representação do problema da 
equivalência.
Fonte: Menezes (2011, p. 261).
Linguagem da diagonalização
Hopcroft, Motwani e Ullman (2002) e Menezes (2011) descrevem um exemplo de 
linguagem não recursivamente enumerável chamada “linguagem da diagona-
lização”. Trata-se de uma linguagem para a qual não existe qualquer MT que a 
processe. Em outras palavras, é um exemplo de um problema incomputável.
A ideia da linguagem da diagonalização é o problema de decisão que con-
siste em todas as palavras w tais que a MT M representada por w não aceita 
a palavra w. É importante salientar que a palavra w representa a própria 
codificação 〈M〉 da máquina.
Neste capítulo, foi possível identificar que um problema de decisão pode 
auxiliar na identificação das classes de problemas definindo se ele é decidível 
(computável) ou não. A decidibilidade corresponde a um método a ser aplicado 
a um problema para gerar uma decisão quanto à resposta afirmativa ou nega-
tiva de um determinado problema. Por meio do seu modelo de computação, 
Turing nos fornece um sistema formal, desde que ele seja decidível e suporte 
um conjunto finito de passos válido para demonstrar a forma como se pode 
resolver um problema.
Decidibilidade14
Laiane
Referências
DIVERIO, T. A.; MENEZES, P. B. Teoria da Computação: máquinas universais e computa-
bilidade. 3. ed. Porto Alegre: Bookman, 2011.
FERREIRA, F. O problema da decisão e a máquina universal de Turing. In: SANTO, J. C. E. 
(Ed.). Alan Turing: cientista universal. Lisboa: UMinho Editora, 2019. p. 55–84. Disponível 
em: https://doi.org/10.21814/uminho.ed.5. Acesso em: 28 fev. 2021.
FONSECA FILHO, C. História da Computação: o caminho do pensamento e da tecnologia. 
Porto Alegre: EDIPUCRS, 2007.
HOPCROFT, J. E.; MOTWANI, R.; ULLMAN, J. D. Introdução à teoria de autômatos, linguagens 
e computação. Rio de Janeiro: Elsevier, 2002.
MENEZES, P. B. Linguagens formais e autômatos. 6. ed. Porto Alegre: Bookman, 2011.
SIPSER, M. Introdução à teoria da computação. 2. ed. São Paulo: Cengage Learning, 2007.
Leitura recomendada
LOBO, D. de C. Problemas indecidíveis. 2013. Dissertação (Mestrado em Matemática) 
– Universidade de Coimbra, Coimbra, 2013. Disponível em: https://eg.uc.pt/bits-
tream/10316/33698/1/Problemas%20indecidiveis_DianaLobo.pdf. Acesso em: 28 fev. 
2021.
Os links para sites da web fornecidos neste capítulo foram todos 
testados, e seu funcionamento foi comprovado no momento da 
publicação do material. No entanto, a rede é extremamente dinâmica; suas 
páginas estão constantemente mudando de local e conteúdo. Assim, os editores 
declaram não ter qualquer responsabilidade sobre qualidade, precisão ou 
integralidade das informações referidas em tais links.
Decidibilidade 15
Dica do professor
Quando existe um problema de decisão, a computabilidade pode ser aplicada para verificar a 
existência de algoritmos que consigam resolver uma classe de linguagens, tratando a possibilidade 
da sua construção e diminuindo a complexidade dos problemas pela eficiência da computação. A 
computabilidade resolve problemas concentrando-se em respostas binárias, sem considerar as 
limitações reais, motivo pelo qual qualquer tarefa computacional passível de ser executada por 
meios mecânicos pode ser executada por uma máquina de Turing.
Nesta Dica do Professor, você verá como a redução em problemas de decisão pode ser aplicada 
com o objetivo de converter o problema original em outro problema, de modo que a mesma 
solução possa ser empregada para ambos os casos visando à resolução do problema.
Aponte a câmera para o código e acesse o link do conteúdo ou clique no código para acessar.
https://fast.player.liquidplatform.com/pApiv2/embed/cee29914fad5b594d8f5918df1e801fd/28fa6e8842b04eda3275392922010579
Exercícios
1) O problema de decisão representa qualquer problema com resposta “sim ou não”, além de 
ser utilizado para decidir se determinado elemento de um universo pertence a um conjunto 
específico.
Sobre o problema de decisão, é correto afirmar que:
A) em um problema de decisão, um algoritmo é utilizado sempre com uma entrada genérica, 
considerando uma linguagem específica e retornando como resultado uma saída que aponte 
se a sentença é verdadeira ou falsa.
B) o termo alemão Entscheidungsproblem pode ser utilizado para se referir ao “problema de 
decisão”, que considera respostas decimais quando corresponde à computabilidade, 
explicando numericamente como resolver os problemas.
C) existem problemas de decisão não solucionáveis, cujo principal define o detector universal de 
loops, em que o algoritmo nunca chega a uma decisão precisa e o algoritmo continua sendo 
executado. 
D) a equivalência de compiladores é um fator determinante, afirmando que é possível usar a 
linguagem livre para criar um algoritmo geral para comparar dois compiladores.
E) existem diversos métodos que podem ser utilizados para determinar a decidibilidade de um 
problema, portanto definir a primalidade de um conjuntode números é um exemplo de 
problema decídivel. 
O problema de decisão descreve uma maneira de buscar um método e uma solução eficaz 
para retornar ou calcular um resultado por meio de uma linguagem específica. Isso serve 
para determinar se a fórmula é ou não um teorema lógico. Sobre o problema de decisão, 
considere as seguintes afirmações: 
 
I. O problema de decisão define que uma ação seja tomada a partir de um número limitado 
de instruções executadas dentro de determinado período para que se possa alcançar o 
resultado esperado. 
 
II. Quando existe pelo menos um algoritmo computacional capaz de solucionar um 
problema, considera-se que ele é decidível; por sua vez, se um algoritmo é executado 
infinitamente, o problema é indecidível. 
2) 
Laiane
Laiane
Um detector universal de loops determina que, independentemente da entrada recebida, não é possível alcançar uma solução; assim, o programa é finalizado sem que o problema seja resolvido.O termo alemão Entscheidungsproblem define o problema de decisão: as respostas de um problema de decisão são binárias considerando sim ou não como saída e tomada de decisão de um problema. Em problemas nos quais não é possível comparar dois compiladores, considera-se que o problema de decisão é indecidível. Existem problemas de decisão não solucionáveis, cujo principal define o detector universal de loops, em que o algoritmo nunca chega a uma decisão precisa e o algoritmo continua sendo executado. O problema de decisão tem sua estrutura basicamente definida em uma entrada, tratada por um algoritmo e uma saída, que pode ser verdadeira ou falsa. Definir problemas matemáticos como MMC e números primos se torna possível por meio da teoria do problema de decisão. 
 
III. Quando um problema é indecidível, não pode ser simplificado ou alterado para que se 
consiga aplicar uma solução algorítmica. 
 
IV. Entender o conceito da máquina de Turing é essencial para compreender os conceitos de 
decidibilidade, indecidibilidade e linguagem relacionados aos problemas de decisão. 
 
V. A máquina de Turing é um modelo abstrato de um computador que surgiu com o objetivo 
de provar resultados, embora não represente o comportamento dos computadores atuais. 
Qual alternativa apresenta somente afirmações corretas?
A) II, III e V.
B) I, II e V.
C) I, II, III e IV.
D) I, II e III.
E) II, III e V.
3) Quando se considera um problema de decisão, a indecidibilidade significa apenas que o 
sistema dedutivo específico em consideração não pode provar a autenticidade ou a falsidade 
da sentença.
Sobre a indecidibilidade, é correto afirmar que: 
A) é uma ação que se refere a um problema de decisão, em que se pode determinar a correlação 
em um conjunto de fórmulas, validando-as com eficácia.
B) quando existe um algoritmo capaz de decidir um resultado, por exemplo, no problema da 
coprimalidade, considera-se que um problema é indecidível, caracterizando, assim, a 
indecidibilidade.
C) as sentenças indecidíveis podem ser descritas como um número infinito de ações aplicadas a 
sentenças e problemas de decisão, e essas ações e problemas nem sempre podem ser 
resolvidos por decisões computáveis.
D) quando um problema de decisão é indecidível, há um sistema formal consistente e eficaz para 
provar “sim para A” ou “não para A” para cada questão.
Laiane
Laiane
Laiane
Laiane
O problema de decisão deve estabelecer um processo bem definido para permitir que as etapas e passos definidos consigam entregar um resultado ao final do processo.Considerando que não haja erros no processo, o problema de decisão é composto por uma entrada de dados, um algoritmo que define uma resposta binária e uma saída.Problemas que não podem ser resolvidos computacionalmente são considerados indecidíveis, o que significa que nenhuma máquina de Turing é capaz de aplicar uma solução.A máquina de Turing é utilizada em conjunto com os problemas de decisão para possibilitar a análise e definir se um problema é decidível ou indecidível.A máquina de Turing se tornou uma máquina universal por muito tempo utilizada para modelar qualquer computador digital, apesar de os computadores modernos terem evoluído e não serem mais baseados na sua estrutur
Laiane
Quando se fala de decidibilidade, existem problemas considerados indecidíveis, quando é impossível construir um algoritmo que sempre responde corretamente sim ou não, caso no qual geralmente o algoritmo é executado de forma infinita, sem retornar eficácia ao processo estabelecido. Por sua vez, o problema decidível refere-se ao problema de decisão, que permite a aplicação de um método eficaz para determinar a correlação em um conjunto de fórmulas.
E) um problema de decisão é considerado indecidível quando qualquer questão arbitrária de 
“sim ou não” é aplicada sobre um conjunto finito de entradas.
4) A importância histórica do problema da parada reside no fato de que foi um dos primeiros 
problemas a serem provados indecidíveis descobertos, definindo se, a partir da entrada 
informada, o programa terminaria ou rodaria infinitamente. Considere as seguintes 
afirmações e classifique-as como verdadeiras (V) ou falsas (F):
( ) Uma consequência da indecidibilidade do problema da parada é que é impossível ter um 
algoritmo geral para determinar se determinada frase está certa ou errada. 
( ) Se a máquina de Turing não puder resolver o problema de parada, nenhum outro sistema 
de algoritmo será capaz de definir uma solução para o mesmo problema. 
( ) O problema de parada é decidível, uma vez que a máquina de Turing sempre permite que 
ele tenha um fim e não se torne infinito por falta de uma solução para qualquer problema. 
( ) A redução (o princípio da redução) é uma técnica que transforma um problema em 
outro, diminuindo sua complexidade. Contudo, ainda não é aplicável para interromper 
problemas.
( ) O problema da parada é um problema de decisão sobre os atributos de um programa de 
computador, como o fato de todos os programas que podem ser escritos em uma linguagem 
de programação geral serem equivalentes a máquinas de Turing. 
Assinale a alternativa que indica a ordem correta.
A) V – V – F – F – F. 
B) V – V – V – F – V. 
C) F – V – F – F – F. 
D) F – V – F – F – V. 
E) V – V – F – F – V. 
Se houver um problema que uma máquina de Turing não consiga resolver, nenhum algoritmo 
pode aplicar a solução. Essa conclusão parte do conceito de decidibilidade da máquina de 
Turing e promove a pesquisa e a determinação de problemas solucionáveis. Portanto, 
considere as seguintes afirmações sobre computabilidade e decidibilidade.
5) 
Laiane
Laiane
Uma consequência da indecidibilidade do problema da parada é que é impossível ter um algoritmo geral para determinar se determinada frase está certa ou errada: um mesmo algoritmo não consegue resolver diversos problemas, tornando o processo mais complexo e, muitas vezes, os problemas indecidíveis. Se a máquina de Turing não puder resolver o problema de parada, nenhum outro sistema de algoritmo será capaz de definir uma solução para o mesmo problema: ela serve como um modelo computacional para o poder computacional. O problema da parada é decidível, uma vez que a máquina de Turing sempre permite que ele tenha um fim e não se torne infinito por falta de uma solução para qualquer problema: o problema da parada é indecidível, já que, considerando a entrada recebida, o problema se torna infinito. A redução (o princípio da redução) é uma técnica que transforma um problema em outro, diminuindo a sua complexidade. Contudo, ainda não é aplicável para interromper problemas: o princípio da redução é justamente utilizado para provar que um problema é indecidível, como o caso do problema da parada.O problema da parada é um problema de decisão sobre os atributos de um programa de computador, como o fato de todos os programas que podem ser escritos em uma linguagem de programação geral serem equivalentes a máquinas de Turing: o problema da parada é o mais conhecido dos problemas de decisão.
I. Existem problemas quesão insolúveis na visão computacional, já que os computadores são 
limitados e nem sempre capazes de resolver problemas comuns.
II. Decidibilidade é uma definição para um caso particular de computabilidade, quando a 
função somente pode atribuir dois valores possíveis à saída quando ela recebe alguma 
entrada.
III. Apesar de o problema da parada ser o principal quando falamos de decidibilidade, 
existem outras variações, como o problema da parada da palavra vazia, em que uma entrada 
sempre é recebida, mas nem sempre se tem como resultado uma saída válida. 
IV. Linguagens são utilizadas na decidibilidade e definem como as máquinas expressam e 
resolvem problemas usando algoritmos por meio de uma série de etapas capazes de 
determinar as ações necessárias. 
V. O problema de totalidade é um problema de decisão que pode ser do tipo verdadeiro ou 
falso, verificando a equivalência entre duas máquinas universais. 
Qual alternativa apresenta somente afirmações corretas?
A) I, II e IV.
B) I, II e V.
C) II, III e IV.
D) II, IV e V.
E) I e II, apenas. 
Laiane
Laiane
Muitas vezes, por mais que se tenha solução para um problema de decisão, os recursos utilizados encontram dificuldade em chegar a um resultado específico.Decidibilidade é um termo ligado à computabilidade que permite dois valores de saída possíveis quando um problema é decidível.O problema da parada da palavra vazia é baseado no problema de parada, assim como outros e nesse caso, a entrada sempre é vazia ou não existe sendo definida pelo próprio algoritmo. As linguagens são a forma como as máquinas se comunicam entre si para relacionar as informações recebidas, o algoritmo e a solução do problema. O problema de totalidade é um problema de decisão, porém é o problema de equivalência que faz a verificação entre duas máquinas universais. 
Laiane
Na prática
O problema da parada (the halting problem) é um problema de decisão clássico da ciência da 
computação que consiste, basicamente, em determinar se um dado programa sempre vai parar (ou 
seja, terminar sua execução) para uma dada entrada arbitrária ou se vai executar infinitamente. Alan 
Turing provou, em 1936, que é impossível resolver o problema da parada generalizando para 
qualquer par programa-entrada. Nesse problema, porém, dada a descrição de uma linguagem 
simples, um programa escrito nessa linguagem e uma entrada para esse programa, você deve 
determinar se o programa dado para com a entrada dada e, em caso positivo, qual a saída 
produzida.
Acompanhe, no Na Prática, o problema da parada e uma demonstração de como essa técnica 
funciona.
Aponte a câmera para o 
código e acesse o link do 
conteúdo ou clique no 
código para acessar.
https://statics-marketplace.plataforma.grupoa.education/sagah/61275f84-983b-493c-8e98-1f107b65c667/3cd069dd-55e6-403d-b80d-7644e8bdb7b4.jpg
 
 
Saiba +
Para ampliar o seu conhecimento a respeito desse assunto, veja abaixo as sugestões do professor:
Máquina de Turing, decidibilidade e o problema da parada
O conteúdo aborda alguns exemplos do problema da parada relacionados à computabilidade, 
apresentando os conceitos da máquina de Turing e do problema de decisão (Enscheidungsproblem) e 
sua ligação com as máquinas computacionais.
Aponte a câmera para o código e acesse o link do conteúdo ou clique no código para acessar.
A decidibilidade indutiva
O conteúdo aborda os conceitos de decidibilidade e de computabilidade, a fim de conseguir 
resolver problemas de forma eficaz. Além disso, apresenta vídeos curtos sobre o the halting problem 
e os limites teóricos da computação e da computabilidade, termo ligado diretamente às 
características da decibilidade e seus recursos.
Aponte a câmera para o código e acesse o link do conteúdo ou clique no código para acessar.
Conjuntos indecidíveis e incompletude em sistemas formais
Este artigo descreve de que maneira um algoritmo pode responder aos sistemas se determinado 
elemento pertence ou não ao conjunto especificado, resolvendo problemas específicos. Ainda, 
demonstra a capacidade de decisão.
https://pedroabreu0.github.io/blog/2017/05/08/Maquina-De-Turing-Decidibilidade-e-o-Problema-da-Parada
https://medium.com/@bruno_live/fractais-03-a-decidibilidade-indutiva-b4e688e80460
Aponte a câmera para o código e acesse o link do conteúdo ou clique no código para acessar.
http://www.inicepg.univap.br/cd/INIC_2015/anais/arquivos/RE_0226_0063_01.pdf