Turing

Máquinas de Turing
Arquitetura de MT
Fita de Leitura / Escrita
〈

a1 a2 ...

ai

Controle
+
δ

... an

Registrador de Estado Atual e Máquina de Turing Determinística
Uma MTD é uma óctupla M = (Q, Σ, Γ, 〈, □, δ, i, F) em que:
- Q = conjunto de estados
- Σ = alfabeto de entrada
- Γ = alfabeto da fita ( Σ ⊂ Γ )
- 〈 = representa o primeiro símbolo da fita ( 〈 ∈ Γ − Σ )
- □ = representa o símbolo branco ( □ ∈ Γ − Σ, □ ≠ 〈 )
- δ = função de transição parcial Q × Γ → Q × Γ × { E, D}
- i = estado inicial

- F = conjunto de estados finais

Representação de uma transição : δ(e, a) = [ e´, b, d ]

e

a/bd

e´

Representação Gráfica
Ex.

0/0 E
1/1 E

0/1 D
1/0 D

□/□ E

〈/〈 D

Configuração Instantânea
C.I. de uma MTD é dada pela dupla [ e, x a y ] em que :
- e ∈ Q é o estado atual
- x ∈ Γ* é a palavra à esquerda da cabeça de leitura/escrita
- a ∈ Γ é o símbolo sob a cabeça de leitura/escrita
- y ∈ Γ* é a palavra à direita da cabeça de leitura/escrita

Linguagem Reconhecida por uma MTD
Seja uma MTD M = (Q, Σ, Γ, 〈, □, δ, i, F) então a linguagem reconhecida por M é :

L(M) = {w ∈ Σ* | [i, 〈 w]

[e, x a y], e ∈ F, δ(e,a) é indefinido}

*

Y/Y D

0/X D

1/Y E

X/X D

□/□
Y/Y D

Y/YE
0/0 E

Y/YD
0/0 D

Ex. L = { 0n1n | n ≥ 1}

E

Ex. L = { w ∈ {a, b}* | w = wR, | w | mod 2 = 0 } a/a D b/b D

□/□ E a /□

a/

D

□

E

a/a E b/b E

□/□ D

b

D

/□

/□

E

b

□/□ E a/a D b/b D

Ex. L = {a, b, c}* − ({a, b}{a, b, c}*) a/a D

a/a D b/b E b/b E

Linguagem Recursivamente Enumerável
⇒ Existe uma MT que a reconhece

Linguagem Recursiva
⇒ Existe uma MT que a reconhece e que pare para todas as palavras do alfabeto de entrada

Linguagem Reconhecida por uma MTD M = (Q, Σ, Γ, 〈, □, δ, i, F)
• Por Parada e Estado Final
L(M) = {w ∈ Σ* | [i, 〈 w]
• Por Estado Final
LF(M) = {w ∈ Σ* | [i, 〈 w]

*

*

a/a D

□/□

• Por Parada
LP(M) = {w ∈ Σ*