A Turing Machine is a mathematical model of computing. It utilises symbols on a tape to represent memory, and despite its simplicity, it is capable of representing any computer algorithm. It is a very powerful tool, and we can use it to prove properties of Computer Science itself.
There are certain problems within the field of Computer Science that are undecidable. These are decision problems, where it is impossible to create an algorithm that will always correctly return yes or no. Instead, in some cases, the algorithm will loop forever.
We can use Reductions between Turing Machines to prove the undecidability of problems. This article looks at the Halting Problem, shows why it is undecidable, and gives an example reduction from the Halting Problem to the Membership Problem.
For all of the Turing Machines in this article, assume the alphabet (Σ) = {0,1}. This means that the strings passed to the Turing Machines will be comprised of only 0’s and 1’s (eg. 011010). While this is done for simplicity, these proofs work for other alphabets with little modification.
Please note: This article assumes some prior knowledge of what a Turing Machine is, and how it operates.
What is the Halting Problem?
A Turing Machine M has three possible outputs for a given input x. It can accept x, reject x, or loop forever.
Imagine we are given a Turing Machine M. On a given input string x, can we decide whether M will halt when run on the input x? To put it another way, can we tell whether M will give us a definite output, opposed to looping forever.
The Halting Problem is known to be undecidable, and this can be shown using the following proof created by Christopher Strachey:
Suppose there exists a function halts(x), which will return true, if x halts, and false otherwise.
We define the following function :
def g():
if halts(g):
loop_forever()In this code, if halts(g) returns true, it implies that g halts. However, as halts(g) has returned true, g will loop forever and so will not halt — presenting a contradiction.
On the other hand, if halts(g) returns false, then g will halt — another contradiction.
This small counterexample shows why the Halting Problem is undecidable — we can never create an algorithm to determine whether a given Turing Machine will halt. We can use the Halting Problem, and reduce it to other problems, to show that they are also undecidable. This establishes the Halting Problem as a powerful tool for classifying problems.
Reducing the Halting Problem to the Membership Problem
The Membership Problem is defined simply as:
Given a Turing Machine M and a string x, does M accept x?
To show that the Membership Problem is undecidable, we need to show that the Halting Problem is no harder than the Membership Problem. We can use the symbol ≤ₘ to represent this. So what we are attempting to show, is that HaltingProblem(HP) ≤ₘ MembershipProblem(MP).
We can first assume that we have a decider for the Membership Problem (ie. Assume a function exists such that if we pass in a Turing Machine and a string, the function will return true if the Turing Machine accepts the string, and false otherwise).
If we can use this decider to solve the Halting Problem, we have shown that the Halting Problem is no more difficult than the Membership Problem. Since the Halting Problem is known to be undecidable, we can deduce that the Membership Problem is also undecidable.
Algorithm Plan
Our algorithm has full access to the decider for the membership problem, let’s call this DecideMember. We want to create a new machine, which when passed to the DecideMember function, determines whether the original machine from the Halting Problem halts on its input.
We construct our new Turing Machine in a clever way, such that if the original machine halts, our new machine is always accepted by the DecideMember function. This will ensure that the value of the call to DecideMember is completely determined by whether our original machine halts — solving the Halting Problem.
The Algorithm
We construct a decider for the Halting Problem, let’s call this DecideHalt.
DecideHalt(<M, x>):
Construct new Machine M'
M'(y):
Simulate machine M on input x
Return TRUE
If DecideMember(<M', x>):
Return TRUE
Else
Return FalseIf we can prove this algorithm works in both directions, we can conclude that it is a valid reduction.
=> If M does halt on x
Our machine M' returns true for every string
This includes returning true for the string x
Therefore, our call to DecideMember(<M', x>) will return true
So the decider will return true if M halts
<= If M does not halt on x
Our machine M' will never halt
Therefore, it will not accept any string, including the string x
Therefore, our call to DecideMember(<M', x>) will return false
So the decider will return false if M does not halt
As we can show our decider produces the correct result both for when M halts on x, and when it does not, we have given a valid reduction from the Halting Problem to the Membership Problem. This means that the Halting Problem is no more difficult than the Membership Problem, i.e. HP ≤ₘ MP, and as the Halting Problem is undecidable, the Membership Problem is also undecidable.
Further Reductions
This proof format can be used to show that many other problems are undecidable. For example, consider the following decision problem:
Given a Turing Machine M, can we determine whether M accepts all strings?
We can construct our algorithm in a very similar way, and create a reduction from the Halting Problem to this problem. Let’s call our decider for this problem DecideAllAccept. We construct our algorithm for the Halting Problem as follows:
DecideHalt(<M, x>):
Construct new Machine M'
M'(y):
Simulate machine M on input x
Return TRUE
If DecideAllAccept(<M'>):
Return TRUE
Else
Return FalseAs you can see, our algorithm is almost identical to the reduction to the Membership Problem. The only changes are that we instead call a decider for our new problem, and we only pass our new Turing Machine, without any string, as we are checking that it accepts all strings. We can prove that this holds in both directions using similar logic. From this, we can conclude that checking whether a Turing Machine accepts all strings is also undecidable.
Finally, let’s look at a slightly more difficult reduction. We are given the following problem:
Given a Turing Machine M, can we determine whether M accepts exactly two strings?
We construct our algorithm for DecideHalt in a similar way, calling the decider for this problem DecideTwo.
DecideHalt(<M, x>):
Construct new Machine M'
M'(y):
Simulate machine M on input x
If y == 0 or y == 1:
Return TRUE
Else
Return FALSE
If DecideTwo(<M'>):
Return TRUE
Else
Return FalseThis algorithm takes a similar approach to the Membership Problem reduction, however, we need to artificially ensure that our decider will return true when we pass it our machine M'. To do this, we create a machine which, if M halts on x, only accepts two possible strings: y=0 and y=1. This ensures that our decider will return true for M' as long as M halts.
With this new machine, we can once again prove that our reduction holds in both directions, ensuring that this is a valid reduction. We have proved that checking whether a Turing Machine accepts two strings is undecidable.
Wrapping Up
Reductions between Turing Machines are a powerful tool to show the undecidability of problems. We’ve shown a few reductions, but many more problems can be shown to be undecidable using a reduction from the Halting Problem. We can even use any other problem that we know to be undecidable as the basis for our reductions.
