Maquinas de turing

Maquina de turing
Introducción
En esta tarea se realizara descripción ejercicios de maquinas turing
Ejercicio 1Describir máquinas de Turing que lleven a cabo las siguientes tareas:
§Dados dosnúmeros naturales m; n ε N, calcula su suma m + n.
M=7 n=4
En particular, para los números 7 y 4, se verifica que:
7 + 4 = 4 + 7

§Dados dos números enteros m; n ε N, decide si m ≥ n.
• si a ≥0, |a| = a ; por ejemplo, |5| = 5;
• si a <lal0, |a| = -a ; por ejemplo, |-5| = -(-5) = 5
M=4 n=7
4+7=7≥4
§Dados dos números naturales m; n ε N, calcula su resta m-n siempre y cuando m≥ n. Encaso contrario, i. e. m < n, la máquina rechaza la entrada.
M=5≥ n=(-3)
5 - (-3) = 5 + 3 =≥ 8

§Dados dos números naturales m; n ε N, calcula su producto m - n.
-2 - 5 = (-2) + (-5) = -7§Dados dos números naturales m; n ε N, calcula el cociente y el resto de dividir m por n siempre y cuando m ╪ 0. En caso contrario, i. e. si m = 0, la máquina rechaza la entrada. m : n ≠ n :m
6 : (−2) ≠(−2) : 6

En cualquiera de los casos anteriores se supondrá que los números vienen dados mediante su codificación binaria y están escritos de izquierda a derecha, i.e. las unidades en primer lugar,luego las decenas,... y así sucesivamente.
Ejercicio 2 Diseñe una máquina de Turing para identificar si un número es par o impar.
Problema 3.1.- Diseñe una máquina de Turing
para identificar si unnúmero es par o impar.
f n {
si
( ) =
n e s n o n
si n e s p a r
1
0
Configuración inicial 11 ... 1
Estratégia:
Lee 1, borra y mueve hacia la derecha
Si lee 0: escribe “1”, non
Si lee 1:borra 1, mueve hacia derecha
Si lee 0, termina par
Si lee 1, inicia rutina principal
Capítulo 3
8
escribe B mueve R escribe 1
1:B B:R B:1
1 2 3 5
PAR
B:R 1:B NON
4
Configuraciones:
NON
111011 011 001 001 000 0000 0001
1 2 3 4 1 2 3 5
PAR
1111 0111 0111 0011 0011 0001
1 2 3 4 1 2
0001 0000 0000
3 4 1

Ejercicio 3 Construlla una MT para Multiplicar en notación monádica lo...