Open Access Te Herenga Waka-Victoria University of Wellington
Browse

Topics in Computability

Download (762.05 kB)
thesis
posted on 2025-01-29, 00:56 authored by Sapir Ben-Shahar

This thesis studies two topics in computability. The first is about computable metric and Polish spaces. We compare different notions of effective presentability and construct some spaces that are 'almost computable', in the sense that they do not have a computable presentation but they do have both left-c.e. and right-c.e. presentations. The second part studies c.e. Quasi-degrees (Q-degrees) and c.e. strong Quasi-degrees (sQ-degrees), which have interesting connections to algebra. We show that the c.e. sQ-degrees are not distributive, embed the lattice $N_5$ into them and show that no initial segment forms a lattice. We construct a non-computable c.e. set that has no c.e. simple set Q-below it. We also briefly study the relationship of sQ-degrees to wtt-degrees. Finally we show there is a minimal pair of sQ-degrees within the same Q-degree, and that if a degree is half of a minimal pair in the Q-degrees, it is also half of a minimal pair in the Turing degrees.

History

Copyright Date

2025-01-29

Date of Award

2025-01-29

Publisher

Te Herenga Waka—Victoria University of Wellington

Rights License

Author Retains Copyright

Degree Discipline

Mathematics

Degree Grantor

Te Herenga Waka—Victoria University of Wellington

Degree Level

Masters

Degree Name

Master of Science

ANZSRC Socio-Economic Outcome code

280118 Expanding knowledge in the mathematical sciences

ANZSRC Type Of Activity code

1 Pure basic research

Victoria University of Wellington Item Type

Awarded Research Masters Thesis

Language

en_NZ

Victoria University of Wellington School

School of Mathematics and Statistics

Advisors

Melnikov, Sasha; Downey, Rod