Turing

Disponível somente no TrabalhosFeitos
  • Páginas : 6 (1327 palavras )
  • Download(s) : 0
  • Publicado : 14 de março de 2013
Ler documento completo
Amostra do texto
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



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

LinguagemRecursivamente 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 ∈ Σ*| [i, 〈 w]
Ex.

[e, x a y], e ∈ F}
b/b E

a/
c/ a D
c
□/□ D
D

D
b
D
b/
c
c/
D

Ex.

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

a/a D
b/b E

*

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

Variações da Máquina de Turing
– MT com Cabeçote Imóvel
δ = função de transição parcial Q × Γ → Q × Γ× { E, D, I}
0/0 D
1/1 D
0/0 D
1/1 D

e

e
□/□ I



□/□

E

d0/0 D
1/1 D

e

□/□

D

d

0/ 0 D
1/ 1 D
〈/〈D
□/□D

0/ 0 E
1/ 1 E
□/□E





Variações da Máquina de Turing
– MT com Múltiplas Trilhas (k trilhas)
δ = função de transição parcial Q × Γk → Q × Γk × { E, D, I}
Controle

Registrador
de Estado Atual

Controle

Registrador
de Estado Atual

+

e

+

e

δ

δ
k-tupla



a11 a21 ... ai1 ...

an1...

Trilha 1



a11 a21 ... ai1 ...

an1

...

a02

a12 a22 ... ai2 ...

an2

...

Trilha 2

a02

a12 a22 ... ai2 ...

an2

...

a03 a13 a23 ... ai3 ... an3
.
. ..
.
. ..
.
a.0k a.12 a.22 ... a.i2 ... a.n2
.
..
..
.
.

...

Trilha 3

...

...

.
.
.

a03 a13 a23 ... ai3 ... an3
.
. ..
.
. ..
.
a.0k a.12 a.22 ... a.i2 ... a.n2
...
..
.
.

a0k

...

Trilha k

a0k

...

a1k a2k

... aik

...

ank

a1k a2k

...

aik ...

ank

...

Fita

Variações da Máquina de Turing
– MT com Fita Ilimitada
Fita de Leitura / Escrita
... a1 a2 ...

ai

... an

...

-3

1

2

4

-2

-1

0

3

Fita de Leitura / Escrita
0

1

2

3

4

5

6



a1 a2

...

ai... an ...



a1 a2

...

ai

... an ...

-1

-2 -3

-4

-5 -6

-7 -8

Variações da Máquina de Turing
– MT com Múltiplas Fitas
δ = função de transição parcial Q × Γk → Q × (Γ × { E, D, I})k
Controle

Registrador
de Estado Atual

+

e

δ



a11 a21 ... ai1 ...

an1

...

Fita 1



a12 a22 ... ai2 ...

an2

...

Fita 2



a13 a23 ......
tracking img