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 (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.
  • 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 April 2012), Undecidable problems: a sampler