# David Wyde

A Slightly Different Halting Problem

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:

1. 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.
2. Zero is not positive or negative, so `positive_or_negative(0)` can’t return either `True` or `False`.
3. 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:

1. Raise an error on an input of `0`.
2. Return three values instead of a Boolean (possibly `-1` for negative, `0` for zero, and `1` for positive).
3. 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`.

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.