En la teoría de la computabilidad , un problema indecidible es un tipo de problema computacional que requiere una respuesta sí / no, pero donde no puede haber ningún programa de computadora que siempre dé la respuesta correcta; es decir, cualquier programa posible a veces da una respuesta incorrecta o se ejecuta indefinidamente sin dar ninguna respuesta. Más formalmente, un problema indecidible es un problema cuyo lenguaje no es un conjunto recursivo ; ver el artículo Lenguaje decidible . Hay innumerables problemas indecidibles, por lo que la siguiente lista es necesariamente incompleta. Aunque los lenguajes indecidibles no son lenguajes recursivos, pueden ser subconjuntos de Turing lenguajes reconocibles: es decir, estos lenguajes indecidibles pueden ser enumerables de forma recursiva.
Muchos, si no la mayoría, de los problemas indecidibles en matemáticas se pueden plantear como problemas de palabras : determinar cuándo dos cadenas distintas de símbolos (que codifican algún concepto u objeto matemático) representan el mismo objeto o no.
Para la indecidibilidad en matemáticas axiomáticas, consulte Lista de declaraciones indecidibles en ZFC .
Problemas de lógica
- Entscheidungsproblem de Hilbert .
- Inferencia de tipos y comprobación de tipos para el cálculo lambda de segundo orden (o equivalente). [1]
- Determinar si una oración de primer orden en la lógica de los gráficos se puede realizar mediante un gráfico finito no dirigido. [2]
- Teorema de Trakhtenbrot: la satisfacibilidad finita es indecidible.
- Satisfacción de las cláusulas Horn de primer orden .
Problemas sobre máquinas abstractas
- El problema de la detención (determinar si una máquina de Turing se detiene con una entrada determinada) y el problema de la mortalidad (determinar si se detiene en cada configuración inicial).
- Determinar si una máquina de Turing es un campeón de castor ocupado (es decir, es la más larga entre las máquinas de Turing detenidas con el mismo número de estados y símbolos).
- El teorema de Rice establece que para todas las propiedades no triviales de las funciones parciales, es indecidible si una máquina dada calcula una función parcial con esa propiedad.
- El problema de la detención de una máquina Minsky : un autómata de estado finito sin entradas y dos contadores que pueden incrementarse, decrementarse y comprobarse a cero.
- Universalidad de un autómata Pushdown no determinista : determinar si se aceptan todas las palabras.
- El problema de si un sistema de etiquetas se detiene.
Problemas sobre matrices
- El problema de la matriz mortal : determinar, dado un conjunto finito de n × n matrices con entradas enteras, si pueden multiplicarse en algún orden, posiblemente con repetición, para producir la matriz cero . Se sabe que esto es indecidible para un conjunto de seis o más matrices de 3 × 3, o un conjunto de dos matrices de 15 × 15. [3]
- Determinar si un conjunto finito de matrices triangulares superiores de 3 × 3 con entradas enteras no negativas genera un semigrupo libre .
- Determinar si dos subsemigrupos de matrices enteras generados finitamente tienen un elemento común.
Problemas en la teoría combinatoria de grupos
Problemas en topología
- Determinar si dos complejos simpliciales finitos son homeomorfos .
- Determinar si un complejo simplicial finito es (homeomorfo a) una variedad .
- Determinar si el grupo fundamental de un complejo simplicial finito es trivial.
Problemas en el análisis
- Para funciones en ciertas clases, el problema de determinar: si dos funciones son iguales, conocido como problema de equivalencia cero (ver el teorema de Richardson ); [4] los ceros de una función; si la integral indefinida de una función también está en la clase. [5] Por supuesto, algunas subclases de estos problemas son decidibles. Por ejemplo, existe un procedimiento de decisión eficaz para la integración elemental de cualquier función que pertenezca a un campo de funciones elementales trascendentales, el algoritmo de Risch ).
- "El problema de decidir si la integral múltiple de contorno definida de una función meromórfica elemental es cero sobre una variedad analítica real en todas partes en la que es analítica", una consecuencia del teorema de MRDP que resuelve el décimo problema de Hilbert . [5]
- Determinación del dominio de una solución a una ecuación diferencial ordinaria de la forma
- donde x es un vector en R n , p ( t , x ) es un vector de polinomios en t y x , y (t 0 , x 0 ) pertenece a R n + 1 . [6]
Problemas sobre los lenguajes formales y las gramáticas.
- El problema de la correspondencia postal .
- Determinar si una gramática libre de contexto genera todas las cadenas posibles o si es ambigua.
- Dadas dos gramáticas libres de contexto, determinar si generan el mismo conjunto de cadenas, o si una genera un subconjunto de las cadenas generadas por la otra, o si hay alguna cadena que ambos generan.
Otros problemas
- El problema de determinar si un conjunto dado de fichas de Wang puede enlosar el avión.
- El problema de determinar la complejidad de Kolmogorov de una cuerda.
- Décimo problema de Hilbert : el problema de decidir si una ecuación diofántica (ecuación polinomial multivariable) tiene una solución en números enteros.
- Determinar si un punto inicial dado con coordenadas racionales es periódico, o si se encuentra en la cuenca de atracción de un conjunto abierto dado, en un mapa iterado lineal por partes en dos dimensiones, o en un flujo lineal por partes en tres dimensiones. [7]
- Determinar si una fórmula de cálculo λ tiene una forma normal.
- El Juego de la vida de Conway sobre si se le da un patrón inicial y otro patrón, ¿puede el último patrón aparecer alguna vez desde el inicial?
- La regla 110 - la mayoría de las preguntas que involucran la propiedad "X", ¿pueden aparecer más tarde?
- El problema de determinar si un sistema mecánico cuántico tiene una brecha espectral . [8] [9]
- Determinar si un jugador tiene una estrategia ganadora en un juego de Magic: The Gathering . [10]
- Planificación en un proceso de decisión de Markov parcialmente observable .
- El problema de planificar los viajes aéreos de un destino a otro, cuando se tienen en cuenta las tarifas . [11]
Ver también
- Listas de problemas
- Lista de problemas no resueltos
- Reducción (complejidad)
Notas
- ^ Wells, JB (1993). "La tipificación y la verificación de tipos en el cálculo lambda de segundo orden son equivalentes e indecidibles". Tech. Rep. 93-011 . Computación. Sci. Departamento, Univ. De Boston: 176-185. CiteSeerX 10.1.1.31.3590 .
- ^ Trahtenbrot, BA (1950). "La imposibilidad de un algoritmo para el problema de decisión para dominios finitos". Doklady Akademii Nauk SSSR . Series nuevas. 70 : 569–572. Señor 0033784 .
- ^ Cassaigne, Julien; Halava, Vesa; Harju, Tero; Nicolás, Francois (2014). "Límites de indecidibilidad más estrictos para la mortalidad de la matriz, problemas de cero en la esquina y más". arXiv : 1404.0644 [ cs.DM ].
- ^ Keith O. Geddes, Stephen R. Czapor, George Labahn, Algoritmos para álgebra informática , ISBN 0585332479 , 2007, pág. 81ff
- ^ a b Stallworth, Daniel T. y Fred W. Roush Una propiedad indecidible de los procedimientos de integrales definidas de la American Mathematical Society Volumen 125, Número 7, julio de 1997, páginas 2147-2148
- ^ Graça, Daniel S .; Buescu, Jorge; Campagnolo, Manuel L. (21 de marzo de 2008). "La delimitación del dominio de la definición es indecidible para las EDO polinomiales" . Notas electrónicas en informática teórica . 202 : 49–57. doi : 10.1016 / j.entcs.2008.03.007 .
- ^ Moore, Cristopher (1990), "Impredecibilidad e indecidibilidad en sistemas dinámicos" (PDF) , Physical Review Letters , 64 (20): 2354-2357, Bibcode : 1990PhRvL..64.2354M , doi : 10.1103 / PhysRevLett.64.2354 , PMID 10041691.
- ^ Cubitt, Toby S .; Pérez-García, David; Wolf, Michael M. (2015). "Indecidibilidad de la brecha espectral". Naturaleza . 528 (7581): 207–211. arXiv : 1502.04135 . Código Bibliográfico : 2015Natur.528..207C . doi : 10.1038 / nature16059 . PMID 26659181 . S2CID 4451987 .
- ^ Bausch, Johannes; Cubitt, Toby S .; Lucia, Angelo; Pérez-García, David (17 de agosto de 2020). "Indecidibilidad de la brecha espectral en una dimensión" . Physical Review X . 10 (3): 031038. Código Bibliográfico : 2020PhRvX..10c1038B . doi : 10.1103 / PhysRevX.10.031038 .
- ^ Herrick, Austin; Biderman, Stella; Churchill, Alex (24 de marzo de 2019). "Magic: The Gathering es Turing completo". arXiv : 1904.09828v2 . Código bibliográfico : 2019arXiv190409828C . Cite journal requiere
|journal=
( ayuda ) - ^ de Marcken, Carl. "Complejidad computacional de la planificación de viajes aéreos" (PDF) . Software ITA . Consultado el 4 de enero de 2021 .
Bibliografía
- Brookshear, J. Glenn (1989). Teoría de la Computación: lenguajes formales, autómatas y complejidad . Redwood City, California: Benjamin / Cummings Publishing Company, Inc. El apéndice C incluye la imposibilidad de que los algoritmos decidan si una gramática contiene ambigüedades y la imposibilidad de verificar la corrección del programa mediante un algoritmo como ejemplo de problema de detención.
- Halava, Vesa (1997). "Problemas decidibles e indecidibles en la teoría de matrices". Informe técnico TUCS. 127 . Centro Turku de Ciencias de la Computación. CiteSeerX 10.1.1.31.5792 . Cite journal requiere
|journal=
( ayuda ) - Moret, BME; HD Shapiro (1991). Algoritmos de P a NP, volumen 1 - Diseño y Eficiencia . Redwood City, California: Benjamin / Cummings Publishing Company, Inc. Discute la intratabilidad de problemas con algoritmos que tienen un rendimiento exponencial en el Capítulo 2, "Técnicas matemáticas para el análisis de algoritmos".
- Weinberger, Shmuel (2005). Computadoras, rigidez y módulos . Princeton, Nueva Jersey: Princeton University Press. Analiza la indecidibilidad del problema verbal para grupos y de varios problemas de topología.
Otras lecturas
- Poonen, Bjorn (2 de abril de 2012), Problemas indecidibles: una muestra , arXiv : 1204.0299 , Bibcode : 2012arXiv1204.0299P
enlaces externos
- Discusión en MathOverflow