Capítulo 5 – MÁquinas de turing



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


Recíprocamente, si L es r.e., entonces existe una función calculable g, tal que se verifica

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

Entonces existe una máquina de Turing M con alfabeto {s1, . . ., sn }

que calcula g(x) estrictamente. Entonces M acepta L.

El teorema anterior es también cierto para máquinas de Turing de quintuplas. Para el caso especial de A = {1}, tenemos el siguiente teorema.



Teorema. - Un conjunto. U, de números es r.e. si. y solo si existe una máquina de Turing M con alfabeto {1} que acepta 1[x] si y solo si x U.

Demostración.-

Se sigue inmediatamente del teorema anterior y del hecho de que la representación en base 1 del número x es 1[x].

Vamos a considerar ahora algunas ambigüedades que a veces resultan al hablar de conjuntos de cadenas r.e. Por ejemplo, consideremos el lenguaje

L0 = {an / n >0},

sobre el alfabeto {a,b}.

De acuerdo con nuestra definición, decir que L es r.e. es equivalente a decir que el conjunto de números que representan las cadenas de este conjunto en base dos, es recursivamente enumerable. Pero este conjunto de números no queda determinado hasta que no se especifique el orden de los símbolos a y b en el alfabeto.

En efecto, si se toman en el orden a-b, el correspondiente conjunto de números es

Q1= { 2n –1 / n>0},

mientras que si tomamos el orden inverso, b-a, el conjunto de números representados por las cadenas de L0 es



Q1 - { 2x / x Q1 } = { 2n+1 - 2 / n > O } .

En este caso resulta que ambos conjuntos son r.e. y no hay problemas en afirmar que L es r.e. Lo que ocurre aquí no es una excepción. De hecho ocurrirá siempre. Esto es una consecuencia del primer teorema de este apartado. El que una cadena sea aceptada por una Máquina de Turing es independiente del orden de los símbolos en el alfabeto. Por tanto, podemos afirmar que el hecho de que un lenguaje particular sobre un alfabeto determinado sea r.e. es independiente del orden que exista en el alfabeto.

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