# Do we need to live with the uncertainty?

##### Introduction

In the previous post we have seen that the halting problem cannot be solved. But maybe the problem is just in our programming languages, so let’s see if we can improve them to disallow non-halting programs.

##### Bounded C

A program can fail to halt by two reasons (we are ignoring I/O, limited memory sizes and all that earthly issues 😀 ): it can get trapped in an infinite loop or we can enter an infinite recursion. So let’s take a language like C and remove these “troublesome” features from it by

• only allowing iteration via the for (b = 0; b < a; b++) construct and
• removing the possibility of doing either direct or indirect recursion.

At first sight we haven’t lost a lot. For example we can easily raise numbers to a power

```int my_pow(int base, int exp)
{
int p = 1, i;
for (i = 0; i < exp; i++)
p *= base;
return p;
}
```

or compute the elements of the Fibonacci series.

```int fib(int n)
{
int a = 0, b = 1, i, t;
for (i = 0; i < n; i++)
{
t = a + b;
a = b;
b = t;
}
return a;
}
```

But maybe we have lost something subtler…

##### Challenge

Can we make a function in “normal C” that cannot be implemented in our “bounded C”? The answer will be given in the following post… or in the comments 😀

# A really impossible problem

##### The problem

Previously we have solved a puzzle that claimed to be impossible but was, in fact, just a bit hard 😀 But in this post we will see a problem that is really impossible to solve, the halting problem:

Given a description of an arbitrary computer program, decide whether the program finishes running or continues to run forever.

For some programs it’s easy to see if they halt or not:

```def program_1():
return 2 + 2

def program_2():
while True: pass

def program_3():
from itertools import count
for i in count():
if str(2**i) == '7':
break

def program_4():
from itertools import count
for i in count():
if str(2**i)[-1] == '7':
break
```

For others it’s not so simple:

```def program_5():
def z(m, n):
if m == 0:
return n + 1
elif n == 0:
return z(m - 1, 1)
else:
return z(m - 1, z(m, n - 1))
z(4, 4)
```

And there are simple ones where it’s an open problem to know if they halt or not:

```def program_6():
from itertools import count
for i in count(1):
p = 2 ** i
r = int(''.join(reversed(str(p))))
for j in count(1):
q = 5 ** j
if q > r:
break
elif q == r:
return
```
##### The proof

Let’s assume we have a procedure, represented by the function does_halt(), to determine if any given program will halt:

```def does_halt(program):
#
# magic implementation
#
```

We don’t care about the details of the does_halt() function. The only requirements are:

• Its implementation should be finite.
• It must accept any Python function that doesn’t take arguments as a program.
• It must give an answer in an easily bounded time. For example, we should be able to say “if the input program has 1000 bytes, the function should return a boolean value indicating if it halts in no more than NNN seconds”.

The clever point of the proof, though it’s not a new kind of cleverness, is to build a program that “halts only if it doesn’t”:

```def paradox():