Descrição

Na década de 30 do século passado, antes dos modernos computadores digitais, alguns lógicos já haviam descoberto certos problemas insolúveis por métodos algorítmicos, isto é, problemas insuscetíveis de serem resolvidos por meio de um computador. Foi uma descoberta impressionante, que impactou profundamente a lógica, a matemática, a filosofia, e lançou as bases teóricas da futura ciência da computação. Teoria da recursão, de Matias Francisco Dias e Leonardo Weber, lançamento da Editora Unesp, oferece uma visão clara do que se faz atualmente no terreno dos mais interessantes e significativos deste campo.

O ponto de partida da teoria da recursão - disciplina que também é conhecida sob outras designações, como "teoria da computabilidade" ou "teoria das funções recursivas" - consiste em analisar conceitualmente, em termos matematicamente precisos, as noções intuitivas de algoritmo e função algorítmica. Lógicos como Herbrand, Post, Gödel, Turing, Church e Kleene conceberam os primeiros modelos matemáticos abstratos de computação, que orientariam a construção de computadores reais nas décadas seguintes.

As questões básicas que motivaram tais modelos eram: qual a natureza da computação? Quais os requisitos mínimos para que um agente, humano ou não (como uma máquina), seja capaz de computar certos problemas, isto é, resolvê-los por meios algorítmicos? Que tipos de problemas são computáveis, ou algoritmicamente solúveis? Há problemas incomputáveis?

O estudo sistemático desses modelos abstratos é aqui apresentando em uma abordagem tematicamente unificada. Como lembra Newton da Costa, no prefácio, "o caráter matemático da teoria da recursão é óbvio e o leitor atento tomará, então, consciência plena do espírito que norteia a investigação lógica de nosso tempo". E também comenta que o trabalho de Matias Francisco Dias e Leonardo Weber "preenche uma lacuna na literatura especializada - em língua portuguesa", e que tende "a se tornar um clássico entre nós."