Turmas - 1º Semestre de 2026Uma Máquina de Turing é um modelo computacional composto por uma fita infinita dividida em células, uma cabeça de leitura/escrita e um controle finito. A cada passo, a função de transição, formalizada como δ(q, σ) → (q’, σ’, D), determina o próximo estado q’, o símbolo a ser escrito σ’ e a direção do movimento da cabeça D ∈ {L, R}. Desenvolva uma Máquina de Turing definida sobre o alfabeto Σ = {0, 1, 2, 3, 4, 5, 6, 7} que aplique a operação de negação bit a bit (NOT) a cada dígito de um número octal fornecido como entrada. A entrada será uma sequência contígua de dígitos octais na fita. Após o processamento, a fita deve conter exclusivamente a sequência transformada, sem símbolos auxiliares residuais. A seguir, são apresentados exemplos de entradas e os respectivos resultados esperados.
| Entrada | Saída | Status |
|---|---|---|
| 123 | 654 | aceita |
| 765 | 123 | aceita |
| 2460 | 5317 | aceita |
| ε | indiferente | rejeita |
M = ({0, 1, 2, 3, 4, 5, 6, 7}, {q0, q1, q2, q3}, ∏, q0, {q3}, ∅, β, ⊗)
Ybadoo - Soluções em Software Livre • Copyright 2009/2026 • 