Zobrazeno 1 - 10
of 832
pro vyhledávání: '"Ng, Keng"'
Answering an open question raised by Cooper, we show that there exist $\Delta^0_2$ sets $D$ and $E$ such that the singleton degree of $E$ is a minimal cover of the singleton degree of $D$. This shows that the $\Sigma^{0}_{2}$ singleton degrees, and t
Externí odkaz:
http://arxiv.org/abs/2412.18991
Autor:
Kihara, Takayuki, Ng, Keng Meng
In this article, we introduce a notion of reducibility for partial functions on the natural numbers, which we call subTuring reducibility. One important aspect is that the subTuring degrees correspond to the structure of the realizability subtoposes
Externí odkaz:
http://arxiv.org/abs/2411.06043
Autor:
Hölzl, Rupert, Ng, Keng Meng
The Weihrauch degrees are a tool to gauge the computational difficulty of mathematical problems. Often, what makes these problems hard is their discontinuity. We look at discontinuity in its purest form, that is, at otherwise constant functions that
Externí odkaz:
http://arxiv.org/abs/2405.04338
We prove that every finite distributive lattice is isomorphic to a final segment of the d.c.e. Turing degrees (i.e., the degrees of differences of computably enumerable sets). As a corollary, we are able to infer the undecidability of the EAE-theory
Externí odkaz:
http://arxiv.org/abs/2403.04254
We investigate what it means for a (Hausdorff, second-countable) topological group to be computable. We compare several potential definitions in the literature. We relate these notions with the well-established definitions of effective presentability
Externí odkaz:
http://arxiv.org/abs/2209.04617
Let $K$ denote prefix-free Kolmogorov Complexity, and $K^A$ denote it relative to an oracle $A$. We show that for any $n$, $K^{\emptyset^{(n)}}$ is definable purely in terms of the unrelativized notion $K$. It was already known that 2-randomness is d
Externí odkaz:
http://arxiv.org/abs/2208.02982
Autor:
Bagaviev, Ramil, Batyrshin, Ilnur I., Bazhenov, Nikolay, Bushtets, Dmitry, Dorzhieva, Marina, Koh, Heer Tern, Kornev, Ruslan, Melnikov, Alexander G., Ng, Keng Meng
Publikováno v:
In Annals of Pure and Applied Logic January 2025 176(1)
Autor:
Vukajlovic, Djurdja, Timmons, Rory, Macesic, Stevan, Sanderson, John, Xie, Fengwei, Abdelghany, Tarek M., Smith, Emma, Lau, Wing Man, Ng, Keng Wooi, Novakovic, Katarina
Publikováno v:
In International Journal of Biological Macromolecules September 2024 276 Part 1
Publikováno v:
Computability, vol. 11 (2022), no. 3-4, pp. 187-221
The complexity of equivalence relations has received much attention in the recent literature. The main tool for such endeavour is the following reducibility: given equivalence relations $R$ and $S$ on natural numbers, $R$ is computably reducible to $
Externí odkaz:
http://arxiv.org/abs/2109.04055