Os algoritmos estão cada vez mais presentes com a tecnologia que já se tornou parte da nossa vida. Seja ajudando a chegar em algum lugar, melhorando nossas experiências de compra ou até sugerindo memes, a precisão e as soluções computacionais estão cada vez mais otimizadas. Alguém poderia presumir que todo problema – se claramente definido em termos matemáticos – encontra seu algoritmo para resolvê-lo. No entanto, a realidade é surpreendentemente diferente.
Falando em algoritmos… Será que nosso pensamento anda algoritmizado? Clica aqui para ler o atigo!
Alan Turing, hoje em dia muito mencionado em razão da IA, é a mente prodigiosa por trás da ciência da computação moderna, e propôs uma questão simples, mas revolucionária: Existem problemas que os algoritmos, por mais avançados que sejam, não conseguem resolver? A resposta, como ele demonstrou, é sim. Turing não chegou a essa conclusão explorando as infinitas possibilidades de soluções, mas sim adotando uma abordagem fascinantemente contrária. Ele delineou um problema que essencialmente desafiava toda tentativa de solucioná-lo.
O experimento é como se alguém insistisse em sempre fazer o oposto do que você pede. Nas palavras de Rahul Ilango, um pós-graduando do MIT que estuda a ciência da computação teórica, é como dizer: “Pergunto o que você está fazendo e depois digo: ‘Não, vou fazer algo diferente’ “
Esta metodologia intrigante tem suas raízes em um truque matemático chamado diagonalização proposta inicialmente por Georg Canto. Vamos entender como a prova de Turing incorpora essa técnica em sua estrutura.
A lógica da diagonalização
A diagonalização é um método inteligente para lidar com um desafio simples: imagine ter várias sequências de números, onde cada número é apenas 0 ou 1 (essas sequências são chamadas strings binárias). Se você tiver uma lista dessas sequências e todas tiverem o mesmo tamanho, como você criaria uma nova sequência que não existisse nessa lista?
Em nosso cotidiano, muitas vezes não nos deparamos com o conceito de sequências infinitas, mas a diagonalização nos permite enfrentar um desafio específico relacionado a computadores.
É um desafio gerar uma sequência de bits inédita que se destaque por ser diferente de todas as outras em uma lista específica. Em um primeiro momento, muitos de nós poderíamos ser levados pela abordagem mais intuitiva, pensando: “Por que não experimentar todas as combinações possíveis, sequência por sequência?”. Esta estratégia, à primeira vista, é semelhante à de alguém diante de um molho abarrotado de chaves, tentando cada uma delas até encontrar a que destranca a fechadura.
Contudo, à medida que a lista de sequências se expande, essa abordagem, por mais direta que pareça, começa a mostrar suas fraquezas. O processo se torna progressivamente lento, e a tarefa de encontrar a sequência inédita se transforma em uma missão exaustiva, especialmente quando estamos lidando com strings particularmente longas.
É aqui que entra a genialidade da diagonalização. Em vez de seguir o tedioso caminho de verificar cada string possível, a diagonalização introduz uma tática mais inteligente.
Simplificadamente seria algo assim: Comece invertendo o primeiro bit da string inicial. Essa pequena inversão estabelece a pedra angular para uma nova string. Avançando, você pega o segundo bit da string subsequente e inverte esse. Continue esse processo e no final, você terá uma string que é única, sempre diferente de todas as strings da lista original.
Um fato curioso sobre este método é que os bits invertidos, quando marcados, esboçam uma linha diagonal através da nossa lista de bits, dando à técnica seu nome evocativo.
No entanto, a verdadeira mágica da diagonalização não está apenas em sua velocidade ou eficiência, e sim em sua incrível versatilidade com o conceito de infinito. No mundo da diagonalização, as strings não precisam ser limitadas por tamanho, as listas não têm que ser confinadas em tamanho. Ryan Williams, cientista teórico da computação do MIT afirma que então as strings agora podem ser infinitas e a lista pode ser infinita.
Transportando este conceito de volta ao século XIX, foi Georg Cantor, fundador do subcampo matemático da teoria dos conjuntos, quem primeiro se aproximou das infinitas possibilidades da diagonalização. Em 1873, Cantor não só usou este método para resolver um enigma computacional, ele também trouxe algo revolucionário: Alguns infinitos, contrariamente à crença intuitiva, são genuinamente maiores do que outros.
Após seis décadas, Alan Turing se debruçou sobre a questão da diagonalização, usando o trabalho fundamental de Cantor adaptando-o à teoria da computação, dando a issto um sentido contrário.
A busca pelos algoritmos ideiais por Turing
Na busca insaciável da humanidade por soluções, Alan Turing não apenas se propôs a encontrar respostas, mas também a descobrir os próprios limites de nossa capacidade de resolver problemas. Ao passar pela complexidade dos problemas matemáticos, Turing se concentrou em um conjunto especial conhecido como “problemas de decisão“. Estes são caracterizados por entradas de 0s e 1s e apenas dois possíveis resultados: 0 ou 1.
Pense em verificar se um número é primo. Se representássemos o número em uma string e o número fosse primo, a saída correta seria 1; caso contrário, seria 0. Similarmente, pense na verificação de programas de computador para erros de sintaxe, uma espécie de “gramática” dos códigos. As entradas seriam diferentes programas, e a saída nos diria se há ou não um erro no código.
No entanto, o desafio não é apenas sobre ter um algoritmo que funcione a maior parte do tempo, ele precisa acertar todas as vezes. Enquanto muitos cientistas começavam definindo o problema e depois tentavam encontrar uma solução, Turing fez o contrário ao procurar problemas insolúveis, uma lista infinita de todos os algoritmos concebíveis e usando a diagonalização para colocar um problema para desafiar cada um deles.
Imagine um jogo manipulado de 20 perguntas onde, em vez de ter uma resposta específica em mente, a pessoa que responde inventa uma nova desculpa para dizer “não” a cada questão. Ao final, o objeto descrito seria conhecido apenas pelo que ele não é. Turing, em sua abordagem, utilizando a diagonalização, essencialmente jogou essa versão do jogo, perguntando continuamente se um algoritmo específico da lista poderia resolver um problema teimosamente incalculável, seria como jogar um jogo de “questões infinitas”.
Para vencer esse jogo, Turing teve que desenhar um problema que ficasse sempre um passo à frente de cada algoritmo, fazendo com que todos tropeçassem. Seu método envolveu identificar entradas específicas que fariam cada algoritmo falhar. Ele descobriu que Kurt Gödel havia usado uma abordagem semelhante que mostrou as implicações complexas de afirmações autorreferenciais na matemática.
O ponto central do argumento de Turing era que cada algoritmo pode ser esmiuçado em uma string de 0s e 1s. Isso significa que um algoritmo pode, teoricamente, analisar o código de outro ou até mesmo o seu próprio. Usando essa noção, ele descreveu um problema que se mostrou impossível para qualquer algoritmo resolver. Se um algoritmo, quando dado seu próprio código como entrada, produzisse uma saída de 0, o output deveria ser 1 e vice-versa. Esse problema enigmático garantiria que todo algoritmo cometesse pelo menos um erro.
Resumindo, quando um algoritmo recebe o seu próprio código como entrada, seja esse algoritmo qual for, ele não pode resolver esse problema.
O papel da teoria de Turing na teoria da complexidade computacional
Essa técnica ainda pedia mais, e em 1965, Juris Hartmanis e Richard Stearns revisitaram a abordagem fundamental de Turing, se baseando nos princípios da diagonalização para demonstrar uma ideia cativante: nem todos os problemas computacionais são iguais. Alguns apresentam desafios inerentemente maiores que outros.
Seus esforços inovadores deram origem a um novo domínio na ciência da computação conhecido como teoria da complexidade computacional. Este campo não se trata apenas de identificar problemas, mas também de classificar sua dificuldade, de compreender as nuances que tornam um desafio computacional mais difícil do que outro.
No entanto, toda ferramenta, por mais poderosa que seja, tem seus limites. Isso se tornou evidente em 1975, quando Theodore Baker, John Gill e Robert Solovay chegaram a uma realização significativa. Descobriram que a diagonalização, apesar de suas forças, não podia responder a todas as questões da teoria da complexidade computacional.
Um dos problemas mais conhecidos é o problema P versus NP, que basicamente busca determinar se todo problema com uma solução que é fácil de verificar também é fácil de resolver. Uma solução, uma vez que sabemos que está correta, sempre pode ser encontrada sem uma busca extensa?
Um desafio único com a diagonalização é a sua natureza abstrata. Esse nível de abstração, embora ofereça vastos insights, o separa dos dilemas tangíveis do mundo real. Ryan Williams apontou que usar a diagonalização parece “lidar com a computação à distância”. É como um pesquisador tentando estudar um vírus, mas apenas acessando-o através de uma barreira protetora. Há um grau de separação, um buffer que impede a interação direta.
No entanto, apesar de suas limitações, seria um erro minimizar a importância da diagonalização. Este método permanece um aliado indispensável para aqueles que exploram teoria da complexidade. Um testemunho de seu valor duradouro veio em 2011 quando Williams, combinando a diagonalização com outras técnicas avançadas, desvendou um enigma computacional que havia confundido especialistas por mais de duas décadas. Embora essa conquista possa não abordar diretamente a monumental questão P vs NP, simboliza um avanço substancial no campo.
Há uma lição importante a ser tirada da diagonalização: nunca subestime a pura força da contradição. Turing nos mostra que, às vezes, os insights mais profundos surgem não de afirmações, mas do poder de refutar, de simplesmente dizer “não”.
Fonte: Quanta Magazine
