REDUCCIBILIDAD DE TURING

La reduccibilidad de turing son funciones intuitivas que pueden ser calculadas por una maquina calculadora para esto tienen que haber numeros naturales
Dado dos sistemas de números naturales, decimos A es Turing reducible a B

LENGUAJE ACEPTADO POR LA MT

Lenguaje aceptado por la Máquina de Turing

Una cadena _  A* , es aceptada por una MT, si comienza en el estado e0, con la cabeza de

lectura/escritura en el símbolo más a la izquierda, luego de leer toda la cadena _, llega a un estado

ef  F.

El lenguaje aceptado por MT, es el conjunto de todas las cadenas que son aceptadas por MT:

L(MT)= { _ / e0 _ | * 1 ef 2 y ef  F y 1, 2 C* y _  A*}

Los lenguajes aceptados por las Máquinas de Turing se denominan lenguajes recursivos

enumerables o estructurados por frases.