What are the simplest examples of programs that we do not know whether they terminate?
A pretty simple example could be a program testing the Collatz conjecture:
$$
f(n) =
\begin{cases}
\text{HALT}, &amp;\text{if $n$ is 1} \\
f(n/2),  &amp; \text{if $n$ is even} \\
f(3n+1), &amp; \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.