Lista de problemas indecidíveis – Wikipédia, a enciclopédia livre
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 | editar código-fonte]- Problema de decisão de Hilbert.
Problemas sobre máquina abstratas
[editar | editar código-fonte]- 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 | editar código-fonte]- 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 | editar código-fonte]Problemas de Topologia
[editar | editar código-fonte]- 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 | editar código-fonte]- 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 | editar código-fonte]- 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 | editar código-fonte]- Poonen, Bjorn (2 de abril de 2012), Undecidable problems: a sampler, arXiv:1204.0299