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