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,036 questions
13
votes
4
answers
3k
views
{transcendental numbers} \ {computable transcendental numbers}
I know Chaitin's constant Ω is not computable (and therefore transcendental). Are there other specific, known noncomputable numbers? I am trying to understand what distinguishes a computable ...
- 3,065
5
votes
0
answers
153
views
What is known about propositional realizability for the second Kleene algebra and related PCAs?
Short version: Various things are known about realizability of propositional formulas for Kleene's “first algebra” (i.e., $\mathbb{N}$), like examples of realizable but unprovable formulas, and some ...
- 32.5k
4
votes
1
answer
257
views
What is the theory of statements with a provably *bounded* realizer (according to PA)?
$\let\T\mathrm\def\kr{\mathrel{\mathbf r}}$This is a follow up to Kleene realizability in Peano arithmetic.
We can summarize the results from Emil Jeřábek's answer as follows:
\begin{gather*}
T_1 = \{ ...
- 12.9k
8
votes
4
answers
941
views
Are there two computable binary trees such that each has a branch not computing any branch through the other?
It is a well-known elementary classical result in computability theory that there are computable infinite binary trees $T\subset 2^{<\omega}$ having no computable infinite branch. (One can build ...
CommunityBot
- 1
3
votes
1
answer
134
views
A $\Pi^0_1$ class of $\alpha$-subgenerics for all $\alpha < w_1^{CK}$
In Harrington's mimeographed notes (see here) solving McLaughlin's conjecture he builds reals $f \in \omega^\omega$ which have the property of being $\alpha$-subgeneric defined as follows. He does ...
CommunityBot
- 1
3
votes
2
answers
262
views
Question regarding $W$ as not hyperarithmetic
Consider the indexes of all ordinary programs generating functions from $\mathbb{N}^2$ to $\{0,1\}$. If we let $W$ be the set of exactly of all those indexes $e$ such that $\phi_e$ computes a total ...
- 21.2k
35
votes
3
answers
5k
views
Using Busy Beavers to prove conjectures
I've been pondering some stuff on Shtetl Optimized where Yedidia and Aaronson construct Turing machines that will only halt if (e.g.) the Riemann Hypothesis is false, or Goldbach's conjecture is false....
- 245
8
votes
1
answer
1k
views
Why don't Zeilberger and Gosper's algorithms contradict Richardson's theorem?
Richardson's theorem proves that whether an expression A is equal to zero is undecidable. A is in this case an expression, constructed from $x,e^x,\sin(x)$ and the constant function $\pi$ and $\ln(2)$ ...
- 157
6
votes
3
answers
392
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 ...
- 32.5k
14
votes
2
answers
2k
views
Church–Turing thesis for higher order functions
The Church–Turing thesis states that, simply speaking, any reasonable definition of "effectively computable functions" $\mathbb{N} \to \mathbb N$ agrees with the definition using Turing ...
6
votes
1
answer
293
views
Need help in trying to understand an argument by V. A. Yankov on the nonrealizability of Scott's axiom
(This is really long because I give a lot of context, but you can skip right to the end where the excerpt I'm trying to make sense of is copied and translated.)
Background: I'm trying to understand ...
- 32.5k
2
votes
0
answers
151
views
Notes on Lachlan's monster
I have been trying to look for a reference I have seen in a paper called "R. Soare, Notes on Lachlan’s Monster Theorem" without success. I was wondering if anyone had a digital copy of them ...
- 893
13
votes
1
answer
649
views
Kleene realizability in Peano arithmetic
For completeness of MathOverflow and for clarity of the question, I will first recall a few things, including the the definition of Kleene realizability: experts can jump directly to the question ...
- 47.3k
4
votes
0
answers
214
views
Computational complexity of zeros of an analytic function
The work of Friedman and Ko, page 342, Corollary 4.3.1
states that all zeros of analytic polynomial time computable function are polynomial time computable, but for me that is not clear how it could ...
- 24.2k
3
votes
1
answer
308
views
Root finding algorithm for an analytic function
Given an analytic function $f(x)$. What is the best algorithm to find roots on the interval $[a,b]$ inside the radius of convergence> What is its complexity with respect to the length of input of ...
- 81
3
votes
1
answer
123
views
Kleene normal form theorem for r.e. relations proven in arithmetical theories
After reading the relevant chapters of Classical Recursion Theory (freely available from here), I have the following questions concerning Theorem II.1.10 (Normal form theorem) and Theorem IV.1.9 (...
- 17.7k
1
vote
2
answers
482
views
Satisfiability problem for FOL[<,R]
Let FOL[<,R] be the fragment of first-order logic enriched with two relational symbols < and R and the first-order axioms that say:
< is a strict partial order and R is an irreflexive and ...
- 236k
12
votes
1
answer
752
views
Fast-growing hierarchy and Turing machines
Is it possible to get an estimate of the size of a Turing machine computing $f_\alpha(n)$, for a given $\alpha$ (I am especialy interested in moderately large $\alpha$ like the ordinal of Fefferman-...
- 1,446
6
votes
1
answer
230
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 (...
CommunityBot
- 1
4
votes
3
answers
406
views
Hyperarithmetically least elements in $\Pi^1_1$ sets
My question is: Do we have a hyperarithmetically $\le_H$-least real in any $\Pi^1_1$ set? That is
Question. Suppose that $A$ is a non-empty $\Pi^1_1$ set. Then can we find a real $a\in A$ such that $...
CommunityBot
- 1
14
votes
1
answer
572
views
How exactly are realizability and the Curry-Howard correspondence related?
Consider, on the one hand:
the Curry-Howard correspondence between, on the one hand, types and terms (programs) in various flavors of typed $\lambda$-calculus, and on the other, propositions and ...
- 48.8k
6
votes
2
answers
769
views
Representation of μ-recursive functions
Can every μ-recursive function be defined using a single instance of the μ operator applied to a primitive recursive function?
According to Wikipedia, any μ-recursive function can be expressed as the ...
- 1,446
7
votes
1
answer
331
views
Proving finiteness in Reverse Mathematics
In (second-order) Reverse Mathematics, a (code for an) open set $U\subset \mathbb{R}$ is given by two sequences of rationals $(a_n)_{n \in \mathbb{N}}, (b_n)_{n \in \mathbb{N}}$. The idea is that $U$ ...
- 21.2k
16
votes
2
answers
3k
views
Why is there no product type in simply typed lambda-calculus?
$\DeclareMathOperator\Pair{Pair}\DeclareMathOperator\First{First}\DeclareMathOperator\Second{Second}\DeclareMathOperator\Left{Left}\DeclareMathOperator\Right{Right}\DeclareMathOperator\Choice{Choice}$...
- 12.9k
5
votes
0
answers
192
views
Complexity implications on computability
Are there any known links between complexity theory and computability theory by which I mean non-trivial theorems of the form: If NP $\neq$ co-NP then there is no strong minimal pair of r.e. sets or ...
- 63.9k
16
votes
3
answers
19k
views
Non-computable but easily described arithmetical functions
I have read about the existence of functions of the kind described in the title in several places, but never seen an instance of them. Sorry if this is too much an elementary question to be posted ...
- 18.7k
3
votes
0
answers
99
views
Comparing computable structures via Kleene and Skolem
Below, by "structure" I mean "computable structure in a finite language with domain $\omega$," and by "sentence" I mean "finitary first-order sentence containing no ...
- 21.2k
8
votes
2
answers
518
views
History of forcing over admissible sets
In his paper "Forcing in admissible sets", Ershov writes
In unpublished lectures given at Novosibirsk State University in 1976-1977 on the theory of admissible sets, the author
showed that it is ...
- 17.7k
0
votes
1
answer
137
views
Is there a canonical mapping between countable transfinite ordinals and $\omega$? What about recursive ordinals?
Consider $\omega^2$. We can build a simple bijection between the ordinal and $\omega$ similarly to how the bijection between $\mathbb{Q}$ and $\mathbb{N}$ can be built.
I was wondering if there is a ...
- 21.2k
4
votes
1
answer
287
views
Can a halting oracle determine if a Turing machine is an ordinal?
For the sake of clarity, I am regarding a computable relation on $\mathbb{N}$ as a $2$-symbol ($0$ and $1$) Turing machine $T$ which halts on any initial binary string (which are interpreted as some ...
- 21.2k
1
vote
0
answers
116
views
Sudden drop in complexity class due to the more general correlations
Recently I was asking about the impact of the groundbreaking result MIP*=RE on logic and proof theory (see this discussion). Surprising as it is I got confused with the following: MIP* is a ,,quantum''...
- 9,330
1
vote
1
answer
98
views
How large can a subset of computable reals, whose comparison function is computable, grow?
How large can a subset of computable reals, whose comparison function is computable, grow?
For example, rational numbers are computable reals, and its comparison function is computable. As another ...
- 21.2k
0
votes
0
answers
181
views
Can a model of "true computation" exist? What would be its consequences?
Analogous to the model of True Arithmetic, the model of "True Computation" is defined to be the set of all true first-order statements about Turing machines i.e. answers to elementary ...
CommunityBot
- 1
4
votes
0
answers
108
views
Decidability of whether two polynomial bijections generate a free group
I am wondering about the decidability of the following question:
Given two polynomial bijections $f, g$ from the real numbers to the real numbers (with say rational coefficient just to simplify what &...
- 63.9k
4
votes
1
answer
212
views
Extending the class of primitive recursive functions with higher order recursion schema
I'm trying to extend the class of primitive recursive functions by extending the recursion schema over higher types.
We usually define the class of primitive recursive functions by using zero function,...
- 300
1
vote
0
answers
67
views
Are the lower elementary functions closed under limited recursion?
The lower elementary functions (also called Skolem elementary functions) are functions generated from the successor, modified subtraction, projection functions by the operations of composition and ...
- 1,792
8
votes
2
answers
586
views
Turing degrees of sets separating two computably inseparable sets (theorems and antitheorems)
Let $A\subseteq\mathbb{N}$ be the set of Gödel codes of theorems of Peano arithmetic, and $B\subseteq\mathbb{N}$ be the set of codes of antitheorems (i.e, refutable statements, statements whose ...
- 3,073
10
votes
2
answers
470
views
Is the set of permissible numbers of models of various cardinalities computable?
This question arose in the comments to this question.
Let $X$ be the set of pairs $(m,k)$ such that there is some (consistent complete countable first-order) theory $T$ with exactly $m$ models of size ...
- 5,031
2
votes
1
answer
122
views
Splitting $\Pi^0_2$ Singletons?
Given a (non-computable) $\Pi^0_2$ singleton $Y$ are there Turing incomparable $\Pi^0_2$ singletons $X_0, X_1$ with $Y \equiv_T X_0 \oplus X_1$?
What about the same question for arithmetic ...
- 1,780
5
votes
1
answer
487
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}<_{...
- 2,031
6
votes
1
answer
307
views
What is the power of the “anti-halting” oracle?
Let me first ask the question, and then, as it may seem a bit cryptic, explain how it comes up (and whence the “anti-halting oracle” in the title):
Notations: we write $\langle m,n\rangle$ for a ...
- 32.5k
15
votes
1
answer
1k
views
Higher recursion theory and reverse mathematics: What is to $\Pi^1_1$-$CA_0$ as $RCA_0$ is to $ACA_0$?
There is an extremely rich and well-understood analogy between "recursively enumerable" and "$\Pi^1_1$" – indeed, this is the starting point of metarecursion theory, and $\alpha$-...
- 47.3k
8
votes
2
answers
489
views
Comprehension axiom that helps in the opposite direction
Usually, having more comprehension axiom means the more you can prove. We wonder if the converse can be the case.
Is there a natural problem $\mathsf{P}$ so that $\mathsf{P}+\neg(\Gamma-\mathsf{...
- 4,359
8
votes
1
answer
601
views
Proof-theoretic ordinals: inevitable consistency?
There are various different notions of the proof-theoretic ordinal of a theory; most of these are "notation-dependent" in that they're only nontrivial once we restrict attention to a class of "natural"...
- 2,031
3
votes
1
answer
126
views
The sequence of the power chromatic numbers $(\chi(G^n))_{n\in\mathbb{N}}$
For any finite, simple, undirected graphs $G, H$ we denote by $G\times H$ their categorical product. For any graph $G$ we let $G^1 = G$ and for $n\geq 1$ we let $G^{n+1} = G \times G^n$.
It is easy to ...
- 981
2
votes
1
answer
135
views
Harrington's notes on McLaughlin/Arithmetically incomparable singletons
At one point I had copies of the handwritten notes Leo created about the McLaughlin conjecture and I know a similar set of notes exist titled Arithmetically incomparable arithmetic singletons. I've ...
- 3,029
45
votes
5
answers
64k
views
How large is TREE(3)?
Friedman, in _Lectures notes on enormous integers shows that TREE(3) is much larger than n(4), itself bounded below by $A^{A(187195)}(3)$ (where $A$ is the Ackerman function and exponentiation ...
- 257
5
votes
0
answers
215
views
Status of Problems in 102 problems in mathematical logic
Is there any location that records the current status of the problems in 102 problems in mathematical logic? Or, better yet, serves as a status board for open problems in mathematical logic? ...
- 3,029
7
votes
0
answers
110
views
How tightly are decidability and "induction-completeness" linked?
It is known that there are a number of expansions of the structure $\mathfrak{N}:=(\mathbb{N};+)$ which are decidable (= have computable theories); one such example is the expansion by a predicate ...
- 21.2k
2
votes
1
answer
123
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 ...
- 3,073