FUNÇÕES RECURSIVAS PRIMITIVAS: CARACTERIZAÇÃO E ALGUNS RESULTADOS

A CLASSE DAS FUNÇÕES RECURSIVAS PRIMITIVAS NÃO CONSTITUI UMA VERSÃO FORMAL PARA A CLASSE DAS FUNÇÕES ALGORÍTMICAS, ESTUDAMOS ESTA CLASSE ESPECIAL DE FUNÇÕES NUMÉRICAS DEVIDO AO FATO DE QUE MUITAS DAS FUNÇÕES CONHECIDAS COMO ALGORÍTMICAS SÃO RECURSIVAS PRIMITIVAS. A ABORDAGEM ACERCA DA CLASSE DAS FUNÇÕES RECURSIVAS PRIMITIVAS TEM COMO OBJETIVO EXPLORAR ESTA CLASSE ESPECIAL DE FUNÇÕES E, A PARTIR DISTO, APRESENTAR SOLUÇÕES PARA OS SEGUINTES PROBLEMAS: (1) DADA A CLASSE DAS DERIVAÇÕES RECURSIVAS PRIMITIVAS, HÁ UM ALGORITMO, OU SEJA, UM PROCEDIMENTO MECÂNICO, PARA RECONHECER DERIVAÇÕES RECURSIVAS PRIMITIVAS? (2) EXISTE UMA FUNÇÃO UNIVERSAL PARA A CLASSE DAS FUNÇÕES RECURSIVAS PRIMITIVAS? SE SIM, ESSA FUNÇÃO É RECURSIVA PRIMITIVA? (3) TODA FUNÇÃO ALGORÍTMICA É RECURSIVA PRIMITIVA? PARA APRESENTAR SOLUÇÕES PARA ESTAS QUESTÕES, NOS PAUTAMOS NO MÉTODO HIPOTÉTICO-DEDUTIVO E ARGUMENTAMOS COM BASE NOS MANUAIS DE DAVIS (1982), MENDELSON (2009), DIAS E WEBER (2010), ROGERS (1987), SOARE (1987), COOPER (2004), ENTRE OUTROS. APRESENTAMOS A TEORIA DAS MÁQUINAS DE TURING, QUE CONSTITUI UMA VERSÃO FORMAL PARA A NOÇÃO INTUITIVA DE ALGORITMO, E, EM SEGUIDA, A FAMOSA TESE DE CHURCH-TURING, A QUAL IDENTIFICA A CLASSE DAS FUNÇÕES ALGORÍTMICAS COM A CLASSE DAS FUNÇÕES TURING-COMPUTÁVEIS. EXIBIMOS A CLASSE DAS FUNÇÕES RECURSIVAS PRIMITIVAS, E MOSTRAMOS QUE A MESMA CONSTITUI UMA SUBCLASSE DAS FUNÇÕES TURING-COMPUTÁVEIS. TENDO EXPLORADO A CLASSE DAS FUNÇÕES RECURSIVAS PRIMITIVAS, COMO RESULTADOS, PROVAMOS QUE EXISTE UM ALGORITMO RECONHECEDOR PARA A CLASSE DAS DERIVAÇÕES RECURSIVAS PRIMITIVAS; QUE EXISTE UMA FUNÇÃO UNIVERSAL PARA A CLASSE DAS FUNÇÕES RECURSIVAS PRIMITIVAS A QUAL NÃO PERTENCE A ESTA CLASSE; E QUE NEM TODA FUNÇÃO ALGORÍTMICA É RECURSIVA PRIMITIVA.