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.
74 questions from the last 365 days
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
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
11
votes
0
answers
233
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 ...
- 21.2k
-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
0
answers
157
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.4k
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
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
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
1
vote
1
answer
149
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
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
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
10
votes
0
answers
423
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
3
votes
0
answers
152
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 $\...
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 ...
- 21.2k
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
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
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
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
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
3
votes
0
answers
96
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 ...
- 21.2k
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
-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
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
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
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.4k
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
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
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 ...
- 21.2k
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
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
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
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
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:\...
- 21.2k
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
5
votes
0
answers
187
views
Is there an effective way to compute the square root of an algebraic number?
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
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&...
- 21.2k
1
vote
0
answers
123
views
Is possibile to define transfinite sum and product recursively? [closed]
On mathstackexchange a few days ago I published the following question where I asked about "transfinite" sum and products but actually nobody answered or gave an opinion with a comment: thus ...
3
votes
0
answers
87
views
Is the probability distribution of a graphon given as a graph limit computable?
Let $G_i$ be a sequence of finite graphs that is Cauchy in the space of graphons. That is, for every $\epsilon \in \mathbb Q_+$ there is a $N \in \mathbb N$ such that $$\forall n, m > N. \delta_\...
- 6,353
10
votes
0
answers
181
views
"Effective gaps" in the c.e. degrees
Below, $W_e$ is the $e$th c.e. set according to some appropriate list of such.
In a very loose analogy with Hausdorff gaps, say that an effective gap is a pair of computable sequences $(c_i)_{i\in\...
- 21.2k
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
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
-3
votes
1
answer
173
views
why $L=\{\langle M\rangle\mid M \text{ is a TM that accepts all even number}\} \notin \text{RE}$ [closed]
$L=\{\langle M\rangle \mid M \text{ is a TM that accepts all even number}\}$
hello everyone I anderstennd why $L\in \text{coRE} $ b but I don't understand why $ L\notin \text{RE}$
I Have proved that $ ...
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
7
votes
0
answers
255
views
Is it decidable whether a statement about reals (in the language of ordered rings) is constructively provable?
The language of ordered rings is a first-order language with operators for $+$, $-$, and $\cdot$, constants for $0$ and $1$, and relations for $<$, $=$ and $>$.
To decide whether such a ...
- 6,353
5
votes
1
answer
560
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
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
2
votes
0
answers
118
views
Uniformization and functions on Turing degrees
Assuming Martin's Conjecture on functions between Turing degrees, is AD + DC consistent with existence of an $f:\mathcal{D}_t → \mathcal{D}_t$ of rank $Θ$ ?
$\mathcal{D}_t$ is the set of Turing ...
- 7,545