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.

Filter by
Sorted by
Tagged with
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 ...
Andreas Tsevas's user avatar
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 (...
Manlio's user avatar
  • 302
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 ...
Gro-Tsen's user avatar
  • 29.9k
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}<_{...
Reflecting_Ordinal's user avatar
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) ...
Noah Schweber's user avatar
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 ...
Keshav Srinivasan's user avatar
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 ...
Peter Gerdes's user avatar
  • 2,551
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 ...
Reflecting_Ordinal's user avatar
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 ...
Peter Gerdes's user avatar
  • 2,551
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 ...
Darren Li's user avatar
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 ...
Gro-Tsen's user avatar
  • 29.9k
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 ...
Dan Turetsky's user avatar
  • 2,678
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 ...
Gro-Tsen's user avatar
  • 29.9k
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 $\...
Lorenzo's user avatar
  • 2,134
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 ...
Keshav Srinivasan's user avatar
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 ...
Peter Gerdes's user avatar
  • 2,551
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) ...
lyrically wicked's user avatar
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 ...
Arshak Aivazian's user avatar
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 ...
Timothy Chow's user avatar
  • 78.1k
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 ...
Peter Gerdes's user avatar
  • 2,551
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-...
Noah Schweber's user avatar
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?
Peter Gerdes's user avatar
  • 2,551
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 (...
Peter Gerdes's user avatar
  • 2,551
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. ...
Peter Gerdes's user avatar
  • 2,551
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 ...
Peter Gerdes's user avatar
  • 2,551
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, ...
Armin Weiß's user avatar
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 ...
Peter Gerdes's user avatar
  • 2,551
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-...
Peter Gerdes's user avatar
  • 2,551
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 ...
Clement Yung's user avatar
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 ...
Sam Sanders's user avatar
  • 3,901
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$ ...
Peter Gerdes's user avatar
  • 2,551
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 ...
Dominic van der Zypen's user avatar
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'...
hatch22's user avatar
  • 123
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 ...
Peter Gerdes's user avatar
  • 2,551
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. ...
Peter Gerdes's user avatar
  • 2,551
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$ ...
Peter Gerdes's user avatar
  • 2,551
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$. ...
Peter Gerdes's user avatar
  • 2,551
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 ...
K. Bountrogiannis's user avatar
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)) ...
manu fava's user avatar
  • 393
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) ...
Mare's user avatar
  • 25.8k
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 ...
H.C Manu's user avatar
  • 733
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 ...
oma sun's user avatar
  • 51
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)$...
oma sun's user avatar
  • 51
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 ...
Zoorado's user avatar
  • 1,215
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. ...
Duncan W's user avatar
  • 341
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 ...
Gro-Tsen's user avatar
  • 29.9k
-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 ...
mishmish's user avatar
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 ...
Sidharth Ghoshal's user avatar
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$...
Dominic van der Zypen's user avatar
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 ...
Arno's user avatar
  • 4,366

1
2
3 4 5
20