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
5
votes
1
answer
469
views
Is the set of generalized Fermat triples computable?
Is $\;\big\{(a,b,c)\in\mathbb{N}^3: \big(\exists m,n,\ell \in (\mathbb{N}\setminus\{0,1,2\})\big): a^m + b^n= c^\ell\big\}\;$ computable?
- 48.9k
0
votes
1
answer
194
views
How slow can an uncomputable function from $\mathbb{N}$ to $\mathbb{N}$ grow? [closed]
I found this question here on MO: What about the fastest-growing non-computable function ?
and at first I thought I misread it. Given that all uncomputable functions seem to grow mind-bogglingly fast, ...
- 2,493
11
votes
0
answers
235
views
+50
Is there a decidable theory of arithmetic with a non-collapsing quantifier hierarchy?
This question is very close to this old MSE question of mine, which is still unanswered.
Is there an (ideally reasonably-natural!) expansion of the structure $(\mathbb{N};+)$ in a finite language ...
- 20.9k
-1
votes
0
answers
94
views
Relation between properties of functions/sets and Grzegorczyk's hierarchy
I know for example that the first level of the Grzegorczyk hierarchy contains the functions which enumerate the c.e sets and that it has an interesting relation to the provably total functions in ...
- 893
1
vote
1
answer
67
views
Recursive formula for divided differences
In general, a function $f(\cdot)$ defined at points $x_1,x_2,\dots, x_k$, the $(k − 1)$th-order
divided difference is defined by the recurrence relation:
$$
f[x_1,x_2,\dots...x_k]=\frac{f[x_2,\dots......
- 147
5
votes
1
answer
202
views
Turing degrees of lim infs of computable functions
The limit lemma gives a natural characterisation of functions $f : \mathbb{N} \to 2$ with Turing degree below $0'$: they are precisely those that can be written as $f(n) = \lim_k f_k(n)$ where $f_k : \...
- 4,378
5
votes
0
answers
158
views
If $\omega_1$ is not inaccessible in $L$, how hard can it be to find a non-measurable $\Sigma^1_3$ set of reals?
In his wonderfully titled paper Can you take Solovay's inaccessible away? Shelah showed that if every $\mathbf{\Sigma}^1_3$ set of reals is Lebesgue measurable, then $\omega_1$ is an inaccessible ...
- 12.5k
2
votes
1
answer
161
views
Are Cohen Generics Minimal Covers?
Are Cohen generics (in $2^\omega$) minimal covers?
I'm ultimately interested in this question for some more effective notion of forcing but I realized I wasn't sure how to show this even assuming full ...
- 3,029
1
vote
1
answer
150
views
Resource request (probability theory, computability theory, algebra)
I'm a first year graduate student trying to explore specific topics I might be interested in researching. Currently, I enjoy algebra, probability theory, and the computability theory side of logic, ...
- 121
3
votes
1
answer
144
views
Descriptive set theoretic complexity of computable maps with respect to the Turing jump of the input
For natural numbers $e$, $n$ and elements of Cantor space $X$ let $\{e\}^X(n)$ be the result of running the $e$th Turing machine with oracle $X$ on input $n$. Let $X'$ be the Turing jump of X.
Suppose ...
- 2,221
5
votes
0
answers
137
views
Cone avoidance and $\Pi^0_1$-classes
Suppose $X \subseteq 2^{\omega}$ is nonempty and $\Pi^0_1$ relative to $a$. Assume $c_0 \nleq_T b_0 \oplus a$ and $c_1 \nleq_T b_1 \oplus a$. Must there exist some $y \in X$ such that $c_i \nleq_T ...
- 51
6
votes
2
answers
276
views
Extending polynomial hierarchy above $\omega$
The arithmetic hierarchy is naturally extended to all ordinals via ordinal notations creating a hierarchy for all hyperarithmetic sets. The polynomial time hierarchy is defined analogously to the ...
- 3,029
6
votes
1
answer
228
views
Can we computably escape infinitely many functions (allowing partiality)?
Let $(p_i)_{i\in\omega}$ be a uniformly computable sequence of partial functions (i.e. the partial function $q(i,x)=p_i(x)$ is computable) such that infinitely many $p_i$s are total. Must there be a ...
- 20.9k
1
vote
0
answers
108
views
Name For Effective Cantor-Bendixsonish Derivitive
When dealing with a tree (substring closed subset of $\omega^{< \omega})$ a useful operation will frequently be to remove any nodes with finite ordinal rank (i.e., all nodes whose extensions on the ...
- 3,029
10
votes
0
answers
426
views
Function related to length of group presentations: is it computable?
(This question comes from a friend who works in sofic group theory.)
Consider the function $f: \mathbb{N} \to \mathbb{N}$, defined, for any $n \in \mathbb{N}$, by putting $f(n)$ to be the largest ...
- 339
7
votes
1
answer
716
views
What is the flaw in Cooper's argument?
Lately I have been studying in the subject of degree theory, specifically definability results related to $\mathcal{D}$. A famous conjecture in the field due to Slaman and Woodin is that the only ...
- 893
43
votes
4
answers
3k
views
What do we know about the computable surreal numbers?
The surreal numbers are built up in a natural iterative process, by which at any ordinal stage, if one has two sets of surreal numbers $L$ and $R$, with every number $x_L$ in $L$ strictly below every ...
- 236k
2
votes
0
answers
102
views
Direct construction of an arithmetically high degree below $0^{(\omega)}$
The existence of a high arithmetic degree (meaning the degrees induced by the notion of relative arithmetic definability) below $0^\omega$ can be established by using Harrington/Simpson's ...
- 3,029
1
vote
1
answer
87
views
A variant of Seetapun's theorem
Let $X \in 2^{\omega} \setminus \Delta^1_1$ (i.e., $X$ is not hyperarithmetical) and $A \subseteq \omega$. Must there exist $B \in [A]^{\omega} \cup [\omega \setminus A]^{\omega}$ such that no ...
- 325
4
votes
2
answers
134
views
Properties of all relatively computable branches
I'm probably just missing something obvious but suppose that $T \subset 2^{< \omega}$ is a perfect tree with no terminal nodes (what about just $[T]$ non-empty?). If $Y \leq_{T} X$ for all $X \...
- 3,029
3
votes
0
answers
153
views
What is known about the word problem on free algebraic models?
Consider the fragment of first-order logic with equality and universal quantification as the only logical symbols; we call this logic the logic of universal algebra. I am interested in languages $\...
3
votes
0
answers
97
views
Can the differential field of d.c.e. reals be nicely construed as a field of functions?
This question is basically a special case of this older question of mine, which is still unanswered.
Let $\mathcal{D}$ be the field of d.c.e. reals; these turn out to be exactly the reals $\alpha$ for ...
- 20.9k
3
votes
0
answers
146
views
Lower Bound of Solutions to P=NP?
Do we at least know that simulating polynomial time non-deterministic Turing machines requires more than a linear slowdown? That is, do we know there is some non-deterministic Turing machine with ...
- 3,029
4
votes
1
answer
266
views
Are (group theoretic) Markov properties on groups with decidable word problems, decidable?
(Link to SE duplicate: https://math.stackexchange.com/questions/4959071/are-group-theoretic-markov-properties-on-groups-with-decidable-word-problems)
The Adian-Rabin theorem says that if a property of ...
- 191
6
votes
0
answers
263
views
Decidably clarifying ordinals
For a computable$^*$ ordinal $\alpha$ (viewed as an $\{<\}$-structure), say that a first-order sentence $\sigma$ in a relational language $\Sigma\supseteq \{<\}$ decidably clarifies $\alpha$ iff ...
- 20.9k
15
votes
2
answers
918
views
Which are the hereditarily computably enumerable sets?
My question is about sets that are computably enumerable with respect to their hereditary membership structure. Specifically, let me define that a hereditarily computably enumerable (h.c.e.) set is ...
- 236k
1
vote
0
answers
40
views
Can a positive elementary inductive definition refer to its own stage comparison relation?
This is a cross-post of a question from cstheory.SE
Moschovakis' stage comparison theorem says that the stage comparison relation associated with any positive elementary induction is itself definable ...
- 211
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....
- 483
6
votes
1
answer
197
views
Is there a 1-generic degree g such that Th(D(< g)) is more complicated than true arithmetic?
I am currently reading an article titled "Embedding and Coding Below a 1-Generic Degree" by Greenberg and Montalbán(link to a free source:https://pi.math.cornell.edu/~erlkonig/Papers/...
- 893
1
vote
1
answer
246
views
Minimal Turing machines associated to math statements
It is known that some famous Number Theoretic problems are equivalent to halting of specific Turing machines:
Goldbach conjecture holds iff a 47 state TM halts
Lagarias' formulation of Riemann ...
- 593
-2
votes
1
answer
181
views
What is the computational complexity to verify a P solution with a deterministic Turing machine? [closed]
As we know, NP (nondeterministic polynomial time) is a complexity class used to classify decision problems. NP is the set of decision problems for which the problem instances, where the answer is &...
- 3,094
2
votes
0
answers
78
views
Is this variant of post correspondence problem undecidable?
The post correspondence problem, as defined by wikipedia, is undecidable. The problem is defined as follows.
Let $A$ be an alphabet with at least two symbols. The input of the problem consists of ...
- 21
16
votes
2
answers
1k
views
Is it decidable whether two real algebraic irrationals generate the same extension of the rationals?
For an algebraic number $\alpha$, let $f_\alpha$ denote its minimal polynomial. We can symbolically represent an algebraic number $\alpha$ by the tuple
$$
(f_\alpha, x, y, r) \in \mathbb{Q}[x] \times ...
- 1,087
135
votes
43
answers
38k
views
What are the most attractive Turing undecidable problems in mathematics?
What are the most attractive Turing undecidable problems in mathematics?
There are thousands of examples, so please post here only the most attractive, best examples. Some examples already appear on ...
2
votes
0
answers
142
views
Can a path in Kleene's $\mathcal{O}$ enumerate all of the computable reals via uniform diagonalization?
It's a well-known fact that there are computable diagonalization functions on Baire space $\mathbb{B} = \mathbb{N}^\mathbb{N}$ (i.e., functions which take a sequence $(r_i)_{i\in \mathbb{N}}$ of ...
- 12.5k
4
votes
0
answers
149
views
Computable subsets of non-standard models of arithmetic
By Tennenbaum's theorem, there exists no computable non-standard model of $\mathsf{PA}$. That is, for any nonstandard model $M$, we cannot define an encoding of the integers $x\in M$ such that $+_M$, $...
- 291
7
votes
2
answers
644
views
Ideals generated by Turing independent sets
Recall that $X \subseteq 2^{\omega}$ is Turing independent if no $y \in X$ is computable from the Turing join of any finite subset of $X \setminus \{y\}$.
Question 1. Can we construct a Turing ...
- 71
95
votes
2
answers
8k
views
Will this Turing machine find a proof of its halting?
Consider the following Turing machine $M$: it searches over valid ZFC proofs, in lexicographic order, and if it finds a proof that $M$ halts, then it halts.
If we fix a particular model of Turing ...
- 2,019
7
votes
0
answers
161
views
Is strictness decidable?
Let $\mathcal C$ be an $\infty$-category. We can ask:
Q: Is $\mathcal C$ a 1-category?
That is, are the hom-spaces of $\mathcal C$ essentially discrete?
Roughly, my question is:
Proto-Question: Is Q ...
- 63.9k
2
votes
0
answers
132
views
A property of < in Primitive recursive arithmetic
In Primitive recursive arithmetic (PRA), we can introduce $\lt$ by introducing its representing function $K_{\lt}$, where $K_{\lt}(x,y) =sg(x+1-y)$. Here "sg" and "-" are the ...
- 29
3
votes
1
answer
170
views
Reverse mathematics on lightface $\Pi^1_1$-uniformization for unary relation
It is known that the following form of $\Pi^1_1$-uniformization is equivalent to $\Pi^1_1$-Comprehension over $\mathsf{ATR}_0$ (cf. VI.2.6 of Simpson's book) :
(Kondo's uniformization theorem) For ...
- 3,042
1
vote
1
answer
558
views
Natural Numbers
Let $L$ be a countable language and $M$ be a model of $L^N$ (the realization of $L$ in the natural numbers $N$) in which every recursive unary relation is expressible. Show that $M$ is not recursive.
- 265
7
votes
2
answers
230
views
Why does Weihrauch reducibility make use of multi-functions?
This is probably a kinda dumb question, but why is Weihrauch reducibility defined in terms of multi-functions (i.e. why isn't it just the degree structure of regular functions under that reducibility)?...
- 3,029
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 ...
- 1,263
9
votes
1
answer
261
views
Does there exist a geometric morphism between the effective and topological topoi? Does one arise from synthetic topology?
I'm presenting in final projects for my computability and computational topology courses on the connections between computability, continuity, and logic. As a mathematician/unmentored baby logician ...
- 433
2
votes
0
answers
235
views
Is there a computable model of HoTT?
Among the various models of homotopy type theory (simplicial sets, cubical sets, etc.), is there a computable one?
Can the negative follow from the Gödel-Rosser incompleteness theorem?
If there is no ...
user507115
4
votes
1
answer
192
views
Further research on relevant realizability etc
I just read Dunn's 1979 paper Relevant Robinson's Arithmetic, and the end especially caught my interest. Following the surprising role of constant functions in collapsing "relevant Q with zero&...
- 20.9k
5
votes
1
answer
246
views
Splitting 0' into two 1-generic reals
I have come across multiple research papers where they have mentioned that two 1-generic reals $x$ and $y$ can be constructed such that $x \oplus y \equiv_{T} \textbf{0}'$, where $\textbf{0}'$ is the ...
user527095
5
votes
1
answer
563
views
Hilbert's and Gödel's expanded definition of "Recursive Function"
There is a very interesting comment in this post:
I must also make one terminological caveat: Hilbert, and later Godel, used the phrase "recursive function" in a way very different from the ...
- 4,897
5
votes
0
answers
109
views
Computational complexity of arithmetic sentences over classical theories
Below, I use the term "tracker" rather than "realizer" since I'm not requiring the relevant objects to be computable.
Define the relation "$f$ tracks $\varphi$" for $f:\...
- 20.9k