TIPOS DE MAQUINA DE TURING

¿ 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.