Maquinas de turing

Solo disponible en BuenasTareas
  • Páginas : 2 (460 palabras )
  • Descarga(s) : 0
  • Publicado : 15 de noviembre de 2011
Leer documento completo
Vista previa del texto
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...
tracking img