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 Publicar / Tuitear