2021-07-22

# Introduction

The halting problem asks whether it’s possible to design a function `halts(f)`

that
returns `True`

if a function `f`

halts or `False`

if `f`

runs forever.

# A Proof That the Halting Problem Is Undecidable

The most common proof that the halting problem is undecidable defines a
program that halts if and only if `halts`

says it does not halt:

```
def liar():
if halts(liar):
liar()
```

The idea is that `liar`

enters infinite recursion if `halts(liar)`

returns
`True`

, and `liar`

halts if `halts(liar)`

returns `False`

. It isn’t clear
whether `halts(liar)`

should return `True`

or `False`

, so the standard
conclusion is that `halts`

cannot exist and thus the halting problem is
undecidable.

# An Analogous Proof

Consider the following proof:

- Define
`positive_or_negative(x)`

as a function that takes an integer parameter`x`

and returns`True`

if`x`

is positive or`False`

if`x`

is negative. - Zero is not positive or negative, so
`positive_or_negative(0)`

can’t return either`True`

or`False`

. - The problem of determining whether a number is positive or negative is undecidable.

There are several ways to design a function that determines whether a number is positive or negative, including:

- Raise an error on an input of
`0`

. - Return three values instead of a Boolean (possibly
`-1`

for negative,`0`

for zero, and`1`

for positive). - Use an
`if-else`

construct instead of`if-elif`

: define`is_positive`

or`is_negative`

instead of`positive_or_negative`

.

The standard proof that the halting problem is undecidable chooses an approach similar to option 1. I wonder if option 2 or 3 would make more sense.

# Tweaking the Definition of `halts`

The original specification for `halts`

looks something like this:

```
def halts(f):
if f halts:
return True
elif f does not halt:
return False
else:
raise an error
```

The analog of option 2 from `positive_or_negative`

is to return a different
value for each type of halting behavior, rather than just `True`

or `False`

.
There are at least five cases to handle: halting programs, infinite
loops, `f`

halts if `halts(f)`

returns `False`

, `f`

halts if `halts(f)`

returns `True`

, and invalid functions (for example, `f`

is a string).

One solution based on option 3 from `positive_or_negative`

looks like this:

```
def halts(f):
if f halts:
return True
else:
return False
```

Here the `else`

clause covers all cases other than simple halting, including `liar`

.

The question I’d like to raise is whether the standard proof that the halting
problem is undecidable applies to these latter two versions of `halts`

.

# Notes

Eric Hehner and Bill Stoddart have raised similar questions in the past. I wrote
a longer paper on the halting problem that
looked at Turing’s work on the topic, including an incomplete proof of the
`if-else`

case in the last paper that he published.