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.
8 questions from the last 30 days
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
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
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
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
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
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
-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