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.
910
questions
2
votes
0
answers
32
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 ...
- 4,401
2
votes
1
answer
76
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 ...
- 2,261
7
votes
1
answer
305
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) ...
- 899
7
votes
1
answer
406
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 ...
- 5,250
6
votes
1
answer
553
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 ...
- 72.6k
4
votes
1
answer
62
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 ...
- 2,261
5
votes
0
answers
84
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-...
- 19.1k
8
votes
1
answer
340
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?
- 2,261
1
vote
0
answers
39
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 (...
- 2,261
1
vote
2
answers
96
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.
...
- 2,261
1
vote
1
answer
102
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,261
2
votes
0
answers
77
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, ...
- 55
1
vote
0
answers
36
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 ...
- 2,261
3
votes
1
answer
83
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-...
- 2,261
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 ...
- 904
2
votes
0
answers
69
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,877
2
votes
1
answer
109
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$ ...
- 2,261
16
votes
1
answer
524
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 ...
- 42.5k
2
votes
1
answer
146
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'...
- 123
1
vote
0
answers
37
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 ...
- 2,261
6
votes
3
answers
413
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. ...
- 2,261
1
vote
0
answers
37
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,261
0
votes
0
answers
62
views
Pseudo-isomorphicity as a polynomial-time fingerprint for graphs
Motivation. It is well-known that determining whether two graphs $G_1, G_2$ on $n$ vertices are isomorphic, is hard. The iterated degree matrix $\mathbb{D}(G)$ of a finite simple undirected graph $G$ ...
- 42.5k
2
votes
3
answers
122
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$. ...
- 2,261
1
vote
0
answers
72
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
143
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)) ...
- 363
4
votes
1
answer
179
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)
...
- 24.4k
2
votes
0
answers
71
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 ...
- 525
2
votes
1
answer
166
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 ...
- 51
2
votes
1
answer
255
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)$...
- 51
2
votes
3
answers
81
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 ...
- 1,047
4
votes
4
answers
422
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. ...
- 341
4
votes
1
answer
141
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 ...
- 26.4k
-2
votes
1
answer
190
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 ...
- 11
8
votes
2
answers
863
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 ...
- 1,450
2
votes
1
answer
135
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$...
- 42.5k
3
votes
0
answers
176
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 ...
- 3,919
17
votes
5
answers
2k
views
What are some interesting applications/corollaries of Kleene's Recursion theorem?
Lately I became very interested in the theory of computability and a fundamental early result you learn is the Recursion Theorem also known as the Fixed point theorem. At first sight you can see it's ...
- 525
6
votes
1
answer
102
views
Sets meeting and avoiding computable sets
Call a set $X$ hesive if for every infinite computable set $C$, both $C \cap X$ and $C \setminus X$ are infinite.
It's not hard to see that every hyperimmune degree computes a hesive set, but this isn'...
- 2,442
3
votes
1
answer
123
views
What's the measure of all 1-generic sets?
A set $A$ is 1-generic if it forces its jump, namely for any $e\in\omega$, there exists $\sigma\preceq A$ such that: $\Phi^{\sigma}_{e}(e)\downarrow\vee(\forall\tau\succeq\sigma)(\Phi^{\tau}_{e}(e)\...
- 33
24
votes
3
answers
3k
views
"Natural" undecidable problems not reducible to the halting problem
There is a lot of known examples of undecidable problems, a large amount of them not directly related to turing machines or equivalent models of computations, for example here: https://en.m.wikipedia....
- 363
3
votes
0
answers
205
views
Has an uncomputable variant of the Cantor staircase ever been used in constructive logic?
An open problem in choiceless constructivism is to prove that if a function $f:\mathbb R \to \mathbb R$ is pointwise differentiable everywhere, with $f'=0$, then $f$ is constant. See In choiceless ...
- 4,511
3
votes
0
answers
112
views
Recursive axiomatizability over non-recursive base theory
This is a somewhat open-ended question — I’m curious whether there are any known results which are able to prove that one theory is not recursively axiomatizable over another, despite both having the ...
3
votes
0
answers
100
views
What is the $E$-r.e. part of $L$?
See Sacks' paper $E$-recursive inuitions or his book for background on $E$-recursion. Throughout, work in $\mathsf{ZFC+V\not=L}$. I'll use $\varphi_e$ in place of $\{e\}$ for the $e$th partial $E$-...
- 19.1k
4
votes
1
answer
120
views
Does the set of infinite random strings satisfy an analogue of immune sets?
Let $K(x)$ denote the Kolmogorov complexity of a finite binary string $x$. A finite binary string $x$ is called Kolmogorov random if $K(x) \geq |x|$. And an infinite binary sequence is called Martin-...
- 4,401
6
votes
0
answers
101
views
Reverse mathematics of Banach-Mazur games
Given $\mathcal{A}\subseteq\omega^\omega$, the Banach-Mazur game with payoff set $\mathcal{A}$ consists of players $1$ and $2$ alternately playing nonempty finite strings of naturals with player $1$ ...
- 19.1k
6
votes
0
answers
117
views
Complexity of constructive arithmetical truth vs second order arithmetic
Let us say that an arithmetic statement is constructively true iff it is realized by a computable function under Kleene's function realizability. Does the set of constructively true (first order) ...
- 5,507
2
votes
0
answers
68
views
Is parquetability decidable?
Let $T\neq \emptyset$ be a finite subset of $\mathbb{Z}\times\mathbb{Z}$. We say that $\mathbb{Z}^2 = \mathbb{Z}\times\mathbb{Z}$ is parquettable by $T$ if there is a partition $\frak P$ of $\mathbb{Z}...
- 42.5k
2
votes
0
answers
96
views
Enumerating unions of arithmetical sets
In Simpsons's excellent Subsystems of Second-order Arithmetic, we find V.4.10 which tells us the following:
The following is provable in ATR$_0$. Let $(A_n)_{n\in \mathbb{N}}$ be a sequence of ...
- 2,877
2
votes
1
answer
101
views
Axiomatization of S2S
What is a reasonable axiomatization of S2S?
S2S is the monadic second order theory with two successors (Wikipedia link). It has finite binary strings, operations $s→s0$ and $s→s1$ on strings, and ...
- 5,507