A topological and domain theoretical study of total computable functions

• Ano de defesa: 2016
• Autor(a) principal: Olguin, Cláudio Andrés Callejas
• Orientador(a): Bedregal, Benjamin Rene Callejas
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: por
• Programa de Pós-Graduação: PROGRAMA DE PÓS-GRADUAÇÃO EM SISTEMAS E COMPUTAÇÃO
• País: Brasil
• Palavras-chave em Português: Computabilidade; Funções totais computáveis; Espaços topológicos; Métricas; Topologia de Scott; Domínios algébricos
• Área do conhecimento CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::SISTEMAS DE COMPUTACAO
• Link de acesso: https://repositorio.ufrn.br/jspui/handle/123456789/22327

O conjunto de funções totais computáveis somente tem sido estudado topologicamente como um subespaço de um espaço de Baire. Onde a topologia deste espaço de Baire é a topologia induzida de uma topologia de Scott para as funções parciais (não necessariamente computáveis). Nesta tese constrói-se uma topologia original no conjunto de índices das funções totais computáveis e demonstra-se que ela não é homeomorfa com o subespaço do espaço de Baire que foi mencionado. Há um subconjunto indecidível importante no conjunto de funções totais computáveis chamado “o conjunto de funções computáveis regulares”, que recebe atenção especial nesta tese. Com a finalidade de fazer um estudo topológico deste conjunto constrói-se todo um aparato teórico. Após apresentar o estado da arte da teoria dos domínios generalizada introduz-se uma generalização original dos domínios algébricos nomeados como “quase domínios algébricos”. Com uma ordem parcial adequada, constrói-se um quase-domínio algébrico para o conjunto de funções computáveis totais. Por meio da topologia de Scott associada a esse quase-domínio algébrico, obtém-se uma condição necessária para as funções computáveis regulares. Fica provado que esta última topologia não é homeomorfa com o subespaço previamente mencionado do espaço de Baire apresentado. Como subproduto, introduz-se uma topologia de Scott para o conjunto de funções totais (não necessariamente computáveis). Fica provado que esta última topologia não é homeomorfa com o espaço de Baire apresentado. Fica também provado que as topologias de Scott no conjunto de funções totais e no subconjunto de funções totais computáveis têm o conjunto de funções totais com suporte finito como conjunto denso comum. Analogamente, fica provado que a topologia no conjunto índice do conjunto de funções totais computáveis tem como conjunto denso os índices correspondentes a uma enumeração computável sem repetição do conjunto de funções totais com suporte infinito.