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.
974
questions
5
votes
0
answers
207
views
Is there a transfinite version of Post's Theorem?
Let $\emptyset^{(n)}$ denote the $n$th Turing jump of the empty set. Post's theorem states:
A set $B$ is $\Sigma^0_{n+1}$ if and only if $B$ is recursively enumerable by an oracle Turing machine with ...
5
votes
1
answer
204
views
Is there an injective homomorphism on the Turing degrees?
I know that the existence of a non-trivial automorphism of the Turing degrees is a long-standing open problem. I am curious to know if something is known about (non-trivial) injective homomorphisms (...
5
votes
1
answer
99
views
Understanding the definition of a (computably / continuously) “transparent” function
The following definitions of a “transparent function” are essentially taken from references [1] (where it is called a “jump operator”), [2] and [3], except that the variation “primitively recursively ...
5
votes
1
answer
440
views
How to solve this exercise about large countable ordinals?
In this note (Notes on Higher Type ITTM-recursion, 2021) written by Philip Welch, I'm trying to solve exercise 3.5(i), but I don't know how to solve it.
The problem is: assume that $L_{\gamma_0}<_{...
5
votes
2
answers
262
views
Is the usual enumeration of $\mathsf{PA}$ "minimal for consistency strength"?
This question is about a technical imprecision which is easily avoidable but whose details I'd like to understand better. When we refer to "the consistency strength of $\mathsf{PA}$" (say) ...
1
vote
0
answers
90
views
What computable pseudo-ordinals are there with initial segment $\omega_1^{CK}(1+\eta+1)$?
The notion of a “computable pseudo-ordinal”, i.e. a computable linear order with no hyperarithmetical descending chains, is an old one going back to Stephen Kleene. Joe Harrison wrote the definitive ...
1
vote
1
answer
84
views
Intersection of (relativized/preimage) measure 0 with every hyperarithmetic perfect set
Given a perfect tree $T$ on $2^{<\omega}$ viewed as a function from $2^{<\omega}$ to $2^{<\omega}$ define the measure of a subset of $[T]$ to be the measure of it's preimage under the usual ...
6
votes
1
answer
501
views
Parameter-free effective cardinals
In the paper "Effective cardinals and determinacy in third order arithmetic" by Juan Aguilera, effective cardinals is defined.
I'm curious about its little variation, parameter-free ...
4
votes
1
answer
494
views
Complexity of |a| < |b| for ordinal notations?
What is the complexity (e.g. is it $\Sigma^0_1$, arithmetic, fully $\Pi^1_1$) of the relation $|a| < |b|$ given two notations $a, b \in \mathscr{O}$ (Kleene's O)?
What about the case where only one ...
2
votes
0
answers
118
views
Higher-order oracle computation of reals and axiom of constructibility
Certain real numbers can be approximated arbitrarily well by computable functions. If we introduce halting oracles, then more real numbers can be "computed", like Chaitin's constant or the ...
4
votes
0
answers
109
views
A kind of “weak” filtered colimit in the effective topos
I was recently reminded that even filtered colimits in the effective topos generally do not exist. However, there is an important (albeit restrictive) situation that looks a lot like them and that I ...
2
votes
1
answer
110
views
Maximal chains of order type $\omega_1^{ck}$ in computable partial orders?
Can a computable partial order have a maximal chain of order-type $\omega_1^{ck}$? My instinct is to say no, of course not, but I can't actually make the argument. If the p.o. also has chains of ...
5
votes
1
answer
245
views
(When) do filtered colimits exist in the effective topos?
(My apologies if this is well-known: I feel that I'm missing something very obvious here.)
Basic question: Do filtered colimits exist in the effective topos?
The reason I feel I'm missing something ...
4
votes
0
answers
173
views
Some questions on a paper of Gerald Sacks
I've been reading Sacks' Countable admissible ordinals and hyperdegrees as I'm interested in Theorem 5.3 of the paper:
Let $M$ be a countable standard model of $\mathsf{ZF}$ and $V=L$. Suppose $\...
3
votes
0
answers
69
views
What are all the order types of maximal chains of $\Delta^0_2$ sets?
A set of natural numbers is $\Delta^0_2$ if it’s computable from the halting set. Consider the quasi-order/pre-order of all $\Delta_0^2$ sets ordered by $m$-reduction, or equivalently consider the ...
2
votes
1
answer
107
views
$\Pi^0_2$ singleton forming minimal pair with $0''$
Is there a $\Pi^0_2$ singleton that forms a minimal pair with $0''$? That is, is there a set $X$ such that $X$ is the unique solution to $\forall x \exists y \phi(X|_y, x)$, $X$ and $0''$ are ...
7
votes
1
answer
385
views
Gaps in the ordinals writable by Ordinal Turing Machines with a single countable parameter
Let $W(\alpha)$ denote the set of all (countable) ordinals writable by Ordinal Turing Machines with a single (countable) parameter $\alpha$, i.e. each computation starts with a single ($\alpha$-th) ...
7
votes
1
answer
438
views
Is the isomorphism problem solvable for torsion-free groups?
Given two finite presentations of torsion-free groups, is there an algorithm to determine whether the given groups are isomorphic or not?
I have found results for narrower classes (for example, they ...
6
votes
1
answer
626
views
Hilbert's tenth problem for equations with finitely many solutions
Is there a known example of a set $S$ of Diophantine equations such that
$S$ is computable;
it is a theorem that every equation in $S$ has (at most) finitely many solutions;
the function that maps an ...
4
votes
1
answer
69
views
Effectively non-arithmetic $\omega$-REA degrees
Say that a function $f \in \omega^\omega$ witnesses that an $\omega$-REA set $A = \bigoplus_{i \in \omega} A^{[i]}$ is non-arithmetic if $A^{[\leq f(n)]} \not\leq_T 0^n$. Say that $A$ is effectively ...
5
votes
0
answers
91
views
Entailment in one-point extensions of standard-enough models
This is one of two questions about the power of "one-point extensions" in reverse mathematics. This one focuses on what separations can be achieved as one-point extensions of as-closed-as-...
8
votes
1
answer
380
views
Good source for admissible set theory?
So I need to writeup some old results of Harrington's which imply various results about admissible ordinals. I've never really learned admissible recursion theory so what's a good reference?
1
vote
0
answers
45
views
Is $0^{\omega}$ a minimal cover of a minimal arithmetic degree?
Is there a minimal arithmetic degree $d <_a 0^{\omega}$ such that $0^{\omega}$ is a minimal cover of $d$ in the arithmetic degrees? [1]
While whether or not $0^{\omega}$ is a minimal cover at all (...
1
vote
2
answers
122
views
Double Posner-Robinson Join (or a cupping analog of minimal pair)
Are there incompatible degrees $D_0, D_1 <_T 0'$ such that for all $X$ if $D_0 \oplus X \equiv_T D_1 \oplus X \equiv_T 0'$ then $X \equiv_T 0'$? So kinda like a cupping analog of a minimal pair.
...
1
vote
1
answer
107
views
Double Hop Inversion Theorem
The hop $H_e$ is defined by $H_e(X) = X \oplus W_e^{X}$. A 2-REA operator (or double hop) $J_{\langle e,i\rangle}$ is defined by $J_{\langle e,i\rangle}(X) = H_e(H_i(X))$
By a famous result from ...
2
votes
0
answers
87
views
decidability special case of column generation problem
I have the following problem:
Input: sub-spaces $V_1, \dots, V_d$ of $\mathbb{Z}^{d}$
Question: are there $v_i \in V_i$ such that the matrix $(v_1, \dots, v_d)$ has determinant $\pm 1$ (equivalently, ...
1
vote
0
answers
37
views
Are the $\omega$-generic arithmetic degrees downward closed
A degree is $\alpha$-generic if it has representative that is $\alpha$-generic. Are the $\omega$-generic arithmetic degrees (i.e. the degree structure induced by arithmetic reproducibility) downward ...
3
votes
1
answer
90
views
Does every arithmetic degree below $0^\omega$ have a representative computable in $0^\omega$?
Suppose that $A \leq_a 0^\omega$ (i.e. $A$ is arithmetic in $0^\omega$) does there exist $\widehat{A} \equiv_a A$ with $\widehat{A} \leq_T 0^\omega$ [1]?
More generally, say that a set $X$ is aT-...
18
votes
4
answers
2k
views
Theorems in set theory that use computability theory tools, and vice versa
I recently learnt that the proof of the classical theorem "$\mathsf{AD}$ $\implies$ $\aleph_1$ is measurable" uses computability theory tools (or at least one of its proofs does so). I'm ...
3
votes
0
answers
91
views
Logical strength of the pigeon-hole principle for measure spaces
In his book on measure theory, Tao discuss the pigeon-hole principle for measure spaces, which expresses that the union of measure zero sets is again measure zero.
I am interested in the logical ...
2
votes
1
answer
114
views
Arithmetically-hyperimmune-free degrees are comeager
I think proposition XIII.1.22 of Odifreddi is false but I wanted to check I wasn't being dumb. Here's the claim.
Definition: The set$^1$ $A$ is arithmetically-hyperimmune-free if every function $f$ ...
17
votes
1
answer
567
views
Aperiodic monotile in $\mathbb{R}$
Motivation. Recently a group of researchers found an aperiodic monotile in $\mathbb{R}^2$, answering a long-standing question. There are many results in higher dimensions, so let's explore the lower ...
2
votes
1
answer
161
views
How can Kőnig's Lemma be expressed in Monadic Second-Order Logic of 2 Successors?
I read the following on Wikipedia's page on Monadic Second-Order Logic of Two Successors (MS2S):
Weak S2S (WS2S) requires all sets to be finite (note that finiteness
is expressible in S2S using Kőnig'...
1
vote
0
answers
41
views
Base of cone of arithmetic minimal covers
By Borel determinacy (exercisce XIII.1.7 in Odifreddi) there is a cone of minimal covers in the arithmetic degrees. Is the base of such a cone known? A minimal such base?
For that matter, is it even ...
6
votes
3
answers
433
views
Is $0^{(\omega)}$ a minimal cover in the arithmetic degrees
Is it known if $0^{(\omega)}$ a minimal cover in the arithmetic degrees? In the Turing degrees to show that $0'$ (indeed $0^{(n)}$) isn't a minimal cover one uses the density of r.e. degrees. ...
1
vote
0
answers
42
views
No arithmetic degree that always joins to arithmetic minimal cover
Is there (I strongly presume not but not seeing how to show it) a (non-zero) arithmetic degree $a$ such that for all arithmetic degrees $e \not\geq_a a$ we have $e \oplus a$ is a minimal cover of $e$ ...
2
votes
3
answers
133
views
Incompatible degrees $a,b$ s.t. $x < a$ implies $x \leq b$
Are there incompatible Turing degrees $a,b$ s.t any degree computable in $a$ either computes $a$ or is computed by $b$?
Obviously, if $a$ was above $b$ then $a$ would be a strong minimal cover of $b$. ...
1
vote
0
answers
84
views
Derive a closed-form expression of this recursive formula
$$\begin{equation}
S(r,k) = f(r)S(0,k-1) + g(r)S(r+1,k-1)
\end{equation}\ ,$$
where $r=0,1,2,\dots$ and $k=1,2,3,\dots$ . Also, $0<f(r)<1$ is an increasing function and $0<g(r)<1$ is a ...
2
votes
0
answers
155
views
f(f(x)) computable but f(f(f(x))) not computable
Like the title says, I am looking for a function f from N to N such that f(f(x)) is computable but f(f(f(x))) is not. I think it should exist, because i dont see how knowing how to calculate f(f(x)) ...
4
votes
1
answer
226
views
Classification of simple modules for the free algebra
Let $A=K\langle x,y\rangle$ be the free associative algebra in two generators over a field $K$ (we can assume that the field is algebraically closed or even $K=\mathbb{C}$ first if that helps)
...
2
votes
0
answers
87
views
Can one extend higher randomness theory to the entire analytical hierarchy under certain large cardinal assumptions?
In the "Recursion Theory" book by C.T Chong, Liang Yu, towards the end of the book they list a few "open" research areas connected to higher computability theory. One such ...
2
votes
1
answer
184
views
A question about computability and Turing machines Part 2
I asked a question a few days ago and got a response
But my follow-up question was not answered (maybe my email was not sent successfully)
A question about computability and Turing machines
My quesion ...
2
votes
1
answer
276
views
A question about computability and Turing machines
For any recursively enumerable set theory $T$ (of consistency strength at least superior to KP), if we want to calculate $F(n)=\{F(m):m∈ω∧mEn\}$ and can determine each $F(n)$ for a Henkin model $(ω,E)$...
2
votes
3
answers
108
views
If the join of two degrees compute one of their jumps, what can we say about the jump of the other degree?
Let $\mathbf{a}$ and $\mathbf{b}$ be two Turing degrees such that $\mathbf{a'} = \mathbf{a} \oplus \mathbf{b}$. Must it be the case that $\mathbf{a'} \leq \mathbf{b'}$? What if in addition, we know ...
4
votes
4
answers
447
views
Automatically generating combinatorial conjectures
It very often happens that one reduces a problem to a bunch of combinatorial data, and need to sift through this data for patterns, which form conjectures on which to do "real" mathematics. ...
6
votes
3
answers
339
views
Intuition behind Kleene's “second algebra” $\mathcal{K}_2$
The “second Kleene algebra” $\mathcal{K}_2$ is defined, e.g. here on nLab, or in section 1.4.3 of van Oosten's book Realizability: an Introduction to its Categorical Side (2008), or as example 3.4 of ...
-2
votes
1
answer
230
views
Are there any non-elementary functions that are computable?
Does a function $\mathit{f}:\mathbb{R}→\mathbb{R}$ being non-elementary (not expressible as a combination of finitely many elementary operations), imply that it is not computable?
The particular case ...
9
votes
2
answers
916
views
What theories are larger than the real closed field but still decidable?
It's well known that sentences about the real closed field can be decided by algorithm and the complexity of this is about $d^{2^{O(n)}}$ where $d$ is the product of the degrees of polynomials in the ...
2
votes
1
answer
140
views
Computability of fillability of unit cube in $\mathbb{R}^n$ by $k$ $\varepsilon$-balls
Let $\mathbb{N}$ denote the set of positive integers. We define a relation $R \subseteq \mathbb{N}^4$ in the following way:
$(p,q,n,s)\in R$ if and only if there is $S\subseteq [0,1]^n$ with $|S| = s$...
3
votes
0
answers
189
views
Which arxiv-category should computability theory be submitted to?
There are two categories on the arXiv that seem like a potential fit for computability research to me, although none of them explicitly lists it in the description. These would be:
cs.LO
Covers all ...