O início da computação moderna

Vamos contar aqui sobre o paradoxal início da Ciência da Computação moderna. E eu digo paradoxal, porque ela veio à luz não quando se buscava uma forma eficiente de fazer contas, mas quando estava se tentando mostrar que existiam problemas não computáveis.

O herói dessa história é um tal de Alan Turing, que já foi personagem de filme de Hollywood em O Jogo da Imitação e possui um prêmio de ciência da computação com seu nome, o Prêmio Turing, distribuído anualmente para algum pesquisador que se destacou na área. Em 1937, ele demonstrou matematicamente que existem problemas que não podem ser computados. Só que, para isso, ele teve que estabelecer o que quer dizer “ser computável” e, nesse processo, criou as Máquinas de Turing. Essas máquinas são conceitos matemáticos abstratos que formalizam a noção de computação, e um resultado matemático importante que ele descobriu mostra que existe uma máquina especial, chamada de Máquina Universal de Turing, que desempenha um papel central na Teoria da Computação. Esta Máquina Universal de Turing é a base para a construção dos computadores como a gente os conhece hoje.

O artigo inicial de Turing tem algumas coisas que chamam a atenção e que estão presentes no próprio título do artigo, traduzido de forma livre aqui para: Sobre números computáveis e uma aplicação ao problema de decisão. Como assim, números computáveis? Quer dizer que existem números não computáveis?

Sim, e nem é tão difícil de ver isso. Mas antes, vamos voltar um pouquinho no tempo, pois os primórdios da computação estão intimamente ligados aos números infinitos. Em 1874, o matemático alemão Georg Cantor publicou um artigo em que mostrava que existia mais de um tipo de infinito. Em particular, ele mostrou que o infinito dos números naturais 0,1,2,3, … é menor do que o infinito dos números reais. Talvez você já tenha até notado isso, a partir de um simples desenho. O infinito dos números reais corresponde a uma linha contínua (esse conjunto é chamado de Contínuo), e, sobre essa linha, bem espaçadamente, a gente pode inserir os números naturais ou os números inteiros (o tamanho do infinito desses outros é chamado de Contável). Com uma estratégia bastante inovadora, Cantor mostrou que não é possível alinhar os elementos do Contínuo um a um com os elementos Contáveis, sempre sobra algum número que não fica alinhado. Desta forma ele mostrou que o contínuo é estritamente maior que os números contáveis.

Então vem Turing e mostra que existem números reais não computáveis. Os números não computáveis são sempre elementos do Contínuo. Pela definição dele, um número real é computável se existe um programa ou, na versão original, uma Máquina de Turing, que imprime infinitamente os seus dígitos. Mas cada programa e cada Máquina de Turing tem tamanho finito e fica armazenado em um arquivo. Um arquivo nada mais é que um número natural, que pode ser bem grande. Então o número máximo de programas é um infinito Contável, e não pode haver programas o suficiente para imprimir todos os números reais. Muitos números reais não podem ser impressos por nenhum programa, e estes são os números reais não computáveis. E a gente agora sabe que a maioria dos números reais não é computável, só uma pequena proporção deles pode ser impressa por um programa ou por uma Máquina de Turing.

Uma pequena fofoca aqui. Quando Turing escreveu seu artigo em 1936, sem o seu conhecimento, outro matemático famoso, chamado Alonzo Church, já havia demonstrado a existência de números não computáveis, usando técnicas bem diferentes. Então os editores da revista ficaram na dúvida se o artigo de Turing era verdadeiramente original. O artigo ficou parado em alguma mesa até que alguém teve a ideia de mostrar esse artigo para o próprio Church, que achou tão original a ideia do Turing que o convidou para ser seu aluno de doutorado nos Estados Unidos. Por essa demora, o artigo só foi publicado em 1937. Turing terminou seu doutorado em um ano e estava de volta à Inglaterra quando explodiu a Segunda Guerra. É aí que se inicia a história do filme O Jogo da Imitação, depois que Turing já tinha feito sua grande contribuição para a história da Ciência da Computação moderna.

Voltando aos números, a primeira reação das pessoas quando aprendem que existem números não computáveis é a seguinte: “Por favor, me mostre um exemplo de número não computável”. E eu, prazerosamente, respondo: “Não posso mostrar. Se eu mostrar o número, eu acabei de computá-lo. E um número não computável não dá para ser computado. Óbvio, não? Bom, se não for óbvio, acostume-se com a ideia de que você nunca poderá ver um número não computável, exatamente por ele não ser computável”.

Mas, se o número não é computável, como é que a gente se refere a ele? Bom, a gente tem de usar formas indiretas de definir o número sem fazer conta nenhuma. Um exemplo bem famoso é “a probabilidade de um programa de computador parar”. Essa expressão entre aspas é a definição do número. Demonstra-se que esse é um número não computável do qual não podemos saber quase nenhuma propriedade. Não dá para saber se esse número é menor do que 0,5 ou maior do que 0,00000001. Todas essas perguntas são também questões não computáveis.

E isso nos faz retornar ao artigo inicial de Alan Turing. Ele mostrou que existem problemas não computáveis, ou seja, que não podem ser calculados por nenhuma Máquina de Turing, inclusive aquele tal Problema da Decisão (da lógica de primeira ordem) que estava no título de seu artigo.

E assim nasceu a computação moderna, mostrando que a computação tem limite. Existem coisas que nunca poderão ser computadas, e a gente tem que viver dentro dos limites do que é possível fazer com uma máquina de computação. O Teorema de Turing não depende de nenhuma linguagem de programação e nenhum tipo de computador. Sendo assim, os problemas não computáveis permanecem não computáveis com qualquer tecnologia, mesmo com a mais moderna inteligência artificial ou as tecnologias que serão inventadas daqui a mais de um século.

________________
(As opiniões expressas nos artigos publicados no Jornal da USP são de inteira responsabilidade de seus autores e não refletem opiniões do veículo nem posições institucionais da Universidade de São Paulo. Acesse aqui nossos parâmetros editoriais para artigos de opinião.)