Imagine um dispositivo extremamente simples: uma fita infinita dividida em células, um cabeçote que lê e escreve símbolos, e um conjunto de regras que determina o comportamento. Parece básico demais para ser relevante? Pois este dispositivo hipotético, concebido há quase 90 anos, é capaz de computar qualquer coisa que os supercomputadores modernos conseguem calcular. Estamos falando da Máquina de Turing.
O que é uma máquina de Turing ?
A Máquina de Turing não é apenas um conceito histórico relegado aos livros de teoria da computação. Ela é a pedra fundamental sobre a qual toda a ciência da computação foi construída. Compreender seu funcionamento é essencial para qualquer pessoa que deseje entender verdadeiramente o que significa “computar” e quais são os limites fundamentais da computação.
Uma Máquina de Turing é um modelo matemático abstrato de computação que manipula símbolos em uma fita de acordo com uma tabela de regras. Formalmente, uma Máquina de Turing é definida como uma 7-tupla:
$$ M = (Q, \Sigma, \Gamma, \delta, q_0, q_{aceite}, q_{rejeite}) $$
Onde:
- Q = conjunto finito de estados
- Σ = alfabeto de entrada
- Γ = alfabeto da fita
- δ = função de transição: Q × Γ → Q × Γ × {L, R}
- q0 = estado inicial (q₀ ∈ Q)
- q_aceite = estado de aceitação (qₐ ∈ Q)
- q_rejeite = estado de rejeição (qᵣ ∈ Q)
O conceito em termos simples
Pense na Máquina de Turing como um leitor de fita cassete muito especial contendo uma fita, um cabeçote, uma estrutura de controle e uma tabela de que definem o comportamento do que a máquina irá fazer.
Dessa maneira, a fita inicia contendo a entrada do programa, e o restante é preenchido com um símbolo especial chamado “branco”. A partir daí o cabeçote pode ler o símbolo na célula atual, escrever um novo símbolo nessa célula, e mover-se uma posição para a esquerda ou direita. Esses movimentos acontecem até que a máquina chegue no estado de aceite ou rejeite.
Além disso, quando o cabeçote faz esses movimentos para esquerda ou direita é necessário guardar o estado da máquina e é aí que atua a estrutura de controle guardando o estado atual da máquina. O que você pode estar se perguntando é: Mas o que determina se o cabeçote vai para esquerda ou direita ? A resposta é simples: As regras de transições ! Essas regras definem tanto o movimento do cabeçote quanto o novo estado após o processamento de alguma regra.
Veja abaixo uma representação iterativa de uma Máquina de Turing capaz de inverter os bits de uma sequência numérica binária.
Representação da Máquina de Turing
Aguardando leitura do cabeçote…
Logo a seguir, podemos ver a tabela de transição dessa representação iterativa que foi demonstrada. A partir dessas regras que podemos inverter uma sequência de números.
Tabela de Transição (Inversor de Bits)
| Estado Atual | Símbolo Lido | Símbolo Escrito | Movimento | Novo Estado |
|---|---|---|---|---|
| q0 | 0 | 1 | Direita (R) | q0 |
| q0 | 1 | 0 | Direita (R) | q0 |
| q0 | B | B | Parar | ACEITE |
Contexto histórico
Em 1928, o matemático David Hilbert propôs o Entscheidungsproblem (Problema da Decisão): seria possível criar um procedimento mecânico que determinasse se qualquer afirmação matemática é verdadeira ou falsa?
Um pouco mais tarde, em 1936, Turing publicou o artigo “On Computable Numbers, with an Application to the Entscheidungsproblem” (Sobre Números Computáveis, com uma Aplicação ao Problema da Decisão). Nesse artigo, Turing abordou este problema de forma revolucionária. Em vez de simplesmente tentar criar tal procedimento, ele primeiro formalizou o que significa “procedimento mecânico” através do conceito da Máquina de Turing.
No artigo, Turing define uma Máquina de Turing Universal, isto é, uma máquina que pode simular qualquer outra Máquina de Turing dando início a ideia de máquina de propósito geral. Isso é o que conhecemos hoje como computadores.
Por que a Máquina de Turing é importante ?
É muito comum olhar para as fórmulas matemáticas e achar que a Máquina de Turing é apenas um exercício de lógica restrito aos laboratórios universitários e artigos científicos. No entanto, ela dita as regras de tudo o que você faz no seu cotidiano digital.
O celular no seu bolso, o notebook que você usa para trabalhar e os servidores do Google são, na sua essência, Máquinas de Turing Universais físicas. Mas a genialidade desse conceito vai muito além do hardware. Na computação, usamos o termo “Turing Completo” para classificar qualquer sistema que consiga simular o comportamento de uma Máquina de Turing. Se um sistema é Turing Completo, ele consegue calcular e resolver qualquer problema computável.
Isso aparece em coisas simples do dia a dia que raramente paramos para pensar que:
- No Excel, as fórmulas de uma planilha formam um sistema Turing Completo. Em teoria, você poderia programar um jogo de videogame inteiro ou um sistema de inteligência artificial usando apenas as células e fórmulas de uma planilha.
- Já no Minecraft os famosos blocos de redstone dentro do jogo permitem criar portas lógicas (AND, OR, NOT). Por causa disso, o Minecraft é Turing Completo. Jogadores já construíram computadores funcionais de 8-bits trabalhando inteiramente dentro do jogo.
Por fim, a Máquina de Turing nos diz o que um computador não pode fazer. Se um problema lógico não pode ser resolvido por uma Máquina de Turing no papel, nem a Apple, nem o Google, nem a NASA conseguirão construir um supercomputador capaz de resolvê-lo. Ela traça a linha exata entre a realidade e a ficção científica.
Entender a Máquina de Turing é entender os limites da própria tecnologia humana.
Traduzindo a teoria para o código
Antes de tudo, precisamos definir como iremos estruturar esse projeto. Ele será feito usando o conceito de programação orientada a objetos e ainda terá uma interface gráfica. Estruturar é importante para melhor entendimento e clareza do código. Abaixo é mostrado como ficará cada classe criada e em qual diretório será criada.
turing_machine/ ├── domain/ │ ├── direction.py │ ├── symbol.py │ ├── alphabet.py │ ├── state.py │ ├── transition.py │ ├── cell_tape.py │ └── turing_machine.py ├── validator/ │ └── turing_machine_validator.py ├── response/ │ ├── turing_machine_processing_response.py │ └── turing_machine_response.py ├── exception/ │ └── turing_machine_exception.py ├── reader/ │ └── turing_machine_reader.py ├── gui/ │ └── turing_machine_gui.py ├── resources/ │ └── entrada/ │ └── exemplo.json ├── saida/ └── main.py
Esta estrutura segue boas práticas de organização de código Python
- domain/: Classes que representam os conceitos da máquina
- validator/: Classes com a lógica de validação
- response/: Classes para estruturar as respostas.
- exception/: Classes com exceções personalizadas
- reader/: Classes com a lógica de leitura de arquivos
- gui/: Classes que criam a interface gráfica
- resources/: Arquivos de configuração.
- saida/: Arquivos de saída gerados
Adiante,apresentamos as classes principais explicando sua funcionalidade dentro do sistema.
Classe Direction
Abaixo é apresentado todas as classes que compõem no modulo domain. Iniciamos apresentando a classe Direction(Direção).
from enum import Enum, auto
class Direction(Enum):
RIGHT = "RIGHT"
LEFT = "LEFT"
@classmethod
def from_string(cls, value: str) -> 'Direction':
try:
return cls[value.upper()]
except KeyError:
valid_values = [d.value for d in cls]
raise ValueError(
f"'{value}' não é uma direção válida. "
f"Use uma das seguintes: {valid_values}"
)
Essa classe representa as direções de movimento do cabeçote. Na Máquina de Turing, o cabeçote pode se mover apenas uma célula por vez, seja para a esquerda (LEFT) ou para a direita (RIGHT). Esta é uma das características fundamentais que torna a máquina simples mas poderosa com apenas esses dois movimentos básicos, ela pode acessar qualquer posição da fita.
Classe Symbol
from dataclasses import dataclass, field
from typing import Optional, Dict, Any
@dataclass
class Symbol:
character: str = ""
def __post_init__(self):
if self.character is None:
self.character = ""
self.character = str(self.character)
@classmethod
def from_dict(cls, data: Dict[str, Any]) -> 'Symbol':
return cls(character=data.get('caracter', ''))
def to_dict(self) -> Dict[str, Any]:
return {'caracter': self.character}
def __eq__(self, other: object) -> bool:
if isinstance(other, Symbol):
return self.character == other.character
if isinstance(other, str):
return self.character == other
return False
def __hash__(self) -> int:
return hash(self.character)
def __str__(self) -> str:
return self.character
Essa classe representa um símbolo que pode aparecer na fita da Máquina de Turing. Os símbolos são os elementos básicos que a máquina manipula. O conjunto de todos os símbolos possíveis forma o “alfabeto da fita” (Γ).
Classe Alphabet
from dataclasses import dataclass
from typing import Dict, Any
@dataclass
class Alphabet:
character: str = ""
@classmethod
def from_dict(cls, data: Dict[str, Any]) -> 'Alphabet':
return cls(character=data.get('caracter', ''))
def to_dict(self) -> Dict[str, Any]:
return {'caracter': self.character}
def __eq__(self, other: object) -> bool:
if isinstance(other, Alphabet):
return self.character == other.character
if isinstance(other, str):
return self.character == other
return False
def __hash__(self) -> int:
return hash(self.character)
Essa classe representa um caractere do alfabeto de entrada da Máquina de Turing. O alfabeto de entrada (Σ) é o conjunto de símbolos que podem aparecer na entrada inicial da máquina
Classe State
from dataclasses import dataclass
from typing import Dict, Any
@dataclass
class State:
name: str = ""
@classmethod
def from_dict(cls, data: Dict[str, Any]) -> 'State':
return cls(name=data.get('nome', ''))
def to_dict(self) -> Dict[str, Any]:
return {'nome': self.name}
def __eq__(self, other: object) -> bool:
if isinstance(other, State):
return self.name == other.name
if isinstance(other, str):
return self.name == other
return False
def __hash__(self) -> int:
return hash(self.name)
def __str__(self) -> str:
return self.name
A classe representa um estado da Máquina de Turing. Estados são fundamentais para o funcionamento da máquina. O conjunto finito de estados (Q) forma a “memória de controle” da máquina. A máquina sempre está em exatamente um estado por vez, e o estado atual, junto com o símbolo lido, determina completamente a próxima ação. Na nossa implementação, um estado é identificado por seu nome, que é uma string arbitrária
Classe Transition
# domain/transition.py
from dataclasses import dataclass
from typing import Dict, Any
from .direction import Direction
@dataclass
class Transition:
origin_state: str = ""
symbol_read: str = ""
destiny_state: str = ""
write_symbol: str = ""
direction: Direction = Direction.RIGHT
@classmethod
def from_dict(cls, data: Dict[str, Any]) -> 'Transition':
direction_str = data.get('direcao', 'RIGHT')
if isinstance(direction_str, Direction):
direction = direction_str
else:
direction = Direction.from_string(direction_str)
return cls(
origin_state=data.get('estadoOrigem', ''),
symbol_read=data.get('leSimbolo', ''),
destiny_state=data.get('estadoDestino', ''),
write_symbol=data.get('escreve', ''),
direction=direction
)
def to_dict(self) -> Dict[str, Any]:
return {
'estadoOrigem': self.origin_state,
'leSimbolo': self.symbol_read,
'estadoDestino': self.destiny_state,
'escreve': self.write_symbol,
'direcao': self.direction.value
}
def matches(self, state: str, symbol: str) -> bool:
return self.origin_state == state and self.symbol_read == symbol
def __str__(self) -> str:
return (
f"δ({self.origin_state}, '{self.symbol_read}') = "
f"({self.destiny_state}, '{self.write_symbol}', {self.direction.value})"
)
Essa classe representa uma transição da Máquina de Turing. Transições são o “coração” da Máquina de Turing. Cada transição define uma regra no formato:
$$ \delta(estado\space atual, símbolo\space lido) = (novo\space estado, símbolo\space escrito, direção) $$
Classe Cell Tape
from dataclasses import dataclass, field
from typing import Optional
from .symbol import Symbol
@dataclass
class CellTape:
symbol: Symbol = field(default_factory=Symbol)
x_axis: int = 0
y_axis: int = 0
width: int = 0
height: int = 0
draw_string_y_axis: int = 0
def get_character(self) -> str:
return self.symbol.character
def set_character(self, character: str) -> None:
self.symbol = Symbol(character=character)
def get_center_x(self) -> int:
return self.x_axis + self.width // 2
def get_center_y(self) -> int:
return self.y_axis + self.height // 2
def contains_point(self, x: int, y: int) -> bool:
return (self.x_axis <= x <= self.x_axis + self.width and
self.y_axis <= y <= self.y_axis + self.height)
def __str__(self) -> str:
return f"[{self.symbol.character}]"
A fita da Máquina de Turing é composta por uma sequência (teoricamente infinita) de células. Cada célula contém exatamente um símbolo e tem uma posição específica. Esta classe também armazena informações de renderização para a interface gráfica, como coordenadas e dimensões. Isso combina dados do modelo com dados de visualização (coordenadas) em uma única classe.
Nota sobre design: Em uma arquitetura mais purista, separaríamos o modelo da visualização (coordenadas). Porém, para este projeto educacional, a combinação simplifica o código da interface gráfica.
Classe Turing Machine
from dataclasses import dataclass, field
from typing import List, Optional, Dict, Any
from .transition import Transition
from .symbol import Symbol
from .alphabet import Alphabet
from .state import State
@dataclass
class TuringMachine:
name: str = ""
transitions: List[Transition] = field(default_factory=list)
symbols: List[Symbol] = field(default_factory=list)
alphabet: List[Alphabet] = field(default_factory=list)
white_symbol: str = ""
initial_state: str = ""
final_states: List[State] = field(default_factory=list)
states: List[State] = field(default_factory=list)
start_marker: Optional[str] = None
@classmethod
def from_dict(cls, data: Dict[str, Any]) -> 'TuringMachine':
return cls(
name=data.get('nome', ''),
transitions=[
Transition.from_dict(t)
for t in data.get('transicoes', [])
],
symbols=[
Symbol.from_dict(s)
for s in data.get('simbolos', [])
],
alphabet=[
Alphabet.from_dict(a)
for a in data.get('alfabeto', [])
],
white_symbol=data.get('simboloBranco', ''),
initial_state=data.get('estadoInicial', ''),
final_states=[
State.from_dict(s)
for s in data.get('estadosFinais', [])
],
states=[
State.from_dict(s)
for s in data.get('estados', [])
],
start_marker=data.get('marcadorInicio')
)
def to_dict(self) -> Dict[str, Any]:
result = {
'nome': self.name,
'transicoes': [t.to_dict() for t in self.transitions],
'simbolos': [s.to_dict() for s in self.symbols],
'alfabeto': [a.to_dict() for a in self.alphabet],
'simboloBranco': self.white_symbol,
'estadoInicial': self.initial_state,
'estadosFinais': [s.to_dict() for s in self.final_states],
'estados': [s.to_dict() for s in self.states]
}
if self.start_marker:
result['marcadorInicio'] = self.start_marker
return result
def is_valid_white_symbol(self) -> bool:
return any(
symbol.character == self.white_symbol
for symbol in self.symbols
)
def is_valid_initial_state(self) -> bool:
return any(
state.name == self.initial_state
for state in self.states
)
def is_valid_final_states(self) -> bool:
return all(
any(state.name == final_state.name for state in self.states)
for final_state in self.final_states
)
def is_valid_transition_origin_state(self, transition: Transition) -> bool:
return any(
state.name == transition.origin_state
for state in self.states
)
def is_valid_transition_destiny_state(self, transition: Transition) -> bool:
return any(
state.name == transition.destiny_state
for state in self.states
)
def is_valid_transition_write_symbol(self, transition: Transition) -> bool:
if transition.write_symbol == self.start_marker:
return True
return any(
symbol.character == transition.write_symbol
for symbol in self.symbols
)
def is_valid_transition_read_symbol(self, transition: Transition) -> bool:
if transition.symbol_read == self.start_marker:
return True
return any(
symbol.character == transition.symbol_read
for symbol in self.symbols
)
def validate_all_transitions(self) -> bool:
return all(
self.is_valid_transition_origin_state(t) and
self.is_valid_transition_destiny_state(t) and
self.is_valid_transition_write_symbol(t) and
self.is_valid_transition_read_symbol(t)
for t in self.transitions
)
def find_transition(
self,
current_state: str,
read_symbol: str
) -> Optional[Transition]:
for transition in self.transitions:
if transition.matches(current_state, read_symbol):
return transition
return None
def is_accepting_state(self, state: str) -> bool:
return any(
final_state.name == state
for final_state in self.final_states
)
def has_final_states(self) -> bool:
return len(self.final_states) > 0
def get_state_names(self) -> List[str]:
return [state.name for state in self.states]
def get_symbol_characters(self) -> List[str]:
return [symbol.character for symbol in self.symbols]
def get_alphabet_characters(self) -> List[str]:
return [a.character for a in self.alphabet]
def __str__(self) -> str:
return (
f"TuringMachine(name='{self.name}', "
f"states={len(self.states)}, "
f"transitions={len(self.transitions)})"
)
def __repr__(self) -> str:
return (
f"TuringMachine(\n"
f" name='{self.name}',\n"
f" states={self.get_state_names()},\n"
f" initial_state='{self.initial_state}',\n"
f" final_states={[s.name for s in self.final_states]},\n"
f" symbols={self.get_symbol_characters()},\n"
f" white_symbol='{self.white_symbol}',\n"
f" transitions_count={len(self.transitions)}\n"
f")"
)
Esta classe é o núcleo da implementação, contendo todos os componentes que definem uma Máquina de Turing. A classe também fornece métodos de validação para garantir que a máquina está bem formada , por exemplo: todos os estados referenciados existem, todos os símbolos são válidos, etc.
Onde está o resto do código ?
Como o objetivo deste artigo é descomplicar a Teoria da Computação, nós mergulhamos fundo apenas em algumas classes do pacote domain, que são o verdadeiro coração matemático da Máquina de Turing.
Para que o sistema fosse robusto e aplicasse boas práticas de Engenharia de Software, eu também desenvolvi pacotes de validação de dados, leitura de arquivos de configuração em JSON , tratamento de exceções customizadas e, claro, a interface gráfica .
Para não transformar este post em um livro infinito de código, eu omiti essas classes estruturais aqui. Mas não se preocupe! O projeto completo, 100% funcional e pronto para você rodar na sua própria máquina, está disponível no meu repositório.
A execução da máquina de turing
Para executarmos a Máquina de Turing, o primeiro passo é inserir no diretório “resources/entrada” a configuração na máquina no formato json. Para esse teste, irei utilizar uma configuração que reconhece a linguagem an bn.
Esse arquivo, estará disponível juntamente com o projeto no GitHub.
O próximo passo é executar no terminal o comando.
python3 main.py
Você notará que uma janela abrirá como essa da imagem abaixo.
Pronto! Nesse momento basta inserir a palavra de entrada e clicar em enviar. A palavra será inserida na fita e depois clique em “Executar tudo” ou “Processar passo” para ir um passo de cada vez. O vídeo abaixo mostra o processamento da cadeia “aaaabbbbb” qual deve ser rejeitada por não ter a mesma quantidade de a’s e b’s.