Sobre a existência ou inexistência de uma função universal para a classe das funções recursivas primitivas

Abstract

Embora a classe das funções recursivas primitivas não constitua uma versão formal para a classe de todas as funções algorítmicas, estuda-se esta classe especial de funções numéricas pelo fato de que muitas das funções conhecidas como algorítmicas são recursivas primitivas. Tomando em consideração esta classe de funções, o presente artigo destina-se a solucionar o seguinte problema: existe uma função universal para a classe das funções recursivas primitivas? Se sim, ela é recursiva primitiva? Para apresentar solução para este problema, a argumentação será realizada com base nos manuais de Cooper (2004), Davis (1982), Dias & Weber (2010), Mendelson (2009), Rogers (1987), Soare (1987, 2016), entre outros. Como resultado, é demonstrado, em termos matematicamente precisos, que embora tal função universal exista, ela não é recursiva primitiva.