Maquina de turing

EISC

M´quinas de Turing a

M´quinas de Turing a

Definici´n 1 o La M´quina de Turing (MT) es el moa delo de aut´mata com m´xima capacidad o a computacional: la unidad de control puede desplazarse a izquierda o derecha y sobreescribir s´ ımbolos en la cinta de entrada.

Definici´n 2 o Una M´quina de Turing (MT), a M = (Q, Σ, Γ, q0, T, B, δ)

EISC

M´quinas de Turing a

donde:

1. Qes un conjunto finito de estados.

2. Σ es el alfabeto de entrada.

3. Γ es el alfabeto de la cinta, que incluye a Σ, Σ ⊆ Γ

4. q0 ∈ Q es el estado inicial.

5. B ∈ Γ es el s´ ımbolo blanco (el s´ ımbolo B no puede hacer parte de Σ) aparece en todas las casillas excepto en aqu´llas que contienen los s´ e ımbolos de entrada.

6. T ⊆ Q conjunto de estados finales.

EISC

M´quinas deTuring a

7. δ es la funci´n de transici´n tal que: o o δ : Q × Γ → Q × Γ × {I, D} δ(q, X) = (p, Y, {I, D}) δ es una funci´n parcial, es decir, No o puede estar definida en algunos elementos del dominio. Definici´n 3 o (Funci´n parcial) Una funci´n f , o o f : A → B se dice que es una funci´n o parcial si ∃C ⊆ A, C = ∅, tal que ∀x ∈ C, ∃f (x) ( existe un subconjunto no vac´ ıo de A en el que todoslos elementos tienen imagen calculable.) Observaci´n 1 o

Una MT procesa una entrada w ∈ Σ∗ colocadas sobre una cinta infinita en ambas direcciones. Para procesar la

EISC

M´quinas de Turing a

cadena w, la unidad de control de M est´ en el estado inicial q0 escanendo a el primer s´ ımbolo de w. Las dem´s caa sillas de la cinta contienen el s´ ımbolo en blanco B.

Una descripci´ninstant´nea, es una o a expresi´n de la forma: o a1a2 . . . ai−1qai . . . an donde los s´ ımbolos a1, . . . , an ∈ Γ y q ∈ Q

Esta descripci´n instant´nea a1a2 . . . ai−1qai . . . o a indica que la unidad de control de M est´ en el estado q escanendo el s´ a ımbolo ai.

EISC

M´quinas de Turing a

Una transici´n δ(q, B) = (p, s, D) en o una MT requiere que el s´ ımbolo este escrito en la casillaescaneada, adem´s a la unidad de control sobre-escribe el blanco B sobre s y realiza un desplazamiento D.

EISC

M´quinas de Turing a

Computos especiales Durante el c´mputo o procesamiento de o la palabra de entrada, hay dos situaciones especiales que se pueden presentar:

1. El c´mputo termina por que en deo terminado momento no hay transici´n o definida.

2. El c´mputo no termina;esto es lo que o se denomina un bucle infinito. Esta situaci´n se representa as´ o ı: w1qw2 ∗ ∞ que indica que el c´mputo que se inio cia en w1qw2 no se detiene nunca.

EISC

M´quinas de Turing a

Lenguaje aceptado por una MT Una cadena de entrada w es aceptada por una MT M si el c´mputo que se indica la o configuraci´n inicial q0w termina en una o configuraci´n instant´nea w1pw2, p es un o aestado de aceptaci´n, en la cual M se o detiene completamente. El lenguaje L(M ) aceptado por una MT M se define como: L(M ) = {w ∈ Σ : q0w ∗ w1pw2, p ∈ T } M se para en w1pw2 Si la cadena de entrada en una m´quina M pertenece a L(M ), a la m´quina M siempre se detiene. a Definici´n 4 o Las m´quinas de Turing originan las sia guientes clases de lenguajes:

1. L es un lenguaje recursivamenteenumerable (RE) si existe una MT M tal que L(M ) = L.

EISC

M´quinas de Turing a

Definici´n 5 o Sea M una m´quina de Turing; se dice a que L = L(M ) es un lenguaje recursivamente enumerable si: ∀x ∈ L, M se DETIENE en q ∈ T , ∀x ∈ L, M se DETIENE en q ∈ T / / o ´ bien No se DETIENE.

2. L es un lenguaje recursivo si existe una MT M tal que L(M ) = L y M se DETIENE con todas las cadenas deentrada. Definici´n 6 o

EISC

M´quinas de Turing a

Se dice que L es un lenguaje recursivo si existe al menos una m´quina de Tua ring M , tal que L = L(M ) y ∀x ∈ L, M se DETIENE en q ∈ T , ∀x ∈ L, M se DETIENE en q ∈ T / /

Observaci´n 2 o Todo lenguaje recursivo es recursivamente enumerable, pero la afirmaci´n rec´ o ıproca no es (en general) v´lida. a Definici´n 7 o Un diagrama de transici´n...