patternMajor
What are the simplest examples of programs that we do not know whether they terminate?
Viewed 0 times
thewhetherknowwhatterminatearesimplestexamplesthatprograms
Problem
The halting problem states there is no algorithm that will determine if a given program halts. As a consequence, there should be programs about which we can not tell whether they terminate or not. What are the simplest (smallest) known examples of such programs?
Solution
A pretty simple example could be a program testing the Collatz conjecture:
$$
f(n) =
\begin{cases}
\text{HALT}, &\text{if $n$ is 1} \\
f(n/2), & \text{if $n$ is even} \\
f(3n+1), & \text{if $n$ is odd}
\end{cases}
$$
It's known to halt for $n$ up to at least $5 × 2^{60} ≈ 5.764 × 10^{18}$, but in general it's an open problem.
$$
f(n) =
\begin{cases}
\text{HALT}, &\text{if $n$ is 1} \\
f(n/2), & \text{if $n$ is even} \\
f(3n+1), & \text{if $n$ is odd}
\end{cases}
$$
It's known to halt for $n$ up to at least $5 × 2^{60} ≈ 5.764 × 10^{18}$, but in general it's an open problem.
Context
StackExchange Computer Science Q#44869, answer score: 47
Revisions (0)
No revisions yet.