Maqunas de turing

Solo disponible en BuenasTareas
  • Páginas : 7 (1551 palabras )
  • Descarga(s) : 0
  • Publicado : 30 de mayo de 2011
Leer documento completo
Vista previa del texto
Unidad 4
Maquinas de Turing
4.1 Definición
4.2 Construcción
4.3 Lenguajes aceptados por la máquina de Turing
4.4 variantes de la quina de Turing
4.5 problemas de Hilbert

MÁQUINAS DE TURING

Definimos una máquina de Turing como una 7-tupla M = (Q, Σ, Γ, s, (, F, δ), donde

Q es un conjunto finito de estados
Σ es un alfabeto de entrada
Γ es un alfabetollamado alfabeto de la cinta
s ( Q es el estado inicial
( ( Γ es el símbolo blanco
F ( Q es el conjunto de estados finales o de aceptación
δ: Q ( Γ ( Q ( Γ ( {L, R} es una función parcial que se llama función de transición.

La máquina de Turing posee una cinta dividida en celdas, cada celda es capaz de almacenar un símbolo. Además posee una cabezalectora/escritora que lee y escribe un símbolo en la cinta. Inicialmente la cinta contiene b en todas sus celdas. La función de transición δ transforma pares (q, σ) en ternas de la forma (p, t, X), donde p es el siguiente estado, t es el símbolo escrito en la cinta y X es el movimiento de la cabeza lectora/escritora, que puede ser L o R.

Por ejemplo, la transición δ(q1, a) = (q5, b, R) provoca quela máquina pase de una configuración

a la configuración

Se puede dar una descripción instantánea de la máquina de Turing similar a la de los ADPND, para la transición anterior sería

(q1, abb) ( (q5, bbb)

el carácter subrayado indica la posición de la cabeza lectora/escritora.

Otra posibilidad es anteponer el estado actual al carácter señalado por la cabeza lectora/escritora como semuestra

q1abb ( bq5bb

Máquinas de Turing como aceptadores de lenguajes

Sea M = (Q, Σ, Γ, s, (, F, δ) una máquina de Turing. Entonces el lenguaje aceptado por M es

L(M) = {w ( Σ* | q1w (* w1pw2 para p ( F y wi ( Γ*}

Los lenguajes aceptados por las máquinas de Turing se conocen como lenguajes recursivamente enumerables.

El siguiente grafo muestra una máquina de Turing transforma unacadena de la forma anbam en an+mb mediante la siguiente función de transición:

δ(q1, a) = (q1, a, R)
δ(q1, b) = (q2, a, R)
δ(q2, a) = (q2, a, R)
δ(q2, () = (q3, (, L)
δ(q3, a) = (q4, b, L)
δ(q4, a) = (q4, a, L)
δ(q4, () = (q5, (, R)

La siguiente máquina de Turing reconoce el lenguaje anbn.

δ(q1, a) = (q2, c, R)
δ(q2, a) = (q2, a, R)
δ(q2, d) = (q2, d, R)
δ(q3, b) = (q3, d, L)δ(q3, d) = (q3, d, L)
δ(q3, a) = (q3, a, L)
δ(q3, c) = (q1, c, R)

δ(q1, d) = (q4, d, R)
δ(q4, d) = (q4, d, R)
δ(q4, () = (q5, (, L)

Construcción de máquinas de Turing

Lenguajes aceptados por Máquinas de Turing

Definición. Una lenguaje L sobre un alfabeto Σ se dice que es recursivamente enumerable si es aceptado por alguna máquina de Turing. Es decir, L es recursivamente enumerablesi para alguna máquina de Turing M tenemos que

L(M) = {w ( Σ* | qw (* upv para p ( F y u, v ( Σ*}

(donde q es el estado inicial de M y F es el conjunto de estados finales de M).
Un lenguaje L es recursivo si L es recursivamente enumerable y hay alguna máquina de Turing que para sobre todas las entradas que acepta L.

Lenguajes regulares, independientes del contexto, recursivos yrecursivamente enumerables

Sea M = (Q, Σ, s, F, δ) un autómata finito determinista. Se puede construir una máquina de Turing M’ = (Q’, Σ', Γ, s’, (, F’, δ’) para la cual L(M) = L(M’) por medio de:

Q’ = Q ( {q’}, donde q’ es un nuevo estado que no esta en Q.
Σ' = Σ
Γ = Σ ( {(}
F’ = {q’}
δ’(q, σ) = (δ(q, σ), σ, R), para q ( Q y σ ( Σ‘
δ’(q, () = (q’, (, S), para todo q ( F, donde Ses la directiva de cinta “no moverse”

Teorema. Si L es un lenguaje regular, entonces L es también un lenguaje recursivo.

Sea M un autómata de pila no determinista. Podemos construir una máquina de Turing que emule el comportamiento de M. Supongamos un MT con dos cintas, la primera contendrá la cadena de entrada y la segunda se utilizará para almacenar la pila. Un apilamiento se emula...
tracking img