Decidibilidade linguagens decidíveis e redutibilidade

Seminário de Teoria da Computação
Tema 2: Decidibilidade Linguagens Decidíveis e Redutibilidade
Ciência da Computação
6º Semestre

Nome: Renato Lima da Silva RA: 0991007327

Decidibilidade
Decidibilidade é o estudo dos problemas codificados como linguagens;
Por que estudar decidibilidade?
Ajuda a identificar problemas insolúveis;
Evita desperdício de tempo e esforço com a tentativa de resolução de problemas insolúveis;
Aponta para possibilidades de simplificações e/ ou alterações do problema original, a fim de que ele se torne solúvel;
Amplia a sua compreensão sobre a natureza, as possibilidades e os limites da computação.
Decidibilidade
Objetivos
Investigar o poder de algoritmos para a solução de problemas.
Explorar os limites da possibilidade de solução de problemas por processos algorítmicos.
Demonstrar que certos problemas podem ser resolvidos por processos algoritmos e outros não.
Linguagens decidíveis
Exemplo de linguagem decidível de aceitação em autômatos finitos determinísticos:

Linguagens Decidíveis
Linguagens Regulares
Problemas decidíveis:
Um dado autômato finito aceita uma cadeia em particular?
A linguagem de um autômato finito é vazia?
Dois autômatos finitos são equivalentes?
Outros problemas computacionais podem ser formulador como a pertinência a uma certa linguagem. Mostrar que a linguagem é decidível equivale a mostrar que o problema computacional é decidível.
Redutibilidade
Conceito
Técnica para determinar a decidibilidade de um problema a partir de outro cuja natureza é conhecida; Uma redução é uma maneira de converter um problema em um outro de tal forma que uma solução para o segundo problema possa ser usada para resolver o primeiro problema:

Redução de P1 para P2

Redutibilidade
Redução
Esquema de conversão de um problema em algum outro, de modo que a solução deste segundo problema passa ser utilizada para resolver o primeiro.
Se A é redutível a B, resolver A não pode ser mais difícil do que