Introdução à máquina de Turing
Uma Máquina de Turing é um dispositivo de aceitação que aceita as linguagens (conjunto recursivamente enumerável) geradas por gramáticas do tipo 0. Foi inventado em 1936 por Alan Turing.
Definição
Uma Máquina de Turing (TM) é um modelo matemático que consiste em uma fita de comprimento infinito dividida em células nas quais a entrada é dada. Consiste em uma cabeça que lê a fita de entrada. Um registro de estado armazena o estado da máquina de Turing. Depois de ler um símbolo de entrada, ele é substituído por outro símbolo, seu estado interno é alterado e ele se move de uma célula para a direita ou esquerda. Se a TM atinge o estado final, a string de entrada é aceita, caso contrário, rejeitada.
A TM pode ser formalmente descrita como uma 7-tupla (Q, X, ∑, δ, q 0 , B, F) onde -
Q é um conjunto finito de estados
X é o alfabeto da fita
∑ é o alfabeto de entrada
δé uma função de transição; δ: Q × X → Q × X × {Left_shift, Right_shift}.
q0 é o estado inicial
B é o símbolo em branco
F é o conjunto de estados finais
Comparação com o autômato anterior
A tabela a seguir mostra uma comparação de como uma máquina de Turing difere do Autômato Finito e do Autômato Pushdown.
| Máquina | Estrutura de dados da pilha | Determinístico? |
|---|---|---|
| Autômato Finito | N / D | sim |
| Pushdown Automaton | Último a entrar, primeiro a sair (UEPS) | Não |
| Máquina de Turing | Fita infinita | sim |
Exemplo de máquina de Turing
Máquina de Turing M = (Q, X, ∑, δ, q 0 , B, F) com
- Q = {q 0 , q 1 , q 2 , q f }
- X = {a, b}
- ∑ = {1}
- q 0 = {q 0 }
- B = símbolo em branco
- F = {q f }
δ é dado por -
| Símbolo do alfabeto de fita | Estado Atual 'q 0 ' | Estado Atual 'q 1 ' | Estado Atual 'q 2 ' |
|---|---|---|---|
| uma | 1Rq 1 | 1Lq 0 | 1Lq f |
| b | 1Lq 2 | 1Rq 1 | 1Rq f |
Aqui, a transição 1Rq 1 implica que o símbolo de gravação é 1, a fita se move para a direita e o próximo estado é q 1 . Da mesma forma, a transição 1Lq 2 implica que o símbolo de gravação é 1, a fita se move para a esquerda e o próximo estado é q 2 .
Complexidade de tempo e espaço de uma máquina de Turing
Para uma máquina de Turing, a complexidade do tempo refere-se à medida do número de vezes que a fita se move quando a máquina é inicializada para alguns símbolos de entrada e a complexidade do espaço é o número de células da fita gravada.
Complexidade de tempo, todas as funções razoáveis -
T(n) = O(n log n)
A complexidade do espaço da TM -
S(n) = O(n)