Máquina Norma e Modelo Formal da Máquina de Turing

Simulações da Máquina Norma

A máquina Norma exemplifica diversas simulações com as seguintes características:

• Operações e Testes: Adição, subtração, multiplicação, divisão e testes sobre números primos.
• Valores Numéricos: Armazenamento e tratamento de diversos tipos, como inteiros ($\mathbb{Z}$) e racionais ($\mathbb{Q}$).
• Dados Estruturados: Acesso, armazenamento e tratamento de arranjos, vetores, pilhas, etc.
• Endereçamento Indireto e Recursão: Desvio para uma instrução determinada pelo conteúdo de um registrador e simulação de mecanismos de recursão.
• Cadeias de Caracteres: Definição e manipulação.

Diversas características de máquinas reais são simuladas usando a máquina Norma, reforçando a evidência de que, de fato, trata-se de uma máquina universal.

Operações de Atribuição a um Registrador

• Zero ou um valor natural.
• Valor de um registrador.
• Número primo.

Operações Matemáticas entre Registradores

• Adição.
• Multiplicação.

Representação de valores:

• Um valor inteiro x pode ser representado como um par ordenado: (s, |x|), onde s é o sinal (positivo= 0, negativo= 1) e |x| é o valor absoluto.
• Representação racional: 0.75 pode ser representado pelos pares (3, 4).

Aplicações da Máquina de Turing

• Reconhecimento de linguagens.
• Processamento de funções.

Classe das Linguagens Recursivas

A classe é composta pelas linguagens para as quais existe pelo menos uma Máquina de Turing que pára para qualquer entrada, aceitando-a ou rejeitando-a.

Assim, uma linguagem L é dita recursiva se existe uma Máquina de Turing M tal que:

• ACEITA(M) = L
• REJEITA(M) = $\Sigma^* - L$
• LOOP(M) = $\emptyset$

Portanto, a classe das linguagens recursivas define a classe de todas as linguagens que:

• Podem ser reconhecidas mecanicamente.
• Para as quais sempre existe um reconhecedor (“compilador”) que sempre pára, para qualquer entrada, reconhecendo ou rejeitando.

Modelo Formal da Máquina de Turing

Modelo formal baseado em:

• Fita infinita (usada para entrada, saída e rascunho).
• Unidade de controle.
• Programa.

Componentes:

• $\Sigma$ = alfabeto de símbolos de entrada.
• Q = conjunto de estados da máquina (finito).
• $\Pi$ = programa ou função de transição (substituído de '2romano' para $\Pi$ para notação padrão).
• $q_0$ = estado inicial da máquina ($q_0 \in Q$).
• F = conjunto de estados finais ($F \subseteq Q$).
• V = alfabeto auxiliar.
• $\beta$ = símbolo especial branco (substituído de 'B' para $\beta$ para clareza).
• ']' = símbolo especial marcador de início da fita.

Notação formal: $M = (\Sigma, Q, \Pi, q_0, F, V, \beta, ])$

Processamento da Máquina de Turing

Consiste na sucessiva aplicação da função programa $\Pi$ a partir:

• Do estado inicial $q_0$.
• Da cabeça posicionada na célula mais à esquerda da fita.

O processamento acontece até atingir uma condição de parada (se ocorrer), pois eventualmente pode ficar em loop infinito.

Ao parar, duas informações estão disponíveis e podem ser usadas como resultado ou saída do processamento:

• Estado da máquina.
• Conteúdo da fita.

Em relação ao estado, a parada do processamento pode ser de duas maneiras:

• Aceitando a entrada.
• Rejeitando a entrada.

Condições de Parada e Resultado