Maquina de Turing generadora

L={ aⁿb²ⁿaⁿ, con n mayor o igual a 0} .


En la cinta 2, se mostrarán las cadenas generadas del lenguaje.
Se empieza en q₁.

Multicinta	(0, B)	(1, B)	(B, B)
q1	{q1, (0, R), (B, Z)}	{q2, (1, R), (B, Z)}	{q2, (0, R), (B, Z)}
q2		{q2, (1, R), (B, Z)}	{q3, (1, L), (a, R)}
q3	{q3, (0, L), (b, R)}	{q3, (1, L), (a, R)}	{q4, (B, R), (B, Z)}
q4	{q4, (0, R), (b, R)}	{q4, (1, R), (a, R)}	{q5, (B, L), (#, R)}
q5	{q5, (0, L), (B, Z)}	{q5, (1, L), (B, Z)}	{q1, (0, R), (B, Z)}

Máquina de Turing para saber si un bloque de ceros está ordenador crecientemente

Ejemplo de cadena que debe aceptar: B01000010000000B

Ejemplo de cadena que debe rechazar: B010000100B

Principal	0	1	$	B	X
q0	(q1, B, R)			(q2, 0, L)
q1	(q1, 0, R)	(q1, 1, R)		(q0, $, R)
q2	(q2, 0, L)	(q2, 1, L)	(q2, $, L)	(q3, B, R)
q3	(q4, B, R)	(q5, B, R)	(q13, B, R)
q4	(q4, 0, R)	(q4, 1, R)	(q4, $, R)	(q2, 0, L)
q5	(q6, X, R)	(q9, 1, R)
q6	(q6, 0, R)	(q6, 1, R)	(q6, $, R)	(q7, B, L)
q7	(q8, B, L)		(q11, $, L)
q8	(q8, 0, L)	(q8, 1, L)	(q8, $, L)		(q5, X, R)
q9	(q9, 0, R)	(q9, 1, R)	(q10, $, R)
q10				(q11, B, L)
q11	(q11, 0, L)	(q11, 1, L)	(q11, $, L)		(q12, 0, L)
q12				(q3, B, R)	(q12, 0, L)
q13	(q13, B, R)			(q14, B, L)
q14

Multicabezal	(0, 0)	(1, 0)	(0, 1)	(1, 1)	(0, B)	(1, B)
q0	{q0, (0, Z), (0, R)}		{q1, (0, Z), (1, R)
q1	{q1, (0, R), (0, R)}	{q2, (1, R), (0, R)}		{q1, (1, R), (1, R)}	{q3, (0, Z), (B, Z)}	{q3, (1, Z), (B, Z)}
q2	{q2, (0, Z), (0, R)}		{q1, (0, Z), (1, R)}
q3

Maquina de Turing para contar el número de parámetros.

Cinta de entrada: B00010001010000100B
Cinta de salida:B00000B

A continuación ponemos la tabla de transición de la MT "normal". El cabezal inicialmente está posicionado sobre el primer cero. El estado final es el q8.

Principal	0	1	$	B
q0	(q0, 0, R)	(q0, 1, R)		(q1, $, L)
q1	(q1, 0, L)	(q1, 1, L)		(q2, B, R)
q2	(q3, B, R)
q3	(q3, B, R)	(q4, B, R)	(q7, B, R)
q4	(q4, 0, R)	(q4, 1, R)	(q5, $, R)
q5	(q5, 0, R)			(q6, 0, L)
q6	(q6, 0, L)	(q6, 1, L)	(q6, $, L)	(q2, B, R)
q7	(q7, 0, R)			(q8, 0, R)
q8

La tabla de transición siguiente, corresponde al modelo de Máquina de Turing multicinta para resolver el mismo problema que el anterior. En la cinta 2 guardamos la salida.

Multicinta	(0, B)	(1, B)	(B, B)
q0	{q1, (0, R), (0, R)}
q1	{q1, (0, R), (B, Z)}	{q0, (1, R), (B, Z)}	{q2, (B, Z), (B, Z)}
q2

Diario de la semana del 7-04-08 al 18-04-08

Esta semana quedamos el lunes, para empezar a enfocar como resolveríamos las dos Máquinas de Turing (la simple y la multicinta para sacar los divisores de un número), también tratamos un poco por encima la exposición que teníamos que hacer sobre que las MT “normales” tienen el mismo poder computacional que las MT no deterministas y al revés. Eso fue de 8:45 hasta cerca de las 10 que teníamos la clase de TALF.

Al enterarnos que teníamos que dar la exposición citada anteriormente el viernes próximo, creyendo primero que era el otro viernes. El martes a las 10 quedamos media hora para hablar como lo haríamos y para que buscáramos información por Internet.

El miércoles, a las 11 aproximadamente empezamos a realizar el powerpoint hasta las 13 horas. Y por la tarde continuamos haciendo el powerpoint y el guión que usaríamos donde poníamos los puntos a recalcar sobre las distintas diapositivas.

El jueves quedamos a las 10h nos repartimos las partes de la charla a suertes e hicimos un pequeño ensayo.

El viernes hicimos la exposición a la clase del tema anteriormente preparado.

Máquina de Turing Multicinta de Obtener los Divisores:

Subrutina	(0, 0, B)	(0, B, B)	(B, 0, B)	(B, B, B)	(0, X, B)	(B, X, B)
qi	(qi, (0, R), (X, R), (B, Z))	(qi2, (0, Z), (B, L), (B, Z))		(qi3, (B, Z), (B, L), (B, Z))
qi2		(qi, (0, Z), (B, R), (B, Z))		(qi3, (B, Z), (B, R), (B, Z))	(qi2, (0, R), (0, L), (B, Z))
qi3			(qi7, (B, Z), (0, Z), (B, Z))			(qi4, (B, Z), (X, Z), (B, Z))
qi4				(qi5, (B, Z), (B, R), (B, Z))		(qi4, (B, Z), (0, L), (0, R))
qi5			(qi6, (B, L), (B, R), (B, Z))	(qi11, (B, L), (B, Z), (B, Z))
qi6	(qi6, (0, L), (O, Z), (B, Z))		(qi, (B, R), (0, Z), (B, Z))
qi7			(qi7, (B, Z), (0, R), (0, R))	(qi8, (B, L), (B, L), (B, Z))
qi8	(qi9, (0, Z), (B, L), (B, Z))
qi9	(qi10, (0, L), (0, L), (B, Z))	(qi11, (0, L), (B, Z), (B, Z))
qi10	(qi10, (0, L), (0, L), (B, Z))	(qi10, (0, L), (B, Z), (B, Z))		(qi, (B, R), (B, R), (B, Z))
qi11		(qi11, (0, L), (B, Z), (B, Z))		(qr, (B, R), (B, Z), (B, Z))

Principal	(0, 0, B)	(0, B, B)	(B, B, B)
q0		(q1, (0, R), (B, Z), (B, Z))	(q2, (B, L), (B, L), (B, Z))
q1		(q0, (0, R), (0, R), (B, Z))	(q2, (B, L), (B, L), (B, Z))
q2	(q3, (0, L), (0, L), (B, Z))
q3	(q3, (0, L), (0, L), (B, Z))	(q3, (0, L), (B, Z), (B, Z))	(qi, (B, R), (B, R), (B, Z))
qr

Máquina de Turing "Normal" de Obtener los Divisores:

Subrutina	0	1	$	B	X	Y
qi	(qi2, X, R)		(qi5, $, R)
qi2	(qi2, 0, R)		(qi3, $, R)
qi3	(qi4, Y, L)					(qi3, Y, R)
qi4	(qi4, 0, L)		(qi4, $, L)		(qi, X, R)
qi5	(qi6, 0, L)		(qi7, $, L)			(qi5, Y, R)
qi6			(qi6, $, L)	(qi, B, R)	(qi6, 0, L)	(qi6, Y, L)
qi7			(qi7, $, L)	(qi8, B, R)	(qi7, 0, L)	(qi7, 0, L)
qi8	(qi9, X, R)		(qi11, $, R)
qi9	(qi9, 0, R)	(qi9, 1, R)	(qi9, $, R)	(qi10, 0, L)
qi10	(qi10, 0, L)	(qi10, 1, L)	(qi10, $, L)		(qi8, X, R)
qi11	(qi11, 0, R)	(qi11, 1, R)	(qi11, $, R)	(qi12, 1, L)
qi12	(qi12, 0, L)	(qi12, 1, L)	(qi12, $, L)	(qi13, B, R)	(qi12, 0, L)
qi13	(qi14, B, R)
qi14	(qi15, 0, L)		(qr, B, R)
qi15				(qi, B, R)

Principal	0	B	X	$
q0		(q1, $, R)
q1	(q2, X, R)
q2	(q2, 0, R)	(q3, $, L)	(q3, X, L)
q3	(q3, 0, L)		(q3, X, L)	(q4, $, L)
q4	(q4, 0, L)	(q5, 0, R)
q5	(q5, 0, R)			(q6, $, R)
q6	(q7, 0, L)		(q6, X, R)	(q8, $, L)
q7			(q1, X, R)	(q1, $, R)
q8	(q8, 0, L)	(qi, B, L)	(q8, 0, L)	(q8, $, L)
qr	(qr, B, R)			(q9, B, R)
q9

Máquina de Turing N(cuadrado)

Esto es un enlace al pdf de la Máquina de Turing que calcula el N(cuadrado): Para descargar pincha aquí

Máquina de Turing de la División

Subrutina	0	1	$	B	Y
qi	(qi2, B, R)	(qr, B, R)
qi2	(qi2, 0, R)	(qi2, 1, R)	(qi3, $, L)		(qi2, Y, R)
qi3	(qi4, Y, L)	(qi5, 1, R)			(qi3, Y, L)
qi4	(qi4, 0, L)	(qi4, 1, L)		(qi, B, R)
qi5	(qi5, 0, R)		(qi5, $, R)	(qi6, 0, L)	(qi5, Y, R)
qi6	(qi6, 0, L)	(qi6, 1, L)	(qi6, $, L)	(qi, B, R)	(qi6, 0, L)

Principal	0	1	$	B	Y
q0	(q1, 0, R)
q1	(q1, 0, R)	(q2, 1, R)
q2	(q3, 0, R)
q3	(q3, 0, R)			(q4, B, L)
q4	(q5, $, L)
q5	(q5, 0, L)	(q5, 1, L)		(qi, B, R)
qr	(qr, B, R)		(q6, 1, L)		(qr, 0, R)
q6

Máquina de Turing para la multiplicación

Máquina de Turing de la Multiplicación:

Subrutina	0	1	$	B	X
qi	(qi2, X, R)		(qi6, $, L)
qi2	(qi2, 0, R)		(qi3, $, R)
qi3	(qi3, 0, R)			(qi4, 0, L)
qi4	(qi4, 0, L)		(qi5, $, L)
qi5	(qi5, 0, L)				(qi, X, R)
qi6		(qr, 1, L)			(qi6, 0, L)

Principal	0	1	$	B
q0	(q0, 0, R)	(q0, 1, R)		(q1, $, L)
q1	(q1, 0, L)	(q1, 1, L)		(q2, B, R)
q2	(q3, B, R)	(q4, B, R)
q3	(q3, 0, R)	(qi, 1, R)
qr	(qr, 0, L)			(q2, B, R)
q4	(q4, B, R)		(q5, B, R)
q5