Máquina de Turing Multipista
Páginas: 2 (329 palabras)
Publicado: 11 de noviembre de 2013
Máquina de Turing Multipista
Es aquella mediante la cual cada celda de la cinta se divide en subceldas. Cada subcelda es capaz de contener símbolos de la cinta. La cinta tiene cada celdasubdividida en tres subceldas. Se dice que esta cinta tiene múltiples pistas. Puesto que cada celda de esta máquina de Turing contiene múltiples caracteres, el contenido de las celdas de la cinta puede serrepresentado mediante n-tuplas ordenadas. En el ejemplo anterior, las celdas de la cinta contienen (B, a, a), (b, a, a) y (b, b, B).
Por tanto, los movimientos que realice está máquina dependeránde su estado actual y de la n-tupla que represente el contenido de la celda actual.
Una máquina de Turing multipista no tiene más potencia que la máquina de Turing original. Sin embargo, hace quesea más fácil la construcción de máquinas de Turing que resuelvan ciertos problemas.
Ejemplo: Para una máquina de Turing que sume dos números binarios. Primero se construye una máquina de Turing detres pistas. La entrada serán dos números binarios que ocupen las dos pistas superiores de la cinta. Suponiendo que sus dígitos se alinean por la derecha, que sus representaciones binarias son de lamisma longitud (lo que se puede conseguir rellenándolas con tantos ceros como sea necesario) y que la cabeza de lectura/escritura se sitúa sobre la celda del extremo izquierdo de la cadena. Por tanto,si tuvieran que sumar 101 y 10, la cinta debería contener
La máquina de Turing realizará la suma en la tercera pista. Por tanto, el alfabeto de cinta estará formado por las ternas:
(B, B,B) (1, 1, B) (1, 1, 0) (1, 1, 1)
(0, 0, B) (0, 0, 0) (0, 0, 1) (B, B, 1)
(0, 1, B) (0, 1, 0) (0, 1, 1)
(1, 0, B) (1, 0, 0) (1, 0, 1)
Esta máquina de Turing buscaráprimero hacia la derecha el extremo derecho de los números que van a ser sumados. Entonces sumará pares de dígitos, desde la derecha hacia la izquierda, llevando la cuenta de los resultados que...
Es aquella mediante la cual cada celda de la cinta se divide en subceldas. Cada subcelda es capaz de contener símbolos de la cinta. La cinta tiene cada celdasubdividida en tres subceldas. Se dice que esta cinta tiene múltiples pistas. Puesto que cada celda de esta máquina de Turing contiene múltiples caracteres, el contenido de las celdas de la cinta puede serrepresentado mediante n-tuplas ordenadas. En el ejemplo anterior, las celdas de la cinta contienen (B, a, a), (b, a, a) y (b, b, B).
Por tanto, los movimientos que realice está máquina dependeránde su estado actual y de la n-tupla que represente el contenido de la celda actual.
Una máquina de Turing multipista no tiene más potencia que la máquina de Turing original. Sin embargo, hace quesea más fácil la construcción de máquinas de Turing que resuelvan ciertos problemas.
Ejemplo: Para una máquina de Turing que sume dos números binarios. Primero se construye una máquina de Turing detres pistas. La entrada serán dos números binarios que ocupen las dos pistas superiores de la cinta. Suponiendo que sus dígitos se alinean por la derecha, que sus representaciones binarias son de lamisma longitud (lo que se puede conseguir rellenándolas con tantos ceros como sea necesario) y que la cabeza de lectura/escritura se sitúa sobre la celda del extremo izquierdo de la cadena. Por tanto,si tuvieran que sumar 101 y 10, la cinta debería contener
La máquina de Turing realizará la suma en la tercera pista. Por tanto, el alfabeto de cinta estará formado por las ternas:
(B, B,B) (1, 1, B) (1, 1, 0) (1, 1, 1)
(0, 0, B) (0, 0, 0) (0, 0, 1) (B, B, 1)
(0, 1, B) (0, 1, 0) (0, 1, 1)
(1, 0, B) (1, 0, 0) (1, 0, 1)
Esta máquina de Turing buscaráprimero hacia la derecha el extremo derecho de los números que van a ser sumados. Entonces sumará pares de dígitos, desde la derecha hacia la izquierda, llevando la cuenta de los resultados que...
Leer documento completo
Regístrate para leer el documento completo.