Banca de DEFESA: CLAUDIO ANDRÉS CALLEJAS OLGUÍN

Uma banca de DEFESA de DOUTORADO foi cadastrada pelo programa.
DISCENTE : CLAUDIO ANDRÉS CALLEJAS OLGUÍN
DATA : 29/07/2016
HORA: 14:00
LOCAL: Auditório B321 do IMD
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