Por @Alvy — 29 de Noviembre de 2008

Igor Ostrovsky es un desarrollador de Microsoft que trabaja en computación en paralelo; escribió una interesante anotación titulada Numbers that cannot be computed donde describe un fenómeno curioso, los números que no son computables.

El asunto dista de ser trivial, pero allí se explica con bastante claridad por qué existen números reales que ningún programa de ordenador puede computar.

Para argumentarlo primero afirma que, por un lado, números decimales sencillos y también los periódicos como 1/7 se pueden calcular (en el sentido de generar todos sus dígitos, de forma detallada). Luego que cualquier otro número racional, o incluso irracionales como π, también son computables, porque existen algoritmos para generarlos, que se pueden implementar en un programa. Como algunos tienen infinidad de decimales, basta suponer que el ordenador en que se ejecutan tiene una cantidad infinita de memoria (lo cual no es muy realista, pero es necesario para entender las máquinas de Turing y estos temas sobre computación).

El siguiente paso es entender que existen más números reales que programas en C# (o cualquier otro lenguaje de programación que se elija). Aunque ambas cantidades son infinitas (los números reales, y la cantidad de programas en C#), la primera es «más infinita que la otra». En la explicación el autor utiliza un argumento similar a la diagonalización de Cantor para hacer ver que, aunque ambos sean infinitos, los programas en C# son contables y los números reales no.

En las aportaciones que los lectores en la anotación y también en el hilo de reddit sobre el tema aparecieron algunas otras cuestiones colaterales interesantes al respecto. Una es aquella de si todos los números están en pi o no (lo cual invalidaría la idea, pues bastaría poder calcular pi para tenerlos todos; pero en realidad pi sólo contiene todos los números… finitos). También me sirvió para reeler algunas buenas notas que Tio Petros hizo sobre los números trascendentes y los mensajes ocultos en pi y para revisar el problema del castor afanoso.

Aparte de todo esto que me pareció muy interesante, mirando por ahí también encontré algo llamado la constante de Chaitin que tampoco es computable; es un número entre cero y uno, que equivale a la probabilidad de que un programa elegido al azar detenga correctamente a una máquina de Turing determinada.

Compartir en Flipboard Compartir en Facebook Tuitear

PUBLICIDAD




PUBLICIDAD


Encuesta AIMC 2020

Microsiervos Selección


El libro de las matemáticas: de Pitágoras a la 57ª dimensión

EUR 18,95 (Reseña en Microsiervos)

Comprar


El andar del borracho: Cómo el azar gobierna nuestras vidas

EUR 10,40

Comprar


Amazon Associates

Los productos aquí enlazados están a la venta en Amazon. Incluyen un código de Afiliado Amazon Associates que nos cede un pequeño porcentaje de las ventas. Los productos están seleccionados por los autores del blog, pero ni Amazon ni los editores de los libros o fabricantes de los productos participan en dicha selección.

Más libros y productos en:

Microsiervos Selección