Máquina de Turing

Número computable

Son los números reales que pueden ser calculados con la precisión que se desee por un algoritmo finito. Un número computable es aquel para el que hay una máquina de Turing dado n su cinta inicial termina con el n-esimo digito de ese número

Por ejemplo tenemos un número con infinitos decimales como π , hay un algoritmo que te permite calcular un numero finito de decimales de π , por lo que π sería computable.

Problemas de decisión

Un problema de decisión es una pregunta que tiene una respuesta verdadera o falsa.
Por ejemplo: ¿Es 11 número primo?

Church y Turing demostraron en 1936 que no hay un algoritmo general capaz de decidir si una fórmula es un teorema.

Un problema de decisión puede tener una solución si la maquina de Turing se para y da un resultado, de lo contrario si la máquina no se para y sigue hasta el infinito no tendrá solución.

Máquina de Turing

Consta de una cinta infinita con cuadros, cada cuadro es capaz de almacenar un simbolo de un conjunto de símbolos definidos (en este caso: espacio en blanco,0 y 1). La cinta esta en un estado inicial con unos simbolos pertenecientes al conjunto.

Tiene un cabezal que esta en un estado inicial que lee el simbolo que se encuentra en ese cuadro, según el simbolo que lea y como este programada la máquina borrara el simbolo o lo mantendrá o escribirá un espacio en blanco y se desplazará a izquierda o derecha y cambiará de estado.



Enlaces de interés:

Puedes comprobar como funciona la máquina de Turing en el siguiente enlace, tienes programas de prueba.
http://morphett.info/turing/turing.html

2 opiniones en “Máquina de Turing”

    1. No hay ninguna máquina de Turing que pueda determinar, en un número finito de pasos, si una fórmula dada del cálculo de predicados es o no un teorema del cálculo.

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *