# 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.

694 questions
Filter by
Sorted by
Tagged with
67 views

387 views

### Does every cofinal branch through Kleene's O compute true arithmetic?

My question concerns cofinal branches through Kleene's $O$, which is a set of natural numbers and a computably enumerable relation $<_O$ on this set that provides ordinal denotations for any ...
58 views

### Constructing Turing degrees near $\mathcal{O}$

I'm looking for some examples of constructions for Turing degrees close to, but not above, Kleene's $\mathcal{O}$. I know of one by Jockusch and Simpson using forcing with hyperarithmetic, uniformly ...
438 views

189 views

155 views

### Detecting comprehension topologically

This question basically follows this earlier question of mine but shifting from standard systems of nonstandard models of $PA$ to $\omega$-models of $RCA_0$. For $X$ a Turing ideal we get the map $c_X$...
165 views

### Combinatorially defined effectively closed set

Is there a combinatorially defined, nonempty effectively closed set $Q\subseteq 2^\omega$ such that all members of $Q$ are incomputable? Combinatorially defined means that the definition of $Q$ does ...
213 views

### The “higher topology” of countable Scott sets

Fix some computable bijection $b$ between $\omega$ and $2^{<\omega}$. For $r\in 2^\omega$, let $$[r]=\{f\in 2^\omega: \forall\sigma\prec f(b^{-1}(\sigma)\in r)\}$$ be the closed subset of Cantor ...
32 views

### Is every productive set not Martin-Lof random？

every productive set is not Martin-Lof random，and so are some immune set.Therefore,do we have to have a definition for productive sets and such immune set which is different from Martin-Lof ...
64 views

### Non-relativized, Computable and Schnor randomness w.r.t a measure

Riemann and Slaman have some great work classifying what reals are 1-random with respect to a measure $\mu$ relative to $\mu$. In that paper they cite Levin and Kautz (but not to refs I can find) for ...
61 views

255 views

### The expressiveness of functions computable on trees

Motivation: Let's define a function computable on a $k$-ary tree as a function composed with simpler computable functions defined at each node such that a function of this kind defined on a binary ...
91 views

### Does relationship between c.e.set, productive set, immune set, ML-random set exist between sets of class of other level

Is relationship between c.e.set, productive set, immune set, ML-random set similar to relationship between polynomial complexity set, polynomial complexity-productive set, P-immune set, P-random set?
205 views

### Large “computably un-simplifiable” computable well-orderings

Question Suppose $A,X$ are computable well-orderings. Say that $A$ is $X$-unsimplifiable if there is no computable well-ordering $B$ whose ordertype is strictly less than that of $A$ but such that ...
340 views

### Is the Hilbert space-filling curve bijective over computable numbers?

The Hilbert curve is a continuous space-filling curve that maps $I$ to $I^n$ where $I$ denotes the unit interval . Like all other space-filling curves, it is not one-to-one. I am wondering if the ...
174 views

### Turing-independent joins

Define $Y \subseteq 2^{\omega}$ to be Turing independent if for every finite $F \subseteq Y$ and $y \in Y \setminus F$, the Turing join of $F$ does not compute $y$. Define $X \subseteq 2^{\omega}$ ...
101 views

### Are all $P$-noncomputable sets $P$-random? [duplicate]

$P$ means polynomial complexity. $S_p$ is class of all $P$_random sets, and $S_{pc}$ is class of all $P$ incomputable sets, is $S_{pc} \setminus S_p$ empty? If not empty, any example? what is the ...
242 views

### Relationship between P-noncomputable and P-random sets

$P$ means polynomial complexity. $S_p$ is the class of all $P$_random set, and $S_{pc}$ is the class of all $P$ incomputable sets, is $S_p \bigcap S_{pc}$ empty? If not empty, any example? what is ...
279 views

### Understanding a part of Friedberg’s Priority Argument Paper

This is Richard Friedberg’s original 1957 proof of the Friedberg-Muchnik Theorem, the origin of the ground-breaking priority argument. (The result proven is that there are two recursively enumerable ...
Let $\varphi_0,\varphi_1,\varphi_2,\dots$ be an acceptable programming system. A function $f$ is extensional if, for all $x$ and $y$, $\varphi_x=\varphi_y$ implies that $\varphi_{f(x)}=\varphi_{f(y)}$....