“O ponto de partida da teoria da recursão – disciplina que também é conhecida sobre 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. Essas são suas noções fundamentais. Um algoritmo é, rudimentarmente falando, um conjunto finito de regras ou instruções, concebidas para serem aplicadas mecanicamente (isto é, sem recurso à criatividade – por uma máquina, por exemplo) a um dado input simbólico, com vistas à obtenção, após a execução de um número finito de operações elementares, de um respectivo output simbólico. E uma função diz-se algorítmica quando se dispões de um algoritmo para computar os seus valores.
Essas duas noções são razoavelmente familiares. Inúmeros exemplos matemáticos prosaicos podem ser lembrados aqui: o método que aprendemos bem cedo na escola para efetuar a soma de números naturais em notação arábica decimal; os métodos para efetuar outras operações aritméticas básicas (subtração, multiplicação, divisão); os procedimentos para se encontrar o mínimo múltiplo comum ou o máximo divisor comum entre dois inteiros (neste último caso, com o conhecido algoritmo de Euclides); o chamado crivo de Eratóstenes para determinar o n-ésimo número primo – entre muitos outros exemplos que o leitor poderia citar para estender essa lista, sofisticando-a segundo seu gosto e seus conhecimentos. Exemplos não numéricos também podem ser aduzidos, como o método das tabelas de verdade, familiar àqueles que já travaram algum contato com a lógica matemática, para determinar se uma certa forma proposicional é ou não uma tautologia, ou as regras de diferenciação de expressões polinomiais, que se aprendem nos primeiros contatos com o cálculo.”
Assim começa o livro “Teoria da recursão” dos autores Matias Francisco dias e Leonardo Weber que recebi da Editora UNESP. É um ótimo livro para matemáticos, físicos e outros que tenham interesse em lógica.
“O presente livro trata da teoria da recursão que, embora presentemente quase tenha adquirido vida própria, ainda constitui um ramo da lógica, concebida em sentido amplo. Tal teoria nasceu em torno dos anos trinta do século XX, tendo sido criada por lógicos e matemáticos do calibre de K. Gödel, A. M. Turing, J. Herbrand, A. Church, S. C. Kleene, J. B. Rosser e E. L. Posto.
A obra de Dias e Weber é muito boa, fornecendo ao leitor uma visão clara do que se faz atualmente em um terreno dos mais interessantes e significativos da lógica hodierna. 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.” – Newton C. A. da Costa.
Editora Unesp
Área: matemática
Idioma português
Número de páginas 276
O livro pode ser adquirido no site da Livraria UNESP:
Este é um post da série “Livros de Física“.