Diagrama de bloques procesador pipeline RISC

Máquinas de turing

• Máquina abstracta definida por el matemático inglés Alan
Turing en Proceedings of the London Mathematical Society
2:230-265, 1936.
• Reglas básicas
– Sólo se pueden escribir símbolos que pertenecen a un conjunto finito.
– Cada acción que la máquina toma sólo depende del símbolo que está
siendo examinado y del “estado mental” en ese momento.
– Aunque el estadopuede cambiar como resultado de los símbolos o
cálculos que se han efectuado, el número de estados distintos es finito.

• Máquina abstracta



– Examinar un símbolo individual en el papel.
– Borrar un símbolo o reemplazarlo por otro.
– Trasladar la atención de una parte del papel a otra.


Máquinas de Turing
• Se tiene un alfabeto de entrada y un alfabeto,
posiblemente mayor, de lossímbolos utilizados durante
la operación o cálculos de la máquina.
• Un conjunto finito de estados que representan los
distintos “estados mentales”.
• En lugar de una hoja de papel, se tiene una cinta linear
“infinita” con inicio en el extremo izquierdo e infinita
hacia la derecha. Esta cinta esta dividida en cuadros, en
cada uno de los cuales puede estar un símbolo o un
espacio en blanco(#).




Máquinas de turing


Definición formal de Máquina de Turing
• Una Máquina de Turing es un 6-tupla
T = (Q, , , q0, , F)

– Q es un conjunto finito de estados incluidos los estados de paro
ha y hr .
–  es el alfabeto de entrada con el que se forman las cadenas a
procesar.
–  es el alfabeto de la cinta que contiene a  pero no al espacio
en blanco (#).
– q0 es elestado inicial y pertenece a Q.
– La función de transición
: Q  (  {#})  Q  (  {#})  {R, L}


Estatus de una MT. Versión 1
• La configuración o descripción instantánea de una Máquina de
Turing está definida por:
a) El estado en el que se encuentra,
b) El contenido de la cinta y
c) La posición de la cabeza lectora.
• La configuración se representa como uqv cuando la MT se
encuentraen el estado q, el contenido de la cinta es la cadena uv
(en ese orden, de izquierda a derecha) y la cabeza lectora se
encuentra en el primer símbolo de v. La cinta sólo contiene
espacios blancos (#) a la derecha del último símbolo de v; para
Lenguajes de abreviar, estos blancos a la derecha de la palabra no se indican en la
Computación
configuración .

Estatus de una MT. Versión 2
• Laconfiguración de una Máquina de Turing se representa por una
pareja ordenada (q, xay) que indica que la MT se encuentra en el
estado q, el contenido de la cinta es xay y la cabeza lectora se
encuentra en el símbolo subrayado. En xay se incluye sólo hasta el
último símbolo a la derecha diferente del espacio en blanco
representado por # ó por □, .
• La siguiente configuración se representapor
(q7,, #101101111).
#


1

0

1

1

0

1

1

1

1

#

#

#

...
q7

Operación de la MT
• La acción está determinada por el estado actual y el símbolo en la
cinta y consiste de tres partes
– Reemplazar el símbolo en el cuadrado actual por otro que puede ser distinto o
el mismo.
– Mover la cabeza lectora a la derecha o a la izquierda (a menos que se
encuentreen el extremo izquierdo de la cinta) o quedarse donde está.
– Hacer una transición de estado, que puede ser distinto o el mismo.

• La cinta sirve como dispositivo de entrada y salida así como la
memoria disponible para utilizar durante la operación o cálculos de la
máquina.

Lenguajes de
Computación

Otoño
2013

Turing computable
• Definicion: Se dice que una función de cadena f esturing computable si existe una maquina de turing
M=(Q,Σ,Γ,q1,#,F,δ) para la cual 𝑞1 𝑤
algún 𝑞 𝑓 ∈ 𝐹, cuando 𝑓 𝑤 = 𝑢.



∗

𝑞 𝑓 𝑢 para

𝑰 |𝒘
L={𝒘𝒘
• B es blanco.

Lenguajes de
Computación



∈ *𝒂,

+}
𝒃+

L={a,b}* numero de a’s+b’s es
par
•
•
•
•
•

δ(q0,a)=(q1,a,R)
δ(q0,b)=(q1,b,R)
δ(q1,a)=(q0,a,R)
δ(q1,b)=(q0,b,R)
δ(q0,#)=(qf,#,R)

Lenguajes de...