TEORIA DA COMPUTAÇÃO - T4

Prévia do material em texto

TEORIA DA COMPUTAÇÃO – T4
José Augusto Accorsi, Gabriel Colling e Leonardo Morais
1. Quais as ideias básicas do princípio da redução? 
	A ideia básica do principio da redução é investigar a solucionabilidade de um problema a partir de outro, cuja classe de solucionalidade é conhecida.
 
2. O que é um problema de decisão? 
	Problema de decisão são problemas do tipo SIM/NÃO, com o objetivo de investigar a computabilidade. A ideia básica é identificar se a função associada a eles é computável em uma máquina universal.
3. Defina a relação entre as seguintes classes de problemas:
a) Solucionáveis 
Um problema é dito solucionável se existe um algoritmo (Máquina Universal) que solucione o problema para qualquer entrada informando uma resposta de aceitação ou rejeição (resposta negativa).
b) Parcialmente solucionáveis (computáveis) 
	Um problema é dito parcialmente solucionável se existe um algoritmo que soluciona o problema e informa a resposta se ela é positiva. Porém, se for negativa, o algoritmo pode parar ou continuar processando indefinidamente.
c) Não-solucionáveis 
	Um problema é dito não solucionável se não existe um algoritmo que sempre resolva o problema.
d) Completamente insolúveis (não-computáveis) 
	Um problema é dito completamente insolúvel se não existe um algoritmo (Máquina Universal) que solucione o problema tal que sempre para quando a resposta é afirmativa (ACEITA). Os problemas Completamente Insolúveis não possuem solução total nem parcial.
4. Qual a diferença entre uma linguagem recursiva e uma linguagem enumerável recursivamente? Qual a relação dessa diferença entre a diferença de problemas parcialmente solucionáveis e problemas não solucionáveis?
	Uma linguagem recursivamente enumerável é uma linguagem formal para a qual existe uma máquina de Turing que irá parar e aceitar quando se roda com qualquer cadeia da linguagem na entrada, pode parar e rejeitar ou entrar em loop quando se roda com qualquer cadeia que não é da linguagem. Esta é a diferença entre linguagem recursiva, que exige que a máquina de Turing sempre pare, ou seja a diferença entre as duas tem relação com a sua solucionabilidade. 
	Logo, podemos afirmar que classe dos problemas solucionáveis corresponde à classe das linguagens recursivas e a classe dos problemas não solucionáveis corresponde a classe das linguagens enumeráveis recursivamente.