Parte 8

Prévia do material em texto

Teoria da Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
Texto base 
8 
 
Teoria da Computação 
Ana Paula Ferreira da Rocha 
Resumo 
O significado histórico de entender as teorias computacionais, a máquina de Turing e a 
tese de Turing-Church. O princípio da solucionabilidade é de primordial importância 
para os algoritmos das linguagens utilizadas e entender o funcionamento da máquina de 
Turing nos mostra o valor computacional que devemos incluir nos símbolos que vamos 
utilizar. Quanto mais direto o código menor a probabilidade de cometer erros e 
interromper a execução do programa. 
Introdução 
 Abordaremos a teoria da computabilidade, máquina de Turing e tese de Turing-
Church, veremos a importância do poder computacional e importância da 
solucionabilidade para os algoritmos e as linguagens computacionais utilizadas levando 
em consideração que os formalismos não computáveis podem ser processados em 
situações de exceção. 
 
 
8.1. Teoria da Computabilidade 
O estudo da computabilidade tem como objetivo determinar a solucionabilidade de 
problemas, investigar a existência ou não de algoritmos que solucionem determinada 
classe de problemas. Investigar os limites da computabilidade e os limites do que pode 
efetivamente ser implementado em um computador. O efeito do estudo da 
solucionabilidade tem por objetivo evitar a pesquisa de soluções inexistentes de 
problemas. 
Um exemplo de problema que não tinha solução e que foi estudado por muitos anos foi 
um dos 23 problemas propostos por David Hilbert, no ano de 1900 durante o II Congresso 
Internacional de Matemática, entre eles consta como o décimo problema o seguinte 
enunciado: 
 
Teoria da Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
Dada uma equação diofantina P(a0, ..., an) = 0, onde P é um polinômio com 
coeficientes inteiros, quer-se saber se existe um procedimento efetivo que seja 
capaz de determinar, em um tempo finito, se suas raízes são inteiras. 
(HILBERT, 1900) 
Sabemos que as equações diofantinas são equações algébricas com coeficientes inteiros. 
Neste sentido quando o problema foi proposto por Hilbert buscava-se estabelecer 
fundamentos rigorosos para a aritmética visando representar todas as leis científicas em 
equações matemáticas. O princípio era estabelecer a consistência formal da aritmética e 
em seguida estender às demais áreas do conhecimento. 
Procurou-se definir uma linguagem puramente sintática, ou seja, sem significado, 
denominada de sistema formal. Recaiu-se então no problema da existência ou não de um 
procedimento mecânico efetivo que decidisse a veracidade ou falsidade de qualquer 
enunciado aritmético. 
Em 1928, Hilbert propôs o problema de decisão, também conhecido como 
Entscheidungsproblem, o qual questionava a existência de um procedimento mecânico, 
baseado no trabalho de Gottfried Leibniz que buscava um mecanismo mecânico de 
manipulação de fórmulas, capaz de decidir se dado um enunciado da lógica de primeira 
ordem, ele seria válido ou não em um tempo finito. 
Esta ideia de considerar a matemática um sistema formal empolgou os matemáticos no 
século XIX, pretendia-se obter uma teoria aritmética como um sistema formal consistente 
e completo. Isso infelizmente não foi possível, como foi afirmado por Kurt Gödel em 
1931 com seu teorema da não completude, também conhecido como incompleteness 
theorem: 
Todas as formulações axiomáticas consistentes da teoria dos números incluem 
proposições indecidíveis, ou seja, que não podem ser provadas como 
verdadeiras ou como falsas. Portanto, se um sistema formal é consistente, ele 
não pode ser completo, e a consistência dos axiomas não pode ser provada 
usando o próprio sistema formal. (GÖDEL, 1931) 
A demonstração usou uma codificação de primos, número de Gödel, de forma que as 
formulações axiomáticas eram codificadas em números naturais. 
A resolução do problema de decisão começou a apresentar resultados em 1936, quando 
Alonzo Church provou que não existia nenhum algoritmo definido por meio de funções 
recursivas que decidisse se para duas expressões dadas em cálculo Lambda seriam ou não 
equivalentes. Alan Turing também contribuiu na resolução do problema de decisão 
transformando-o em um problema da parada em sua máquina. 
Na resolução do problema de decisão, uma boa parte do sucesso se deu pelo uso da técnica 
da redução, teoria do princípio da redução, na qual as partes de um problema são 
transformadas em outro o que permite usar resultados já conhecidos para se obter a 
resolução de partes do problema atual e assim resolvê-lo. 
A solução definitiva do problema de decisão foi apresentada em 1970, pelo matemático 
Yuri Matiyasevich o qual provocou que tal procedimento efetivo, o algoritmo, não existe. 
A prova é complexa envolvendo teoria dos números e resultados anteriores sobre este 
problema. Basicamente se tem: 
Se R é uma relação que pode ser codificada em um número natural, então R é 
uma equação diofantina se, e somente se, R é enumerável (MATIYASEVICH, 
1970). 
 
Teoria da Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
 
O resultado disso é o conjunto das equações diofantinas com raízes inteiras não é 
solucionável. A abordagem apresentada concentra-se nos problemas com respostas 
binárias do tipo sim ou não, os quais também são conhecidos como problemas sim/não 
ou problemas de decisão. Portanto, um problema de decisão é uma questão sobre um 
sistema formal com uma resposta do tipo sim ou não, como por exemplo dados dois 
números naturais, eles são primos entre si? 
A resposta para tal problema pode ser sim ou não dependendo dos números informados. 
Um problema de decisão também pode ser formalizado como um problema de verificar 
se uma determinada palavra pertence ou não a uma linguagem formal. O conjunto contém 
exatamente as palavras para as quais a resposta à pergunta é sim. 
Assim, os problemas de decisão são problemas que tem por objetivo determinar se um 
dado elemento de algum universo pertence ou não a um determinado conjunto A, ou 
satisfazendo uma determinada propriedade. Se existir um algoritmo que que receba como 
entrada um elemento qualquer x e retorne como saída sim, caso x pertença ao conjunto 
A, ou não, caso contrário, então se diz que o problema de decisão para o conjunto A é 
solucionável. Do contrário se não existir um algoritmo capaz de fazer essa avaliação, 
então se diz que problema de decisão para o conjunto A é não solucionável. É comum 
definir-se o problema decisão em termos do conjunto de entradas para as quais o problema 
retorna sim, sendo assim, um problema de decisão é equivalente a uma linguagem formal. 
Contudo temos que ressaltar que ainda possuímos diversos problemas interessantes que 
não possuem solução, ou seja, não são solucionáveis. Alguns exemplos de problemas não 
solucionáveis de fundamental importância, introduzidos informalmente, são: 
• Detector universal de loops – dados um programa e uma entrada qualquer, não 
existe algoritmo genérico capaz de verificar se o programa vai parar ou não para 
a entrada, este problema é universalmente conhecido como o problema da parada; 
• Equivalência de compiladores – não existe algoritmo genérico que sempre pare 
capaz de comparar qualquer dos dois compiladores de linguagens livre do 
contexto, reconhecidas pelo formalismo autômato com pilha não determinístico, 
verificar se são equivalentes, se de fato reconhecem a mesma linguagem. 
Alguns problemas não solucionáveis são parcialmente solucionáveis, existe um algoritmo 
capaz de responder sim, embora eventualmente possa ficar processando indefinidamente 
para uma resposta que deveria ser não. Problemas parcialmente solucionáveis são 
computáveis e tem-se que: 
• A classe dos problemas parcialmente solucionáveis é equivalente à classe das 
linguagens enumeráveis recursivamente; 
• Comparar o cardinal da classe dos problemas computáveiscom o cardinal da 
classe dos problemas não computáveis, tal relação fornece uma noção de 
grandeza. 
Assim podemos estabelecer que: 
• A classe dos problemas computáveis é contável; 
• A classe dos problemas não computáveis é não contável. 
 
Teoria da Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
Informalmente pode-se afirmar que o cardinal da classe dos problemas não computáveis 
é muito maior que o da classe dos problemas computáveis, existem muito mais problemas 
não computáveis do que computáveis. 
A solucionabilidade de um problema é feita usando o princípio da redução, que consiste 
na investigação da solucionabilidade de um problema a partir de outro cuja classe de 
solucionabilidade é conhecida, o princípio da redução pode ser demonstrado resumido 
como a figura abaixo: 
Figura 1.1 – Princípio da redução 
 
Fonte: Tiarajú Asmuz Diverio e Paulo Blauth Menezes, 2011. 
• Sejam A e B dois problemas de decisão suponha que é possível modificar/reduzir 
o Problema A de tal forma que ele se porte como um caso do Problema B; 
• Se A é não solucionável, então como A é um caso de B conclui-se que B também 
é não solucionável; 
• Se B é solucionável, então como A é um caso de B conclui-se que A também é 
solucionável. 
 
Você sabia? 
Vamos aprofundar o conhecimento sobre a Teoria da Computabilidade? Assista ao 
vídeo Introdução à Teoria da Computabilidade – com Prof. Pablo Sampaio. Disponível 
em: 
< https://www.youtube.com/watch?v=A65SbSJX6H8 >. Acesso em: 27 abr. 2023. 
8.2. Máquina de Turing 
A noção de algoritmo não é matematicamente precisa, contudo intuitivamente um 
algoritmo deve possuir as seguintes características: 
• Ter uma descrição finita; 
• Consistir de passos: discretos em oposição ao contínuo, executáveis 
mecanicamente e executáveis em um tempo finito. 
 
Teoria da Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
A máquina de Turing, proposta por Alan Turing em 1936, é um mecanismo simples que 
formaliza a ideia de uma pessoa que realiza cálculos, apesar de sua simplicidade o modelo 
da máquina de Turing possui no mínimo o mesmo poder computacional de qualquer 
computador de propósito geral. 
O ponto de partida de Turing foi analisar a situação na qual uma pessoa, equipada com 
um instrumento de escrita e um apagador, realiza cálculos em uma folha de papel 
organizada em quadrados. Sendo assim inicialmente suponha que a folha de papel contém 
somente os dados iniciais do problema, o trabalho da pessoa pode ser resumido em 
sequências de operações simples: 
• Ler um símbolo de um quadrado; 
• Alterar um símbolo em um quadrado; 
• Mover os olhos para outro quadrado. 
Quando é encontrada alguma representação satisfatória para a resposta desejada, a pessoa 
termina seus cálculos, para viabilizar esse procedimento as seguintes hipóteses são 
aceitáveis: 
• A natureza bidimensional do papel não é um requerimento essencial para os 
cálculos, pode ser assumido que o papel consiste de uma fita infinita organizada 
em quadrados; 
• O conjunto de símbolos deve ser finito, para representar informações mais 
complexas é possível utilizar sequências de símbolos semelhante a noção de 
alfabeto e linguagem natural; 
• O conjunto de estados da mente da pessoa durante o processo de cálculo é finito, 
entre esses estados existem dois em particular estado inicial e estado final 
correspondendo ao início e ao fim dos cálculos; 
• O comportamento da pessoa é determinado somente pelo seu estado presente e 
pelo símbolo para qual sua atenção está voltada; 
• A pessoa é capaz de observar e alterar o símbolo de apenas um quadrado de cada 
vez, bem como de transferir sua atenção para somente um dos quadrados 
adjacentes. 
Modelo 
Essa noção de uma pessoa calculando pode ser vista como uma máquina constituída de 
três partes: 
• Fita – usada simultaneamente como um dispositivo de entrada, de saída e de 
memória de trabalho; 
• Unidade de controle – reflete o estado corrente da máquina, possui uma unidade 
de leitura e gravação, cabeça da fita, a qual acessa uma célula da fita de cada vez 
e se movimenta para a esquerda ou para a direita; 
• Programa, função programa ou função transição – função que define o estado da 
máquina e comanda as leituras, as gravações e o sentido de movimento da cabeça. 
A fita é finita à esquerda e infinita à direita sendo dividida em células cada uma 
armazenando um símbolo, os símbolos podem: 
• Pertencer ao alfabeto de entrada; 
• Pertencer ao alfabeto auxiliar; 
 
Teoria da Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
• Ser branco; 
• Ser marcador de início de fita. 
Inicialmente a palavra a ser processada, a informação de entrada para a máquina, ocupa 
as células mais à esquerda após o marcador de início da fita, ficando as demais com 
branco como ilustrado na figura abaixo: 
Figura 1.2 – Máquina de Turing – fita e unidade de controle 
 
Fonte: Paulo Blauth Menezes, 2011. 
 
Os símbolos 𝜷 e b representam o branco e o marcador de início de fita respectivamente. 
A unidade de controle possui um número finito e predefinido de estados a cabeça da fita 
lê o símbolo de uma célula de cada vez e grava um novo símbolo, após a leitura/gravação, 
a gravação é realizada na mesma célula de leitura, a cabeça move uma célula para a direita 
ou para a esquerda o símbolo gravado e o sentido do movimento são definidos pelo 
programa. 
Uma máquina de Turing é abreviada como MT, M é uma 8-upla: 
 M = (∑, Q, 𝜹, q0, F, V, 𝜷, ⊛) 
Na qual: 
• ∑ é um alfabeto de símbolos de entrada; 
• Q é um conjunto de estados possíveis da máquina, o qual é finito; 
• 𝜹 é a função programa, programa ou função transição, suponha que ∑ ∪ V e { 𝜷, 
⊛} são conjuntos disjuntos: 
 𝜹: Q x (∑ ∪ V ∪ { 𝜷, ⊛}) → Q x ((∑ ∪ V ∪ { 𝜷, ⊛}) x {E, D} 
A qual é uma função parcial, supondo que a função é definida para p ∈ Q, x ∈ ∑ ∪ V ∪ 
{ 𝜷, ⊛}, resultando em q ∈ Q, y ∈ ∑ ∪ V ∪ { 𝜷, ⊛} e m ∈ {E, D}, então: 
 𝜹(p, x) = (q, y, m) 
É uma transição da máquina; 
• q0 é um elemento distinguido de Q, estado inicial; 
• F é um subconjunto de Q, conjunto de estados finais; 
• V é um alfabeto auxiliar, pode ser vazio; 
• 𝜷 é o símbolo especial branco; 
• ⊛ é o símbolo de início ou marcador de início da fita; 
 
Teoria da Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
O símbolo início da fita sempre ocorre exatamente uma vez e na célula mais à esquerda 
da fita, auxiliando na identificação de que a cabeça da fita se encontra na célula mais à 
esquerda da fita. 
A função programa considera o estado corrente e o símbolo lido da fita para determinar 
o novo estado, o símbolo a ser gravado e o sentido de movimento da cabeça, sendo que 
esquerda e direita são representadas por E e D, respectivamente. A função programa pode 
ser interpretada como no diagrama abaixo: 
 
Figura 1.3 – Diagrama MT – transição 
 
Fonte: Paulo Blauth Menezes, 2011. 
Suponha a transição 𝜹(p, x) = (q, y, m), neste caso os estados inicial e finais são 
representados como nos autômatos finitos. 
A computação de uma máquina de Turing M, para uma palavra de entrada w consiste na 
sucessiva aplicação da função programa a partir do estado inicial e da cabeça posicionada 
na célula mais à esquerda da fita até ocorrer uma condição de parada. O processamento 
de M para a entrada w pode parar ou ficar processando indefinidamente, em um ciclo ou 
loop infinito. 
A parada de um processamento de uma máquina de Turing para uma entrada w pode ser 
de duas maneiras: 
• Aceita a entrada w, atinge um estado final a máquina para e a palavra w é aceita; 
• Rejeita a entrada w, sendo neste caso duas as possibilidades: 
a) a função programa é indefinida para o argumento, símbolo lido e estado corrente, 
a máquina para e a palavra w é rejeitada; 
b) o argumento corrente da função programa define um movimento à esquerda, e a 
cabeça da fita já se encontra na célulamais à esquerda a máquina para e a palavra 
w é rejeitada. 
Para definir formalmente o comportamento de uma máquina de Turing é necessário 
estender a definição da função programa usando como argumento um estado e uma 
palavra. 
 
Teoria da Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
Você sabia? 
Vamos aprofundar o conhecimento sobre Máquina de Turing? Assista ao vídeo 
Máquinas de Turing. Disponível em: 
< https://www.youtube.com/watch?v=jaygKjE4dZc>. Acesso em: 27 abr. 2023. 
8.3. Tese de Church-Turing 
O modelo abstrato de computação proposto por Alan Turing em 1936, a máquina de 
Turing tinha como objetivo explorar os limites da capacidade de expressar soluções 
problemas. Trata-se de uma proposta de definição formal da noção intuitiva de algoritmo. 
Diversos outros trabalhos como o Cálculo de Lambda, Church, 1936, e funções 
recursivas, Kleene, 1936, resultaram em conceitos equivalentes ao de Turing. O fato de 
todos esses trabalhos independentes gerarem o mesmo resultado em termos de capacidade 
de expressar computabilidade é um forte reforço no que é conhecido como tese de Church 
ou tese de Turing- Church e/ou Church-Turing. 
 
A capacidade de computação representada pela máquina de Turing é o limite 
máximo que pode ser atingido por qualquer dispositivo de computação 
(CHURCH, 1936). 
 
Em outras palavras a hipótese de Church afirma que qualquer outra forma de expressar 
algoritmos terá no máximo a mesma capacidade computacional da máquina de Turing. 
Como a noção de algoritmo ou função computável é intuitiva, a hipótese de Church não 
é demonstrável, entretanto como é assumida como verdadeira, é assumida como hipótese 
também ficou conhecida como hipótese de Church ou hipótese de Turing-Church e/ou 
Church-Turing. 
 
 
Considerações finais 
 Como vimos a importância histórica para o entendimento das teorias da 
computabilidade, máquina de Turing e tese de Turing-Church. O princípio da 
solucionabilidade é de suma importância para os algoritmos das linguagens utilizadas, a 
compreensão do funcionamento da máquina de Turing nos mostra o valor computacional 
que devemos inserir nos códigos que utilizaremos. Quanto mais direto for o código menor 
haverá a probabilidade de erro e parada de execução do programa. 
 
Teoria da Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
Referências 
DIVERIO, Tiarajú Asmuz; MENEZES, Paulo Blauth. Teoria da Computação: 
máquinas universais e computabilidade. Porto Alegre: Bookman, 2011. 
MENEZES, Paulo Blauth. Linguagens Formais e Autômatos. 6. ed. Porto Alegre: 
Bookman, 2011. 
SIPSER, Michael. Introdução à Teoria da Computação. 2. ed. São Paulo: Cengage 
Learning, 2007.