Please use this identifier to cite or link to this item: https://repositorio.ufpb.br/jspui/handle/tede/8514
metadata.dc.type: Dissertação
Title: Funções recursivas primitivas: caracterização e alguns resultados para esta classe de funções
metadata.dc.creator: Gomes, Victor pereira
metadata.dc.contributor.advisor1: Dias, Matias Francisco
metadata.dc.description.resumo: 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.
Abstract: The class of primitive recursive functions is not a formal version to the class of algorithmic functions, we study this special class of numerical functions due to the fact of that many of the functions known as algorithmic are primitive recursive. The approach on the class of primitive recursive functions aims to explore this special class of functions and from that, present solutions for the following problems: (1) given the class of primitive recursive derivations, is there an algorithm, that is, a mechanical procedure for recognizing primitive recursive derivations? (2) Is there a universal function for the class of primitive recursive functions? If so, is this function primitive recursive? (3) Are all the algorithmic functions primitive recursive? To provide solutions to these issues, we base on the hypothetical-deductive method and argue based on the works of Davis (1982), Mendelson (2009), Dias e Weber (2010), Rogers (1987), Soare (1987), Cooper (2004), among others. We present the theory of Turing machines which is a formal version to the intuitive notion of algorithm, and after that the famous Church-Turing tesis which identifies the class of algorithmic functions with the class of Turing-computable functions. We display the class of primitive recursive functions and show that it is a subclass of Turing-computable functions. Having explored the class of primitive recursive functions we proved as results that there is a recognizer algorithm to the class of primitive recursive derivations; that there is a universal function to the class of primitive recursive functions which does not belong to this class; and that not every algorithmic function is primitive recursive.
Keywords: Funções algorítmicas
Algorithmic functions
Funções recursivas primitivas
Algoritmo reconhecedor
Função universal
Primitive recursive functions
Recognizer algorithm
Universal function
metadata.dc.subject.cnpq: CIENCIAS HUMANAS::FILOSOFIA
metadata.dc.language: por
metadata.dc.publisher.country: Brasil
Publisher: Universidade Federal da Paraíba
metadata.dc.publisher.initials: UFPB
metadata.dc.publisher.department: Filosofia
metadata.dc.publisher.program: Programa de Pós-Graduação em Filosofia
Citation: GOMES, Victor Pereira. Funções recursivas primitivas: caracterização e alguns resultados para esta classe de funções, 2016. 55 f. Dissertação (Mestrado em Filosofia) - Universidade Federal da Paraíba, João Pessoa, 2016.
metadata.dc.rights: Acesso Aberto
URI: https://repositorio.ufpb.br/jspui/handle/tede/8514
Issue Date: 21-Jun-2016
Appears in Collections:Centro de Ciências Humanas, Letras e Artes (CCHLA) - Programa de Pós-Graduação em Filosofia

Files in This Item:
File Description SizeFormat 
arquivo total.pdf952.15 kBAdobe PDFThumbnail
View/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.