MAquinas de Turing

5. Maquinas de Turing
5.1 Introdução
As maquinas de Turing são uma proposta de formalização da noção de procedimento efetivo
(programa executado num computador que sempre fornece uma resposta)
A maquina de Turing não é nada mais do que um autômato finito determinístico com uma fita, onde será escrita a palavra a processar, e uma cabeça de leitura que pode se movimentar tanto a direita quanto a esquerda. Com a cabeça de leitura podemos então ler e escrever símbolos do alfabeto de fita.

5.2 Definição
Uma maquina de Turing é formalmente descrita pela tupla de 7 valores:
M= (Q,Γ,Σ,δ,s,B,F) onde:
- Q é um conjunto finito de estados
- Γ é o alfabeto de fita
-Σ

Γ é o alfabeto de entrada

-s

Q é o estado inicial

-F

Q é o conjunto dos estados de aceitação

-B
#)

Γ-Σ é o símbolo branco (geralmente anotado

- δ: QxΓ → QxΓx{L,R} é a função de transição
(L=Left e R=Right)

A configuração de uma maquina de Turing é um elemento que pertence a:
Q x Γ* x (ε Γ*.(Γ-{B})) onde ε Γ*.(Γ-{B}) representa a palavra vazia ou o conjunto de todas as palavras que podem ser definidas pelos símbolos do alfabeto Γ menos o símbolo branco.
Informalmente, a configuração será dada pelo estado do autômato finito, pela palavra que aparece na fita e pela posição da cabeça de leitura.
Uma forma de definir a posição da cabeça de leitura é de considerar a palavra que aparece antes da cabeça de leitura e a palavra que se encontra entre a posição da cabeça e o último símbolo não branco na fita.

Definição : uma configuração C' é derivável em variais etapas a partir da configuração C pela maquina M se existe k ≥ 0 e as configurações intermediárias C0, C1, ... , Ck tais que:
. C = C0
. C' = Ck
. Ci |-M Ci+1 para 0 ≤ i < k
Uma palavra é então aceita por uma maquina de
Turing se a execução da maquina leva uma configuração cujo estado é de aceitação.
Definição : A linguagem L(M) aceita por uma maquina de Turing é o conjunto de palavras