PPgSC/UFRN
PROGRAMA DE PÓS-GRADUAÇÃO EM SISTEMAS E COMPUTAÇÃO
ADMINISTRAÇÃO DO CCET
Phone:
(84)3342-2225/115
E-mail:
ppgsc@ppgsc.ufrn.br
https://posgraduacao.ufrn.br/ppgsc

DISCENTE : CLAUDIO ANDRÉS CALLEJAS OLGUÍN

DATA : 29/07/2016

HORA: 17:30

LOCAL: Sala 77 do DEST/CCET

TÍTULO:

A topological and domain theoretical study of total computable functions

PALAVRAS-CHAVES:

Computability, total computable functions, topological spces, metrics, Scott topology, algebraic domains.

PÁGINAS: 70

GRANDE ÁREA: Ciências Exatas e da Terra

ÁREA: Ciência da Computação

SUBÁREA: Teoria da Computação

ESPECIALIDADE: Computabilidade e Modelos de Computação

RESUMO:

By the Church thesis any theoretic approach to the class of partial computable functions comes to exactly the same class of functions. Each of these approaches when restricted to the class of total computable functions do not come free of an undecidable component. In particular recursion theory inductively defines this later class from some basic functions and a few constructs, where one of them called restricted minimalization can only be applied to a subclass called regular computable functions which is undecidable.

Topologically the class of total computable functions has been studied only in an extensional way as a subspace of a Baire space and as an induced topology of an Scott topology for the partial functions (not necessarily computable). Both approaches boil down to the same topology.

In this dissertation an intentional and extensional study of the class of total computable functions is made. In the first case a topology on the index set of this class is build as an initial topology of an inverse limit space that is (as always required) a subspace of a product space that in this case is build from an indexed family of metric spaces. In the second case a novel

Scott topology for this class is constructed which is bound to a novel generalization of algebraic domains coined as algebraic quasi-domains having the class of total computable functions proved to be an example of this first-order structure. Through the later Scott topology a necessary condition for the regular computable functions is obtained. All these three topologies are proved to be pairwise not homeomorphic.

As a byproduct of the second case an Scott topology for the class of total functions (not necessarily computable) is presented. It is proved that this topology is not homeomorphic to the Baire space, wherefore the former is a compact topology but the later has a topology that fails to satisfy this property.

It is also proved that all these topologies in the class of total functions and in the subclass of total computable functions have the set of total functions with finite support as a common dense set. Analogously it is proved that the topology in the index set of the class of total computable functions have as a dense set the indexes corresponding to a computable enumeration without repetition of the set of total functions with finite support.

MEMBROS DA BANCA:

Presidente - 2212166 - BENJAMIN RENE CALLEJAS BEDREGAL

Interno - 1345816 - REGIVAN HUGO NUNES SANTIAGO

Externo ao Programa - 1549905 - FAGNER LEMOS DE SANTANA

Externo à Instituição - JORGE PETRUCIO VIANA - UFF

Externo à Instituição - WILSON ROSA DE OLIVEIRA JUNIOR - UFRPE

SIGAA | Superintendência de Tecnologia da Informação - (84) 3342 2210 | Copyright © 2006-2024 - UFRN - sigaa11-producao.info.ufrn.br.sigaa11-producao