Por razones históricas y para tener aplicación en la solución de ecuaciones diofánticas , los resultados en la teoría de números se han examinado 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 cuestión es si, en principio, la lista podría imprimirse después de un cálculo mecánico.
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 número de Skewes .
Más detalladamente, al escribir para una secuencia numérica f ( n ), un resultado efectivo sobre su cambio de signo infinitamente frecuente sería un teorema que incluyera, para cada valor de N , un valor M > N tal que f ( N ) y f ( M ) tienen signos diferentes y tales que M podría calcularse con recursos específicos. En términos prácticos, M se calcularía tomando valores de n a partir de N , y la pregunta es "¿hasta dónde debes 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 sólo un efecto de número pequeño, pero "pequeño" aquí incluía valores de n hasta mil millones.
El requisito de computabilidad refleja y contrasta con el enfoque utilizado en la teoría analítica de números para probar los resultados. Por ejemplo, pone en duda cualquier uso de la notación Landau y sus constantes implícitas: ¿son las afirmaciones puros teoremas de existencia para tales constantes, o se puede recuperar una versión en la que 1000 (digamos) tome el lugar de la constante implícita? En otras palabras, si se supiera que existe M > N con 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 . Es posible que también sea necesario hacer explícito el valor de A , la llamada constante implícita , para fines computacionales. Una de las razones por las que la notación 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 pueda hacerse 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 clases ideales para algunas familias de campos numéricos crecen); y límites de las mejores aproximaciones racionales a números algebraicos en términos de denominadores . Estos últimos podrían leerse de manera bastante directa como resultados de ecuaciones diofánticas, según el trabajo de Axel Thue . El resultado utilizado para los números de Liouville en la demostración 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.
Resultados posteriores, particularmente los de Alan Baker , cambiaron la postura. Hablando cualitativamente, los teoremas de Baker parecen más débiles, pero tienen constantes explícitas y en realidad pueden aplicarse, junto 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 aquí se enfrentaron mediante técnicas de prueba radicalmente diferentes, prestándose mucho más cuidado a 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 bastante vagamente 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 saber cuál.