¿Cuáles son los ejemplos más simples de programas que no sabemos si terminan?

El problema de detención indica que no existe un algoritmo que determine si un programa determinado se detiene. Como consecuencia, debe haber programas sobre los que no podemos saber si terminan o no. ¿Cuáles son los ejemplos más simples (más pequeños) conocidos de tales programas?

Un ejemplo bastante simple podría ser un programa que pruebe la conjetura de Collatz :

Se conoce a alto por hasta al menos , pero en general es un problema abierto.$n$$5 × 2^{60} ≈ 5.764 × 10^{18}$

El problema de detención indica que no existe un algoritmo que determine si un programa determinado se detiene. Como consecuencia, debe haber programas sobre los que no podemos saber si terminan o no.

"Nosotros" no somos un algoritmo =) No existe un algoritmo general que pueda determinar si un programa determinado se detiene para cada programa .

¿Cuáles son los ejemplos más simples (más pequeños) conocidos de tales programas?

Considere el siguiente programa:

n = 3
while true:
    if is_perfect(n):
            halt()
    n = n + 2

La función is_perfect verifica si n es un número perfecto . No se sabe si hay números perfectos impares, por lo que no sabemos si este programa se detiene o no.

Usted escribe:

El problema de detención indica que no existe un algoritmo que determine si un programa determinado se detiene. Como consecuencia, debe haber programas sobre los que no podemos saber si terminan o no.

Este no es un secuestro, en ambas direcciones. Sucumbes a una falacia común que vale la pena abordar.

Dado cualquier programa fijo , su problema de detención ("¿ P siempre se detiene?") Siempre es decidible, porque la respuesta es "sí" o "no". Incluso si no puede decir cuál es, sabe que uno de los dos algoritmos triviales que responden siempre "sí" resp. "no" resuelve el problema de P -halting.$P$$P$$P$

Solo si requiere que el algoritmo resuelva el problema de Detención de todos los programas, puede demostrar que dicho algoritmo no puede existir.

Ahora, saber que el problema de Detener es indecidible no implica que haya ningún programa que nadie pueda probar su terminación o bucle. Incluso si no eres más poderoso que una máquina de Turing (lo cual es solo una hipótesis, no un hecho comprobado), todo lo que sabemos es que ningún algoritmo / persona puede proporcionar tal prueba para todos los programas. Puede haber una persona diferente que pueda decidir para cada programa.

Algunas lecturas más relacionadas:

• ¿Cómo puede ser decidible si tiene alguna secuencia de dígitos?$\pi$
• Potencia informática humana: ¿pueden los humanos decidir el problema de detención en las máquinas Turing?
• Algoritmo para resolver el "problema de detención" de Turing
• Síntesis del programa, capacidad de decisión y el problema de la detención.
• ¿Es posible resolver el problema de detención si tiene una entrada restringida o predecible?
• ¿Por qué las funciones totales no son enumerables?

Entonces verá que su pregunta real (como se repite a continuación) no tiene nada que ver con si el problema de detención es computable. En absoluto.

¿Cuáles son los ejemplos más simples (más pequeños) conocidos de [programas que no sabemos detener o repetir]?

$S$

$\qquad\displaystyle g(n) = \begin{cases}1, &S \text{ true},\\ g(n+1), &\text{else}.\end{cases}$

Por supuesto, estos no son muy "naturales".

1. No necesariamente todos , pero "muchos" en algún sentido. Infinitamente muchos, al menos.

Cualquier problema abierto relacionado con la existencia de un número con propiedades particulares da lugar a dicho programa (el que busca dicho número). Por ejemplo, tome la conjetura de Collatz; Como no sabemos si es cierto, tampoco sabemos si el siguiente programa termina:

    n:=1;
    found:=false;
    while not found do
      s:={};
      i:=n;
      while i not in s do
        add i to s;
        if i even then i:=i/2 else i:=3i+1
      if 1 not in s then found:=true;
      n:=n+1  

Dado que el problema de Busy Beaver no se resuelve para una máquina de Turing de 5 estados y 2 símbolos, debe haber una máquina de Turing con solo cinco estados y solo dos símbolos que no se haya demostrado que se detenga o no cuando se inicie con una cinta vacía . Es un programa muy corto, conciso y cerrado.

La pregunta es complicada porque la capacidad de decisión (el problema de formalización / generalización equivalente de CS de la detención) está asociada con los idiomas, por lo que debe reformularse en ese formato. Esto parece no señalarse mucho, pero muchos problemas abiertos en matemáticas / CS pueden convertirse fácilmente en problemas (idiomas) de capacidad de decisión desconocida. Esto se debe a una estrecha correspondencia entre la prueba de teorema y el análisis de (no) decidibilidad. por ejemplo (algo así como la otra respuesta con números perfectos impares), tome la conjetura de los primos gemelos que data de los griegos (hace más de 2 milenios) y está sujeta a importantes avances de investigación recientes, por ejemplo, de Zhang / Tao. conviértalo a un problema algorítmico de la siguiente manera:

Entrada: n . Salida: Y / N existe al menos n primos gemelos.

el algoritmo busca primos gemelos y se detiene si encuentra n de ellos. No se sabe si este lenguaje es decidible. La resolución del problema de los primos gemelos (que pregunta si hay un número finito o infinito) también resolvería la capacidad de decisión de este lenguaje (si también se prueba / descubre cuántos hay, si es finito).

otro ejemplo, tome la hipótesis de Riemann y considere este lenguaje:

Entrada: n . Salida: Y / N existen al menos n ceros no triviales de la función zeta de Riemann.

el algoritmo busca ceros no triviales (el código no es especialmente complejo, es similar a la búsqueda de raíces, y hay otras formulaciones equivalentes que son relativamente simples, que básicamente calculan sumas de "paridad" de todos los primos menores que x, etc.) y se detiene si encuentra n de ellos y nuevamente, no se sabe si este lenguaje es decidible y la resolución es "casi" equivalente a resolver la conjetura de Riemann.

ahora, ¿qué tal un ejemplo aún más espectacular? ( advertencia, probablemente también más controvertida)

Entrada: c: Salida: Y / N existe un algoritmo O (n ^c ) para SAT.

de manera similar, la resolución de la capacidad de decisión de este lenguaje es casi equivalente al problema P vs NP . sin embargo, hay un caso menos obvio para el código "simple" para el problema en este caso.

$1 ≤ n ≤ 10^{50}$

$10^{20}$