¿ QUÉ ES LA MAQUINA DE TURING ?
Una máquina de Turing es un dispositivo que manipula símbolos sobre una tira de cinta de acuerdo con una tabla de reglas. A pesar de su simplicidad, una máquina de Turing puede ser adaptada para simular la lógica de cualquier algoritmo de computador y es particularmente útil en la explicación de las funciones de una CPU dentro de un computador.
Originalmente fue definida por el matemático inglés Alan Turing como una «máquina automática» en 1936 en la revista Proceedings of the London Mathematical Societynota. La máquina de Turing no está diseñada como una tecnología de computación práctica, sino como un dispositivo hipotético que representa una máquina de computación. Las máquinas de Turing ayudan a los científicos a entender los límites del cálculo mecánico.
Una máquina de Turing que es capaz de simular cualquier otra máquina de Turing es llamada una máquina universal de Turing (UTM, o simplemente una máquina universal). Una definición más matemáticamente orientada, con una similar naturaleza "universal", fue presentada por Alonzo Church, cuyo trabajo sobre el cálculo lambda se entrelaza con el de Turing en una teoría formal de la computación conocida como la tesis de Church-Turing. La tesis señala que las máquinas de Turing capturan, de hecho, la noción informal de un método eficaz en la lógica y las matemáticas y proporcionan una definición precisa de un algoritmo o 'procedimiento mecánico'.
La importancia de la máquina de Turing en la historia de la computación es doble: primero, la máquina de Turing fue uno de los primeros (si no el primero) modelos teóricos para las computadoras, viendo la luz en 1936. Segundo, estudiando sus propiedades abstractas, la máquina de Turing ha servido de base para mucho desarrollo teórico en las ciencias de la computación y en la teoría de la complejidad. Una razón para esto es que las máquinas de Turing son simples, y por tanto amenas al análisis. Dicho esto, cabe aclarar que las máquinas de Turing no son un modelo práctico para la computación en máquinas reales, las cuales precisan modelos más rápidos como los basados en RAM.
La máquina de Turing es un
concepto fundamental en la teoría de la computación, propuesto por el
matemático y lógico británico Alan Turing en 1936. Es una abstracción
matemática que representa un dispositivo teórico capaz de realizar cualquier
cómputo que pueda llevarse a cabo mediante un algoritmo.La máquina de Turing consta de
una cinta infinita dividida en casillas, un cabezal de lectura/escritura que
puede moverse a lo largo de la cinta y un conjunto finito de estados y reglas
de transición. Cada casilla de la cinta puede contener un símbolo de un
alfabeto finito, y el cabezal puede leer, escribir o borrar símbolos en la
cinta.La operación de la máquina de
Turing se rige por un conjunto de reglas de transición que determinan cómo el
estado actual de la máquina, el símbolo leído en la cinta y la regla de
transición específica determinan la acción a realizar (como cambiar el símbolo
en la cinta, mover el cabezal, cambiar de estado, etc.).La máquina de Turing es
significativa porque Turing demostró que, en teoría, cualquier problema
computacional que pueda resolverse de manera algorítmica puede ser resuelto por
una máquina de Turing. Esta idea fue fundamental en el desarrollo de la teoría
de la computación y sentó las bases para entender los límites de la computación
y la computabilidad. La "turing-completitud" es un concepto clave en
informática que se refiere a la capacidad de un sistema para realizar cualquier
cálculo que pueda realizarse en una máquina de Turing.
