Afinal, o que é computação?

Nem toda mudança é computação

Uma pedra cai, uma poça evapora, uma estrela queima. Nenhuma delas está computando — e o universo inteiro muda o tempo todo. Se toda mudança fosse computação, a palavra não distinguiria nada. Mas olhe duas mudanças específicas: um 0 atravessa uma porta NÃO e vira 1; uma operação de reset leva qualquer entrada a 0. Nos dois casos, estados que representam informação foram transformados. Isso basta? Ainda não.

Primeiro, duas ideias erradas. Por séculos, “computar” queria dizer fazer contas, e “computador” era uma profissão — uma pessoa que calculava. Máquinas digitais ainda somam, mas também ordenam nomes, decodificam música, controlam semáforos e simulam o clima. E computação não é sinônimo de eletricidade: um ábaco computa, uma fileira de dominós computa, uma pessoa seguindo instruções à risca computa. A corrente elétrica é um suporte extraordinariamente rápido e controlável, não a definição.

O núcleo aparece quando duas coisas acontecem juntas: alguém escolhe estados para representar alguma coisa, e alguém especifica como esses estados devem mudar. Estado atual, regra aplicável, próximo estado; repita, e uma trajetória organizada chega a um resultado. As leis da física determinam o que o suporte pode fazer; a regra computacional diz quais diferenças contam como símbolo. A energia faz a máquina mudar, mas não diz se o resultado significa uma soma ou uma lista ordenada. Primeira definição: computar é transformar representações por uma sequência de regras.

Problema, entrada, algoritmo

“Ordenar números em ordem crescente” é um problema. A lista 4, 1, 3, 2 é uma entrada. 1, 2, 3, 4 é a saída correta. O problema diz qual relação você quer entre entrada e saída; não diz como chegar lá. Para chegar lá, dá para comparar vizinhos e trocar os invertidos (o método da bolha), escolher o menor do resto de cada vez (seleção), ou uma dúzia de outras estratégias. Cada uma é um algoritmo: um caminho bem definido entre entrada e saída.

“Bem definido” tem sentido preciso: dá para seguir passo a passo sem adivinhar nada. “Compare estes dois cartões” é uma instrução; “tenha uma ideia brilhante” não é. O texto do algoritmo é finito, e para resolver uma tarefa ele precisa terminar com a resposta certa em cada entrada válida. (Programas que rodam para sempre — um servidor, um controlador de tráfego — também computam, mas não são algoritmos que terminam com uma resposta. Algoritmo e programa são próximos, não idênticos.) Numa lista de dez números, a seleção faz sempre 45 comparações — $\frac{n(n-1)}{2}$ —, não importa a ordem de entrada.

E o mesmo algoritmo aceita corpos muito diferentes: uma pessoa com cartões, engrenagens, transistores. Se cada implementação preserva os mesmos estados relevantes e as mesmas transições, todas realizam o mesmo algoritmo abstrato. É por isso que software migra entre computadores tão diferentes.

Memória: estado interno

Uma lista de instruções, sozinha, é papel parado. Para executar, a máquina precisa saber onde está e reter resultados intermediários. Uma porta lógica simples responde só ao que recebe agora: na porta E, 1 e 1 dão 1, e qualquer outra combinação dá 0, hoje e amanhã. Isso é um circuito combinacional — poderoso, mas incapaz de contar passos ou distinguir a primeira vez da décima.

Acrescente memória, e a saída passa a depender da entrada e de um resumo do passado. Um semáforo: o mesmo pulso do relógio leva o verde ao amarelo, o amarelo ao vermelho, o vermelho ao verde — mesma entrada, consequências diferentes. Uma tabela “estado atual + entrada → novo estado + saída”, ou círculos ligados por setas: uma máquina de estados finitos. O estado não guarda o passado inteiro; guarda só as distinções que importam para o próximo passo, e é essa compressão que deixa um sistema finito executar processos arbitrariamente longos.

Portas, células de memória e um relógio, juntos, fazem o resultado de um passo alimentar o seguinte. Um processador moderno tem bilhões de componentes, mas a estrutura continua reconhecível: ler estado, aplicar regra, escrever novo estado. Existe uma máquina simples o bastante para analisar e geral o bastante para qualquer algoritmo?

A máquina de Turing

Alan Turing, em 1936, imaginou três peças: uma fita de células, uma cabeça que lê e escreve um símbolo por vez, e um estado interno — mais uma tabela de regras: no estado q, lendo s, escreva s’, mova para a esquerda ou a direita e passe ao estado q’. A operação mais burra possível: a fita tem 111 (três, em unário); a cabeça anda para a direita enquanto lê 1, grava um 1 no primeiro vazio e para. Agora há quatro. A máquina somou um.

Cada passo é trivial; a força vem de repetir passos exatos sobre uma memória que cresce conforme preciso. E máquinas minúsculas já surpreendem: entre todas as máquinas de 4 estados que param numa fita vazia, a que escreve mais uns para depois de exatamente 107 passos, com 13 uns. Com 5 estados, o recorde (47 176 870 passos) só foi provado em 2024. Com 6, ninguém sabe.

A máquina universal

Até aqui a tabela parecia soldada na máquina. Mas a tabela pode ser escrita como uma sequência de símbolos, exatamente como a entrada. E então dá para construir uma segunda máquina que lê a descrição da primeira e a imita, passo a passo: uma máquina universal. Na fita dela entram a descrição de uma máquina e os dados. Trocar a descrição muda o processo sem reconstruir mecanismo nenhum. Nasce aí a ideia do computador programável: instrução também é dado.

A máquina de Turing não foi a única tentativa de formalizar “procedimento mecânico”: houve o cálculo lambda de Church, as funções recursivas e outros modelos, de intuições completamente diferentes — e todos capturaram exatamente a mesma classe de funções. A tese de Church–Turing afirma que qualquer método efetivo (finito, exato, sem lampejo de criatividade, que termina com a resposta) pode ser realizado por uma máquina de Turing. Não é um teorema comum, porque “método efetivo” começou como noção informal; é uma ponte extraordinariamente bem sustentada entre o procedimento intuitivo e o modelo matemático.

Computação física

Dominós em pé e caídos, relés abertos e fechados, tensões em transistores, moléculas se ligando por regras químicas. Esses sistemas não computam porque se movem — a pedra também se move. Viram computadores quando seus estados são preparados, interpretados e acoplados de modo que a dinâmica física implemente as transições desejadas. Por isso computação é ao mesmo tempo abstrata e física: a função lógica ignora o material, mas cada execução depende dele e herda seus limites de velocidade, ruído, energia e temperatura.

E o episódio sobre informação mostrou a diferença que importa: a porta NÃO é logicamente reversível (da saída se recupera a entrada); o reset não é. Computação não precisa descartar informação a cada passo — dá para construir portas reversíveis, pagando com mais memória —, mas quando uma máquina cíclica apaga distinções, o princípio de Landauer cobra pelo menos $kT\ln 2$ por bit.

O que nenhum algoritmo decide

Se a máquina universal simula qualquer programa, talvez um programa consiga analisar qualquer outro. Imagine um preditor perfeito, PARA?: recebe um programa e uma entrada e diz, sempre corretamente, se a execução termina. Rodar o programa não resolve — se ele para, ótimo; mas enquanto roda, você nunca sabe se vai parar depois de mais um trilhão de passos. Mesmo assim, conceda que PARA? exista.

Construa CONTRÁRIO: ele recebe um programa P, pergunta a PARA? se P para quando recebe a própria descrição, e faz o oposto — se a resposta for “para”, entra num laço infinito; se for “não para”, para na hora. É fácil de escrever: um “se” em volta de uma chamada. Agora entregue a CONTRÁRIO a descrição dele mesmo. Se PARA? disser que ele para, ele não para. Se disser que não para, ele para. Qualquer resposta é falsa. Logo, PARA? não pode existir.

Cuidado com a conclusão. Isso não quer dizer que nunca dá para provar que um programa específico termina — muitos casos são óbvios, e técnicas formais resolvem classes inteiras. O impossível é um único decisor que acerte todos os casos. E há três gavetas que não podem se misturar: um problema não computável não tem algoritmo geral, ponto; um problema computável pode exigir tempo ou memória absurdos; um problema em aberto pode só não ter, ainda, nem método nem prova de impossibilidade.

A parede exponencial

Uma busca com duas escolhas em cada etapa: 10 escolhas, 1024 caminhos; 40 escolhas, mais de um trilhão; 100, mais de $10^{30}$. A busca exaustiva é um algoritmo legítimo — termina, com a resposta certa. Mas a um bilhão de caminhos por segundo, 40 escolhas levam 18 minutos, e 100 levam 4,0 × 10¹³ anos — umas 2.911 vezes a idade do universo. Cada escolha a mais dobra o tempo.

Ser computável em princípio não torna a tarefa viável. E outro algoritmo pode explorar a estrutura do problema e evitar quase todos esses caminhos. Comparar estratégias exige contar recursos — passos, memória, energia — em função do tamanho da entrada. Essa é a próxima pergunta: não mais “pode ser feito?”, mas “quanto custa?” — o território de P contra NP.

Computação, então, é um processo em que estados que representam informação evoluem segundo regras bem definidas, produzindo novas representações. O algoritmo é a descrição abstrata; a execução é a sequência concreta de transições; o computador é o sistema físico que as sustenta. Memória carrega o passado relevante, programas codificam regras, máquinas universais leem programas como dados — e alguns problemas ficam fora do alcance de qualquer algoritmo.

Os números do episódio

Desafios

Para ir além

• No laboratório: as sete máquinas, os dois algoritmos, a parada e a parede exponencial.
• Alan Turing, “On Computable Numbers, with an Application to the Entscheidungsproblem” (1936).
• Antes: o que é informação. E outra prova sobre o infinito: indução.