Capítulo 5 – MÁquinas de turing



Descargar 2,22 Mb.
Página2/31
Fecha de conversión08.06.2017
Tamaño2,22 Mb.
1   2   3   4   5   6   7   8   9   ...   31

2. Máquinas de Turing universales

Recordemos ahora la función calculable, Φ(x , z). Para un z fijo, Φ (x, z) es la función parcial de una variable calculada por el programa número z. Sea M la máquina de Turing que calcula esta función con el alfabeto {1}. A esta máquina de Turing le llamaremos máquina de Turing universal.

Sea g(x) una función calculable de una variable y sea z0 el número de un programa P en el lenguaje φ que calcula g.

Entonces, si comenzamos con la configuración



B x B z0

q1


donde x y z0 están escritos como series de 1 (en notación unaria), y la máquina M comienza a calcular, M calculará Φ(x,z ), es decir g (x ). De esta forma, M puede usarse para calcular cualquier función calculable de una variable.

M proporciona un modelo apropiado de un ordenador de propósito general, en el cual los datos y el programa se almacenan juntos en una única memoria - Podemos considerar a z0 como una codificación del programa que calcula g, y x como la entrada a dicho programa.

La construcción por Turing de un ordenador universal en 1936 hizo pensar que, al menos en principio, los ordenadores de propósito general serían posibles, y por tanto fue una anticipación de los ordenadores digitales modernos.




3. Lenguajes aceptados por Máquinas de Turing

Dada una máquina de Turing con alfabeto A = {s1, . . ., sn }, se dice que una palabra u A* es aceptada por M, si M para cuando comienza con la configuración

B u


q1



Es importante caracterizar los distintos lenguajes aceptados por los distintos tipos de máquinas o dispositivos. Este problema es fácil de resolver en las máquinas de Turing.

Teorema. - Un lenguaje es aceptado por una máquina de Turing si y sólo sí es r.e.

Demostración.- Sea L un lenguaje aceptado por una máquina de Turing M con alfabeto A. Sea g(x) la función unaria en A* que calcula M. Entonces g es una función parcialmente calculable- También,

L = {x A* / g(x)} .

Por tanto L es r.e.

1   2   3   4   5   6   7   8   9   ...   31


La base de datos está protegida por derechos de autor ©absta.info 2016
enviar mensaje

    Página principal