La Singularidad Desnuda

Un universo impredecible de pensamientos y cavilaciones sobre ciencia, tecnología y otros conundros

Turing en una cáscara de nuez: castores afanosos y la paradoja de Berry

Posted by Carlos en mayo 15, 2007

Siguiendo la serie sobre computabilidad, hoy nos vamos a fijar en una función muy interesante, y que nos va a servir de nexo entre computación e información. Se trata de la función castor afanoso (busy beaver en inglés), y que podemos definir informalmente como el mayor valor que un algoritmo de cierto tamaño puede producir. De manera más precisa, supongamos un cierto formalismo para describir algoritmos, y consideremos una función que cuantifique el tamaño de una cierta descripción. Por ejemplo, podemos considerar máquinas de Turing con un alfabeto binario, y usar el número de estados como indicación del tamaño, o un cierto lenguaje de programación de alto nivel, y emplear como medida de tamaño de un programa su número de símbolos o de instrucciones (la elección que hagamos afecta a los valores particulares de la función, pero no a su esencia). Una vez tenemos esto, si A es un cierto algoritmo (que computa una función definida para el valor de entrada 0), emplearemos |A| para indicar su tamaño. Ahora, definimos la función Σ(n) como

\Sigma(n) = \max\{A(0)\ :\ |A|=n\}

esto es, el mayor valor computable por un algoritmo cuya descripción tiene una cierta complejidad (también se puede considerar alternativamente S(n), el mayor número de pasos que realiza un algoritmo de tamaño n antes de detenerse). Consideremos en primer lugar que se trata de una función que crece muy rápidamente. Por ejemplo, cuando hablamos de números grandes dimos una descripción muy concisa del número de Graham (una cantidad cuyo tamaño es simple y llanamente aberrante). Es posible entonces construir un algoritmo relativamente simple que lo calcula (no habría evidentemente forma de almacenarlo ni en un trillón de universos, pero ésa no es la cuestión), lo que evidencia que incluso para valores pequeños del parámetro de entrada, la función Σ(n) devuelve valores astronómicos. Consideremos por otra parte que se trata de una función bien definida: para cada tamaño n, hay un cierto algoritmo que calcula el valor más grande (o varios empatados, que para el caso es lo mismo). Por supuesto, dado un tamaño n hay programas que no se detienen, y que no nos interesan. Dado que el problema de la parada no es computable, por aquí podemos a empezar a ver la dificultad que plantea esta función. De hecho, la función Σ(n) no es computable.

Antes de ver una demostración formal de porqué no es computable esta función, resulta interesante considerar la paradoja de Berry. Esta paradoja se puede plantear de diferentes formas, pero consideremos la siguiente:

Uno más que el mayor número expresable con menos de veinte palabras.

Es fácil ver que esta expresión tiene menos de veinte palabras, y que supuestamente representa un número x. Sin embargo, de ser así, este número x sería estrictamente mayor que el máximo valor del conjunto de todos los números expresables con menos de veinte palabras, conjunto al que el propio x pertenece, lo que resulta en una contradicción. Esta paradoja es en el fondo el motivo por el que la función castor afanoso no es computable. De manera más precisa, supongamos que Σ(n) es computable. Podemos entonces definir una función M como sigue:

M(n) = \Sigma(2n)+1

Sea |M|=w. Definamos ahora Fw(n) como

F_w(n) = M(n+w)

Podemos asumir que |Fw|=2w (por ejemplo, sumar w puede hacerse mediante w instrucciones de incremento). Por la propia definición de la función Σ(n) tenemos que cuando n=2w

\Sigma(2w) \geqslant F_w(0) = M(w) = \Sigma(2w)+1

Llegamos a una contradicción, lo que invalida nuestra suposición inicial de que Σ(n) era computable. La demostración de incalculabilidad de S(n) es más simple todavía, ya que si sabemos el número máximo de pasos que da una máquina de complejidad n antes de detenerse, podemos determinar si una máquina arbitraria se para o no, simplemente simulándola durante dicho número de pasos: si no se para al llegar a ese límite, ya sabríamos que no se pararía nunca.

Tal como apuntaba al principio, uno de los aspectos más relevantes de esta función es como relaciona la complejidad de la descripción de un programa con lo que éste puede calcular. El próximo día habrá ocasión de profundizar en esta relación, que ofrece algunos resultados sumamente interesantes.

Enviar a Blog Memes Enviar a del.icio.us Enviar a digg Enviar a fresqui Enviar a menéame

Anuncios

3 comentarios to “Turing en una cáscara de nuez: castores afanosos y la paradoja de Berry”

  1. Pérez Poch said

    Es curioso que esta entrada no tenga casi comentarios. Puede parecer una cuestión marginal o especultativa, pero esta “cascara de nuez” está entrado en la curva en que… ¡suben las apuestas!: al menos, en el debate sobre si los teoremas de Gödel tienen algo que ver con la cuestión de la equivalencia entre mente humana y computadoras.

  2. JJ said

    Yo diría que la función busy beaver está mal definida. Por el problema de parada, o vaya usté a saber porqué.

  3. […] la época del año en la que nos encontramos, vamos a continuar la serie sobre computabilidad. En el último apunte al respecto vimos el problema del castor afanoso que -entre otras cosas- es especialmente interesante porque […]

Sorry, the comment form is closed at this time.

 
A %d blogueros les gusta esto: