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 .

1 de Julio de 1984
Cómputo

Máquinas de Turing

En su fundamento lógico, todo ordenador digital incorpora en sí uno de estos dispositivos conceptuales ideados por el matemático inglés A. M. Turing. Las máquinas demarcan los límites de la computabilidad.

PHILIP HIETER, Facultad de medicina de la Universidad Johns Hopkins

En síntesis

En 1936 Alan Turing publicaba «Sobre los números computables, con una aplicación al problema de la decisión». El artículo marcó un hito al introducir la noción de computabilidad por medio de lo que hoy denominamos máquinas de Turing.

Una máquina de Turing es un dispositivo conceptual dotado de unas reglas de operación sencillas para la manipulación de símbolos. Dichas reglas son tales que permiten realizar cualquier tarea que pueda llevar a cabo un ordenador real.

El procedimiento concebido por Turing sirvió para demarcar de manera explícita los límites de la computabilidad algorítmica. Al mismo, tiempo, sentaría las bases de la informática moderna y de la teoría de la complejidad computacional.

En 1900, el preeminente matemático David Hilbert presentó al Congreso Internacional de Matemáticos, que se celebraba en París, una relación de problemas no resueltos, que supusieron para el mundo de los expertos un reto y un estímulo. El problema segundo de aquella lista consistía en demostrar que los axiomas de la aritmética ordinaria eran coherentes entre sí. El trabajo de Hilbert sobre la cuestión le llevó a proponer un problema más general: el Entscheidungsproblem, o problema de la decisión. El Entscheidungsproblem consistía en establecer un método general para determinar si una fórmula de la lógica formal podía o no sa­tisfacerse, o declararse verdadera. Treinta y seis años hubieron de transcurrir hasta su resolución completa, que señaló en las matemáticas un giro tan extraordinario como inesperado. En la Universidad de Cambridge, un joven matemático, miembro del King’s College, de nombre Alan Mathison Turing, había llegado a familiarizarse con el problema gracias a una serie de lecciones impartidas por M. H. A. Newman. Turing reflexionó sobre el problema durante los largos paseos que por las tardes solía dar por la campiña inglesa. Fue tras uno de esos paseos cuando le llegó la respuesta. El problema de Hilbert era imposible de resolver.

La publicación en la que Turing anunció su resultado ha tenido una significación y trascendencia que rebasan con mucho el problema al que inmediatamente se dirigía. Al atacar el problema de Hilbert, Turing se vio forzado a plantearse cómo dar al concepto de método una definición precisa. A partir de la idea intuitiva de que un método es un algoritmo —un procedimiento que puede ser ejecutado mecánicamente, sin intervención creativa alguna—, Turing hizo ver cómo esta idea puede refinarse y convertirse en un modelo detallado del proceso de computación, en el cual un algoritmo cualquiera es descompuesto en una secuencia de pasos atómicos simples. El modelo computacional resultante es una construcción lógica conocida como máquina de Turing.

Artículos relacionados

Puedes obtener el artículo en...

¿Tienes acceso?

Los boletines de Investigación y Ciencia

Elige qué contenidos quieres recibir.