Banca de DEFESA: VICTOR PEREIRA GOMES

Uma banca de DEFESA de MESTRADO foi cadastrada pelo programa.
DISCENTE: VICTOR PEREIRA GOMES
DATA: 21/06/2016
HORA: 09:00
LOCAL: CCHLA - UFPB
TÍTULO: Funções recursivas primitivas: caracterização e alguns resultados para esta classe de funções
PALAVRAS-CHAVES: Palavras-chave: funções algorítmicas, funções recursivas primitivas, algoritmo reconhecedor, função universal.
PÁGINAS: 96
GRANDE ÁREA: Ciências Humanas
ÁREA: Filosofia
SUBÁREA: Lógica
RESUMO: A classe das funcoes recursivas primitivas nao constitui uma versao formal para a classe das funcoes algoritmicas, estudamos esta classe especial de funcoes numericas devido ao fato de que muitas das funcoes conhecidas como algoritmicas sao recursivas primitivas. A abordagem acerca da classe das funcoes recursivas primitivas tem como objetivo explorar esta classe especial de funcoes e, a partir disto, apresentar solucoes para os seguintes problemas: (1) dada a classe das derivacoes recursivas primitivas, ha um algoritmo, ou seja, um procedimento mecanico, para reconhecer derivacoes recursivas primitivas? (2) Existe uma funcao universal para a classe das funcoes recursivas primitivas? Se sim, essa funcao e recursiva primitiva? (3) Toda funcao algoritmica e recursiva primitiva? Para apresentar solucoes para estas questoes, nos pautamos no metodo hipotetico-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 maquinas de Turing, que constitui uma versao formal para a nocao intuitiva de algoritmo, e, em seguida, a famosa tese de Church-Turing, a qual identifica a classe das funcoes algoritmicas com a classe das funcoes Turing-computaveis. Exibimos a classe das funcoes recursivas primitivas, e mostramos que a mesma constitui uma subclasse das funcoes Turing-computaveis. Tendo explorado a classe das funcoes recursivas primitivas, como resultados, provamos que existe um algoritmo reconhecedor para a classe das derivacoes recursivas primitivas; que existe uma funcao universal para a classe das funcoes recursivas primitivas a qual nao pertence a esta classe; e que nem toda funcao algoritmica e recursiva primitiva.
MEMBROS DA BANCA:
Presidente - 329455 - MATIAS FRANCISCO DIAS
Interno - 334109 - ANA LEDA DE ARAUJO
Externo ao Programa - 1345968 - GARIBALDI MONTEIRO SARMENTO
Externo à Instituição - AMERICO AUGUSTO NOGUEIRA VIEIRA