Problemas de decisión para los que no se sabe si son decidibles

Question

En la teoría de la computabilidad, ¿cuáles son los ejemplos de problemas de decisión de los que no se sabe si son decidible ?

Answer 1

Un secuencia de recurrencia lineal entera es una secuencia $x_0, x_1, x_2, \ldots$ de enteros que obedece a una relación de recurrencia lineal $$x_n = a_1 x_{n-1} + a_2 x_{n-2} + \cdots + a_d x_{n-d}$$ para algún número entero $d\ge 1$ , algunos coeficientes enteros $a_1, \ldots, a_d$ y todos $n\ge d$ . El siguiente problema se conoce a veces como "problema de Skolem":

Dado $d$ , $a_1, \ldots, a_d$ , $x_0, \ldots x_{d-1}$ ¿existe $n$ tal que $x_n=0$ ?

Se desconoce si el problema anterior es indecidible. Para más información, véase Entrada del blog de Terry Tao sobre el tema.

Answer 2

En El juego de la vida de Conway el problema de decidir si un patrón dado con un número finito de células vivas es un Jardín del Edén (es decir, si carece de predecesor).

El principal obstáculo es que podría haber un patrón que tenga un número finito de células vivas y un predecesor, pero tal que todos sus predecesores tengan infinitas células vivas. Si supiéramos que no existen tales patrones, el problema sería decidible.

Añadido el 3 de diciembre de 2019: Tras conocer el problema a través de este post, Ville Salo y Ilkka Törmä han elaborado un documento (" Jardines del Edén en el Juego de la Vida ") demostrando que este problema es decidible. Curiosamente, no proceden mediante el método que sugerí aquí. Sigue siendo un problema abierto determinar si existe un patrón que no sea el Jardín del Edén con un número finito de células vivas y cuyos predecesores tengan un número infinito de células vivas.

Answer 3

En respuesta a esta CompSciTheory ( cstheory ) pregunta, Un problema sencillo cuya decidibilidad se desconoce , I publicado eso:

Se desconoce si es decidible determinar si una forma dada puede embaldosar el plano ,

refiriéndose a una pregunta anterior de cstheory. Esto está abierto incluso para las fichas de poliomino.

---

         
          (Imagen de Wikipedia .)

---

Answer 4

El problema de palabras para un grupo finitamente presentado $G = \langle A \mid R \rangle $ y el homomorfismo canónico asociado $\pi : F_A \to G$ , pregunta: dado un elemento $w \in F_A$ ¿tenemos $\pi(w) = 1$ ? Existen grupos finitamente presentados en los que el problema de la palabra es indecidible, un resultado debido independientemente a Novikov y Boone.

Sin embargo, W. Magnus demostró que para grupos de un relator , es decir, los grupos $G = \langle A \mid w= 1 \rangle$ con una sola relación definitoria, el problema de la palabra es siempre decidible (aunque la complejidad temporal de esta solución sigue siendo desconocida en general hasta donde yo sé).

Sin embargo, el siguiente problema natural sigue abierto:

¿Es el problema de la palabra siempre decidible para los grupos de dos relatores $G = \langle A \mid w_1 = 1, w_2 = 1 \rangle$ ?

Esto aparece en el Cuaderno Kourovka como el problema 9.29.

También hay ejemplos concretos de grupos para los que no sabemos si su problema de palabras es decidible o no. Por ejemplo, sabemos muy poco sobre cómo resolver el problema de palabras en la mayoría de los grupos de Artin . El siguiente es un problema abierto que aparece en el enlace anterior:

Dejemos que $G = \langle a, b, c, d \mid aba=bab, ad = da, bdb = dbd, aca = cac, bcb = cbc, cdc = dcd\rangle$ .

¿Es el problema de palabras para $G$ ¿decidible?

Es un poco sorprendente que este problema esté abierto, si se tiene en cuenta la semigrupo con los mismos generadores y las mismas relaciones definitorias, entonces el problema de las palabras (adecuadamente formulado como el problema de comparar dos palabras) se puede resolver fácilmente.

Answer 5

$k$ -Disección de piezas no se sabe que sea decidible. Dados dos polígonos y un número entero $k$ ¿existe una disección del primer polígono en k trozos que se puedan volver a ensamblar en el segundo?