As “Funções Recursivas Parciais” (base para se entender “o que é computável e o que não é”) seguem sendo conceito fundamental na Teoria da Computação e na Lógica Matemática dado constituírem forma poderosa e flexível de se descrever algoritmos, “capturando a ideia de que um processo de computação nem sempre precisa produzir um resultado para cada entrada”.
De forma simples e compendiada, as “Funções Recursivas Parciais” são funções que podem ser “parcialmente definidas”, ou seja, que “não necessitam ter um valor de saída para cada possível valor de entrada”.
“Funções Recursivas Parciais” são funções que não estão definidas para todos os possíveis valores de entrada; podendo “não terminar ou não produzir um resultado válido para determinados argumentos”.
São denominadas de "RECURSIVAS" porque podem ser definidas em termos de si mesmas, usando uma abordagem de recursão (baseia-se em valores da própria função para entradas menores); e, são "PARCIAIS" porque seu domínio de definição (o conjunto de entradas para as quais a função tem um valor de saída) pode ser um subconjunto próprio de seu domínio de entrada (“parcialidade”: a função pode não ter uma saída para todas as entradas; de forma que o processo de cálculo da função não termina).
Assim, as “Funções Recursivas Parciais” são aquelas que se chamam a si mesmas para resolver subproblemas menores e não estão definidas para alguns valores (ou seja, podem entrar em “um ciclo infinito” ou “falhar ao atingir um caso base”).
Para os Jovens Acadêmicos que cursavam sob minha orientação as disciplinas de Cálculo Diferencial e Integral no Câmpus Curitiba da TECNOLÓGICA (UTFPR - Universidade Tecnológica Federal do Paraná) ministrei, durante o mês de setembro de 2010, iniciando em 13/09/2010, o Curso de Extensão Universitária em "Funções Recursivas Parciais", com duração de 20 horas, cujo projeto de abertura foi, também, proposto, organizado e coordenado por mim.
DIAS, Carlos Magno Corrêa - 2025
Além da definição, propriedades e exemplos de aplicação, objetivando mostrar o quão importante são as Funções Recursivas Parciais, considerei a necessidade de se distinguir entre “Funções Totais” e “Funções Parciais” para se garantir terminação, correção e segurança (tanto em Linguagens Funcionais quanto em Teoria da Computação).
No curso em referência, inovador naquela época e há algum tempo considerado um marco, apresentei, ainda, a chamada “Tese de Church-Turing” segundo a qual se vem afirmar “que qualquer função que pode ser calculada por um algoritmo (em qualquer Modelo de Computação, como uma Máquina de Turing) é uma Função Recursiva Parcial”. No geral, “a classe das Funções Recursivas Parciais é considerada como a formalização precisa da noção intuitiva de um algoritmo”.
Uma vez mais apresentei elogios ao genial Alan Mathison Turing (1912-1954) aquele que é o “Pai da Computação Moderna” e um dos pioneiros da Inteligência Artificial.
Carlos Magno Corrêa Dias
24/09/2025