Turing Máquinas y teoría de la computabilidad
En 1936, para calcular cualquier función computable, la máquina inventada por "Alan Turing" fue nombrado "Turing Machine (TM)". En informática, TM es el modelo matemático abstracto de cálculo y construcción teórica primaria. Las máquinas de Turing trabajan a través de un número incontable de instrucciones preprogramado. Desempeña un papel importante y ayuda a los usuarios a encontrar el cálculo al delimitar el "Funciones computables".
Este artículo explicará brevemente las máquinas de Turing, su teoría de trabajo y computabilidad.
¿Qué es Turing Machine??
La máquina Turing fue inventada por Alan Turing. Inicialmente, fue nombrado un "A-Machine (máquina automática)". Más tarde, este término se cambió a "Máquina de Turing" por "Iglesia Alonzo", Quien era el asesor doctoral de Turing.
Una máquina Turing es un modelo matemático de cálculo basado en conjuntos de instrucciones infinitos utilizados para implementar cualquier algoritmo de computadora. La manipulación de símbolos se realiza de acuerdo con una tabla de reglas en una tira de cinta.
¿Cómo funciona Turing Machine??
La máquina Turing funciona con una cinta de memoria infinita dividida en celdas individuales. Cada celda puede mantener un símbolo extraído de un conjunto infinito de símbolos. Estos símbolos se conocen como el alfabeto de la máquina. La máquina tiene un "CABEZA"Eso apunta al estado inicial de implementar el algoritmo de computación.
Además, se puede mover sobre una de estas celdas para colocarse. La selección de "estadoSe puede hacer a partir de un conjunto finito de estados. La cabeza lee el símbolo (alfabetos de máquina) de la celda en cada paso. Después de leer el símbolo de la celda, la máquina de Turing puede agregar el nuevo símbolo a la misma celda. En la base del nuevo símbolo, puede mover el puntero de la cabeza un paso a la derecha o izquierda. Es posible que el proceso de cálculo se detenga.
¿Qué es la compatibilidad y la tesis de la iglesia??
La compatibilidad no es solo una máquina A (máquina turing), una función recursiva, lenguaje de programación Pascal o cálculo, sino la combinación de todos. La Iglesia de Alonzo, asesor doctoral de Turing, introdujo este concepto conocido como "Tesis de la iglesia". También se llama el "Tesis de la iglesia".
Además, no es un teorema, sino que se usa para comparar la función computable con las funciones que A-Machine pueden calcular. Esas funciones que no son computables por A-Machines, no pueden calcularse por otro método. Cuando se formuló el concepto de la tesis de la iglesia, en ese momento, la gente no sabía sobre la capacidad de las computadoras modernas, y fue un logro tan significativo.
Turing Máquinas y teoría de la computabilidad
Un conjunto de números naturales es un conjunto decidible o computable de Turing. Por ejemplo, tenemos una máquina Turing con el número "metro", Que se detiene cuando la salida es 1 si"metro"Está en el conjunto computable. Por otro lado, se detiene cuando la salida es 0 si "metro"No está en el conjunto de números naturales. Una función "riñonal"De un número natural a un número natural es un"Turing Computable". Se puede observar que no todos los conjuntos de números naturales son computables.
Hemos explicado el concepto de la máquina Turing y la teoría de la computabilidad.
Conclusión
La máquina de turing fue inventada por "Alan Turing"En 1938 calcular cualquier función computable. Es el modelo matemático abstracto de cálculo y una construcción teórica central en informática. Una máquina Turing es un modelo matemático de cálculo basado en conjuntos de instrucciones infinitos utilizados para implementar cualquier algoritmo de computadora. La manipulación de símbolos se realiza de acuerdo con una tabla de reglas en una tira de cinta. Este artículo demostró los conceptos de las máquinas Turing y la teoría de la computabilidad.