Decidibilida

Decidibilidade
Em teoria Decidibilidade provem da palavra decidível, onde, na lógica o termo decidível, refere-se a um problema de decisão, ou seja, a questão da existência de um método efetivo para determinar a ligação a um conjunto de fórmulas. O conceito de decidibilidade não trata a quantidade de tempo gasto e sim se ele é finito.
Decidibilidade possui como objetivo, investigar a existência ou não de algoritmos que solucionem determinada classe de problema e busca evitar a pesquisa de soluções inexistentes.
Um problema é decidível se e somente se ele é responsável por um algoritmo, para qualquer entrada pertencente ao seu domínio, caso contrário ele é um problema indecidível.
Sistemas lógicos, são decidíveis se a relação em seu conjunto de fórmulas logicamente válido pode ser efetivamente determinado. Uma teoria em um sistema lógico fixo é decidível se existe um algoritmo eficiente para determinar se fórmulas arbitrárias pertencem a ela, porém muitos problemas importantes são indecidíveis.
Contudo, em 1915, o matemático alemão Leopold Löwenheim (Krefeld, 26 de junho de 1878 — Berlim, 5 de maio de 1957) instituiu como umas das primeiras teorias decidíveis, o conjunto de primeira ordem de validações lógicas na assinatura com apenas igualdade.

Relação com computabilidade
A definição de uma teoria decidível pode ser dada em termos de métodos eficazes ou em termos de funções computáveis. Estes termos são geralmente considerados equivalentes pela Tese de Church, onde a prova de que um sistema lógico ou uma teoria é indecidível usa a definição formal de computabilidade para mostrar que um determinado conjunto não é um conjunto decidível, e depois utiliza a tese de Church para mostrar que a teoria ou sistema lógico não é decidível por qualquer método eficaz.