lab de algoritmos(maquinas turing)

Esta entrada se trata de las maquinas de turing, que es una maquina de turing?, bueno una maquina de turing es un tipo de automata que se mueve sobre una banda de datos que tiene un inicio pero no tiene final solo puede ver un dato cada que avanza y avanza hacia la derecha o hacia la izquierda dejando el valor de la celda igual avanzando hacia la derecha o izquierda o quedarse en ese punto, modificandolo avanzano a la derecha o izquierda o quedandose en ese punto  realizando dichas acciones apartir de una tabla que tiene en cuenta en que lugar de la banda esta y el ultimo dato leido

Tiene una cinta sobre la que puede desplazarse a izquierda y derecha un cabezal de lectura/escritura. La cinta contiene una serie de celdas, y en cada una de ellas puede escribirse un símbolo de un conjunto finito; este conjunto de símbolos se denomina el alfabeto de la máquina. En principio todas las celdas que no se hayan escrito antes contienen un carácter especial nulo o vacío (que se representa por 0 o #). La cinta puede contener tantas celdas a derecha e izquierda del cabezal como sean necesarias para el funcionamiento de la máquina.

• El cabezal puede moverse a derecha (R) a izquierda (L) de su posición actual, así como leer el contenido de una celda o escribir en ella cualquier carácter de su alfabeto.
• Existe un registro de estado que almacena el estado de la máquina. El número de estados posibles es finito, y no se exige ningún estado especial con el que sea iniciada la máquina.
• Existe una tabla de acción ,que contiene las instrucciones de lo que hará el autómata. Estas instrucciones representan en cierta forma el "programa" de la máquina. Las ejecución de cada instrucción de la tabla de acción incluye cuatro pasos:
• Leer un carácter en la posición actual.
• Escribir un nuevo símbolo en esta posición (puede ser el mismo que había). El símbolo a escribir es alguno del alfabeto de la máquina, y depende del carácter leído y del estado actual.
• Desplazar el cabezal una celda a derecha o izquierda (R/L); en algunos modelos el desplazamiento puede ser nulo (detener H).
• Decidir cual será el nuevo estado en función del carácter que se acaba de leer y del estado actual. Si la tabla de acción no contiene ninguna correspondencia con el estado actual y el símbolo leído, entonces la máquina detiene su funcionamiento

despues de esta pequeña explicacion de maquinas turing un ejemplo que estube realizando en clase  se le sumava uno a un numero :


# = vacio
&= inicio
<=retroceder
>=avanzar
- =quieto

s,   0  =      s,0,>
s,   1  =      s,1,>
s,   #  =      q,#,<
s,  & =      s,&,>
q,   0 =      Alto,1,-
q,   1 =      q,0,<
q   & =     p,&,>
p   0   =     r,1,>
r    0   =     r,0,>
r    #   =    Alto,0,-

1110011

s, &1110011#    s,&,>
s, &1110011# s,1,>
s, &1110011# s,1,>
s, &1110011# s,1,>
s, &1110011# s,0,>
s, &1110011# s,0,>
s, &1110011# s,1,>
s, &1110011# s,1,>
s, &1110011# q,#,<
q,&1110011# q,0,<
q,&1110010# q,0,<
q,&1110000# Alto,1,-

numero escrito= 1110011=115
resultado=  1110100 = 116
 
bueno esto es una forma de representar las maquinas turing su funcionamiento cabe recordar que existen varios tipos de maquinas turing esta es la estandar basada en base 2 pero puede aber otras que tu le des el alfabeto a utilizar. por mi parte es todo gracias

para aser esta publicacion me base en esta pagina http://www.zator.com/Cpp/E0_1_1.htm