ALAN TURING E A CIÊNCIA DA COMPUTAÇÃO

Valdemar W. Setzer
Depto. de Ciência da Computação da USP
www.ime.usp.br/~vwsetzer

[Este artigo foi escrito sob encomenda, para constar do programa da peça "Quebrando Códigos", que entrou em cartaz em 15/8/03 no Espaço Promon, Sala São Luiz, em São Paulo]

Se o leitor está terminando um Bacharelado em Ciência da Computação, e nunca ouviu falar o nome Turing, é melhor começar tudo de novo em uma faculdade de um nível razoável. Isso se deve ao fato de Alan Mathison Turing (1912-1954) ter estabelecido alguns dos fundamentos mais importantes da Ciência da Computação, tanto do ponto de vista prático quanto teórico e, portanto, deve obrigatoriamente ser mencionado e suas descobertas estudadas em qualquer curso dessa área. É dele, por exemplo, a definição de 1937 do que se constitui a máquina digital abstrata (isto é, existente em nossa mente ou no papel – não há sentido em construir-se uma, pois seria extremamente ineficiente) mais elementar e geral que se pode imaginar: a Máquina de Turing (MT). Esse nome foi dado pelo famoso lógico Alonzo Church, numa revisão de um artigo de Turing de 1937, que se tornou um dos pilares da matemática. Nele, Turing mostra que, contrariamente à conjetura feita em 1928 pelo grande matemático alemão David Hilbert, existem afirmações da matemática que são indecidíveis, isto é, não existe um procedimento efetivo para decidir se elas podem ser provadas dentro de um sistema matemático formal. Um exemplo clássico disso na computação é que é impossível elaborar um programa que examine um outro e decida se este termina a sua execução, para qualquer dado de entrada. Para isso, Turing teve uma inspiração depois de uma de suas longas corridas à tarde: pensou em inventar uma máquina abstrata que pudesse provar qualquer afirmação matemática dada a ela. E aí surgiu o famoso modelo, a MT – com a qual ele acabou provando que aquilo era impossível. A MT é um mecanismo abstrato extremamente simples: pode-se imaginá-la assumindo um número finito de estados (uma lâmpada com interruptor tem só dois: apagada ou acesa), usando uma fita infinita dividida em células, onde inicialmente estão gravados certos símbolos. Um cabeçote de leitura e de gravação pode varrer a fita, uma célula de cada vez. Se a máquina está em um certo estado, para cada possível símbolo na célula da fita examinada pelo cabeçote, é definida uma transição, que consiste em mudar o símbolo dessa célula examinada pelo cabeçote (eventualmente para o mesmo que lá estava), mover a fita uma célula para a esquerda ou direita, e desviar para um estado (eventualmente o mesmo de antes). O incrível é que não se consegue inventar nenhuma máquina digital que consiga resolver mais problemas matemáticos que essa trivial MT consegue! (Essa é a chamada Tese de Church-Turing.) E também não se consegue imaginar uma máquina tão geral ainda mais simples. Ainda mais, é sempre possível programar uma MT (isto é, definir as suas transições) para simular qualquer outra MT, ou seja, a primeira recebe na fita uma descrição das transições da segunda, mais os dados a serem usados por esta última, e passa a executar o programa dela. Daí veio a noção de Máquina Universal. Essa universalidade aplica-se aos computadores digitais modernos: qualquer um, com capacidade suficiente, pode simular qualquer outro; a grande diferença entre eles e a MT é que esta tem uma fita infinita, e suas instruções são as mais elementares possíveis. A MT teve importância fundamental no desenvolvimento das áreas de computabilidade, teoria dos autômatos formais e análise de algoritmos. Baseado nela, Turing tentou construir computadores com instruções extremamente elementares, o que bem depois concretizou-se com as máquinas denominadas de "RISC" (reduced instruction set computer).

Uma contribuição prática de Turing foi o que se chamou depois de Teste de Turing (TT), de 1950: em lugar de responder à pergunta "pode-se ter computadores inteligentes?" ele formulou seu teste, que se tornou praticamente o ponto de partida da pesquisa em "Inteligência Artificial". O teste consiste em se fazer perguntas a uma pessoa e um computador escondidos. Um computador e seus programas passa o TT se, pelas respostas, for impossível a alguém distinguir qual interlocutor é a máquina e qual é a pessoa (interessante é que ele não especificou o nível intelectual e cultural do perguntador...). No seu artigo original ele fez a previsão de que até 2000 os computadores passariam seu teste. Pois bem, há um concurso anual de programas para o TT, e o resultado dos sistemas ganhadores é tão fraco (o último tem o nome "Ella") que com poucas perguntas logo percebe-se a idiotice das respostas da máquina. Não há a mínima esperança de que se consiga um dia um computador que passe o TT; qualquer previsão nesse sentido não tem base científica, o que mostra um dos muitos erros crassos dos filmes "Inteligência Artificial" (Spielberg) e "O Homem Bicentenário" (Columbus). Em ambos, os robôs passariam não só o TT, que é um teste comportamental lingüístico, mas um TT estendido para todo o comportamento humano. É interessante notar que tanto a MT quanto o TT talvez derivem da visão que Turing tinha de que o ser humano é uma máquina. Essa visão está absolutamente errada do ponto de vista linguístico, já que associamos a "máquina" um artefato inventado e eventualmente construído. Nenhum ser humano foi inventado ou construído... Quem sabe sua ingenuidade social, bem mostrada na peça, esteja ligada a essa sua visão de que o ser humano é uma máquina, isto é, infinitamente mais simples do que ele realmente é – apesar de, paradoxalmente, na peça ele afirmar que a vida é complexa.

Recomendo o extraordinário livro de Andrew Hodges, Alan Turing, a origem das informações que levaram à peça, para se conhecer a fundo essa personalidade tão avançada para seu tempo, e que sofreu o que duas décadas mais tarde não teria sofrido.