A Arquitetura Fundamental da Computação
Coleção Escola de Lógica Matemática
JOÃO CARLOS MOREIRA
Doutor em Matemática
Universidade Federal de Uberlândia
Copyright©2013-2025 Coleção Escola de Lógica Matemática. Todos os direitos reservados.
Era 1936, e o mundo matemático fervilhava com uma questão fundamental: o que pode ser calculado? David Hilbert havia desafiado a comunidade com seu Entscheidungsproblem — o problema da decisão — perguntando se existiria um procedimento mecânico capaz de determinar a verdade de qualquer afirmação matemática. A resposta veio de um jovem matemático britânico, Alan Turing, cujo artigo revolucionário não apenas resolveu o problema, mas lançou as bases teóricas para toda a computação moderna. Sua criação, a máquina de Turing, tornou-se o modelo abstrato mais importante para entender o que significa computar.
No início do século XX, a matemática atravessava uma crise de fundamentos. Os paradoxos descobertos por Russell e outros abalaram a confiança na consistência dos sistemas matemáticos. Hilbert propôs um programa ambicioso para estabelecer bases sólidas, buscando procedimentos algorítmicos para resolver questões matemáticas. O conceito de "algoritmo" ainda não tinha definição precisa — diferentes matemáticos trabalhavam com noções intuitivas do que seria um processo mecânico de cálculo.
Turing abordou o problema de forma única. Em vez de tentar definir abstratamente o que seria computável, ele imaginou um ser humano executando cálculos com papel e lápis. Observou que tal processo poderia ser decomposto em operações elementares: ler um símbolo, escrever outro, mover-se para uma nova posição, mudar de estado mental. Essa observação genial levou à concepção de uma máquina abstrata capaz de simular qualquer processo de cálculo humano.
Em "On Computable Numbers, with an Application to the Entscheidungsproblem", Turing não apenas definiu sua máquina abstrata, mas demonstrou resultados surpreendentes. Provou que existem problemas matemáticos bem definidos que nenhuma máquina pode resolver — estabelecendo limites fundamentais para a computação. Mais impressionante ainda, mostrou que uma única máquina universal poderia simular qualquer outra máquina de Turing, antecipando o conceito de computador programável décadas antes de sua realização prática.
Simultaneamente, outros matemáticos atacavam o mesmo problema por diferentes ângulos. Alonzo Church desenvolveu o cálculo lambda, um sistema formal baseado em funções. Emil Post criou sistemas de produção. Kurt Gödel e Jacques Herbrand trabalharam com funções recursivas. Surpreendentemente, todos esses modelos revelaram-se equivalentes em poder computacional, sugerindo que capturavam algo fundamental sobre a natureza da computação.
A resposta ao Entscheidungsproblem foi negativa — não existe algoritmo geral para decidir verdades matemáticas. Este resultado, junto com os teoremas da incompletude de Gödel, estabeleceu limites fundamentais ao conhecimento matemático formal. Paradoxalmente, ao mostrar o que não poderia ser feito, Turing iluminou o que poderia, criando um framework para entender e construir máquinas computacionais.
Durante a Segunda Guerra Mundial, Turing aplicou suas ideias teóricas ao problema prático de quebrar códigos alemães em Bletchley Park. Após a guerra, participou do desenvolvimento dos primeiros computadores eletrônicos britânicos. Sua visão de máquinas universais programáveis guiou o design desses primeiros sistemas, demonstrando que a teoria abstrata das máquinas de Turing tinha profundas implicações práticas.
As máquinas de Turing permanecem centrais na ciência da computação moderna. Todo curso de teoria da computação as estuda. Linguagens de programação são projetadas para serem Turing-completas. A complexidade de algoritmos é medida em termos de recursos necessários por máquinas de Turing. Questões fundamentais como P versus NP são formuladas neste framework. O modelo simples e elegante de Turing continua sendo nossa melhor ferramenta para entender a natureza da computação.
Turing não se limitou a criar um modelo matemático. Ele vislumbrou um futuro onde máquinas pensariam, aprenderiam e talvez até conscientizariam. Seu teste de Turing para inteligência artificial, proposto em 1950, ainda provoca debates. Suas ideias sobre morfogênese anteciparam a biologia computacional. Sua vida e trabalho continuam inspirando gerações de cientistas, matemáticos e filósofos.
A jornada que começou com uma questão abstrata sobre decidibilidade matemática levou à criação do modelo fundamental que sustenta toda a computação moderna. As máquinas de Turing, em sua simplicidade elegante, capturam a essência do que significa computar, estabelecendo tanto as possibilidades quanto os limites do processamento algorítmico de informação. Nos próximos capítulos, exploraremos em detalhes este modelo fascinante, descobrindo como máquinas tão simples podem realizar qualquer computação imaginável.
Imagine uma máquina infinitamente simples, mas infinitamente poderosa. Uma fita sem fim, um cabeçote que lê e escreve, um conjunto finito de estados — estes elementos básicos formam a máquina de Turing, capaz de executar qualquer algoritmo concebível. Como um pianista que com apenas 88 teclas pode tocar infinitas melodias, a máquina de Turing, com seus componentes elementares, pode realizar qualquer computação. Neste capítulo, mergulharemos na estrutura matemática precisa deste modelo, descobrindo como a simplicidade gera universalidade.
Uma máquina de Turing M é formalmente definida como uma 7-tupla M = (Q, Σ, Γ, δ, q₀, qaceita, qrejeita), onde cada componente tem um papel específico e essencial. Q representa o conjunto finito de estados internos da máquina, Σ é o alfabeto de entrada, Γ é o alfabeto da fita (que inclui Σ e o símbolo branco), δ é a função de transição que governa o comportamento, q₀ é o estado inicial, e qaceita e qrejeita são os estados finais de aceitação e rejeição.
O coração da máquina de Turing é sua função de transição δ. Esta função determina completamente o comportamento da máquina: dado o estado atual e o símbolo lido, ela especifica o novo estado, o símbolo a escrever e a direção do movimento. Por exemplo, δ(q₁, a) = (q₂, b, R) significa: "estando no estado q₁ e lendo 'a', mude para o estado q₂, escreva 'b' e mova-se para a direita". Esta simplicidade esconde um poder computacional ilimitado.
Uma configuração da máquina captura completamente seu estado em um momento: a sequência de símbolos na fita, a posição do cabeçote e o estado atual. Representamos isso como αqβ, onde α é o conteúdo à esquerda do cabeçote, q é o estado atual, e β começa com o símbolo sob o cabeçote. Uma computação é uma sequência de configurações, cada uma obtida da anterior aplicando a função de transição.
A linguagem L(M) reconhecida por uma máquina de Turing M é o conjunto de todas as strings que M aceita. Uma string w é aceita se, começando na configuração inicial q₀w, a máquina eventualmente alcança o estado qaceita. Esta definição conecta máquinas de Turing com teoria de linguagens formais, estabelecendo uma hierarquia de classes de linguagens baseada no poder computacional necessário para reconhecê-las.
A máquina de Turing padrão é determinística — cada configuração tem no máximo uma sucessora. Máquinas não-determinísticas permitem múltiplas transições possíveis de cada configuração, explorando todos os caminhos em paralelo conceitual. Surpreendentemente, o não-determinismo não aumenta o poder computacional — toda máquina não-determinística pode ser simulada por uma determinística, embora possivelmente com grande aumento no tempo de execução.
Para processar objetos matemáticos complexos, precisamos codificá-los como strings. Números naturais podem ser representados em unário (n representado por 1ⁿ) ou binário. Pares ordenados usam delimitadores especiais. Grafos são codificados como listas de adjacência. Até mesmo máquinas de Turing podem ser codificadas como strings, permitindo que máquinas processem descrições de outras máquinas — a base para resultados profundos sobre computabilidade.
Diferentes autores usam variações do modelo básico. Alguns permitem que a fita seja infinita em ambas as direções. Outros incluem múltiplas fitas ou cabeçotes. Alguns usam apenas movimento para a direita com capacidade de marcar células. Todas essas variações são equivalentes em poder computacional — qualquer uma pode simular as outras com no máximo overhead polinomial. Esta robustez sugere que o modelo captura algo fundamental sobre computação.
O modelo de Turing possui propriedades matemáticas elegantes. O conjunto de todas as máquinas de Turing é enumerável — podemos listar todas elas. Mas o conjunto de todas as linguagens sobre um alfabeto é não-enumerável. Logo, existem linguagens que nenhuma máquina de Turing pode reconhecer. Esta discrepância fundamental leva a resultados profundos sobre os limites da computação.
O modelo matemático de Turing, em sua elegante simplicidade, captura a essência da computação. Cada componente — estados, alfabetos, transições — desempenha um papel crucial, e juntos formam um sistema de poder ilimitado. Esta formalização precisa permite não apenas construir máquinas para tarefas específicas, mas também provar teoremas fundamentais sobre o que pode e não pode ser computado. Com esta base sólida estabelecida, estamos prontos para examinar em detalhes cada componente individual da máquina de Turing.
Como um relojoeiro que desmonta um mecanismo para revelar cada engrenagem e mola, vamos agora dissecar a máquina de Turing em seus componentes fundamentais. Cada peça, por mais simples que pareça, desempenha um papel vital no funcionamento do todo. A beleza desta máquina está justamente em como elementos tão básicos — uma fita, um cabeçote, alguns estados — combinam-se para criar um dispositivo de poder computacional ilimitado. Exploraremos cada componente em profundidade, entendendo não apenas o que são, mas por que são necessários e suficientes.
A fita é o componente mais distintivo da máquina de Turing — uma sequência infinita de células, cada uma capaz de armazenar um símbolo. Inicialmente, apenas um número finito de células contém símbolos da entrada; as demais contêm o símbolo branco (□). Esta infinitude é crucial: garante que nunca faltará espaço para computações, por mais complexas que sejam. A fita serve simultaneamente como dispositivo de entrada, memória de trabalho e saída.
O cabeçote é o ponto de interação entre a máquina e sua memória. Em cada momento, ele está posicionado sobre exatamente uma célula da fita, podendo ler seu conteúdo, escrever um novo símbolo e mover-se uma célula para a esquerda ou direita. Esta simplicidade de operação — ler, escrever, mover — é suficiente para realizar qualquer manipulação de dados imaginável. O cabeçote é como o dedo de um leitor seguindo as linhas de um texto infinito, podendo também fazer anotações.
Os estados representam a "memória interna" finita da máquina. Como diferentes modos de operação ou fases de um processo, cada estado determina como a máquina reagirá ao símbolo lido. O número de estados é sempre finito, refletindo a ideia de que qualquer procedimento algorítmico pode ser decomposto em um número finito de passos distintos. Estados especiais marcam o início da computação e seus possíveis fins — aceitação ou rejeição.
O alfabeto de entrada Σ define os símbolos válidos que podem aparecer na entrada da máquina. Tipicamente finito e pequeno — frequentemente apenas {0, 1} — este alfabeto é suficiente para codificar qualquer informação. A escolha do alfabeto é uma questão de conveniência; alfabetos maiores podem simplificar o design mas não aumentam o poder computacional. É como escolher entre escrever em decimal ou binário — a expressividade é a mesma.
O alfabeto da fita Γ é um superconjunto do alfabeto de entrada, incluindo adicionalmente o símbolo branco e possivelmente outros símbolos auxiliares. Estes símbolos extras servem como "memória de trabalho", permitindo que a máquina marque posições, armazene resultados intermediários ou sinalize condições especiais. Como post-its em um documento, esses símbolos auxiliares facilitam computações complexas.
Embora não seja um componente físico, a tabela de transições é o "programa" da máquina. Ela especifica completamente o comportamento: para cada combinação de estado atual e símbolo lido, determina o próximo estado, símbolo a escrever e direção de movimento. Esta tabela pode ser visualizada como uma matriz, onde linhas representam estados e colunas representam símbolos, com cada célula contendo uma tripla (novo estado, novo símbolo, direção).
A magia acontece quando todos os componentes trabalham em harmonia. O cabeçote lê um símbolo da fita; este símbolo, combinado com o estado atual, consulta a tabela de transições; a transição determina o novo símbolo a escrever, o movimento do cabeçote e o próximo estado; o ciclo se repete. Esta dança sincronizada continua até alcançar um estado de parada ou entrar em loop infinito.
Cada componente tem limitações deliberadas que, paradoxalmente, contribuem para o poder do modelo. A fita é infinita mas o acesso é sequencial. Os estados são finitos mas podem controlar processamento infinito. O alfabeto é limitado mas pode codificar qualquer informação. O cabeçote move-se apenas uma célula por vez mas pode eventualmente alcançar qualquer posição. Estas restrições tornam o modelo simples de analisar mantendo poder computacional completo.
Os componentes da máquina de Turing formam um sistema minimalista de elegância matemática. Cada elemento é necessário — remova qualquer um e perde-se o poder computacional. Juntos, são suficientes — nada mais é necessário para computação universal. Esta economia de design não é acidental, mas reflete insights profundos sobre a natureza da computação. Compreender cada componente individualmente prepara-nos para apreciar sua orquestração conjunta, que exploraremos no próximo capítulo sobre o funcionamento e as transições da máquina.
Observar uma máquina de Turing em operação é como assistir a uma dança meticulosamente coreografada, onde cada movimento segue regras precisas e inevitáveis. O cabeçote desliza sobre a fita, lendo, escrevendo, movendo-se em um balé computacional que pode durar instantes ou eternidade. Neste capítulo, acompanharemos passo a passo o funcionamento de uma máquina de Turing, desvendando a mecânica das transições e compreendendo como movimentos tão simples podem resolver problemas de complexidade arbitrária.
Cada passo computacional de uma máquina de Turing segue o mesmo ritual invariável. O cabeçote observa o símbolo na célula atual e consulta seu estado interno. Esta dupla (estado, símbolo) é a chave que desbloqueia a próxima ação através da função de transição. A máquina então executa três ações atomicamente: escreve um novo símbolo (que pode ser o mesmo), move o cabeçote uma posição, e transita para um novo estado. Este ciclo simples, repetido milhares ou milhões de vezes, realiza computações de complexidade ilimitada.
Uma configuração instantânea captura completamente o estado global da máquina em um momento específico. Inclui o conteúdo completo da fita (omitindo brancos infinitos), a posição do cabeçote e o estado atual. Representamos configurações como strings da forma αqβ, onde α representa o conteúdo à esquerda do cabeçote, q é o estado atual, e β começa com o símbolo sob o cabeçote. Esta notação compacta permite rastrear precisamente a evolução da computação.
Uma computação é uma sequência de configurações, cada uma derivada da anterior por uma aplicação da função de transição. Usamos o símbolo ⊢ para denotar "deriva em um passo" e ⊢* para "deriva em zero ou mais passos". Por exemplo, se δ(q₁, 0) = (q₂, 1, R), então q₁01 ⊢ 1q₂1. Uma computação completa é uma sequência maximal — que termina em estado de parada ou continua infinitamente.
O movimento do cabeçote, limitado a uma célula por vez, pode parecer restritivo, mas é suficiente para qualquer navegação necessária. Movimentos para a esquerda (L) e direita (R) permitem varreduras da fita, busca de padrões, e transporte de informação entre posições distantes. Algumas máquinas fazem múltiplas passagens sobre os dados, outras organizam a fita em "trilhas" conceituais. A disciplina do movimento unitário simplifica a análise sem limitar o poder.
Os estados funcionam como a memória de controle finita da máquina, determinando seu "modo" de operação. Máquinas complexas organizam estados em grupos funcionais: estados de busca, estados de cópia, estados de verificação. A transição entre grupos marca mudanças de fase na computação. Como um programa com múltiplas sub-rotinas, cada grupo de estados realiza uma tarefa específica, passando controle adiante quando completa.
Uma computação termina quando alcança um estado sem transição definida (qaceita ou qrejeita) ou quando a transição leva a um desses estados. Nem toda computação termina — a máquina pode entrar em loop infinito, repetindo configurações ou gerando configurações sempre novas. Detectar se uma máquina terminará para uma entrada específica é o famoso problema da parada, provadamente indecidível. Esta indecidibilidade é uma característica fundamental, não uma limitação técnica.
Programar máquinas de Turing requer técnicas especializadas. Marcação de células processadas evita reprocessamento. Símbolos auxiliares servem como flags e contadores. Estados codificam informação sobre o que foi visto. Shuttling entre extremos da entrada transporta informação. Estas técnicas, desenvolvidas ao longo de décadas, formam um repertório de padrões reutilizáveis para construir máquinas complexas.
Simular manualmente uma máquina de Turing é exercício valioso para compreender seu funcionamento. Começando com a configuração inicial, aplicamos repetidamente a função de transição, registrando cada configuração. Tabelas de rastreamento mostram a evolução passo a passo. Para máquinas complexas, simuladores computacionais permitem explorar comportamentos em larga escala, visualizando padrões que emergem de regras simples.
Embora máquinas de Turing não sejam projetadas para eficiência prática, podemos otimizar seu desempenho teórico. Reduzir o número de estados minimiza a descrição. Diminuir passes sobre a entrada acelera a computação. Usar alfabetos maiores pode simplificar a lógica. Trade-offs existem: menos estados podem requerer mais tempo, alfabetos menores podem necessitar mais estados. Estas otimizações iluminam relações entre recursos computacionais.
O funcionamento de uma máquina de Turing revela a essência da computação mecânica: repetição incansável de passos simples seguindo regras fixas. Cada transição é trivial, mas sua composição gera comportamentos de complexidade ilimitada. Como gotas d'água esculpindo cânions, as transições simples da máquina de Turing podem resolver qualquer problema computável. Esta compreensão profunda do funcionamento prepara-nos para construir e analisar máquinas específicas, que exploraremos através de exemplos concretos no próximo capítulo.
Ver uma máquina de Turing em ação vale mais que mil descrições abstratas. Como um mecânico que aprende desmontando motores reais, vamos agora construir e executar máquinas de Turing concretas, desde as mais simples até algumas surpreendentemente sofisticadas. Cada exemplo iluminará diferentes aspectos do modelo, mostrando como combinar os componentes básicos para resolver problemas específicos. Prepare-se para testemunhar a dança hipnótica dos símbolos na fita enquanto nossas máquinas ganham vida.
Começemos com uma máquina simples que inverte todos os bits de uma string binária. Esta máquina M₁ tem apenas dois estados além dos de parada: q₀ (inicial) e q₁ (processamento). A estratégia é direta: percorrer a entrada da esquerda para a direita, trocando cada 0 por 1 e vice-versa, parando ao encontrar o primeiro branco.
Uma máquina mais complexa verifica se uma string binária é palíndromo. A estratégia: marcar o primeiro símbolo, encontrar o último, compará-los, marcá-los como processados, e repetir com os símbolos internos. Se todos correspondem, aceita; se algum par difere, rejeita. Esta máquina demonstra como usar estados para "lembrar" informação e símbolos auxiliares para marcar progresso.
Construir uma máquina que soma dois números binários demonstra processamento aritmético. Os números são separados por # na fita. A máquina simula o algoritmo de soma bit a bit com carry, escrevendo o resultado em uma área separada. Estados diferentes codificam se há carry (0 ou 1) do bit anterior. Este exemplo mostra como simular operações aritméticas familiares.
Uma máquina útil que duplica sua entrada, produzindo w#w para entrada w. O algoritmo: para cada símbolo da entrada, marcá-lo temporariamente, copiá-lo após o delimitador #, depois restaurar o símbolo original. Repetir até processar toda a entrada. Esta máquina ilustra o padrão de "shuttle" — movimento repetido entre duas regiões da fita para transferir informação.
O ápice da programação de máquinas de Turing: uma máquina U que simula qualquer outra máquina M dada sua descrição. A entrada é ⟨M⟩#w, onde ⟨M⟩ codifica a tabela de transições de M e w é a entrada para M. U mantém o estado atual de M e a posição do cabeçote, consultando a descrição codificada para determinar cada transição. Embora complexa, U demonstra que uma única máquina pode ser programável — o conceito fundamental do computador moderno.
Para demonstrar um algoritmo diferente, construamos uma máquina que multiplica dois números em notação unária. A entrada "111#11" representa 3 × 2. A máquina implementa multiplicação como soma repetida: para cada 1 do segundo número, adiciona uma cópia do primeiro número ao resultado. Este exemplo mostra como operações complexas se decompõem em operações simples repetidas.
Uma máquina prática que verifica se uma expressão tem parênteses balanceados. Para cada '(' encontrado, marca com X; para cada ')', busca o '(' mais próximo não-marcado e marca ambos. Se todos se correspondem, aceita; caso contrário, rejeita. Este exemplo demonstra como máquinas de Turing podem processar estruturas aninhadas, fundamentais em linguagens de programação.
Máquinas também podem gerar, não apenas reconhecer. Construamos uma que gera os primeiros n números da sequência de Fibonacci em binário. Começando com entrada n em unário, a máquina mantém dois números anteriores, soma-os para obter o próximo, e repete. Este exemplo mostra como máquinas de Turing podem implementar algoritmos iterativos complexos.
Para demonstrar hierarquia computacional, criemos uma máquina que simula qualquer autômato finito determinístico (AFD). A entrada codifica o AFD e uma string. A máquina mantém o estado atual do AFD e, para cada símbolo da string, consulta a função de transição codificada. Este exemplo mostra como modelos mais simples são casos especiais de máquinas de Turing.
Estes exemplos revelam a versatilidade das máquinas de Turing. Desde operações simples como inversão de bits até simulação de outras máquinas, o mesmo modelo básico acomoda toda a gama de computações. Cada exemplo ensina técnicas valiosas: uso de estados para memória, símbolos auxiliares para marcação, movimento shuttle para transferência de dados. Mais importante, eles demonstram que a aparente simplicidade das máquinas de Turing esconde poder computacional ilimitado. Com esta experiência prática, estamos prontos para explorar as variantes e extensões do modelo básico.
Como músicos que experimentam variações sobre um tema clássico, pesquisadores exploraram inúmeras modificações do modelo original de Turing. Múltiplas fitas, múltiplos cabeçotes, fitas bidimensionais, não-determinismo — cada variante oferece vantagens práticas ou insights teóricos. Surpreendentemente, quase todas estas extensões aparentemente poderosas não aumentam o poder computacional fundamental. Neste capítulo, exploraremos estas variantes, compreendendo como cada uma se relaciona com o modelo original e o que suas equivalências nos ensinam sobre a natureza da computação.
Uma extensão natural é permitir k fitas independentes, cada uma com seu próprio cabeçote. A máquina lê simultaneamente um símbolo de cada fita e, baseada nestes k símbolos e seu estado, escreve novos símbolos e move cada cabeçote independentemente. Esta arquitetura simplifica dramaticamente muitos algoritmos — por exemplo, copiar dados torna-se trivial com duas fitas. Mas o poder adicional é ilusório: qualquer máquina de k fitas pode ser simulada por uma máquina de fita única, embora com desaceleração quadrática.
Para simular k fitas em uma única, intercalamos suas células. A célula i da fita j é mapeada para a célula k·i+j da fita única. Marcadores especiais indicam as posições dos k cabeçotes virtuais. Cada transição da máquina multi-fita requer múltiplas varreduras na simulação: localizar cabeçotes, ler símbolos, atualizar, reposicionar. Esta construção prova que múltiplas fitas não aumentam o poder computacional, apenas a eficiência.
Máquinas não-determinísticas podem ter múltiplas transições válidas para o mesmo par (estado, símbolo). Conceitualmente, a máquina explora todos os caminhos possíveis em paralelo, aceitando se algum caminho leva à aceitação. Praticamente, visualizamos a computação como uma árvore em vez de uma sequência linear. O não-determinismo parece adicionar poder imenso, mas o teorema de Rabin-Scott mostra que toda máquina não-determinística tem uma equivalente determinística.
O modelo original tem fita infinita apenas à direita. Variantes com fita infinita em ambas as direções parecem mais naturais para certas aplicações. Células são indexadas por todos os inteiros, não apenas naturais. Surpreendentemente, isto não adiciona poder: podemos simular fita bi-infinita em fita semi-infinita "dobrando" — células pares representam posições positivas, ímpares representam negativas. A equivalência reforça a robustez do modelo.
No extremo minimalista, consideremos máquinas com alfabeto de apenas um símbolo (além do branco). Parece impossível computar algo significativo, mas estas máquinas podem simular máquinas com alfabetos maiores! A ideia: codificar cada símbolo como um bloco de 1s de comprimento diferente, separados por brancos. A simulação é tremendamente ineficiente, mas demonstra que até o alfabeto mínimo é universal.
Estender a fita para duas ou mais dimensões cria um "papel quadriculado" infinito onde o cabeçote pode mover-se em múltiplas direções. Aplicações incluem processamento de imagens e simulação de autômatos celulares. Novamente, não há ganho em poder computacional — podemos linearizar o espaço multidimensional usando técnicas de numeração diagonal. Mas a naturalidade da representação para certos problemas é inegável.
Máquinas com oráculo têm acesso a uma "caixa preta" que responde instantaneamente perguntas sobre membros de um conjunto específico. Por exemplo, um oráculo para o problema da parada poderia dizer se qualquer máquina para em qualquer entrada. Estas máquinas são genuinamente mais poderosas — podem resolver problemas indecidíveis para máquinas ordinárias. Oráculos criam hierarquias de poder computacional, fundamentais em teoria da complexidade.
Máquinas probabilísticas podem "jogar moedas" — ter transições que escolhem aleatoriamente entre opções com probabilidades específicas. Aceita se a probabilidade de aceitar excede um limiar. Estas máquinas não são mais poderosas em termos de computabilidade, mas podem ser mais eficientes. Classes como BPP (tempo polinomial probabilístico com erro limitado) capturam este poder. A aleatoriedade é recurso computacional valioso, embora não fundamental.
Máquinas de Turing quânticas utilizam superposição e emaranhamento quântico. Estados são superposições de configurações clássicas, evoluindo unitariamente. Medição colapsa para resultado clássico. Acredita-se que não são mais poderosas em computabilidade, mas podem ser exponencialmente mais rápidas para certos problemas (fatoração, busca). Representam a fronteira entre física e computação.
A proliferação de variantes das máquinas de Turing revela uma verdade profunda: o modelo original capturou algo fundamental sobre computação que transcende detalhes de implementação. Múltiplas fitas, não-determinismo, múltiplas dimensões — todas estas aparentes extensões não aumentam o poder computacional básico. Esta robustez não é acidente, mas reflexo de que Turing identificou a essência da computação mecânica. Apenas adições genuinamente não-mecânicas, como oráculos ou talvez computação quântica em larga escala, podem transcender estes limites. Esta universalidade e robustez formam a base para a teoria da computabilidade, nosso próximo tópico.
Nem todo problema tem solução algorítmica. Esta revelação, central para a ciência da computação, emergiu diretamente do estudo das máquinas de Turing. Como cartógrafos mapeando os limites do mundo computável, descobrimos fronteiras intransponíveis — problemas que nenhuma máquina, por mais engenhosa, pode resolver. Neste capítulo, exploraremos a paisagem da computabilidade, distinguindo entre o que pode ser computado, o que pode ser decidido, e o que permanece para sempre além do alcance algorítmico.
Em teoria da computação, problemas são formalizados como linguagens — conjuntos de strings. O problema "n é primo?" corresponde à linguagem PRIMOS = {2, 3, 5, 7, 11, ...} em representação binária. Resolver um problema significa determinar pertinência à linguagem correspondente. Esta abstração unifica problemas diversos sob um framework comum, permitindo classificação precisa baseada em dificuldade computacional.
Uma linguagem é decidível (ou recursiva) se existe uma máquina de Turing que sempre para, aceitando strings na linguagem e rejeitando as demais. Estas são as linguagens "bem-comportadas" — temos algoritmos que sempre fornecem resposta definitiva. Exemplos incluem linguagens regulares, linguagens livres de contexto determinísticas, e muitos problemas práticos como verificação de primalidade ou ordenação.
Uma linguagem é reconhecível (ou recursivamente enumerável) se existe uma máquina que aceita exatamente as strings na linguagem, mas pode não parar para strings fora dela. São "semi-decidíveis" — podemos confirmar pertinência mas não necessariamente não-pertinência. A classe das linguagens reconhecíveis propriamente contém as decidíveis, revelando uma assimetria fundamental na computação.
O problema da parada pergunta: dada uma máquina M e entrada w, M para em w? Este é o problema indecidível mais famoso. A prova usa diagonalização: assumindo que existe decisor H para o problema, construímos máquina D que para em sua própria descrição se e somente se não para — contradição! A indecidibilidade do problema da parada tem consequências profundas para verificação de programas.
Redução é técnica fundamental para provar indecidibilidade. Se problema A reduz a problema B (A ≤ B), então B é pelo menos tão difícil quanto A. Se A é indecidível e A ≤ B, então B é indecidível. Construímos catálogo de problemas indecidíveis reduzindo do problema da parada: verificar se máquina aceita string vazia, se duas máquinas são equivalentes, se máquina aceita infinitas strings.
O teorema de Rice fornece caracterização devastadora: toda propriedade não-trivial de linguagens reconhecíveis é indecidível. Uma propriedade é não-trivial se algumas máquinas a satisfazem e outras não. Isto significa que essencialmente qualquer pergunta interessante sobre o comportamento de programas é indecidível! Não podemos algoritmicamente verificar correção, eficiência, ou quase qualquer propriedade semântica.
Problemas indecidíveis formam hierarquia infinita de dificuldade crescente. Nível Σ₁: reconhecíveis (∃ quantificador). Nível Π₁: co-reconhecíveis (∀ quantificador). Nível Σ₂: reconhecíveis com oráculo para parada. Cada nível contém problemas não nos níveis anteriores. Esta hierarquia revela estrutura rica mesmo entre problemas insolúveis.
Nem todos os problemas indecidíveis são igualmente difíceis. Graus de Turing classificam problemas por redutibilidade mútua. O grau 0 contém problemas decidíveis. O grau 0' (zero-primo) contém o problema da parada e equivalentes. Existem infinitos graus, formando estrutura parcialmente ordenada de complexidade incomparável. Alguns problemas são literalmente incomparáveis — nenhum reduz ao outro.
Embora a indecidibilidade pareça abstrata, tem implicações práticas profundas. Compiladores não podem otimizar perfeitamente. Verificadores não podem garantir ausência de bugs. Antivírus não podem detectar todos os malwares. Estas limitações não são tecnológicas mas fundamentais. Entender o que não pode ser feito é tão importante quanto saber o que pode, guiando expectativas realistas e abordagens pragmáticas.
A teoria da computabilidade revela os limites fundamentais do que pode ser alcançado através de processos algorítmicos. Como exploradores que descobriram os limites do mundo navegável, identificamos fronteiras intransponíveis no território computacional. Problemas indecidíveis não são meramente difíceis — são impossíveis de resolver algoritmicamente em geral. Esta compreensão profunda dos limites da computação não diminui o poder das máquinas de Turing; pelo contrário, estabelece precisamente seu domínio e fundamenta expectativas realistas sobre o que a computação pode alcançar. Com esta perspectiva sobre os limites absolutos, estamos prontos para explorar a tese que conecta estes modelos teóricos com nossa intuição sobre computação.
No coração da ciência da computação pulsa uma afirmação extraordinária que não pode ser provada matematicamente, apenas evidenciada: todo processo computacional intuitivo pode ser realizado por uma máquina de Turing. Esta tese, formulada independentemente por Church e Turing, forma a ponte entre nossa noção informal de algoritmo e sua formalização matemática. Como uma constituição não-escrita da computação, ela fundamenta toda nossa compreensão do que significa calcular. Neste capítulo, exploraremos esta tese profunda, suas evidências, implicações e os debates filosóficos que continua a provocar.
A tese de Church-Turing afirma que a classe de funções computáveis intuitivamente coincide com a classe de funções computáveis por máquinas de Turing. Não é teorema — não pode ser provada porque "computável intuitivamente" não tem definição matemática precisa. É uma proposta de definição, uma identificação entre conceito informal e formalização. Sua aceitação universal deriva de evidências convergentes esmagadoras de múltiplas direções independentes.
A evidência mais convincente vem da equivalência de modelos desenvolvidos independentemente. Máquinas de Turing, cálculo lambda, funções recursivas, algoritmos de Markov, máquinas de Post — todos definem exatamente a mesma classe de funções. Como exploradores chegando ao mesmo pico por rotas diferentes, estes matemáticos descobriram o mesmo conceito fundamental. Esta convergência sugere fortemente que capturaram algo essencial sobre computação.
Décadas de experiência prática reforçam a tese. Todo algoritmo já concebido pode ser implementado em uma máquina de Turing. Toda linguagem de programação desenvolvida é Turing-completa ou deliberadamente restrita. Nenhum modelo de computação fisicamente realizável transcendeu os limites de Turing. Esta evidência empírica acumulada, embora não constitua prova, fornece suporte avassalador.
A tese tem consequências filosóficas profundas. Se verdadeira, estabelece limites fundamentais ao conhecimento algorítmico. Sugere que a mente humana, se puramente computacional, não pode transcender estes limites. Questões sobre consciência, livre-arbítrio e criatividade entrelaçam-se com a validade da tese. Alguns argumentam que a mente transcende computação Turing; outros que isto apenas revela nossa ignorância sobre como o cérebro computa.
Propostas de hipercomputação desafiam a tese. Máquinas de Turing com tempo infinito, computação em buracos negros, computadores analógicos ideais — modelos teóricos que transcenderiam Turing. Mas nenhum é fisicamente realizável com tecnologia conhecida. Computação quântica, embora potencialmente mais eficiente, aparentemente não ultrapassa a barreira da computabilidade. A tese resiste, adaptando-se a novos paradigmas.
Uma versão mais forte propõe que todo processo físico pode ser simulado por máquina de Turing, possivelmente probabilística. Isto conecta computação com física fundamental. Se verdadeira, o universo é essencialmente computacional. Simulações quânticas eficientes requerem computadores quânticos, mas ainda dentro do framework de Turing estendido. Esta versão transforma a tese em princípio físico fundamental.
A tese fundamenta a matemática construtiva e teoria da prova. Se aceita, estabelece limites ao que pode ser provado algoritmicamente. Os teoremas de incompletude de Gödel ganham interpretação computacional: existem verdades matemáticas não-computáveis. Programas de formalização matemática operam dentro dos limites de Turing. A tese molda nossa compreensão da natureza da verdade e prova matemática.
Para ciência da computação prática, a tese é fundacional. Justifica usar máquinas de Turing como modelo universal para análise de algoritmos. Garante que resultados sobre MTMs aplicam-se a computadores reais. Linguagens Turing-completas podem expressar qualquer algoritmo. Limites de computabilidade são limites reais, não artefatos do modelo. A tese conecta teoria abstrata com prática concreta.
A tese de Church-Turing permanece não-refutada após quase 90 anos. Novos paradigmas computacionais — quântico, biológico, neuromórfico — operam dentro de seus limites. Mas a ciência mantém mente aberta. Uma descoberta de computação super-Turing revolucionaria nossa compreensão de realidade, mente e matemática. Até lá, a tese permanece como princípio organizador central da computação.
A tese de Church-Turing é mais que conjectura técnica — é declaração profunda sobre a natureza da computação, conectando intuição humana com formalismo matemático. Como pedra angular sustentando o edifício da ciência da computação teórica, ela justifica nosso uso de máquinas de Turing como modelo definitivo de computação. Sua resistência a décadas de escrutínio sugere que captura verdade fundamental sobre o que significa computar. Com esta ponte filosófica estabelecida, estamos prontos para explorar como medimos e classificamos a dificuldade dos problemas computáveis — o reino da complexidade computacional.
Saber que um problema é computável não basta — precisamos saber se é tratável. Uma solução que demora mais que a idade do universo é tão inútil quanto nenhuma solução. A teoria da complexidade computacional classifica problemas não apenas por serem solúveis, mas pelo custo de resolvê-los. Como economistas do mundo algorítmico, medimos recursos — tempo, espaço, aleatoriedade — necessários para computação. Neste capítulo, exploraremos esta rica teoria que estratifica o mundo computável em hierarquias de dificuldade crescente.
Complexidade de tempo conta passos executados por uma máquina de Turing em função do tamanho n da entrada. Complexidade de espaço mede células de fita utilizadas. Expressamos estes custos assintoticamente: O(n) é linear, O(n²) é quadrático, O(2ⁿ) é exponencial. A notação big-O captura crescimento ignorando constantes, focando no comportamento para entradas grandes onde diferenças tornam-se dramáticas.
P contém problemas solúveis em tempo polinomial por máquina determinística. Estes são os problemas "eficientemente" solúveis — embora n¹⁰⁰ seja tecnicamente em P, na prática considera-se tratável até n³ ou n⁴. P inclui ordenação, busca, aritmética, caminhos mínimos em grafos, programação linear. A tese de Cobham-Edmonds propõe P como formalização de "eficientemente computável", análogo computacional da tese de Church-Turing.
NP (Nondeterministic Polynomial) contém problemas cujas soluções podem ser verificadas em tempo polinomial. Equivalentemente, solúveis em tempo polinomial por máquina não-determinística. NP inclui muitos problemas práticos importantes: satisfatibilidade booleana, caixeiro-viajante, coloração de grafos, mochila. A intuição: é mais fácil verificar uma solução fornecida do que encontrá-la do zero.
A questão P = NP é o problema aberto mais importante da computação teórica, com prêmio de um milhão de dólares. Se P = NP, todo problema verificável eficientemente seria solúvel eficientemente — revolucionando matemática, criptografia, otimização. A maioria acredita P ≠ NP, mas a prova permanece elusiva após décadas. A questão transcende técnica matemática, tocando a natureza da criatividade versus verificação.
Problemas NP-completos são os mais difíceis em NP — se qualquer um estiver em P, então P = NP. Cook e Levin provaram que SAT é NP-completo. Karp identificou 21 problemas NP-completos fundamentais. Hoje conhecemos milhares. São problemas "universais" — cada um codifica essencialmente todo problema em NP. Para mostrar NP-completude, provamos que está em NP e que todo problema em NP reduz a ele.
PSPACE contém problemas solúveis com espaço polinomial. Como espaço pode ser reutilizado, PSPACE inclui problemas requiring tempo exponencial. PSPACE-completos incluem jogos generalizados (xadrez, go em tabuleiros n×n), planejamento com incerteza, verificação de propriedades temporais. L (espaço logarítmico) e NL (não-determinístico logarítmico) capturam computações com memória severamente limitada.
BPP (Bounded-error Probabilistic Polynomial) contém problemas solúveis em tempo polinomial com erro limitado usando aleatoriedade. Teste de primalidade estava em BPP antes de ser provado em P. RP (um lado erro), ZPP (zero erro esperado) capturam variantes. Aleatoriedade parece ajudar, mas conjectura-se BPP = P — derandomização seria possível.
A hierarquia polinomial estende P e NP com alternância de quantificadores. Σ₁ᴾ = NP (existe certificado). Π₁ᴾ = co-NP (para todo, falha). Σ₂ᴾ = NPᴺᴾ (existe-para todo). Cada nível captura problemas com estrutura lógica mais complexa. Se P = NP, toda a hierarquia colapsa. Problemas naturais existem em cada nível, sugerindo separação genuína.
EXP contém problemas solúveis em tempo exponencial 2^(n^O(1)). NEXP é versão não-determinística. Teoremas de hierarquia garantem EXP ≠ P e NEXP ≠ NP — problemas genuinamente requerem tempo exponencial. Xadrez generalizado, verificação de teoremas, síntese de programas estão em EXP. Classes ainda maiores como 2-EXP (duplamente exponencial) capturam problemas ainda mais difíceis.
Modelo alternativo mede tamanho de circuitos booleanos computando funções. P/poly contém problemas com circuitos polinomiais não-uniformes. NC captura paralelização eficiente. ACC₀, TC₀, NC¹ formam hierarquia de classes de circuitos. Lower bounds são notoriamente difíceis — não sabemos se NP ⊆ P/poly. Conexões profundas existem entre circuitos e máquinas de Turing.
Classes interativas modelam computação com comunicação. IP (Interactive Polynomial) surpreendentemente equals PSPACE. Arthur-Merlin capturam interação com aleatoriedade pública. Zero-knowledge permite provar afirmações sem revelar informação. PCP (Probabilistically Checkable Proofs) revolucionou aproximação e verificação. Estas classes revelam poder surpreendente da interação e aleatoriedade.
A teoria da complexidade computacional revela um universo rico e estruturado dentro do mundo computável. Como geólogos identificando camadas de rocha, classificamos problemas em estratos de dificuldade crescente. Questões fundamentais como P versus NP permanecem abertas, desafiando as mentes mais brilhantes. Mas mesmo sem respostas definitivas, a teoria guia prática: identificando problemas intratáveis, sugerindo aproximações, revelando estruturas exploráveis. Esta compreensão profunda da dificuldade computacional complementa nosso entendimento dos limites absolutos da computabilidade. Com o panorama teórico completo, estamos prontos para explorar como estas ideias abstratas impactam tecnologia e sociedade modernas.
As máquinas de Turing, nascidas da abstração matemática pura, permeiam invisíveis nossa realidade digital. Cada smartphone, cada servidor na nuvem, cada linha de código executada é, em essência, uma máquina de Turing disfarçada. Os limites teóricos descobertos por Turing moldam o que podemos e não podemos esperar da tecnologia. Neste capítulo final, traçaremos as conexões entre a teoria abstrata e suas manifestações concretas, descobrindo como as ideias de Turing continuam moldando o futuro da computação e da humanidade.
Todo computador digital é fundamentalmente uma máquina de Turing com recursos finitos. A arquitetura von Neumann — processador, memória, entrada/saída — espelha componentes de Turing: unidade de controle (estados), memória (fita), processador (cabeçote). Instruções de máquina implementam transições. A universalidade de Turing garante que qualquer computador pode simular qualquer outro, diferindo apenas em eficiência. Esta equivalência fundamental permite portabilidade de software e padrões universais.
Cada linguagem de programação útil é Turing-completa — capaz de expressar qualquer algoritmo. Designers garantem Turing-completude incluindo loops/recursão e memória arbitrária. Linguagens domain-specific às vezes sacrificam completude por garantias. A hierarquia de Chomsky conecta gramáticas de linguagens com poder computacional. Compiladores são essencialmente tradutores entre diferentes representações de máquinas de Turing.
Os limites de Turing constrangem verificação de programas. Correção total é indecidível, forçando aproximações. Model checking verifica sistemas finitos exaustivamente. Verificação simbólica usa SMT solvers para explorar espaços de estado. Análise estática detecta bugs sem executar código, mas com falsos positivos. Testes cobrem casos específicos sem garantias gerais. A indecidibilidade não paralisa, mas guia estratégias práticas.
O teste de Turing propôs inteligência como comportamento indistinguível de humano. Redes neurais são Turing-completas — teoricamente podem computar qualquer função. Mas aprendizado é diferente de computação arbitrária. Limites de Turing implicam que IA não pode resolver todos os problemas. Criatividade, consciência, compreensão permanecem misteriosos. ChatGPT e similares são máquinas de Turing sofisticadas, mas ainda máquinas de Turing.
Segurança criptográfica depende de problemas computacionalmente difíceis. Se P = NP, criptografia moderna colapsa. Funções one-way existem se P ≠ NP. Protocolos zero-knowledge provam afirmações sem revelar segredos. Computação segura multipartidária permite colaboração sem confiança. Criptografia pós-quântica prepara para computadores quânticos. Limites de Turing garantem existência de informação perfeitamente segura.
Computadores quânticos são máquinas de Turing com twist quântico. BQP (Bounded-error Quantum Polynomial) captura seu poder. Algoritmo de Shor fatora em tempo polinomial. Grover acelera busca quadraticamente. Mas não transcendem Turing — simuláveis classicamente com slowdown exponencial. Supremacia quântica demonstrada para problemas específicos. Futuro: computação híbrida clássico-quântica.
DNA computing realiza computações com moléculas. Experimento de Adleman resolveu hamiltoniano com DNA. Células são máquinas de Turing bioquímicas processando informação genética. Dobramento de proteínas é problema computacional. Evolução como algoritmo de busca. Neurônios como elementos computacionais. Vida pode ser vista como computação, mas transcende modelo de Turing?
Princípio de Landauer: apagar informação dissipa energia. Limite de Bremermann: máximo de 10⁴⁷ bits/segundo/grama. Computação reversível minimiza dissipação. Computadores approaching limites atômicos. Computação besides silicon: fotônica, spintrônica, neuromórfica. Limites fundamentais de Turing permanecem independente de substrato.
A mente é uma máquina de Turing? Argumento da sala chinesa questiona compreensão. Problema difícil da consciência transcende computação? Livre arbítrio incompatível com determinismo de Turing? Criatividade matemática excede procedimentos mecânicos? Estas questões conectam Turing com questões fundamentais sobre natureza humana.
Computação molecular, celular, quântica expandem horizontes práticos. Mas permanecem dentro do framework de Turing. Hipercomputação permanece especulativa. IA approaching capacidades humanas levanta questões éticas. Computação ubíqua transforma sociedade. Limites de Turing são limites do knowable algoritmicamente. Futuro: não transcender Turing, mas explorar completamente seu domínio.
As máquinas de Turing, concebidas para resolver uma questão abstrata de lógica matemática, tornaram-se o blueprint invisível de toda computação moderna. Cada processador executando bilhões de transições por segundo, cada algoritmo transformando dados, cada IA aprendendo padrões — todos dançam a mesma dança fundamental que Turing coreografou. Os limites que descobriu não são grades que nos aprisionam, mas mapas que guiam exploração. Compreender máquinas de Turing é compreender não apenas o que computadores fazem, mas o que podem e não podem fazer. Este conhecimento, longe de ser meramente técnico, toca questões fundamentais sobre conhecimento, mente, e os limites do possível. As máquinas de Turing continuarão centrais enquanto a humanidade buscar entender e expandir as fronteiras da computação.
Este volume sobre Máquinas de Turing foi construído sobre quase um século de desenvolvimento em teoria da computação, lógica matemática e ciência da computação. As referências abrangem desde o trabalho seminal de Turing até pesquisas contemporâneas em complexidade computacional e computação quântica. Esta bibliografia oferece recursos para aprofundamento em cada aspecto das máquinas de Turing, desde sua teoria fundamental até suas aplicações práticas no mundo digital moderno.
AARONSON, Scott. Quantum Computing Since Democritus. Cambridge: Cambridge University Press, 2013.
ARORA, Sanjeev; BARAK, Boaz. Computational Complexity: A Modern Approach. Cambridge: Cambridge University Press, 2009.
BRASIL. Base Nacional Comum Curricular: Educação é a Base. Brasília: MEC/CONSED/UNDIME, 2018.
CHURCH, Alonzo. An Unsolvable Problem of Elementary Number Theory. American Journal of Mathematics, v. 58, n. 2, p. 345-363, 1936.
COBHAM, Alan. The Intrinsic Computational Difficulty of Functions. In: Logic, Methodology and Philosophy of Science. Amsterdam: North-Holland, 1965.
COOK, Stephen A. The Complexity of Theorem-Proving Procedures. In: Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, p. 151-158, 1971.
COPELAND, B. Jack (Ed.). The Essential Turing. Oxford: Oxford University Press, 2004.
CORMEN, Thomas H. et al. Algoritmos: Teoria e Prática. 3ª ed. Rio de Janeiro: Elsevier, 2012.
DAVIS, Martin. Computability and Unsolvability. New York: Dover Publications, 1982.
DAVIS, Martin. The Universal Computer: The Road from Leibniz to Turing. New York: W. W. Norton, 2000.
DAVIS, Martin; SIGAL, Ron; WEYUKER, Elaine J. Computability, Complexity, and Languages. 2nd ed. San Diego: Academic Press, 1994.
DEUTSCH, David. Quantum Theory, the Church-Turing Principle and the Universal Quantum Computer. Proceedings of the Royal Society A, v. 400, p. 97-117, 1985.
DIVERIO, Tiaraju Asmuz; MENEZES, Paulo Blauth. Teoria da Computação: Máquinas Universais e Computabilidade. 3ª ed. Porto Alegre: Bookman, 2011.
EDMONDS, Jack. Paths, Trees, and Flowers. Canadian Journal of Mathematics, v. 17, p. 449-467, 1965.
FORTNOW, Lance. The Golden Ticket: P, NP, and the Search for the Impossible. Princeton: Princeton University Press, 2013.
GAREY, Michael R.; JOHNSON, David S. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman, 1979.
GÖDEL, Kurt. Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I. Monatshefte für Mathematik, v. 38, p. 173-198, 1931.
GOLDREICH, Oded. Computational Complexity: A Conceptual Perspective. Cambridge: Cambridge University Press, 2008.
HAREL, David; FELDMAN, Yishai. Algorithmics: The Spirit of Computing. 3rd ed. London: Addison-Wesley, 2004.
HERKEN, Rolf (Ed.). The Universal Turing Machine: A Half-Century Survey. Vienna: Springer, 1988.
HILBERT, David; ACKERMANN, Wilhelm. Grundzüge der theoretischen Logik. Berlin: Springer, 1928.
HODGES, Andrew. Alan Turing: The Enigma. London: Vintage Books, 2014.
HOPCROFT, John E.; MOTWANI, Rajeev; ULLMAN, Jeffrey D. Introdução à Teoria de Autômatos, Linguagens e Computação. Rio de Janeiro: Elsevier, 2003.
IMMERMAN, Neil. Descriptive Complexity. New York: Springer, 1999.
KARP, Richard M. Reducibility Among Combinatorial Problems. In: Complexity of Computer Computations. New York: Plenum Press, 1972.
KLEENE, Stephen Cole. Introduction to Metamathematics. Amsterdam: North-Holland, 1952.
KNUTH, Donald E. The Art of Computer Programming. 3rd ed. Reading: Addison-Wesley, 1997-2011. 4 v.
KOZEN, Dexter C. Theory of Computation. London: Springer, 2006.
LEVIN, Leonid A. Universal Sequential Search Problems. Problems of Information Transmission, v. 9, n. 3, p. 265-266, 1973.
LEWIS, Harry R.; PAPADIMITRIOU, Christos H. Elements of the Theory of Computation. 2nd ed. Upper Saddle River: Prentice Hall, 1998.
LINZ, Peter. An Introduction to Formal Languages and Automata. 6th ed. Burlington: Jones & Bartlett Learning, 2017.
MENEZES, Paulo Blauth. Linguagens Formais e Autômatos. 6ª ed. Porto Alegre: Bookman, 2011.
MINSKY, Marvin. Computation: Finite and Infinite Machines. Englewood Cliffs: Prentice-Hall, 1967.
MOORE, Cristopher; MERTENS, Stephan. The Nature of Computation. Oxford: Oxford University Press, 2011.
NIELSEN, Michael A.; CHUANG, Isaac L. Quantum Computation and Quantum Information. Cambridge: Cambridge University Press, 2010.
PAPADIMITRIOU, Christos H. Computational Complexity. Reading: Addison-Wesley, 1994.
PENROSE, Roger. The Emperor's New Mind. Oxford: Oxford University Press, 1989.
POST, Emil L. Finite Combinatory Processes - Formulation 1. Journal of Symbolic Logic, v. 1, n. 3, p. 103-105, 1936.
RAMOS, Marcus Vinícius Midena et al. Introdução à Teoria da Computação. Lavras: UFLA, 2016.
RICE, H. G. Classes of Recursively Enumerable Sets and Their Decision Problems. Transactions of the American Mathematical Society, v. 74, n. 2, p. 358-366, 1953.
ROGERS, Hartley. Theory of Recursive Functions and Effective Computability. Cambridge: MIT Press, 1987.
SAVAGE, John E. Models of Computation: Exploring the Power of Computing. Reading: Addison-Wesley, 1998.
SEARLE, John R. Minds, Brains, and Programs. Behavioral and Brain Sciences, v. 3, n. 3, p. 417-424, 1980.
SHOR, Peter W. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM Journal on Computing, v. 26, n. 5, p. 1484-1509, 1997.
SIPSER, Michael. Introdução à Teoria da Computação. 2ª ed. São Paulo: Cengage Learning, 2007.
SOARE, Robert I. Recursively Enumerable Sets and Degrees. Berlin: Springer, 1987.
SUDKAMP, Thomas A. Languages and Machines. 3rd ed. Boston: Addison-Wesley, 2006.
TURING, Alan M. On Computable Numbers, with an Application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, v. 42, n. 2, p. 230-265, 1936.
TURING, Alan M. Computing Machinery and Intelligence. Mind, v. 59, n. 236, p. 433-460, 1950.
VIEIRA, Newton José. Introdução aos Fundamentos da Computação. São Paulo: Thomson Learning, 2006.
WEGENER, Ingo. Complexity Theory: Exploring the Limits of Efficient Algorithms. Berlin: Springer, 2005.
WOLFRAM, Stephen. A New Kind of Science. Champaign: Wolfram Media, 2002.