# Questions tagged [computability-theory]

computable sets and functions, Turing degrees, c.e. degrees, models of computability, primitive recursion, oracle computation, models of computability, decision problems, undecidability, Turing jump, halting problem, notions of computable randomness, computable model theory, computable equivalence relation theory, arithmetic and hyperarithmetic hierarchy, infinitary computability, $\alpha$-recursion, complexity theory.

831 questions
Filter by
Sorted by
Tagged with
1 vote
107 views

### Why are there no "natural" occurrences of high or low r.e sets?

The notions of a low and high sets were introduced, I think by Soare, in the context of the dense structure of degrees of those sets which are neither r.e. neither recursive. My question is: Why are ...
124 views

### $\Pi^0_2$ singleton of minimal arithmetic degree?

Is it known if there is a $\Pi^0_2$ singleton of minimal arithmetic degree? To elaborate a bit, this is asking whether there is a non-arithmetic set $X$ such that for any $Y$ arithmetic in $X$ either ...
1k views

### Does permission always work?

Suppose $g$ is a total computable injective function and $f$ is a total computable function satisfying $$g(x)<f(x)$$ for all sufficiently large $x$. Then we have $ran(f)\le_Tran(g)$; basically, ...
101 views

385 views

288 views

### Different definitions of 'countable set'

There are a number of different definitions of 'countable set', all equivalent given a strong enough (classical) system. The obvious ones (injection to $\mathbb{N}$, bijection to $\mathbb{N}$, ...
### Sets $A$ such that $A$-maximal sets are $\Delta^0_2$
Recall that $M\subseteq\omega$ is maximal if it is c.e., and can be only trivially extended by other c.e. sets, i.e. if $M\subseteq N$ and $N$ is c.e., then either $\overline{N}$ or $N\setminus M$ is ...