Em Teoria da Computabilidade, o Problema indecidível é um problema em que é impossível construir um algoritmo que sempre responde sim ou não, ele pode não responder ou responder errado. Mais formalmente, um problema indecidível é o problema em que a linguagem não é um conjunto recursivo; veja Decidibilidade. Existem incontáveis problemas indecidíveis, por isso essa lista é incompleta. Apesar de linguagens indecidíveis não serem recursivas, eles podem ser subconjuntos de linguagens Turing-reconhecíveis, ou seja, muitas linguagens indecidíveis podem ser recursivamente enumeráveis.
Problemas na lógica Problema de decisão de Hilbert.
Problemas sobre máquina abstratas
O problema da parada (Determina se a máquina de Turing pára). Determinar se a máquina de Turing é castor ocupado, ver Algoritmo do Castor O problema da mortalidade Teorema de Rice afirma que, para qualquer propriedade não-trivial de funções parciais, não existe um método geral e eficaz para decidir se um algoritmo calcula uma função parcial com essa propriedade.
Problemas sobre matrizes
O problema da matriz mortal. Determinar se um conjunto finito superior a matriz triangular 3 × 3 com entradas inteiras não negativas gera um semigrupo livre.
Problemas em Teoria combinatória de grupos
O problema da palavra para grupos. O problema da conjugação. O problema do grupo isomorfo.
Problemas de Topologia
Determinar se dois complexos simpliciais finitos são homeomórfos. Determinar se o complexo simplicial finito é uma superfície. Determinar se o grupo fundamental de um simplicial finito complexo é trivial.
Outros problemas
O Problema da correspondência de Post. O problema da palavra em álgebra e ciência da computação. O problema da palavra para certas linguagens formais. O problema de determinar de um dado conjunto de azulejos de Wang podem preencher um plano. O problema máquina de Post pára. O problema de determinar a complexidade de Kolmogorov de uma cadeia. Décimo problema de Hilbert Determinar se uma gramática livre de contexto gera todas as possibilidades de cadeias, ou se ela é ambígua.
Bibliografia Appendix C includes impossibility of algorithms deciding if a grammar contains ambiguities, and impossibility of verifying program correctness by an algorithm as example of Halting Problem.
Discusses intractability of problems with algorithms having exponential performance in Chapter 2, "Mathematical techniques for the analysis of algorithms." Discusses undecidability of the word problem for groups, and of various problems in topology.
Leitura futura
* problemas indecidíveis