Problema indecidible

En teoria de la computabilidad i en teoria de la complexitat computacional, un problema indecidible és un problema de decisió para el qual és impossible construir un algoritme que sempre conduïxca a una resposta de sí o no correcta. El problema de la parada és un eixemple: no existix algoritme que determine de manera correcta si un programa arbitrari es detindrà, una volta siga eixecutat...

Un problema de decisió és qualsevol pregunta arbitrària de sí o no en un conjunt infinit d'entradas. Per això és tradicional definir el problema de decisió com equivalent al conjunt d'entrades per a les que el problema retorna sí. Estes entrades poden ser número natural, o ben valors d'un atre tipo, tals com cadenes d'un llenguage formal.

Per mig d'alguna codificació, tal com una numeració de Gödel, les cadenes es poden codificar com a número natural. Aixina, un problema de decisió informalmente expressat en térmens d'un llenguage formal és també equivalent a un conjunt d'número natural. Per a mantindre simple la definició formal, s'expressa en térmens de subconjunts dels número natural.

Formalment, un problema de decisió és un subconjunt dels número natural. El problema informal corresponent consistix en decidir si un número donat està en el conjunt. A un problema de decisió A, si A és un conjunt recursivo, se li denomina decidible, o efectivament solucionable. Si A és un conjunt recursivamente enumerable, el problema és parcialment decidible, semidecidible, solucionable, o demostrador. A problemes parcialment decidibles i als no decidibles se'ls califica de indecidibles.

Per a demostrar que un problema és indecidible, generalment es pren un problema que ya s'ha demostrat que ho és i es construïx una transformació que ho reduïx a una instància del nou problema. Es conclou que no pot existir un algoritme per a decidir sobre el nou problema ya que eixe algoritme serviria també per a decidir sobre un problema conegut com indecidible.

Eixemples de problemes indecidibles

Existix una infinitat de problemes indecidibles, per lo que qualsevol llista de problemes indecidibles és necessàriament incompleta.

En llògica

Inferència i verificació de tipos en llògica de segon orde. l'Entscheidungsproblem de Hilbert.

Màquines abstractes

• Problema de parada (determinar si una màquina de Turing es deté en una entrada donada) i el problema de mortalitat (determinant si es deté per a cada configuració de partida).

Determinar si una màquina de Turing és campeó del joc del castor ocupat (és dir, és el més llarc entre les màquines de Turing de detenció en el mateix número d'estats). El Teorema de Rice afirma que, per a totes les propietats no trivials de les funcions parcials, és indecidible si una màquina determinada calcula una funció parcial en eixa propietat.

Matrius

• Problema de la matriu mortal: determinar, donat un conjunt finito de n × n matrius en entrades sanceres, si es poden multiplicar en algun orde, possiblement en repetició, per a obtindre la matriu zero. Açò se sap que és indecidible per a un conjunt de sis o més matrius 3 × 3, o un conjunt de dos matrius 15 × 15..

Determinar si un conjunt finito de matrius 3 × 3 triangulars superiors en entrades sanceres no negatives genera un semigrupo lliure.

Física quàntica

L'existència d'una brecha espectral d'un material quàntic

Teoria combinatòria de grups

• El problema de la conjugació.

El problema del isomorfisme grupal. Problemes de topología Determinar si dos complexos simpliciales finitos són homeomorfos. Determinar si un complex simplicial finito és (homeomorfo a) un colector. Determinar si el grup fonamental d'un complex simplicial finito és trivial.

Atres problemes

El problema de Correspondència de Post. El problema de determinar si un conjunt donat de rajoletes de Wang pot alicatar el pla.

El problema de si un sistema d'etiquetes es deté. El problema de determinar la complexitat de Kolmogorov d'una cadena. El dècim problema de David Hilbert: el problema de decidir si una equació diofántica (equació polinomial multivariable) té una solució en número entero. Determinar si una gramàtica sense context genera totes les cadenes possibles, o si és ambigua. Donades dos gramàtiques sense context, determinar si generen el mateix conjunt de cadenes, o si es genera un subconjunt de les cadenes generades per l'atre, o si hi ha alguna cadena en absolut que abdós generen.

Vore també

• Entscheidungsproblem

Bibliografia

• Rajeev Motwani i Jeffrey D. Ullman. Introducció la teoria d'autómates, llenguages i computació.
• Elisa Vise. Introducció a la Teoria de la Computació.