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).
Questions tagged [computability]
2395 questions
6
votes
1 answer
Is being able to decide which program stop first equivalent to the halting problem?
Here is the "halting first" problem: given two programs $P$ and $Q$, return 0 if $P$ stops after less steps than $Q$, return $1$ if $Q$ stops after less steps than $P$, and otherwise output $0$ or $1$. (So if neither problem halts, or if both halts…
QuinnLesquimau
- 2,053
6
votes
1 answer
A Turing machine for which halting is outside ZFC
If, given Turing machine T, "T halts" or "T doesn't halt" could be derived from axioms of ZFC, halting problem would be in R. As it isn't, there must exist a Turing machine for which truth or falsehood of halting is independent of ZFC.
I want to see…
Karolis Juodelė
- 9,702
- 1
- 25
- 39
6
votes
1 answer
Generating an uncomputable number by throwing dice
If I were to roll a die infinitely many times, assuming the result was truly random, and use the results as the decimal places of a number, would that number (likely) be an uncomputable number?
vinmann11
- 63
6
votes
3 answers
Approachable = provably approachable?
Question: Let’s call a real number $x$ approachable if there exists a Turing machine $M$ such that $M(1), M(2),\dots$ is a sequence than converge to $x$. If we can prove (edit: In ZFC) that the sequence converge, we say that $x$ is provably…
Sune Jakobsen
- 995
6
votes
1 answer
Show $f$ is primitive recursive, where $f(n) = 1$ if the decimal expansion of $\pi$ contains $n$ consecutive $5$'s
Let $f:\mathbb{N}\to\mathbb{N}$ be given by $f(n)=1$ if the decimal expansion of $\pi$ contains $n$ consecutive $5$'s, and $f(n)=0$ otherwise.
How would you go about showing such a function is primitive recursive?
I suppose you should be able to…
FPP
- 2,103
5
votes
3 answers
To Prove an undecidable language on halting
I am student learning Computational Complexity this semester. The text book is Sanjeev Arora et al. Computational Complexity, Cambridge University Press.
I cannot solve the first problem in Chapter Three(p.77), which may be probably…
qsty
- 51
5
votes
3 answers
Why are all finite sets recursive?
Obviously a finite set for which the members are explicitly given or for which a computable rule is available will be recursive. (By which I mean its characteristic function is computable.)
However, suppose the finite set is such that we don't know…
Ray
- 91
5
votes
2 answers
Example of sets $A, B$ such that $A', B'$ are Turing equivalent but $A, B$ are not.
I have been wondering if the following statement is true,
$$
A\equiv_TB\iff A'\equiv_TB'
$$
where $A, B\subseteq\omega$ and $A'$ denotes the Turing jump of $A$. I have been able to show the forward direction, but have been unable to show the…
Trent
- 51
4
votes
2 answers
Showing that a function is not computable.
the following function was shown not to be computable:
$h(x) = \begin{cases} \mu n.\Phi_x(n) \downarrow & \mbox{if } \exists n \Phi_x(n) \downarrow \\ \uparrow & \mbox{otherwise} \end{cases}$
using the following auxiliary function:
$f(x,y) =…
trojan
- 79
4
votes
1 answer
One-reducibility extending to onto function
I'm working on the following problem from Soare: If $A$ is one-reducible to $B$ (i.e. $A \leq_1 B$), and $A, B$ are c.e., and $A$ is infinite, then $A$ is one-reducible to $B$ via some $f$ such that $f(A)=B$.
I know $A \leq_1 B$ if there's a total…
nullgraph
- 653
4
votes
1 answer
A function agreeing with a primitive recursive function at all but finitely many points is primitive recursive
Show that if $f:\mathbb{N} \rightarrow \mathbb{N}$ is primitive recursive,
$A \subseteq \mathbb{N}$ is a finite set, and $g$ is a total function agreeing
with $f$ at every point not in $A$, then $g$ is primitive recursive.
This is exercise…
Anna
- 43
4
votes
2 answers
Why this partial function is not computable?
Let us consider the following function : $g(i,j,x) = \left\{
\begin{array}{ll}
\varphi(i,x) \lor \varphi(j,x) & \mbox{if} \ \varphi(i,x) \downarrow \land \ \varphi(j,x)\uparrow \ \mbox{or} \ \varphi(i,x)\uparrow \land \ \varphi(j,x)…
Maman
- 3,300
4
votes
1 answer
Soare Turing Computability[2016] exercise 6.3.5
Some definitions: A set is $immune$ if it is infinite but contains no infinite r.e. subset. Given a finite set $A = \{x_1 < x_2 < · · · < x_k\}$, the number
$y = 2^{x_1} + 2^{x_2} + · · · + 2^{x_k}$ is called the canonical index of A. Let
$D_y$…
Jun Xu
- 449
4
votes
2 answers
Proving induction from basic recursion lemma
Induction Principle: Let $A$ be a set such that $0 \in A$ and $n \in A \implies n + 1 \in A$. Then for all $n \in \mathbb{N}$, $n \in A$.
Basic Recursion Lemma: For all sets $X, W$ and given functions $g : X \to W$, $h : W \times \mathbb{N} \times X…
zrbecker
- 4,048
