Download talfg_notes.pdf PDF

Titletalfg_notes.pdf
TagsSet (Mathematics) Regular Expression Sequence Theory Of Computation
File Size676.9 KB
Total Pages142
Document Text Contents
Page 71

7.2. OTRAS MÁQUINAS DE TURINGS 61

Definición 97 (Máquina de Turing con k cintas) Una máquina de Tu-
ring con k cintas es una tupla M = (K, Σ, δ, s) satisfaciendo:

1. K es un conjunto finito de estados, suponemos que el estado inicial s
pertenece a K,

2. Σ es un conjunto finito de śımbolos llamado alfabeto tal que Σ∩K = ∅
y contiene los śımbolos especiales t y B, llamados blanco y comienzo
de cinta respectivamente,

3. δ es una función, llamada de transición, definida del conjunto K × Σk

en (K ∪ {h, “si”, “no”}) × (Σ× {←,−,→})
k

tal que para todo p, q ∈
K, σ1, . . . , σk, σ



1, . . . , σ


k ∈ Σ y D1, . . . , Dk ∈ {←,−,→} tales que
δ(q, σ1, . . . , σk) = (p, (σ1, D1), . . . , (σk, Dk)), entonces para todo i ∈ N,
con 1 ≤ i ≤ k, tal que σi =B se verifica que σ



i =B y Di =→.

Las definiciones de configuración y paso de computación son análogas a
las del caso de máquinas de Turing deterministas.

En ocasiones, de entre las cintas de una máquina de Turing se distinguen
dos: la cinta de entrada y la de salida. La cinta de entrada se considera sólo
de lectura mientras que, la cinta de salida se considera sólo de escritura.
Finalmente, notar que la definición de aceptación o rechazo en el caso de
máquinas de Turing con múltiples cintas es idéntica al de las máquinas de
Turing con una única cinta.

El siguiente ejemplo muestra como se simplifica el reconocimiento del
lenguaje de los paĺındromos mediante una máquina de Turing con dos cintas.

Ejemplo 98 (Paĺındromos (y II)) Consideramos M = (K, Σ, δ, s) la má-
quina de Turing, definida como sigue:

Σ := {0, 1, B,t} es el alfabeto,

K := {s, q, q′} es el conjunto de estados, s es el estado inicial, y

la función de transición δ está definida mediante la tabla

Page 72

62 CAPÍTULO 7. MÁQUINAS DE TURING

p ∈ K σ1 ∈ Σ σ2 ∈ Σ δ(p, σ1, σ2)
s 0 t (s, 0,→, 0,→)
s 1 t (s, 1,→, 1,→)
s B B (s, B,→, B,→)
s t t (q,t,←,t,−)
q 0 t (q, 0,←,t,−)
q 1 t (q, 1,←,t,−)
q B t (q′, B,→,t,←)
q′ 0 0 (q′, 0,→, 0,←)
q′ 1 1 (q′, 1,→, 1,←)
q′ 0 1 (“no”, 0,−, 1,−)
q′ 1 0 (“no”, 1,−, 0,−)
q′ t B (“si”,t,−, B,−)

El número de movimientos que lleva a cabo la máquina en una entrada de
tamaño n está acotado por 3n.

Vista la noción de máquinas de Turing con varias cintas, podemos dar,
de manera sencialla, un ejemplo de máquina que enumera un lenguaje.

Ejemplo 99 (Enumeración de los números naturales) Sea M la má-
quina de Turing definida como sigue:

Σ := {0, 1, B,t} es el alfabeto,

K := {s, s′, r, c, c′} es el conjunto de estados, s es el estado inicial, y

la función de transición δ está definida mediante la tabla

p ∈ K σ1 ∈ Σ σ2 ∈ Σ δ(p, σ1, σ2)
s B B (s, B,→, B,→)
s α ∈ Σ \ {B} β ∈ Σ \ {B} (s′, 0,→, 0,−)
s′ α ∈ Σ β ∈ Σ (r, #,→, β,−)
r α ∈ Σ β \ {B} (r, α,−, β,←)
r α ∈ Σ B (c, α,−, B,→)
c α ∈ Σ 0 (c′, 1,→, 1,→)
c α ∈ Σ 1 (c, 0,→, 0,→)
c α ∈ Σ t (s′, 1,→, 1,→)
c′ α ∈ Σ 0 (c′, 0,→, 0,→)
c′ α ∈ Σ 1 (c′, 1,→, 1,→)
c′ α ∈ Σ t (s′, α,→,t,−)

Similer Documents