¿Las consideraciones sobre la indecidibilidad de Turing y la complejidad computacional (dureza NP, etc.) tienen consecuencias para la epistemología? Si la función o proposición X es indecidible o requiere una cantidad intratable de recursos para ser calculada, ¿todavía se considera cognoscible?
Hasta el momento, las consideraciones basadas en los recursos computacionales tienen consecuencias solo para un pequeño grupo de filósofos conocidos como antirrealistas radicales, que extienden el finitismo estricto a la epistemología. A diferencia de los constructivistas y los antirrealistas moderados (intuicionistas) como Dummett, que suelen estar satisfechos con la computabilidad, en principio los antirrealistas radicales insisten en algo más que eso, la "factibilidad práctica". En particular, rechazarían la ley del tercero excluido incluso para los predicados computables.
Una de las sugerencias para la lógica epistémica del antirrealismo radical, dada por Dubucs y Marion, es usar la computabilidad del tiempo polinomial como formalización de la "viabilidad práctica", por lo que presumiblemente simpatizarían con el tipo de preocupaciones como la dureza NP de reducir teorías de nivel superior a las de nivel inferior. Al menos por ahora, las epistemologías antirrealistas clásicas e incluso las dominantes están satisfechas con hacerlo "en principio".
Ver la revisión de Vidal-Rosset y el artículo original de Dubucs-Marion .
Diría que SÍ con respecto al problema de NP. Ver el Teorema Fundamental de la Aritmética . Es un teorema, por lo que es cognoscible como verdadero y demostrable. Sin embargo, si puedes factorizar un número en tiempo NP, entonces eres un dios y arruinaste todo Internet.
Estudiar las proposiciones como si fueran un razonamiento válido no tiene nada que ver con el tiempo involucrado o el número de pasos. Las implicaciones que NP/NPC/NPH tendrían son similares a las implicaciones de la Máquina de Dios tratando de detectar una colisión: es solo una molesta cuestión de tiempo, pero no de validez de razonamiento.
Respecto al problema de la indecidibilidad, el problema emblemático aquí es el Problema de la Detención, y sí, tiene implicaciones epistemológicas . Básicamente: hay algunos límites a su capacidad para probar algo bajo su propio sistema y, bajo un sistema de esquema de Turing, dicho problema se expresa en términos de problemas indecidibles (o semidecidibles) como este.
Cort Amón
Cort Amón