Notas de Estudo — Máquinas de Turing e Modelos Relacionados Flashcards

Front

Algoritmo

Back

Uma sequência finita de instruções simples para realizar uma tarefa. Informalmente descreve como encontrar ou transformar objetos; formalmente requer um modelo de computação para provar propriedades como existência ou não de soluções algorítmicas.

Front

Tese Church‑Turing

Back

Afirma que as definições formais de algoritmo dadas por modelos como a Máquina de Turing e o cálculo λ capturam exatamente a noção informal de computabilidade. Em consequência, qualquer função computável em qualquer modelo razoável é computável por uma Máquina de Turing.

Front

Máquina de Turing

Back

Modelo de computação com uma fita infinita de células, uma cabeça que lê/escreve e um controle finito. Formalmente é dada pela 7‑upla $Q, Σ, Γ, δ, q_0, q_a, q_r$ que descreve estados, alfabetos, e a função de transição.

Front

Fita

Back

Memória unidimensional com infinitas células contendo símbolos de um alfabeto $Γ$ e um símbolo especial em branco $⊔$. A entrada ocupa as primeiras células mais à esquerda e o resto da fita é preenchido com $⊔$.

Front

Cabeça de Leitura

Back

Componente que está sempre posicionada sobre uma célula da fita e pode ler ou escrever um símbolo nessa posição. Pode mover‑se uma posição para a esquerda ou direita (mantendo‑se na primeira posição se tentar ir além).

Front

Função de Transição

Back

Regra que, dado o estado atual e o símbolo lido, determina o novo estado, o símbolo a escrever e o movimento da cabeça. Formalmente: $δ: Q∖\{q_a,q_r\}×Γ→Q×Γ×\{E,D\}$ descrevendo essas alterações até aceitação ou rejeição.

Front

Configuração

Back

Descrição completa do estado atual de uma Máquina de Turing por uma cadeia que representa o conteúdo da fita, a posição da cabeça e o estado atual. Configurações evoluem aplicando‑se regras de transição; configurações com $q_a$ ou $q_r$ são de parada.

Front

MT Multifita

Back

Variante com $k$ fitas, cada uma com sua própria cabeça de leitura/escrita, e função de transição $δ: Q×Γ^k→Q×Γ^k×\{E,D,P\}^k$. Essa variante tem o mesmo poder computacional das MTs de fita única e pode ser simulada por elas.

Front

Equivalência de Variantes

Back

Demonstra‑se que cada variante de Máquina de Turing tem poder computacional equivalente ao modelo original ao construir simulações mútuas. A técnica típica armazena todas as fitas da variante em uma única fita separadas por símbolos especiais e marca posições das cabeças.

Front

Enumerador

Back

Uma MT equipada com uma 'impressora' que, começando com fita em branco, imprime (possivelmente infinitamente) cadeias sobre papel. A linguagem enumerada é o conjunto de cadeias que eventualmente são impressas; linguagens Turing‑reconhecíveis são exatamente as enumeráveis recursivamente.

Front

MT Não‑determinística

Back

Máquina cuja função de transição permite várias escolhas: $δ: Q∖\{q_a,q_r\}×Γ→\mathcal{P}(Q×Γ×\{E,D\})$. Uma entrada é aceita se existe algum ramo de computação que a aceita; toda MT não‑determinística pode ser simulada por uma determinística, enumerando ramos.

Front

Simulação de ND por D

Back

Para simular uma MT não‑determinística uma MT determinística explora todos os ramos de computação de forma sistemática (por exemplo, busca em largura com aprofundamento iterativo). A simulação rastreia escolhas como uma cadeia de índices que representam o caminho na árvore de execução.

Front

Função computável

Back

Uma função $f: Σ^*→Σ^*$ é computável se existe uma MT $M$ que para toda entrada $w$ termina escrevendo exatamente $f(w)$ na fita ao parar. A noção captura transformações efetivas entre cadeias além da simples decisão de linguagens.

Front

Shifting

Back

Operação básica que desloca uniformemente símbolos numa fita para a direita ou esquerda para, por exemplo, prefixar um símbolo. Pode ser implementada por uma MT que percorre a cadeia copiando símbolos e inserindo o símbolo desejado na frente.

Front

Incremento Binário

Back

Algoritmo em MT para computar $w+1$ dado $w$ em representação binária: percorre até o fim, altera o primeiro 0 encontrado para 1 e zera os 1's à direita; se só houver 1's escreve um 1 adicional à esquerda formando um novo bit mais significativo. A MT implementa isso com leituras e escritas locais sobre a fita.

Front

Fecho (T‑reconhecível)

Back

O conjunto das linguagens Turing‑reconhecíveis é fechado sob união, concatenação, estrela e interseção. Construções usam simulações paralelas ou não‑determinísticas para combinar reconhecedores das linguagens originais.

Front

Fecho (Decidível)

Back

O conjunto das linguagens decidíveis é fechado sob união, estrela, interseção e complemento. Para complemento basta trocar estados de aceitação e rejeição num decisor; para as outras operações constroem‑se decisores compostos simulando as máquinas componentes.

Front

A Máquina Registradora

Back

Modelo com vários registradores $R_0,R_1,\dots,R_k$, memória de acesso aleatório e um programa sequencial com um contador de programa. Cada registrador armazena números naturais e o conjunto de instruções inclui leituras/escritas na memória, operações aritméticas e desvios condicionais.

Front

Instruções Básicas

Back

Tipos típicos: transferência de dados entre registrador e memória, carga de constantes, operações aritméticas sobre $R_0$, desvios condicionais e incondicionais, e fim (Halt). Essas instruções formam o programa que o registrador executa passo a passo.

Front

RAM vs Fita

Back

A diferença prática é que máquinas registradoras têm memória de acesso aleatório, permitindo acessar células de memória por endereço diretamente, enquanto MTs usam fita sequencial. Apesar disso, ambos modelos são equivalentes em poder computacional.

Front

Equivalência RM–TM

Back

Teoremas mostram que qualquer linguagem decidível por um Registrador/Máquina RAM também é decidível por uma Máquina de Turing e vice‑versa. A simulação de uma RM por uma MT usa várias fitas para emular registradores, memória e controle; a simulação inversa implementa a fita numa RAM.

Front

Exemplo: Multiplicação

Back

Programa em registradores que multiplica $R_1$ por $R_2$ armazenando o resultado em $R_0$ usa loops e soma sucessiva, testando decrements em $R_2$. O exemplo ilustra como operações aritméticas e desvios condicionais implementam algoritmos aritméticos num modelo RAM.