Utilizamos cookies propias y de terceros para mejorar nuestros servicios y facilitarle el uso de la web mediante el análisis de sus 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úa navegando, consideramos que acepta nuestra Política de cookies .

Actualidad científica

Síguenos
  • Google+
  • RSS
  • Investigación y Ciencia
  • Julio 1984Nº 94

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.

Menear

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.

Puede conseguir el artículo en:

Artículos relacionados