Objeto de finitud comprobada, ¿pero sin algoritmo descubierto?

Question

Explico mi título con dos ejemplos en teoría de números:

Los puntos racionales en una curva elíptica sobre cuerpos de números forman un grupo abeliano finitamente generado, por lo que su rango es un número entero, pero hasta ahora no tenemos un algoritmo que produzca este número una vez que introducimos una ecuación, en tiempo finito.

Otro ejemplo es la conjetura de Mordell sobre la finitud de puntos racionales en curvas de género superior, que fue demostrada por Faltings. No estoy seguro de que los avances recientes puedan producir el número de soluciones una vez que introducimos una ecuación de género mayor que uno, en tiempo finito.

Mi pregunta, que tal vez debería ser de la comunidad wiki, pide más ejemplos (en teoría de números y en otras áreas por supuesto) como estos dos, objetos interesantes que han sido demostrados finitos pero que aún no se ha encontrado un algoritmo. Creo que tales ejemplos son interesantes, porque esto significa que su demostración no proporciona un algoritmo. Sin embargo, existen resultados de finitud y su demostración, como lo que ocurre con los grupos de clase de cuerpos de números, sí proporcionan al menos en principio algoritmos para calcularlos.

Answer 1

Se sabe que el número cromático del plano es a lo sumo 7 pero no se conoce su valor exacto. Para eliminar cualquier dependencia de CA, podríamos preguntar por el número cromático máximo posible de (el grafo de distancia unitaria para) un subconjunto numerable del plano. Para eliminar el problema de tener un 'algoritmo' de salida constante trivial que existe a pesar de no conocerlo, podríamos generalizar preguntando por el número cromático máximo posible de un subconjunto numerable de $^k$ para una entrada de $k$, ya que es trivial probar que es finito.

Answer 2

$\DeclareMathOperator\BB{BB}$Mi respuesta es un ligero engaño, porque voy a dar dos ejemplos donde no solo no hemos descubierto ningún algoritmo sino donde sabemos que no existe tal algoritmo. Ambos utilizan el teorema de la detención, aunque el primero de manera más obvia que el segundo.

El primero es el número Busy Beaver: Para cualquier $n$ dado, hay un número finito de máquinas de Turing con a lo sumo $n$ estados que se detienen cuando se ejecutan en la cinta en blanco. (Aquí, para tratar problemas de ambigüedad, asumimos que los únicos símbolos son 1 y 0). De esas máquinas que se detienen, hay un tiempo máximo en el que cualquiera de ellas se detiene. ¿Cuál es? Esta es una función de $n$, a veces denotada como $\BB(n)$. Es claro a partir de la definición que esta cantidad es finita. Sin embargo, encontrar $\BB(n)$ es equivalente a resolver el problema de la detención. Para una buena introducción a la función Busy Beaver y trabajos relacionados, vea la encuesta de Scott Aaronson aquí.

Dado que el último involucra máquinas de Turing, probablemente no sea sorprendente que no tenga un algoritmo. El segundo tiene un sabor similar, pero donde es menos obvio a partir de la afirmación: Para cualquier $n$ dado, solo hay un número finito de ecuaciones diofánticas con a lo sumo $n$ variables, grado como máximo $n$, y ningún coeficiente mayor que $n$. De esas ecuaciones, algunas no tienen solución. Defina $D(n)$ como el número de esas ecuaciones que no tienen soluciones. Como antes, $D(n)$ es claramente finito. En este caso, el problema nuevamente es equivalente al problema de la detención. En este caso, se debe a la solución del décimo problema de Hilbert, que muestra que este problema es equivalente al problema de la detención.

Dos observaciones tangenciales: Primero, si se define una función similar a $D(n)$, $F(n)$ que cuenta en su lugar el número más grande de soluciones de cualquier ecuación diofántica con a lo sumo $n$ variables, grado como máximo $n$, y ningún coeficiente mayor que $n$, entonces este número también es finito. Pero no conozco una prueba o desmentido de que haya un algoritmo para $F(n)$. Segundo, no conozco ejemplos similares a estos donde podamos probar la finitud y saber que no hay un algoritmo, pero donde la prueba no pase fundamentalmente por el teorema de la detención.

Answer 3

Aquí hay un ejemplo donde la finitud es conocida, existe un algoritmo, pero ese algoritmo es ineficaz, en el sentido de que las computadoras actuales (hasta donde sé) no terminarán en un tiempo razonable:

Un sistema Y asociado a un diagrama de Dynkin Q de tipo ADE es un cierto sistema de ecuaciones que surge en la física. Dado un Q fijo, se sabe que

1. hay un número finito de soluciones enteras positivas al sistema Y asociado a Q, ya que dichas soluciones están limitadas por debajo por 1 y por encima por una constante digamos $c(Q)$.

2. un algoritmo de fuerza bruta definido por probar todos los valores entre 1 y $c(Q)$ funciona en principio.

3. En general, la constante $c(Q)$ es excesivamente grande, y mucho más grande que el número esperado de soluciones (por ejemplo, cuando $Q$ es de tipo $E_8$, se tendría que probar algo así como $2^{400000}$ valores, mientras que se "espera" muchas menos soluciones).