Lista de problemas indecidíveis

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

• Brookshear, J. Glenn (1989). Theory of Computation: Formal Languages, Automata, and Complexity. Redwood City, California: Benjamin/Cummings Publishing Company, Inc.  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.
• Halava, Vesa (1997). «Decidable and undecidable problems in matrix theory». Turku Centre for Computer Science. TUCS technical report. 127 
• Moret, B. M. E.; H. D. Shapiro (1991). Algorithms from P to NP, volume 1 - Design and Efficiency. Redwood City, California: Benjamin/Cummings Publishing Company, Inc.  Discusses intractability of problems with algorithms having exponential performance in Chapter 2, "Mathematical techniques for the analysis of algorithms."
• Weinberger, Shmuel (2005). Computers, rigidity, and moduli. Princeton, NJ: Princeton University Press  Discusses undecidability of the word problem for groups, and of various problems in topology.

Leitura futura

• Poonen, Bjorn (2 de abril de 2012), Undecidable problems: a sampler, arXiv:1204.0299