Utilizamos cookies propias y de terceros para mejorar nuestros servicios y facilitarte el uso de la web mediante el análisis de tus preferencias de navegación. También compartimos la información sobre el tráfico por nuestra web a los medios sociales y de publicidad con los que colaboramos. Si continúas navegando, consideramos que aceptas nuestra Política de cookies .

Ordenadores y números naturales

Cómo demostrar el teorema de Gödel a partir de la complejidad de Kolmogórov.
REGUIIEEE/WIKIMEDIA COMMMONS/DOMINIO PÚBLICO
Todos nosotros estamos familiarizados con la aritmética: el estudio de los números naturales y sus dos operaciones básicas, la suma y la multiplicación. Pero ¿cuán complejo es el conjunto de las verdades aritméticas? ¿Sería posible programar un ordenador para que anunciase, una por una, todas las verdades de la aritmética sin formular jamás una falsedad? Dado que existe un número infinito de verdades aritméticas, nuestra computadora nunca completaría su tarea, sino que debería trabajar por toda la eternidad. Pero este detalle no nos preocupa: nos conformamos con que toda verdad aritmética sea anunciada por nuestro ordenador en algún momento.
Para llevar a cabo semejante proyecto, lo primero que hemos de decidir es el lenguaje que queremos que utilice nuestro ordenador para anunciar sus resultados. Supongamos, por ejemplo, que ese lenguaje contiene los símbolos 0 y 1 para nombrar el cero y el uno, y los símbolos + y × para denotar la suma y la multiplicación. Esto nos basta para nombrar todos los números naturales: el número dos puede representarse por medio de la expresión 1 + 1 (o por su abreviación, 2), y así sucesivamente. Si introducimos el símbolo = para designar la identidad entre números, nuestro lenguaje podrá también expresar verdades matemáticas simples, como 2 × 1 = 1 × 2.

Artículos relacionados

Puedes obtener el artículo en...

¿Tienes acceso?

Los boletines de Investigación y Ciencia

Elige qué contenidos quieres recibir.