FUNCOES PARCIAIS RECURSIVAS E FUNCOES PARCIALMENTE TURING-COMPUTAVEIS: UMA PROVA DE EQUIVALENCIA

NA DÉCADA DE 30 DO SÉCULO PASSADO, FORAM OFERECIDAS VÁRIAS VERSÕES FORMAIS PARA A NOÇÃO INTUITIVA DE FUNÇÃO ALGORÍTMICA. DENTRE ELAS, A VERSÃO DAS FUNÇÕES RECURSIVAS E A VERSÃO DAS FUNÇÕES TURING-COMPUTÁVEIS. POSTERIORMENTE, TAIS VERSÕES FORAM ESTENDIDAS A FIM DE ABRANGER TAMBÉM AS FUNÇÕES PARCIAIS ALGORÍTMICAS, DANDO ORIGEM, DESTE MODO, À VERSÃO DAS FUNÇÕES PARCIAIS RECURSIVAS E À VERSÃO DAS FUNÇÕES PARCIALMENTE TURING-COMPUTÁVEIS. NESSE CONTEXTO, ESTA PESQUISA, SITUADA DENTRO DO DOMÍNIO DA TEORIA DA COMPUTABILIDADE E CONSTRUÍDA À LUZ DOS PRESSUPOSTOS TEÓRICOS DE DAVIS (1982), MENDELSON (2009), DIAS E WEBER (2010), ROGERS (1987), SOARE (1987), COOPER (2004), ENTRE OUTROS, DESTINA-SE A RECONSTRUIR A PROVA DE QUE AS REFERIDAS VERSÕES FORMAIS DADAS PARA A NOÇÃO INTUITIVA DE FUNÇÃO PARCIAL ALGORÍTMICA, APESAR DE CONCEITUALMENTE DISTINTAS, SÃO EXTENSIONALMENTE EQUIVALENTES NO SENTIDO DE QUE ELAS DETERMINAM O MESMO CONJUNTO DE FUNÇÕES NUMÉRICAS. COMO PARTE DESTA RECONSTRUÇÃO, PROVAREMOS, DE MODO INÉDITO, MEDIANTE O USO DE QUÍNTUPLAS, QUE TODA FUNÇÃO PARCIAL RECURSIVA É PARCIALMENTE TURING-COMPUTÁVEL. NA LITERATURA ESPECIALIZADA, ESSE TEOREMA É PROVADO POR MEIO DE UM CONJUNTO DE QUÁDRUPLAS. PORÉM, DEFININDO UM CONJUNTO DE MENOR CARDINALIDADE CONSTITUÍDO POR QUÍNTUPLAS, É POSSÍVEL PROVÁ-LO EM UM INTERVALO MENOR DE TEMPO, O QUE REPRESENTA UM GANHO DO PONTO DE VISTA COMPUTACIONAL. ALÉM DE APRESENTAR ESSA PROVA ALTERNATIVA, POSTO PELA TESE DE CHURCH-TURING QUE O CONJUNTO DAS FUNÇÕES PARCIAIS RECURSIVAS CONTÉM TODAS AS FUNÇÕES PARCIAIS ALGORÍTMICAS, INVESTIGAREMOS SE ELE PRÓPRIO E OS SEUS INFINITOS SUBCONJUNTOS SÃO OU NÃO ALGORÍTMICOS. NESTA INVESTIGAÇÃO, DEMONSTRAREMOS, EM TERMOS ARITMÉTICOS, COM O AUXÍLIO DO TEOREMA DE RICE, QUE EMBORA O CONJUNTO DAS FUNÇÕES PARCIAIS RECURSIVAS SEJA ALGORÍTMICO, TODOS OS SEUS SUBCONJUNTOS DIFERENTES DO CONJUNTO VAZIO NÃO O SÃO, DENTRE OS QUAIS ESTÃO O CONJUNTO DAS FUNÇÕES RECURSIVAS E O CONJUNTO DAS FUNÇÕES RECURSIVAS PRIMITIVAS.