Epistemología y complejidad computacional

En cuanto a la complejidad computacional, Velupillai (2000) proporciona definiciones y discusión general y Koppl y Rosser Jr. (2002) proporcionan una formulación más precisa del problema, basándose en los argumentos de Kleene (1967), Binmore (1987), Lipman (1991) y enlatado (1992). Velupillai define la complejidad computacional directamente como “intratabilidad” o insolubilidad. Detener problemas como el estudiado por Blum et al. (1998) proporcionan excelentes ejemplos de cómo puede surgir tal complejidad, con este problema estudiado por primera vez para sistemas recursivos por Church (1936) y Turing (1936, 1937).

En particular, Koppl y Rosser reexaminaron el famoso problema “Holmes-Moriarty” de la teoría de juegos, en el que dos jugadores que se comportan como máquinas de Turing contemplan un juego entre ellos que implica una regresión infinita del pensamiento sobre lo que está pensando el otro (Morgenstern 1935). Esencialmente, este es el problema del juego de n niveles con n sin límite superior (Bacharach y Stahl2000). Esto tiene un equilibrio de Nash, pero las máquinas de Turing “hiperracionales” no pueden llegar a saber que tienen esa solución o no debido al problema de la detención. Que las mejores funciones de respuesta no sean computables surge del problema de autorreferencia involucrado fundamentalmente similar a las que subyacen al Teorema de incompletitud de Gödel (Rosser Sr1936; Kleene1967, pag. 246). Aaronson (2013) ha mostrado vínculos entre estos problemas en la teoría de juegos y el problema N = P de complejidad computacional. Tales problemas se extienden también a la teoría del equilibrio general (Lewis1992; Richter y Wong1999; Landini y col.2020).

Binmore’s (1987, págs. 209-212), la respuesta a tal indecidibilidad en los sistemas de autorreferencia invoca una forma “sofisticada” de actualización bayesiana que implica un grado de mayor ignorancia. Koppl y Rosser están de acuerdo en que los agentes pueden operar en tal ambiente aceptando límites en el conocimiento y operar en consecuencia, tal vez sobre la base de la intuición o “espíritus animales keynesianos” (Keynes1936). Los agentes hiperracionales no pueden tener un conocimiento completo, esencialmente por la misma razón por la que Gödel demostró que ningún sistema lógico puede ser completo en sí mismo.

Sin embargo, incluso para la solución propuesta por Binmore también existen límites. Así, Diaconis y Freedman (1986) han demostrado que el teorema de Bayes no se sostiene en un espacio de dimensión infinita. Puede haber una falla para converger en la solución correcta a través de la actualización bayesiana, especialmente cuando la base es discontinua. Puede haber convergencia en un ciclo en el que los agentes están saltando de una probabilidad a otra, ninguna de las cuales es correcta. En el ejemplo simple del lanzamiento de una moneda, es posible que estén saltando de un lado a otro asumiendo a priori de 1/3 y 2/3 sin poder nunca converger en la probabilidad correcta de 1/2. Nyarko (1991) ha estudiado este tipo de dinámicas cíclicas en situaciones de aprendizaje en modelos económicos generalizados.

Koppl y Rosser comparan este tema con el problema de Keynes (1936, Cap. 12) del concurso de belleza. En esto, se supone que los participantes ganan si adivinan con mayor precisión las conjeturas de los otros participantes, lo que potencialmente implica un problema de regresión infinita con los participantes tratando de adivinar cómo los otros participantes adivinarán sobre sus conjeturas, etc. Esto también puede verse como un problema de reflexividad (Rosser Jr.2020b). Una solución viene al optar por ser algo ignorante o limitadamente racional y operar en un nivel particular de análisis. Sin embargo, como no hay forma de determinar racionalmente el grado de acotación, lo que en sí mismo implica un problema de regresión infinita (Lipman1991), esta decisión también implica en última instancia un acto arbitrario, basado en espíritus animales o lo que sea, una decisión que finalmente se toma sin pleno conocimiento.

Un punto curiosamente relacionado aquí está en los resultados posteriores (Gode y Sunder 1993; Mirowski2002) sobre el comportamiento de los traders de inteligencia cero. Gode ​​y Sunder han demostrado que en muchas configuraciones de mercado artificial, los comerciantes de inteligencia cero que siguen reglas muy simples pueden converger en equilibrios de mercado que incluso pueden ser eficientes. No solo puede ser necesario limitar el conocimiento de uno para comportarse de una manera racional, sino que uno puede ser capaz de ser racional en algún sentido sin tener conocimiento alguno. Mirowski y Nik-Kah (2017) argumentan que esto completa una transformación del tratamiento del conocimiento en economía en la era posterior a la Segunda Guerra Mundial, pasando de suponer que todos los agentes tienen conocimiento completo a todos los agentes que tienen conocimiento cero.

Otro punto sobre esto es que hay grados de complejidad computacional (Velupillai 2000; Markose2005), con Kolmogorov (1965) proporcionando una definición ampliamente aceptada de que el grado de complejidad computacional viene dado por la duración mínima de un programa que se detendrá en una máquina de Turing. Hemos estado considerando los casos extremos de no detenerse, pero de hecho existe una jerarquía aceptada entre los niveles de complejidad computacional, y las dificultades de conocimiento experimentan cambios cualitativos a través de ellos. Se considera que esta jerarquía consta de cuatro niveles (Chomsky1959; Wolfram1984; Mirowski2007). En el nivel más bajo se encuentran los sistemas lineales, de fácil resolución, con un nivel tan bajo de complejidad computacional que podemos verlos como no complejos. Por encima de ese nivel se encuentran los problemas polinomiales (P) que son sustancialmente más complejos desde el punto de vista computacional, pero que en general se pueden resolver. Por encima de eso están los problemas exponenciales y otros problemas no polinomiales (NP) que son muy difíciles de resolver, aunque aún no se ha demostrado que estos dos niveles sean fundamentalmente distintos, uno de los problemas no resueltos más importantes de la informática. Por encima de este nivel se encuentra el de complejidad computacional total asociado donde la longitud mínima es infinita, donde los programas no se detienen. En este caso, los problemas de conocimiento solo pueden resolverse volviéndose efectivamente menos inteligente.