asassa

DecidibilidadeDecidibilidade é 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 deresoluçã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 problemaspor 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ômatosfinitos 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 oproblema 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 deconverter 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 deconversã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