Questions tagged [computability]
Questions about Turing computability and recursion theory, including the halting problem and other unsolvable problems. Questions about the resources required to solving particular problems should be tagged (computational-complexity).
2,547 questions
7
votes
1
answer
241
views
Can countably many giraffes guess the color of their own scarf correctly if each may be mistaken about the color of finitely many scarves?
This question is based on the question Is it possible to formulate the axiom of choice as the existence of a survival strategy? (MathOverflow).
Consider the following "computable giraffes, lion &...
- 4,970
20
votes
1
answer
599
views
Is the Collatz map algorithmically decidable?
Question: Has it been proven that the following decision problem is algorithmically decidable?
$$
P_\text{Collatz} := \text{Given $n \in \mathbb{N}_+$, does the Collatz-Iteration of $n$ eventually ...
- 2,458
3
votes
2
answers
292
views
Recursively enumerable sets and the natural numbers
The standard definition of recursive enumerability is as follows: a set of natural numbers is recursively enumerable if there exists an algorithm which halts precisely on inputs which are elements of ...
- 1,248
4
votes
0
answers
93
views
Can probability theory be made fully computable?
I’ve been reading about objective Bayesian theories lately and came upon the concept of universal priors and specifically, the Solomonoff prior. This seemed to answer my initial query about whether a ...
5
votes
1
answer
152
views
Upward closure of the PA degrees
In the book I read, PA degrees are defined as containing a completion of Peano arithmetic.
I'm searching for a proof that PA degrees are closed upwards (which is non-trivial with this definition). ...
- 166
5
votes
1
answer
150
views
Theorem 3.4 of Soare
I am reading Robert I. Soare's "Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets" for a directed reading course. I am having trouble ...
0
votes
0
answers
66
views
Proving Inf is 1-reducible to Tot
I am currently working on a proof that $\mathrm{Inf}\leq_1\mathrm{Tot}$, where
$$\mathrm{Inf}=\{e:\mathrm{Dom}\,\varphi_e \text{ is infinite}\} \quad \mathrm{Tot}=\{e:\varphi_e\text{ is total}\}$$
(...
- 329
2
votes
1
answer
120
views
Is function defined by infinite cases partial recursive?
I am trying to prove that a certain function is partial recursive. Suppose we have fixed primitive recursive $g:\mathbb{N} \rightarrow \mathbb{N}$ and for each $d$ let $f_d:\mathbb{N}\rightarrow \...
- 167
1
vote
0
answers
110
views
Where is the relativized uniform complementor on r.e. indices stated explicitly (index-operator form)—existence for $\emptyset'$ and any minimality?
Let $\langle W_e : e\in\mathbb{N}\rangle$ be the standard effective enumeration of recursively enumerable (r.e.) sets, where
$$
n\in W_e \;\Longleftrightarrow\; \exists s\;\big(\varphi_e(n)\ \text{...
- 31
4
votes
1
answer
157
views
Can superposition alone generate the Kalmár elementary function $x^y$ from $⟨x + y, x \bmod y, 2^x⟩$?
In Mihai Prunescu, Lorenzo Sauras-Altuzarra, and Joseph M. Shunia (2025), A Minimal Substitution Basis for the Kalmar Elementary Functions, the authors define a minimal generating set for the Kalmár ...
- 41
2
votes
0
answers
90
views
Computational content of axiom of countable choice in HoTT
The question is possibly related to this, but I don’t find a satisfactory answer there.
Let $X$ be a set and $P(n, x)$ be a mere proposition for all $n: \mathbb{N}$ and $x: X$. The axiom of countable ...
- 650
1
vote
1
answer
104
views
Recursive functions are $\Sigma_1$ in PA? [duplicate]
I am working with recursive functions on $\omega$. It is well known that these functions are representable, in the sense of the following definition:
A function $f:\omega\to\omega$ is representable in ...
- 164
3
votes
0
answers
109
views
Proof without diagonalization that Kleene's $\mathcal{O}$ is not computable
I wanted to prove that Kleene's $\mathcal{O}$ is not computable without using the diagonalization trick, and was wondering if the following proof would work?
Note: ordering = well-ordered set.
Suppose ...
- 211
4
votes
0
answers
65
views
When are $\ell$-adic betti numbers of varieties computable
Let $X$ be a proper variety over a global field $k$. Then we can find a model $\mathfrak{X}$ over a Dedekind domain $R$ of finite type. Every special fiber of $\mathfrak{X}$ is over a finite field, so ...
- 650
0
votes
0
answers
105
views
What is the Turing degree of an infinite subset of the Halting problem?
I am not a professional mathematician, so please forgive me for my inaccurate description.
$H$ is a sequence that expands the Chaitin's constant into binary form.
Program $A$ takes $k$ as input and ...
- 1