Un problema simple cuya capacidad de decisión no se conoce.

Me estoy preparando para una charla dirigida a estudiantes de matemáticas de pregrado y, como parte de ella, estoy considerando discutir el concepto de capacidad de decisión. Quiero dar un ejemplo de un problema que actualmente no sabemos que sea decidible o indecidible. Existen muchos problemas de este tipo, pero ninguno parece destacarse como buenos ejemplos hasta ahora.

¿Qué es un problema simple de describir cuya capacidad de decisión está abierta?

El problema de la mortalidad de matrices para matrices de 2x2. Es decir, dada una lista finita de matrices enteras 2x2 M ₁ , ..., M _k , ¿pueden multiplicarse los M _i en cualquier orden (con muchas repeticiones arbitrarias) para producir la matriz todo-0?

(Se sabe que el caso 3x3 es indecidible. El caso 1x1, por supuesto, es decidible).

ACTUALIZACIÓN: ¡Ahora se sabe que el problema que mencioné aquí es indecidible! http://arxiv.org/abs/1605.05274 Además, el documento se inspiró al leer esta misma respuesta. :)

Los programadores en su audiencia principal de matemáticas pueden sorprenderse al saber que la pregunta "¿es este tipo implícitamente convertible a ese tipo?" no se sabe que sea decidible en ninguno de Java 5, C # 4 y Scala 2.

Para más detalles, ver el artículo de Andrew Kennedy y Benjamin Pierce "Sobre la capacidad de decisión del subtipo nominal con varianza" . El documento da algunos ejemplos de restricciones adicionales a los sistemas de tipos de estos lenguajes, bajo los cuales se sabe que el subtipo nominal es decidible o indecidible.

Curiosamente, el documento se escribió mucho antes de que se agregaran covarianza y contravarianza genéricas a C #, pero los autores anticiparon correctamente la dirección en la que se dirigía el lenguaje. (Esto no es sorprendente; ¡los autores diseñaron el soporte subyacente para la varianza en el CLR que aproveché al agregar la varianza a C #! Hicieron el trabajo pesado).

Décimo problema de Hilbert sobre los racionales: "¿Esta ecuación polinómica tiene una solución racional?"

El problema de dar una recurrencia lineal junto con sus valores iniciales, ¿toma el valor 0?

Dos referencias:

http://terrytao.wordpress.com/2007/05/25/open-question-effective-skolem-mahler-lech-theorem/

http://www.cs.ox.ac.uk/joel.ouaknine/publications/positivity12.pdf

Un problema simple cuya capacidad de decisión es desconocida es el siguiente (creo que todavía está abierto):

Ajedrez infinito :

Entrada : una lista finita de piezas de ajedrez y sus posiciones iniciales en un tablero de ajedrez ; Pregunta : ¿Puede la fuerza blanca aparearse?$Z \times Z$

Si agregamos la restricción de que las Blancas deben aparearse en movimientos ( n es parte de la entrada), entonces se vuelve decidible: ver Dan Brumleve, Joel David Hamkins y Philipp Schlicht, El problema compañero-en-n del ajedrez infinito es decidible. .$n$$n$

Otro problema simple es el comportamiento de la hormiga de Langton en la configuración inicial finita.

Comportamiento de las hormigas de Langton con apoyo finito :

Los cuadrados en un avión son de diferentes colores, ya sea negro o blanco. Identificamos arbitrariamente un cuadrado como la "hormiga". La hormiga puede viajar en cualquiera de las cuatro direcciones cardinales en cada paso que da. La hormiga se mueve de acuerdo con las siguientes reglas:

• En un cuadrado blanco, gire 90 ° a la derecha, voltee el color del cuadrado, avance una unidad
• En un cuadrado negro, gire 90 ° a la izquierda, voltee el color del cuadrado, avance una unidad

Entrada : una configuración finita (blanco / negro) del plano y la posición de la hormiga;
Pregunta : ¿La hormiga siempre termina construyendo una "carretera" infinita recurrente?

Para soporte infinito, el problema es indecidible, ver: A. Gajardo, A. Moreira y E. Goles, Complejidad de la hormiga de Langton

El problema de Collatz es un problema fácil de describir cuya capacidad de decisión es abierta. Implica una recurrencia simple de operaciones aritméticas elementales.

$f(n)=\mathsf{\{}$ $n/2$$3n+1$

$n_0$

Curiosamente, se demostró que una generalización del problema de Collatz es indecidible.

Referencias

1- PROBLEMAS INCIDIBLES: UN MUESTREO , BJORN POONEN

2- Weisstein, Eric W. "Problema de Collatz". De MathWorld: un recurso web de Wolfram.

3- El problema 3X + 1: una visión general , Jeffrey C. Lagarias

Se desconoce si es o no determinable determinar si una forma dada puede enlosar el plano .

La capacidad de decisión de la contención de consultas conjuntivas ha estado abierta durante más de veinte años. Resolver esto sería un gran avance en la teoría de bases de datos.

$Q_1$$Q_2$$Q_1$$I$$Q_2$$I$

En las consultas conjuntivas se usa AND para vincular predicados cuantificados existencialmente. En términos de SQL, las consultas conjuntivas son consultas SELECT-FROM-WHERE que usan "=" y "AND" pero no subconsultas ni agregación. Este es quizás el tipo más común de consulta de base de datos e incluye la mayoría de las consultas de motores de búsqueda.

$I$$Q_1$$Q_2$

$\ne$

$(N,+,\times)$$(N,+,\times)$

Para obtener indicaciones sobre la extensa literatura y un tratamiento riguroso, vea el documento ToDS (en prensa) de algunas personas.

$Q$$R$$Q$$Q \text{ AND } R$$Q$

Problema de correspondencia de la publicación con un número fijo de mosaicos de entre 3 y 6.

Si bien no es realmente sencillo de describir, tiene una descripción muy "lúdica", y me parece adecuado para conversaciones a nivel de intuición.

El problema generalizado de la altura de las estrellas: "¿cuántas anidaciones de estrellas de Kleene necesito para representar este lenguaje regular, con una expresión regular con complementación permitida?"

Ni siquiera sabemos si el algoritmo que siempre devuelve 1 (excepto 0 para idiomas sin estrellas, que es un caso decidible) es correcto.

Un problema de la teoría de autómatas.

$D$

$x$$D$$x$$x$$L(D) \cap Primes$

Comentarios: Originalmente escuché este problema de una respuesta de intercambio de pila de Jeffrey Shallit. Si conoce alguna referencia al respecto, hágamelo saber. ¡Gracias!

Artículos Relacionados:

(1) ¿Queda algún problema abierto sobre los DFA?

(2) https://cs.stackexchange.com/questions/48084/determining-if-infinite-binary-language-dfas-contain-at-least-1-prime

Trabajo relacionado: https://cs.uwaterloo.ca/~shallit/Papers/br10.pdf

"Elementos mínimos para los números primos" por C. Bright, R. Devillers y J. Shallit

Mapas iterados en el intervalo (descripción desde aquí ):

(Muy relacionado con el problema propuesto por Magnus Find)

$F$$x$$x$$x$$F(x)$$F(F(x))$$F$$x$$F$

$F$$x$$y$$x$$y$

$F$

$F$$x$$y$$x$$F$

Una referencia: Asarin 2011 .

Parece que hay una forma / ángulo bastante natural para estudiar esta pregunta que se utiliza en al menos 3 documentos de la siguiente manera.

$TM(k,l)$$k$$l$$k,l$$k,l$

los resultados se pueden mostrar en una cuadrícula como en algunas de las siguientes referencias. También en la región intermedia se sabe que algunas máquinas (no resueltas) son capaces de simular la conjetura de Collatz para algunas entradas.

por lo tanto, hay claramente un "punto de transición" como los fenómenos que operan aquí pero no dentro de una región computable sino en un sentido inusual de entre computable y no computable.

• Pequeñas máquinas de Turing y competencia generalizada de castores ocupados Michel

• La complejidad de las pequeñas máquinas universales de Turing: una encuesta Woods, Neary

• En los límites de la solubilidad y la insolubilidad en los sistemas de etiquetas. Resultados teóricos y experimentales De Mol

$2^8$

También como un ejemplo de "casi omisión", o "pregunta abierta resuelta relativamente recientemente como TM completa", la máquina Wolfram 2,3 se demostró universal en 2007 por un premio de $ 25K . El concurso se anunció en mayo de 2007 y el concurso anunció al ganador Smith en octubre de 2007 .

Hay una forma bastante natural de mapear la mayoría de los problemas abiertos en cuestiones de (des) capacidad de decisión. Por lo general, no se sabe que la mayoría de los problemas abiertos sean demostrables o no demostrables.

en la web existe cierta confusión informal sobre la indecidibilidad del problema P vs NP , que no es estrictamente un problema de decisión, por lo tanto, hablar de su indecidibilidad no es técnicamente correcto. pero, por otro lado, parece haber un vínculo cercano / natural entre la indecidibilidad y la demostrabilidad de la siguiente manera.

por ejemplo considere

$L$$x$$O(n^x)$

¿Es este lenguaje decidible? esa es una pregunta sobre un lenguaje con su capacidad de decisión abierta que está básicamente estrechamente vinculada (incluso, prácticamente idéntica) al problema P vs NP y su probabilidad inherente (¿no?).

en cuanto a P vs NP como "simple de describir", solo requiere conceptos de TM , notación de tiempo de ejecución Big O , no determinismo que son bastante simples (algunos de los conceptos más básicos de TCS) y que se enseñan a nivel de pregrado o que un superdotado estudiante de secundaria podría entender.

de hecho, NP vs P / Poly también está abierto, y puede mapearse en una pregunta abierta sobre la capacidad de decisión de la misma manera, y esto puede expresarse como un problema bastante simple sobre el crecimiento de circuitos mínimos (¿monótonos?) para reconocer NP completo problemas (por ejemplo, camarillas).