Ésta podría ser una edición anterior y no la más reciente o aprobada. Ir a la versión actual.

No se ha añadido ninguna twiki todavía.



Procedimiento «mecánico» idealizado, esto es, procedimiento que seguiría una máquina ideal, descompuesto en sus partes elementales e inventado por el matemático inglés Alan Turing (1912-1954) como respuesta al llamado problema de decisión, propuesto en 1900 por David Hilbert, en el Congreso nacional de matemáticos en París. Este problema planteaba si era posible hallar un procedimiento algorítmico, o un procedimiento mecánico, que resolviera, en principio, todos los problemas de matemáticas. Turing diseñó (1937) esta máquina ideal como un dispositivo constituido por un autómata y una cinta (potencialmente) infinita, dividida en casillas con símbolos o en blanco, y un dispositivo capaz de leer el


contenido de cada casilla, borrar o imprimir símbolos, y de desplazarse hacia adelante o atrás (o izquierda y derecha), de modo que, efectuados todos los cálculos, la máquina se parara y diera el resultado final. El resultado a que llegó, más o menos al mismo tiempo que Alonzo Church, que había trabajado en el mismo problema de Hilbert de forma independiente, es que: 1) una máquina de Turing es un algoritmo; 2) si una máquina de Turing resuelve un problema es que éste es computable; 3) no existe un algoritmo general para todo problema matemático o, lo que es lo mismo, no para todo problema la máquina de Turing se para, o no todo problema es computable. Si a estas conclusiones se añade que la mente humana puede considerarse una máquina de Turing, tenemos la denominada tesis de Church-Turing.


Se denomina «máquina universal de Turing» a la máquina de Turing capaz de solucionar todo problema computable. Los computadores digitales actuales se consideran máquinas de este tipo.

Relaciones geográficas

Cargando el mapa…