Como construir um computador de origami. Revista Quanta

Em 1936, o matemático britânico Alan Turing teve a ideia de um computador universal. Era um dispositivo simples: uma tira infinita de fita coberta de zeros e uns, juntamente com uma máquina que podia mover-se para frente e para trás ao longo da fita, transformando zeros em uns e vice-versa, de acordo com algum conjunto de regras. Ele mostrou que tal dispositivo poderia ser usado para realizar qualquer cálculo.

Turing não pretendia que sua ideia fosse prática para resolver problemas. Em vez disso, ofereceu uma forma inestimável de explorar a natureza da computação e seus limites. Nas décadas que se seguiram a essa ideia seminal, os matemáticos acumularam uma lista de esquemas de computação ainda menos práticos. Jogos como Minesweeper ou Magic: The Gathering poderiam, em princípio, ser usados ​​como computadores de uso geral. O mesmo poderia acontecer com os chamados autômatos celulares, como o de John Conway Jogo da vida, um conjunto de regras para a evolução de quadrados pretos e brancos em uma grade bidimensional.

Em Setembro de 2023, Inna Zakharevich da Universidade Cornell e Thomas Casco do Franklin & Marshall College mostrou que qualquer coisa que possa ser computada pode ser calculado dobrando papel. Eles provaram que o origami é “Turing completo” – o que significa que, como uma máquina de Turing, ele pode resolver qualquer problema computacional tratável, com tempo suficiente.

Zakharevich, um entusiasta do origami de longa data, começou a pensar sobre esse problema em 2021, depois de tropeçar em um vídeo que explicava a completude de Turing do Jogo da Vida. “Eu pensei, origami é muito mais complicado do que o Jogo da Vida”, disse Zakharevich. “Se o Jogo da Vida é Turing completo, o origami também deveria ser Turing completo.”

Mas esta não era sua área de especialização. Embora ela dobrasse origami desde que era jovem - “se você quiser me dar uma coisa supercomplexa que requer uma folha de papel de 24 polegadas e tem 400 passos, estou superada nessa coisa”, disse ela - ela a pesquisa matemática tratou dos domínios muito mais abstratos da topologia algébrica e da teoria das categorias. Então ela mandou um e-mail para Hull, que estudava matemática de origami em tempo integral.

“Ela acabou de me enviar um e-mail do nada e eu pensei, por que um topologista algébrico está me perguntando sobre isso?” Hull disse. Mas ele percebeu que nunca havia pensado se o origami poderia ser Turing completo. “Eu pensei, provavelmente é, mas na verdade não sei.”

Então ele e Zakharevich decidiram provar que é possível fazer um computador com origami. Primeiro, eles tiveram que codificar entradas e saídas computacionais – bem como operações lógicas básicas como AND e OR – como dobras de papel. Se pudessem então mostrar que seu esquema poderia simular algum outro modelo computacional já conhecido como Turing completo, eles alcançariam seu objetivo.

Uma operação lógica recebe uma ou mais entradas (cada uma escrita como VERDADEIRO ou FALSO) e gera uma saída (VERDADEIRO ou FALSO) com base em uma determinada regra. Para fazer uma operação com papel, os matemáticos desenharam um diagrama de linhas, chamado padrão de vinco, que especifica onde dobrar o papel. Uma prega no papel representa uma entrada. Se você dobrar ao longo de uma linha no padrão de vinco, a prega vira para um lado, indicando um valor de entrada VERDADEIRO. Mas se você dobrar o papel ao longo de uma linha diferente (próxima), a prega vira para o lado oposto, indicando FALSO.

Duas dessas pregas de entrada alimentam um complicado emaranhado de dobras chamado gadget. O gadget codifica a operação lógica. Para fazer todas essas dobras e ainda fazer com que o papel dobrasse de forma plana – uma exigência imposta por Hull e Zakharevich – eles incluíram uma terceira prega que é forçada a dobrar de uma maneira específica. Se a prega virar para um lado, significa que a saída é VERDADEIRA. Se virar para o outro lado, a saída será FALSE.

Os matemáticos projetaram diferentes dispositivos que transformam entradas em saídas de acordo com diversas operações lógicas. “Foi muito difícil brincar com papel e enviar fotos uns para os outros… e depois escrever provas rigorosas de que essas coisas funcionavam da maneira que dissemos que funcionavam”, disse Hull.

É sabido desde o final da década de 1990 que um método mais simples análogo unidimensional do Jogo da Vida de Conway é Turing completo. Hull e Zakharevich descobriram como escrever esta versão da Vida em termos de operações lógicas. “Acabamos precisando usar apenas quatro portas: AND, OR, NAND e NOR”, disse Zakharevich, referindo-se a duas portas simples adicionais. Mas, para combinar esses diferentes portões, eles tiveram que construir novos dispositivos que absorvessem sinais estranhos e permitissem que outros sinais girassem e se cruzassem sem interferir uns nos outros. “Essa foi a parte mais difícil”, disse Zakharevich, “descobrir como fazer tudo se alinhar corretamente”. Depois que ela e Hull conseguiram encaixar seus dispositivos, eles puderam codificar tudo o que precisavam em dobras de papel, mostrando assim que o origami é Turing completo.

Um computador de origami seria extremamente ineficiente e impraticável. Mas, em princípio, se você tivesse um pedaço de papel muito grande e muito tempo disponível, poderia usar o origami para calcular arbitrariamente muitos dígitos de $latex pi$, determinar a maneira ideal de encaminhar cada motorista de entrega no mundo, ou execute um programa para prever o tempo. “No final das contas, o padrão de vinco é gigantesco”, disse Hull. “É difícil dobrar, mas dá conta do recado.”

Durante décadas, os matemáticos foram atraídos pelo origami porque “parecia divertido e inútil”, disse Erik Demaine, um cientista da computação do Instituto de Tecnologia de Massachusetts que contribuiu extensivamente para a matemática do origami. Mas recentemente também chamou a atenção dos engenheiros.

A matemática do origami tem sido usada para projetar enormes painéis solares que podem ser dobrados e transportados para o espaço, robôs que nadam na água para coletar dados ambientais, stents que viajam através de minúsculos vasos sanguíneos e muito mais. “Agora há centenas, senão milhares de pessoas usando toda a matemática e algoritmos de origami que desenvolvemos no projeto de novas estruturas mecânicas”, disse Demaine.

E assim, “quanto mais fizermos coisas como esta”, disse Hull, “maior probabilidade penso que teremos de estabelecer cruzamentos profundos entre o origami e ramos bem estabelecidos da matemática”.