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 ₀ , 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}.

• q₀ é 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 ₀ , B, F) com

• Q = {q ₀ , q ₁ , q ₂ , q _f }
• X = {a, b}
• ∑ = {1}
• q ₀ = {q ₀ }
• 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 ₁ implica que o símbolo de gravação é 1, a fita se move para a direita e o próximo estado é q ₁ . Da mesma forma, a transição 1Lq ₂ implica que o símbolo de gravação é 1, a fita se move para a esquerda e o próximo estado é q ₂ .

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)