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 editar

Problema de decisão de Hilbert.

Problemas sobre máquina abstratas editar

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 editar

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 editar

Problemas de Topologia editar

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 editar

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 editar

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 editar

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