Problema algorítmicamente irresoluble

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 19 de octubre de 2020; las comprobaciones requieren 12 ediciones .

En la teoría de la computabilidad , un problema algorítmicamente irresoluble es un problema que tiene una respuesta de sí o no para cada objeto de algún conjunto de datos de entrada, para el cual (en principio) no hay ningún algoritmo que, habiendo recibido cualquier objeto posible como datos de entrada. , se detendría y daría la respuesta correcta después de un número finito de pasos.

Problemas relacionados con las máquinas abstractas

• detener el problema
• El problema de la autoaplicabilidad
• Castor ocupado
• Cualquier problema formulado en el teorema de Rice
• Determinar si una configuración inicial dada en el juego " Life " alguna vez alcanzará una configuración final dada [1]

Problemas relacionados con matrices

• Problema de matriz moribunda : dado un conjunto finito de matrices cuadradas n  ×  n , determine si hay un producto de todas o algunas de estas matrices (posiblemente con repeticiones) en algún orden que produzca una matriz nula. El problema es indecidible incluso para n=3 (la decidibilidad para n=2 es una pregunta abierta [2] ). [3]
• Problema de matriz de identidad : dado un conjunto finito de matrices cuadradas n  ×  n , determine si hay un producto de todas o algunas de estas matrices (posiblemente con repeticiones) en algún orden que produzca la matriz de identidad. El problema es indecidible para matrices enteras a partir de n=4 [4] y decidible para n=2 [5] (la decidibilidad para n=3 es una cuestión abierta). El problema es equivalente a preguntar si un semigrupo matricial es un grupo.
• El problema de libertad de semigrupos de matrices es algorítmicamente irresoluble para matrices enteras a partir de n=3 y está abierto para n=2.

Otros temas

• Problema de permisos ( en alemán  Entscheidungsproblem ).
• Derivabilidad de una Fórmula en la Aritmética de Peano .
• Problema de correspondencia postal .
• Cálculo de la complejidad de Kolmogorov de una cadena arbitraria. Importantes consecuencias prácticas de esta afirmación para el campo de la programación:
  • la imposibilidad de crear un archivador ideal que genere para cualquier archivo de entrada un programa del menor tamaño posible que imprima este archivo
  • la imposibilidad de crear un compilador optimizador de tamaño ideal
• Décimo problema de Hilbert
  • en particular, es imposible calcular tal función: f(n) = max{min{max{|x_1|, |x_2|, ..., |x_k|: P(x_1, x_2, ..., x_k ) = 0} }}, donde k varía de 1 a n, P varía sobre todos los polinomios en k variables de grado como máximo n, y el módulo del coeficiente de cada término no excede de n. El valor de esta función nos permite restringir la enumeración de soluciones a una ecuación diofántica de grado como máximo n, con como máximo n variables, cuyo módulo de coeficientes no exceda de n. Por ejemplo, f(1)=1, f(2)=5 Si hubiera una función computable que siguiera el ritmo de f(n), entonces el décimo problema de Hilbert tendría la solución opuesta.
• Determine si el avión se puede teselar con el conjunto dado de teselas Wang .
• Determine si el plano se puede teselar con un conjunto dado de poliominós .
• El problema de la unificación de los órdenes segundo y superior.
• Problema de inferencia de tipos en el sistema de tipos Hindley-Milner con polimorfismo de rango N.

Problemas cuya irresolubilidad algorítmica no ha sido probada

Para algunos problemas, el algoritmo que los resuelve es desconocido y, por su naturaleza, son similares a problemas algorítmicamente irresolubles conocidos. Las preguntas sobre la solución algorítmica de tales problemas son problemas abiertos . Estas son algunas de estas tareas:

• Un análogo del décimo problema de Hilbert para ecuaciones de grado 3
• Un análogo del décimo problema de Hilbert para ecuaciones en números racionales [6]
• Problema de matriz moribunda para matrices de orden 2

Véase también

• Decidibilidad algorítmica de una teoría formal
• Teorema de incompletitud de Gödel

Notas

1. ↑ Computadora Life Universal . Consultado el 13 de mayo de 2010. Archivado desde el original el 31 de octubre de 2014. (indefinido)
2. ↑ ¿Cuándo es mortal un par de matrices? . Consultado el 6 de mayo de 2010. Archivado desde el original el 8 de diciembre de 2015. (indefinido)
3. ↑ Cassaigne, Julien; Halava, Vesa; Harju, Tero & Nicolas, Francois (2014), Límites de indecidibilidad más estrictos para la mortalidad matricial, problemas de cero en la esquina y más, arΧiv : 1404.0644 [cs.DM]. 
4. ↑ Paul C. Campana; Ígor Potapov. Sobre la indecidibilidad del problema de correspondencia de identidad y sus aplicaciones para semigrupos de palabras y matrices  // Revista internacional de fundamentos de  informática : diario. - World Scientific, 2010. - Vol. 21.6 . - Pág. 963-978 . -doi : 10.1142/ S0129054110007660 .
5. ↑ Christian Choffrut; Juhani Karhumaki. Algunos problemas de decisión sobre matrices enteras. (neopr.)  //ITA. - 2005. - T. 39 (1) . - S. 125-131 . -doi : 10.1051/ita : 2005007 .
6. ↑ Uspensky V. A. , Semyonov A. L. Problemas algorítmicos solucionables y no solucionables. // Kvant , 1985, nº 7, pág. 9 - 15