Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA computability theoretic equivalent to Vaughts conjecture
183
0
0.0
(
0
)
Authors
Antonio Montalban
Ask ChatGPT about the research
No Arabic abstract
We prove that, for every theory $T$ which is given by an ${mathcal L}_{omega_1,omega}$ sentence, $T$ has less than $2^{aleph_0}$ many countable models if and only if we have that, for every $Xin 2^omega$ on a cone of Turing degrees, every $X$-hyperarithmetic model of $T$ has an $X$-computable copy. We also find a concrete description, relative to some oracle, of the Turing-degree spectra of all the models of a counterexample to Vaughts conjecture.
rate research
Read More
We present a formulation of the Collatz conjecture that is potentially more amenable to modeling and analysis by automated termination checking tools.
For any class of operators which transform unary total functions in the set of natural numbers into functions of the same kind, we define what it means for a real function to be uniformly computable or conditionally computable with respect to this class. These two computability notions are natural generalizations of certain notions introduced in a previous paper co-authored by Andreas Weiermann and in another previous paper by the same authors, respectively. Under certain weak assumptions about the class in question, we show that conditional computability is preserved by substitution, that all conditionally computable real functions are locally uniformly computable, and that the ones with compact domains are uniformly computable. The introduced notions have some similarity with the uniform computability and its non-uniform extension considered by Katrin Tent and Martin Ziegler, however, there are also essential differences between the conditional computability and the non-uniform computability in question.
We consider two combinatorial principles, ${sf{ERT}}$ and ${sf{ECT}}$. Both are easily proved in ${sf{RCA}}_0$ plus ${Sigma^0_2}$ induction. We give two proofs of ${sf{ERT}}$ in ${sf{RCA}}_0$, using different methods to eliminate the use of ${Sigma^0_2}$ induction. Working in the weakened base system ${sf{RCA}}_0^*$, we prove that ${sf{ERT}}$ is equivalent to ${Sigma^0_1}$ induction and ${sf{ECT}}$ is equivalent to ${Sigma^0_2}$ induction. We conclude with a Weihrauch analysis of the principles, showing ${sf{ERT}} {equiv_{rm W}} {sf{LPO}}^* {<_{rm W}}{{sf{TC}}_{mathbb N}}^* {equiv_{rm W}} {sf{ECT}}$.
We investigate the effectivizations of several equivalent definitions of quasi-Polish spaces and study which characterizations hold effectively. Being a computable effectively open image of the Baire space is a robust notion that admits several characterizations. We show that some natural effectivizations of quasi-metric spaces are strictly stronger.
Algorithmic randomness theory starts with a notion of an individual random object. To be reasonable, this notion should have some natural properties; in particular, an object should be random with respect to image distribution if and only if it has a random preimage. This result (for computable distributions and mappings, and Martin-Lof randomness) was known for a long time (folklore); in this paper we prove its natural generalization for layerwise computable mappings, and discuss the related quantitative results.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
