Anexo:Lista de problemas indecidíveis

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

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]

Problemas sobre máquina abstratas[editar | editar código-fonte]

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]

Outros problemas[editar | editar código-fonte]

Bibliografia[editar | editar código-fonte]

  • Brookshear, J. Glenn. Theory of Computation: Formal Languages, Automata, and Complexity. Redwood City, California: Benjamin/Cummings Publishing Company, Inc., 1989. 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.
  • Moret, B. M. E.. Algorithms from P to NP, volume 1 - Design and Efficiency. Redwood City, California: Benjamin/Cummings Publishing Company, Inc., 1991. Discusses intractability of problems with algorithms having exponential performance in Chapter 2, "Mathematical techniques for the analysis of algorithms."
  • Weinberger, Shmuel. Computers, rigidity, and moduli. Princeton, NJ: Princeton University Press, 2005. Discusses undecidability of the word problem for groups, and of various problems in topology.

Leitura futura[editar | editar código-fonte]

  • Poonen, Bjorn (2 April 2012), Undecidable problems: a sampler