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?
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.
