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.
1,099 questions
8 votes
0 answers
214 views
Can we “encrypt” in the Turing degrees?
Definitions: If $M,C\subseteq\mathbb{N}$, let us say that a function $f\colon\mathbb{N}\to\mathbb{N}$ is an encoding of $M$ by $C$ when $f^{-1}(C) = M$ (i.e., for all $m\in\mathbb{N}$ we have $m\in M$...
- 38.1k
8 votes
0 answers
279 views
For which sets do Arthur and Nimue have a winning strategy in this game (“communicate a bit”)?
TL;DR: I define a three-player game (Arthur, Nimue, Merlin) where Nimue is shown a hidden bit $b$ chosen by Merlin and tries to communicate it to her ally Arthur, but Arthur must act computably while ...
- 38.1k
11 votes
4 answers
376 views
Complete sets in the arithmetic hierarchy from outside of logic
What are some good examples of problems which are complete for higher levels of the arithmetic hierarchy and which come from parts of mathematics outside of logic? By "complete for higher levels ...
- 655
5 votes
1 answer
308 views
A universal ordering on the sets in a (Turing) degree
Do all the Turing degrees agree, in a definable (hyperarithmetic? arithmetic?) way, on an ordering of their representatives? I'll make this precise below but roughly the question is whether there is ...
- 3,987
7 votes
1 answer
188 views
Martin's Conjecture and Arithmetically Pointed Trees
One consequence of Martin's conjecture is that if $f$ is a Turing degree invariant Borel function from $2^\omega$ to $2^\omega$ then there is a pointed perfect tree $T$ such that either $f$ is ...
- 3,987
3 votes
1 answer
168 views
Supernormal sequences
We call a binary sequence $s:\mathbb{N}\to\{0,1\}$ supernormal if for every injective, increasing and computable function $\iota:\mathbb{N}\to\mathbb{N}$, the binary sequence $s\circ\iota:\mathbb{N}\...
- 53.5k
4 votes
1 answer
151 views
What ordering does Ershov's unbounded path through $\mathcal{O}$ have?
There is this theorem I found in an article by Stephen, Yang and Yu due to Ershov(theorem 4.6 in http://maths.nju.edu.cn/~yuliang/ssyy.pdf) which says the following: (a) There exists an unbounded path ...
- 1,411
13 votes
1 answer
299 views
How far does Cantor-Bendixson rank counting let us build computable isomorphisms between ordinals?
This is tangentially related to this old question of mine. Say that a clean well-ordering is a computable well-ordering $\triangleleft$ of $\mathbb{N}$ such that the following additional data is ...
- 19.6k
6 votes
0 answers
211 views
Have you seen this variation of Medvedev reducibility?
In what follows, $A, B$ will denote subsets of $\mathbb{N}^{\mathbb{N}}$, i.e., sets of total functions $\mathbb{N} \to \mathbb{N}$ (maybe assume them to be inhabited to avoid any headaches about the ...
- 38.1k
7 votes
1 answer
177 views
Admissibility spectrum and recursively large ordinals
Some people already have asked questions concerning Sy Friedman's results: (1) For $x\in\mathbb{R}$ if every $x$-admissible ordinals are stable, then $0^\#\in L[x]$. (2) There can be, by a class-...
- 503
5 votes
1 answer
316 views
When does the choice of the fundamental sequence matter?
I am quoting a paragraph from the second paper of Jockush and Shore on REA operators about generating the REA sets recursively via a system of notations: "We can then associate $R$-sets with this ...
- 1,411
21 votes
1 answer
2k views
Is Exercise 5.3.5 of Chong and Yu's book Recursion Theory really correct?
In the book, Chi Tat Chong and Liang Yu, "Recursion Theory, Computational Aspects of Definability", De Gruyter 2015, Exercise 5.3.5 (p.98) quotes S.G.Simpson's result as follows: If there ...
- 503
17 votes
0 answers
689 views
How to compute A263996?
Consider the sequence $$a_n:=\min_{\substack{A\subseteq\mathbb{Z}\\|A|=n}}|(A+A)\cup (A\cdot A)|.$$ This is A263996 in OEIS. (Actually, they restrict to $\mathbb{N}$, but it makes little difference to ...
- 8,095
8 votes
0 answers
409 views
Are there any moderately difficult Collatz-type problems?
This question is inspired by a recent Quanta article, which explained that in order to compute BB(6), it is necessary to solve an "antihydra problem" which is somewhat similar to the ...
- 6,416
3 votes
1 answer
166 views
Models of Second Order Arithmetic with non-standard length and all subsets of $\omega$?
Are there any non-standard models of RCA$_0$ such that every subset of $\omega$ appears as a restriction of a set in the second-order part to it's standard initial segment? In other words, does ...
- 3,987
6 votes
0 answers
127 views
Randomness in $\omega^\omega$ and other measure relativization
It is a result of Levin and (independently?) Kautz that if $X \in 2^\omega$ is 1-ML random relative to a computable measure $\mu$ the either $X$ is computable (it is an atom of $\mu$) or $X$ is Turing ...
- 3,987
20 votes
3 answers
2k views
Is the set of theorems of a PA + “PA is inconsistent” equivalent to the halting set?
In what follows, we let $T$ be a consistent, recursively axiomatizable theory that includes $\mathsf{PA}$ (Peano arithmetic). Definition: Let us say that the theory $T$ is creative when the set of ...
- 38.1k
2 votes
1 answer
258 views
Is choice needed to construct a free ultrafilter on the boolean algebra of computable sets?
Is choice needed to construct a free ultrafilter on the boolean algebra of computable sets? Inspiration I ask this purely out of curiosity and because it's a natural follow-up question to GVT's ...
- 1,703
8 votes
2 answers
573 views
Is there a filter containing every computable set or its complement that is not an ultrafilter?
As in the title: let $\mathfrak{F}$ be a filter on $\mathbb{N}$ such that, for every computable set $A\subseteq \mathbb{N}$, either $A\in\mathfrak{F}$ or $\mathbb{N}\setminus A\in\mathfrak{F}$; is $\...
- 223
8 votes
3 answers
763 views
Model of ZFC In Which Martin's Cone Theorem Fails?
Is it known to be consistent with ZFC for there to exist a Turing degree invariant projective set which neither contains nor is disjoint from a cone? What about in $L$, i.e., is it known that (the ...
- 3,987
11 votes
1 answer
514 views
Computably constructing a set that is not in a free ultrafilter
Let $\mathcal{U}$ be a free ultrafilter on $\mathbb{N}$. Given a computable function $f : \mathbb{N} \to \mathbb{N}$ such that $f(0) < f(1) < \cdots$, suppose we have a set $S(f)$ such that $|\{...
- 1,047
5 votes
0 answers
313 views
Hypercomputational explanatory strength
Lets consider two entities with different hyper-computational strength. Entity A is able to comprehend the whole continuum and hence it decides every arithmetic sentence and, assuming Projective ...
- 489
5 votes
3 answers
385 views
Regarding the realizability topos on the computable part of Kleene's second algebra
Let: $\mathcal{K}_1$ be the first Kleene algebra, meaning $\mathbb{N}$ endowed with the partial operation $(p,n) \mapsto p\bullet n := \varphi_p(n)$ where $\varphi$ is the $p$-th partial computable ...
- 38.1k
2 votes
0 answers
252 views
Using dilators to formalize the intuitions about the size of small uncomputable ordinals
The least recursively inaccessible ordinal $I$, is, intuitively, the supremum of the ordinals that come from "recursively" iterating the function $\alpha\mapsto\omega^{CK}_\alpha$. For an ...
- 1,652
8 votes
0 answers
189 views
Lower bounds on positive $\sin$-polynomials
I am aware that the structure $(\mathbb{R},+,\cdot,<,\sin)$ is extremely wild. Indeed, since the natural numbers are definable in such structure, one can define, via first-order formulas without ...
- 457
2 votes
0 answers
171 views
What is known about realizability model of the real analysis?
What do "Realizability of the axiom of choice in HOL" and "Realizability and the Axiom of Choice" mean when they claim they realize a non extensional version of $\sf AC$? Can they ...
- 1,435
3 votes
0 answers
106 views
Is there a structure properly contained in the $\Pi^0_2$ singleton classes, richer than the $\alpha-REA$ sets?
I am going through Jockush and Shore's paper on transfinite pseudo-jump operators from '84 and in it's introduction it is mentioned that the transfinite pseudo-jump operators are properly contained in ...
- 1,411
18 votes
1 answer
832 views
How to approximate the max and min of Hydra-Game?
Basic background: A hydra is a finite rooted tree (with the root usually drawn at the bottom). The leaves of the hydra are called heads. Hercules is engaged in a battle with the hydra. At each step of ...
- 71
7 votes
1 answer
280 views
A theorem of Harrington on $\Pi^1_1$ paths through $\mathcal{O}$
I am currently reading a subsection of Chong & Yu(2010), specifically section 11.2 which is dedicated to a theorem of Harrington and I quote: Theorem 11.2.1 For any ordinal $ \beta < \omega_{\...
- 1,411
2 votes
2 answers
575 views
Computation Via Infinite Sums
Suppose I want to uniformly represent computation in an infinite series, what is the smallest/most natural set of operations I need to express the $n$-th term that allows me to capture arbitrary ...
- 3,987
2 votes
0 answers
99 views
Determinacy and $\omega$ branching subtrees on which a functional is either partial or total
All trees discussed here are fully pruned subsets of $\omega^{< \omega}$ closed under substring and containing $\langle \rangle$ (the empty string). Definition: T is completely $\omega$ branching ...
- 3,987
-2 votes
1 answer
548 views
Does this specific 5-state Turing machine halt? [closed]
Basic setups: A Turing machine M operates on a doubly infinite tape. The tape is divided into cells. Each cell can hold either a 0 or a 1 (meaning, we will consider only TM’s with two symbols). The ...
- 71
7 votes
1 answer
368 views
Problems on explicit embeddings of recursive groups into finitely presented groups
By this post I would like to ask the Community to kindly share information about existing problems on explicit embeddings of recursive groups into finitely presented groups. Every recursive group (i.e....
- 199
6 votes
0 answers
255 views
Are there natural statements in primitive recursive arithmetic with only bounded quantifiers that are true but not provable?
Goodstein's "Recursive Number Theory" (1957) presents a "logic-free" version of primitive recursive arithmetic: all statements in the logic are equalities of expressions involving ...
- 489
3 votes
1 answer
184 views
On cone avoidance
The following questions may be well-known in which case I would be happy to be directed to a published reference. Q1. Let $d \in 2^{\omega}$ be noncomputable and $A \subseteq \omega$. For each $C \...
- 91
8 votes
1 answer
497 views
What does “the” mean in “the first Kleene algebra”? (In what sense is it unique?)
Definition: “The” first Kleene algebra $\mathcal{K}_1$ is the set $\mathbb{N}$ of natural numbers endowed with the partial operation $(p,n) \mapsto p\bullet n := \varphi_p(n)$ where $\varphi_p$ is the ...
- 38.1k
5 votes
1 answer
478 views
How to understand this inductive definition over a non well-founded set of ordinals
$\newcommand\ZF{\mathrm{ZF}}\newcommand\KPU{\mathrm{KPU}}$I am trying to read Barwise's Admissible Sets and Structures and I am just starting, so pardon if I may be missing something basic here. The ...
- 217
10 votes
0 answers
320 views
Is Noether's Problem undecidable?
I begin by recalling Noether's problem over $\mathbb{Q}$: Let $G$ be a finite group that act faithfully by field automorphisms on $\mathbb{Q}(x_1,\ldots,x_n)$, with the action on $\mathbb{Q}$ trivial. ...
- 3,758
10 votes
2 answers
818 views
Is it possible to add a new axiom schema to classical propositional logic?
Let IPL mean the intuitionist propositional calculus. One can add a great diversity of axiom schemas to obtain intermediate logics between IPL and CPL, where CPL is the classical propositional ...
- 391
7 votes
1 answer
332 views
A topos for realizability under a variable oracle
I am looking for a topos that describes realizability by Turing machines with access to a “variable oracle”. I think the construction I want is this. Start with Baire space $\mathcal{N} := \mathbb{N}^...
- 38.1k
4 votes
1 answer
262 views
Hard to relativize results in computablity theory
There is this paper by Khan and Miller titled "FORCING WITH BUSHY TREES"(here is a free source:https://people.math.wisc.edu/~jsmiller8/Papers/bushy_trees.pdf) in which the main results ...
- 1,411
9 votes
1 answer
575 views
Alternate proofs of the undecidability of the homeomorphism problem for finite simplicial complexes
It is classical that the homeomorphism problem for finite simplicial complexes is unsolvable. All the sources I know for this actually prove something slightly different: Theorem: For $n \geq 5$, ...
4 votes
1 answer
222 views
A local view of $\Pi_2^0$-singletons
In Nies's monograph "Computability and Randomness", there is an interesting remark about $\Pi_2^0$-singletons, where he gives an argument that such singletons can be non-arithmetic and he ...
- 1,411
8 votes
1 answer
570 views
Does the axiom of choice enable shorter minimum proofs of non-halting than ZF alone is capable of?
It is well-known that ZFC cannot prove the non-halting behavior of any more Turing machines than ZF alone can. However, does the addition of AC permit shorter minimum proofs of non-halting behavior in ...
- 203
6 votes
3 answers
538 views
$\omega$-branching tree of mutual generics
Is there an $\omega$-branching tree $T \subset \omega^{< \omega}$ without terminal nodes such that any pair $f \neq g \in [T]$ are mutually generic? Let's say mutually $1$-generic but I'm ...
- 3,987
13 votes
4 answers
2k views
Are Category and Measure Special?
In logic, and I expect in mathematics more broadly, it seems like there is a special role played by notions like measure and (baire) category (as in meeting/avoiding dense sets). Obviously, these ...
- 3,987
3 votes
1 answer
149 views
$\Pi^{1}_1$ Subsets of Orders w/o $\Delta^1_1$ descending sequences
Suppose that $\prec$ is a computable linear order with field $\omega$ with an infinite descending sequence but no hyperarithmetic such one. If $S \subset \omega$ is $\Pi^{1}_1$ must $S$ have a $\prec$...
- 3,987
5 votes
1 answer
216 views
Recursive linear orders given by Kleene-Brouwer order
The Kleene-Brouwer order $<_{KB}$ transforms a computable tree $T$ on $\omega^{< \omega}$ into a computable linear order (mapping infinite paths through $T$ into infinite descending sequences). ...
- 3,987
3 votes
0 answers
90 views
Sequence of polynomals from linear recursion: Decidable or not if all are real-rooted?
Let $P_1(x),P_2(x),P_3(x),\dotsc$ be a sequence of polynomials, determined by some initial conditions and a finite-length linear recursion with coefficients being polynomials in $x$ and the index. For ...
- 16.1k
7 votes
1 answer
252 views
Polynomially normal binary sequences
Motivation. When we try to construct a (pseudo-)random sequence $s:\newcommand{\N}{\mathbb{N}}\N\to\{0,1\}$ we often want $s$ itself, and some of its subsequences, to be normal. Question. Is there a ...
- 53.5k