Fundamentos de la economía de la complejidad computacional

Velupillai2000, págs. 199-200) resume los fundamentos de lo que ha denominado economía computable 9 a continuación.

La computabilidad y la aleatoriedad son las dos nociones epistemológicas básicas que he usado como bloques de construcción para definir la economía computable. Ambas nociones pueden ponerse en práctica para formalizar la teoría económica de manera eficaz. Sin embargo, solo se pueden hacer sobre la base de dos tesis: la tesis de Church-Turing y la tesis de Kolmogorov-Chaitin-Solomonoff.

Iglesia (1936) y Turing (1937) se dieron cuenta de forma independiente de que varias clases amplias de funciones podían describirse como “recursivas” y eran “calculables” (las computadoras programables aún no se habían inventado). Turing (1936, 1937) fue el primero en darse cuenta de que Gödel (1931) El teorema de la incompletitud proporcionó una base para la comprensión cuando los problemas no eran “calculables,” llamados “efectivamente computables” ya que Tarski (1949). El análisis de Turing que introduce el concepto generalizado de la máquina de Turing , ahora visto como el modelo de un agente económico racional dentro de la economía computable (Velupillai2005b, pag. 181). Si bien el teorema de Gödel original se basó en una prueba diagonal de Cantor que surge de la autorreferencia, la manifestación clásica de no computabilidad en la programación es el problema que se detiene : que un programa simplemente se ejecutará para siempre sin llegar nunca a una solución (Blum et al.1998).

Gran parte de la economía computable reciente ha implicado demostrar que cuando se intenta poner partes importantes de la teoría económica estándar en formas que puedan ser computables, se descubre que no son computables de manera efectiva en ningún sentido general. Estos incluyen los equilibrios walrasianos (Lewis1992), Equilibrios de Nash (Prasad 1991; Tsuji y col.1998), aspectos más generales de la macroeconomía (Leijonufvud 1993), y si un sistema dinámico será caótico o no (da Costa et al. 2005). 10

De hecho, lo que se considera como complejidades dinámicas puede surgir de problemas de computabilidad que surgen al saltar de un marco de números reales clásico y continuo a un marco de solo números racionales digitalizado. Un ejemplo es la curiosa “función financiera” de Clower y Howitt (1978) en el que las variables de solución saltan hacia adelante y hacia atrás en grandes intervalos de forma discontinua a medida que las variables de entrada van de números enteros a racionales no enteros a números irracionales y viceversa. Velupillai2005b, pag. 186) señala el caso de un misil Patriot que falló su objetivo por 700 my mató a 28 soldados como “fuego amigo” en Dhahran, Arabia Saudita en 1991 debido a un ciclo sin interrupción de una computadora a través de una expansión binaria en una fracción decimal. Finalmente, el descubrimiento de la dependencia sensible caótica de las condiciones iniciales por Lorenz (1963) debido al error de redondeo de la computadora es famoso, un caso que es computable pero indecidible.

En realidad, existen varias definiciones de complejidad basadas en la computabilidad, aunque Velupillai (2000, 2005a, B) sostiene que pueden vincularse como parte de la base más amplia de la economía computable. El primero es el Shannon (1948) medida del contenido de la información, que puede interpretarse como un intento de observar la estructura en un sistema estocástico. Por tanto, se deriva de una medida de entropía en el sistema, o de su estado de desorden. Por lo tanto, si p ( x ) es la función de densidad de probabilidad de un conjunto de K estados denotados por valores de x , entonces la entropía de Shannon está dada por

\[H(X)=-\sum_{x=1}^{K} \ln (p(x))\]

De aquí es trivial obtener el contenido de información de Shannon de X = x como

\[\mathrm{SI}(x)=\ln (1 / p(x))\]

Se llegó a entender que esto equivale al número de bits en un algoritmo que se necesitan para calcular este código. Esto llevaría a Kolmogorov (1965) para definir lo que ahora se conoce como complejidad de Kolmogorov como el número mínimo de bits en cualquier algoritmo que no prefija ningún otro algoritmo a ( x ) que una Máquina de Turing Universal (UTM) requeriría para calcular una cadena binaria de información, x , o,

\[\mathrm{K}(x)=\min |a(x)|\]

donde │ │ denota la longitud del algoritmo en bits. 11 Chaitin (1987) descubriría y ampliaría de forma independiente este concepto de longitud mínima de descripción (MDL) y lo vincularía con los problemas de incompletitud de Gödel, su versión se conoce como complejidad algorítmica , que sería retomada más tarde por Albin (mil novecientos ochenta y dos) 12 y Lewis (1985, 1992) en contextos económicos. 13

Si bien estos conceptos vincularon de manera útil la teoría de la probabilidad y la teoría de la información con la teoría de la computabilidad, todos comparten el desafortunado aspecto de no ser computable. Esto se remediaría con la introducción de la complejidad estocástica por Rissanen (1978, 1986, 1989, 2005). La intuición detrás de la modificación de Rissanen de los conceptos anteriores es centrarse no en la medida directa de la información, sino en buscar una descripción o modelo más breve que describa las “características regulares” de la cuerda. Para Kolmogorov, un modelo de cadena es otra cadena que contiene la primera cadena. Rissanen (2005, págs. 89-90) define una función de verosimilitud para una estructura dada como una clase de funciones de densidad paramétricas que pueden verse como modelos respectivos, donde θ representa un conjunto de k parámetros yx es una cadena de datos dada indexada por n :

\[M_{k}=\left\{f\left(x^{n}, \theta\right): \theta \in \mathbf{R}^{k}\right}\]

Para una f dada , con f ( y n ) un conjunto de “cadenas normales,” la función de máxima verosimilitud normalizada estará dada por

\[f^{*}\left(x^{n}, M_{k}\right)=f\left(x^{n}, \theta^{*}\left(x^{n}\right)\right) /\left[\int_{\theta(m)} \mathrm{f}\left(y^{n}, \theta\left(y^{n}\right)\right) \mathrm{d} y^{n}\right]\]

donde el denominador del lado derecho se puede definir como C n , k .

A partir de esto, la complejidad estocástica viene dada por

\[-\ln f^{*}\left(x^{n}, M_{k}\right)=-\ln f\left(x^{n}, \theta^{*}\left(x^{n}\right)\right)+\ln C_{n, k}\]

Este término puede interpretarse en el sentido de que representa “la ‘longitud de código más corta’ para los datos x n que se puede obtener con la clase de modelo M k.” (Rissanen2005, pag. 90). Con esto tenemos una medida computable de complejidad derivada de las ideas más antiguas de Kolmogorov, Solomonoff y Chaitin. La conclusión de la complejidad de Kolmogorov es que un sistema es complejo si no es computable. Los partidarios de estos enfoques para definir la complejidad económica (Israel2005; Markose2005; Velupillai2005a, B) señalan la precisión que dan estas medidas en contraste con muchas de las alternativas.

Sin embargo, la complejidad algorítmica de Chaitin (1966, 1987) introduce un límite a esta precisión, una aleatoriedad subyacente última. Consideró el problema de que un programa se haya iniciado sin que uno sepa qué es y, por lo tanto, se enfrenta a una probabilidad de que se detenga, lo que etiquetó como Ω. Vio esta aleatoriedad como subyacente a todos los “hechos” matemáticos. De hecho, este Ω en sí mismo, en general, no es computable (Rosser Jr.2020a).

Un ejemplo de esto involucra un teorema de Maymin (2011) que se extiende a ambos lados del límite del problema profundo sin resolver de si P (polinomio) es igual a NP (no polinomio) en los programas, 14 por lo que tiene un Ω desconocido. Este teorema muestra que bajo ciertas condiciones de información los mercados son eficientes si P = NP, lo que pocos creen. En el borde de este da Costa y Doria (2016) usa el O’Donnell (1979) algoritmo que es exponencial y, por lo tanto, no P pero que crece lentamente hasta “casi P” para establecer una función de contraejemplo para el problema P = NP. El algoritmo de O’Donnell se cumple si P <NP es probable para cualquier teoría estrictamente más fuerte que la aritmética recursiva primitiva, incluso si eso no puede probarlo. Tales problemas pueden aparecer como en el problema del viajante de comercio computacionalmente complejo. Da Costa y Doria establecen que en estas condiciones el algoritmo de O’Donnell se comporta como un sistema “casi P” que implica un resultado de “mercados casi eficientes.” Este es un resultado que camina al borde de lo desconocido, si no de lo incognoscible.

Una cuestión lógica más profunda que subyace a la complejidad computacional y la economía implica debates fundamentales sobre la naturaleza de las matemáticas en sí. Las matemáticas convencionales asumen axiomas etiquetados como el sistema Zermelo-Fraenkel- [Axiom of] Choice, o ZFC. Pero algunos de estos axiomas han sido cuestionados y se han hecho esfuerzos para desarrollar sistemas matemáticos axiomáticos que no los utilicen. Los axiomas que han sido cuestionados han sido el axioma de la elección, el axioma del infinito y la ley del medio excluido. Un término general para estos esfuerzos ha sido matemática constructivista , con sistemas que enfatizan particularmente no depender de la Ley del Medio Excluido, lo que significa que no hay uso de prueba por contradicción, se ha conocido como intuicionismo , inicialmente desarrollado por Luitzen Brouwer (1908) de la fama del teorema del punto fijo. 15 En particular, las demostraciones estándar del teorema de Bolzano-Weierstrass utilizan la prueba por contradicción, con este Lema de Sperner subyacente, que a su vez subyace en las demostraciones estándar de los teoremas de punto fijo de Brouwer y Kakutani utilizados en las pruebas de existencia de equilibrio general y de Nash (Velupillai2006, 2008). dieciséis

Para los matemáticos, si no para los economistas, el más importante de estos axiomas discutibles es el axioma de elección, que permite la ordenación relativamente fácil de conjuntos infinitos. Esto sustenta las demostraciones estándar de los principales teoremas de la economía matemática, con Scarf (1973) probablemente el primero en notar estos posibles problemas. El axioma de elección es especialmente importante en topología y partes centrales del análisis real. Por un lado, Specker (1953). Pero una forma de solucionar algunos de estos problemas es utilizar un análisis no estándar que permita números reales infinitos e infinitesimales (Robinson1966), lo que permite evitar el uso del axioma de elección para demostrar algunos teoremas importantes.

La cuestión del axioma del infinito quizás esté más estrechamente ligada a las cuestiones sobre la complejidad computacional. La idea filosófica profunda detrás de estos enfoques constructivistas es que las matemáticas deberían tratar con sistemas finitos que son más realistas y más fáciles de calcular. En contra de esto, fue la introducción de Cantor de niveles de infinito en las matemáticas, una innovación que llevó a Hilbert a elogiar a Cantor por “traer a los matemáticos al paraíso.” Pero los críticos de la computabilidad argumentan que la economía matemática debe ajustarse al mundo real de una manera creíble, con esfuerzos en curso para construir dicha economía basada en una base constructivista (Velupillai2005a, B, 2012; Bartholo y col.2009; Rosser Jr.2010a, 2012a).