Por razones históricas y con el fin de que tengan aplicación en la solución de ecuaciones diofánticas , los resultados en teoría de números han sido examinados más que en otras ramas de las matemáticas para ver si su contenido es efectivamente computable [ cita requerida ] . Cuando se afirma que alguna lista de números enteros es finita, la pregunta es si en principio la lista podría imprimirse después de un cálculo a máquina.
Un ejemplo temprano de un resultado ineficaz fue el teorema de JE Littlewood de 1914, [1] que en el teorema de los números primos las diferencias de ψ( x ) y π( x ) con sus estimaciones asintóticas cambian de signo infinitamente a menudo. [2] En 1933, Stanley Skewes obtuvo un límite superior efectivo para el primer cambio de signo, [3] ahora conocido como el número de Skewes .
En más detalle, escribiendo para una secuencia numérica f ( n ), un resultado efectivo acerca de su cambio de signo infinitamente a menudo sería un teorema que incluyera, para cada valor de N , un valor M > N tal que f ( N ) y f ( M ) tengan signos diferentes, y tal que M pudiera calcularse con recursos específicos. En términos prácticos, M se calcularía tomando valores de n desde N en adelante, y la pregunta es "¿hasta dónde debe llegar?". Un caso especial es encontrar el primer cambio de signo. El interés de la pregunta era que la evidencia numérica conocida no mostraba ningún cambio de signo: el resultado de Littlewood garantizaba que esta evidencia era solo un pequeño efecto numérico, pero "pequeño" aquí incluía valores de n hasta mil millones.
El requisito de computabilidad se refleja en el enfoque utilizado en la teoría analítica de números para demostrar los resultados y contrasta con él . Por ejemplo, pone en tela de juicio cualquier uso de la notación de Landau y sus constantes implícitas: ¿son las afirmaciones teoremas de existencia pura para tales constantes, o se puede recuperar una versión en la que 1000 (por ejemplo) ocupe el lugar de la constante implícita? En otras palabras, si se supiera que existe M > N con un cambio de signo y tal que
Para alguna función explícita G , digamos construida a partir de potencias, logaritmos y exponenciales , eso significa solo
para alguna constante absoluta A . El valor de A , la llamada constante implícita , también puede necesitar hacerse explícito, para fines computacionales. Una razón por la que la notación de Landau fue una introducción popular es que oculta exactamente qué es A. En algunas formas indirectas de prueba puede no ser del todo obvio que la constante implícita se puede hacer explícita.
Muchos de los principales resultados de la teoría analítica de números que se demostraron en el período 1900-1950 fueron, de hecho, ineficaces. Los principales ejemplos fueron:
La información concreta que quedó teóricamente incompleta incluía límites inferiores para los números de clase ( los grupos de clase ideales para algunas familias de cuerpos numéricos crecen); y límites para las mejores aproximaciones racionales a números algebraicos en términos de denominadores . Estos últimos podrían leerse bastante directamente como resultados sobre ecuaciones diofánticas, después del trabajo de Axel Thue . El resultado utilizado para los números de Liouville en la prueba es efectivo en la forma en que aplica el teorema del valor medio : pero las mejoras (a lo que ahora es el teorema de Thue-Siegel-Roth) no lo fueron.
Los resultados posteriores, en particular los de Alan Baker , cambiaron la situación. Cualitativamente hablando, los teoremas de Baker parecen más débiles, pero tienen constantes explícitas y pueden aplicarse, en combinación con el cálculo automático, para demostrar que las listas de soluciones (que se sospecha que están completas) son en realidad el conjunto completo de soluciones.
Las dificultades en este caso se resolvieron con técnicas de prueba radicalmente diferentes, que se tomaron con mucho más cuidado en las pruebas por contradicción . La lógica involucrada está más cerca de la teoría de la prueba que de la teoría de la computabilidad y las funciones computables . Se conjetura de manera bastante vaga que las dificultades pueden residir en el ámbito de la teoría de la complejidad computacional . Todavía se están demostrando resultados ineficaces en la forma A o B , donde no tenemos forma de decir cuál.