Máquina de Turing: Conceitos e Computabilidade
Classificado em Computação
Escrito em em 
português com um tamanho de 4,47 KB.
Máquina de Turing
Os componentes da Máquina de Turing são: Fita, Cabeça de Leitura e Gravação, Unidade de Controle, Função de Transição.
Operação da Máquina
Para uma palavra w, aplicar sucessivamente a função programa, a partir de q0 e estando a cabeça de leitura na posição mais à esquerda da fita, até ocorrer uma condição de parada.
Condições de Parada
Estado final: A máquina assume um estado final, a máquina para e a palavra de entrada é aceita.
Função indefinida: A função programa é indefinida para o argumento; a máquina para e a palavra de entrada é rejeitada.
Movimento inválido: O movimento à esquerda quando a cabeça de leitura já está na posição mais à esquerda; a máquina para e a palavra de entrada é rejeitada.
Modelo Formal
Uma Máquina de Turing é uma 8-tupla
M = (A, Q, P, q0, F, V, b, *)
Onde
A: Alfabeto de símbolos de entrada
Q: Conjunto de estados possíveis da máquina
P: Função de Transição
q0: Estado inicial da máquina
F: Conjunto de Estados Finais
V: Alfabeto auxiliar
b: branco
*: início da fita
Computação da Máquina de Turing
(q0, [*aaabbb]) ├
Reconhecimento de Linguagens
L(M) = { w | M ao processar w Є A*, pára em um estado qf Є F }
L(M) U R(M) U Loop(M) = A *
L(M) ∩ R(M) ∩ U Loop(M) = Ø
Uma linguagem aceita por uma Máquina de Turing é dita “Linguagem Enumerável Recursivamente”
As linguagens para as quais existe uma máquina de Turing que sempre pára para aceitar ou rejeitar são chamadas “Linguagens Recursivas”.
Computabilidade de Funções
Problemas Solucionáveis: existe um algoritmo, para uma máquina universal, que soluciona o problema tal que sempre pára para qualquer entrada, com uma resposta afirmativa ou negativa.
Problemas Não-solucionáveis: não existe um algoritmo, para uma máquina universal, que solucione o problema e sempre pare para qualquer entrada.
Problemas Computáveis: existe um algoritmo, para uma máquina universal, que para quando a resposta é afirmativa. Entretanto, o algoritmo pode permanecer em loop infinito quando a resposta deveria ser negativa.
Problemas Não-computáveis: não existe um algoritmo, para uma máquina universal, que solucione o problema parando sempre que a resposta deveria ser afirmativa.
Reconhecimento de Linguagens X Computabilidade
A linguagem associada a um problema é o conjunto de todas as palavras para as quais o problema deve responder afirmativamente.
Se a linguagem associada a um problema é enumerável recursivamente, então o problema é computável.
Os problemas associados a linguagens recursivas são solucionáveis.
Princípio da Redução
Para se classificar problemas de decisão quanto a sua Classe de Computabilidade, basta classificar a classe da linguagem correspondente.
A determinação da classe de uma linguagem pode ser feita com base no conhecimento da classe de outra linguagem a ela relacionada. Pelo teorema da redução, sabe-se que se existe uma redução de uma linguagem L1 para uma linguagem L2, então:
a) Se L2 é recursiva, então L1 é recursiva;
b) Se L2 é enumerável recursivamente, então L1 é enumerável recursivamente.
Obs: O uso da seguinte equivalência lógica: p -> q <-> ~q -> ~p , possibilita outras inferências baseadas nesse mesmo teorema.