Turing Machine and Halting Problem

In a previous post
I talked briefly about Alan Turing's model of computation, called the
Turing Machine.

Today we will look into this in more detail and discuss an interesting
problem called the Halting problem.

Context¶

Alan Turing was interested in what it meant to compute something.
To fully grasp the severity of this problem we need to step back in time.

This is the 1930s that we are talking about, there were no proper
computers yet. Computers and the whole computer science field was not
yet born. So in this context a computer was something (or someone)
that could perform arithmetic operations. Humans who did this were
called human computers
There were
mechanical
calculators
that existed back then but again, they all required a human operator.

So ultimately it was the operator who was responsible for making
decisions about what to do with the numbers. There was not automated
reasoning that any machine could follow.

What Alan Turing was interested in; was to understand the meaning of
what it means for a task to be computable. This is one of the core
areas in Philosophy of Computer Science. However to answer this
question he needed a a formal definition of computation itself (which
did not exist at that time).

NOTE : As a mental exercise before doing anything else just sit back and
think about this yourself. We use computers daily but at its very
core, what does computation mean ?

So in order to have a formal definition of computation we needed a
model for computation. This is what Alan Turing came up with and this
is what we now call the Turing Machine.

The Idea¶

Picture a typewriter. The Turing Machine is heavily inspired by this
system (typewriter + operator). In the book "Alan Turing: The Enigma"
the writer Andrew Hodges tells us that Alan was fascinated by
typewriters. We can see this inspiring his work.

What does a typewriter have ? A typewriter has a paper for printing, a
system that outputs characters on said paper, a mechanism for input
that tells the typewriter what to print. Additionally the typewriter
system also has the user whose job is to tell the typewrite what to do
and it keeps track of what the typewriter has already done.

Now, the Turing Machine is a hypothetical machine (or more precisely a
mathematical model); it does not exist in real life. It is a state
machine which means that the machine has a finite number of states in
which it can be. It can read information/instructions from a tape and
based on that it moves from one state to another. The number of states
is finite. It can also write data on the tape.

A Turing Machine has 4 main parts:

The tape
The head
The state
The transition table

The tape is the memory of the machine. The tape is divided into
blocks of the same width and only one symbol is present in one
block. The machine can read symbols from this tape and can write
symbols to this tape. At a given time there is only one symbol in the
machine. This symbol is referred to as the scanned symbol. The
machine can be supplied with an infinitely long tape.

The head is a contraption that can read symbols from the tape and can
write symbols to the tape as well. The head can also move the tape to
the left or right but by only one block at a time.

The state of the Turing Machine. This state is a intriguing
concept. This state is used to replace the state of mind of the
typewriter operator (or any person performing any computation for that
matter). At any time the Turing Machine can be one of many finite
states.

The transition table is a set of finite rules that given the current
state the machine is currently and the scanned symbol tells the Turing
Machine to write a symbol into the tape, then move the tape left or
right and finally to assume a new state (or stay in the same one).

Now the Turing Machine is a model of computation, thus it must be
able to do some computation; right? So how does it do that.

Problems for a Turing Machine.¶

Problems in Automata Theory are generally of the form that involves
some "computer" determining if some string belongs to a set of strings
or not, based on some rules. This set of strings is called that follow
a general rule for membership is called a Language and the "computer"
involved is called an automaton which is nothing but a model of
computation. We choose to represent various computational problems as
languages because we already have established a terminology for
dealing with languages.

To perform some computation in a Turing Machine we write a program
for the machine. This program is basically a set of transition rules.

Given any string as input the Turing Machine can do one of three
things. It can stop and accept the string or it can reject the
string or it can loop indefinitely over the input.

When the TM is in either the accept or the reject state after
processing a string then we say that the TM has halted (as in stopped
running on the output). On the other hand if the TM does not halt and
instead keeps on looping indefinitely then it means that the TM will
never stop working or never halt. When a TM has halted it indicates
that the TM has decided the string (either accept or reject) on the
other hand when it does not halt then the string (or rather the
problem) is said to be undecidable.

All this can get quite intense, so here is an intuitive definition of
computation by a Turing
Machine. The
Church-Turing thesis showed
that a Turing Machine algorithm captures all algorithms. This
means that if for a given problem we can design a Turing Machine
algorithms then that problem is actually solvable. As we will soon
see that there are certain problems that are so complex that there
exists no algorithm that can solve them. In-fact while describing
Turing Machine algorithms we do not need to go into the implementation
level details of how the head and the tapes move; instead we can just
use English prose to describe an algorithm. The only requirement is
that an algorithm to stop in a finite number of steps (this is quite
literally the definition of an algorithm).

Universal Turing Machine¶

A Turing Machine is generally programmed to perform only a single type
of computation. However there is a class of Turing Machines called the
Universal Turing Machine which can perform any sort of computation. In
fact this property of this Turing Machine is what makes a Turing
Machine such a powerful model for computation.

The Universal Turing Machine can simulate any arbitrary Turing machine
on any arbitrary string. It does this by reading the description of
the Turing machine and the string input from its own tape and then
processing them.

This makes the Turing Machine capable of answering questions about the
behavior of other Turing machines. This model of computation is a
very accurate model of modern computers where computers have access to
a random access memory. This is the same as the tape in a Turing
Machine.

Thus the problems these Turing Machines can tackle are generally of
the form where we test the behavior of some arbitrary Turing machine
on some arbitrary input.

The Halting Problem¶

The Halting Problem is a decision problem of determining whether any
arbitrary Turing Machine will halt on an arbitrary string input or
not.

In other words lets say that we have a Language \(H_{Lang}\) which is
made up of all string encoding of the form \(<B,w>\) where \(B\) is a
Turing Machine and \(w\) is a string and \(B\) halts on \(w\). We need to
show that \(H_{Lang}\) is undecidable. Which means that there isn't a
single imaginable Turing Machine that can decide \(H_{Lang}\).

Which means that no one can ever design a Turing Machine that will
be able to take an arbitrary string \(w\) and an arbitrary Turing
machine \(B\) and tell whether \(B\) will halt on \(w\) or not.

Now, this might seem like a fairly un-important detail but this has
some far-reaching implications as we will soon see. But before that we
will prove the above statement. This is a fun proof that illustrates
how to think about these problems in general.

Proof¶

Let us assume that such a machine does exist and let us call it
\(H_{TM}\).

Construction of \(H_{TM}\):

Input : String \(<B,w>\), where \(B\) is a TM and \(w\) is a string.
Run : Simulates \(w\) on \(B\).
Accepts : \(w\) if \(B\) halts on \(w\)
Rejects : \(w\) if \(B\) does not halt on \(w\).

This is the decider that we have to prove can not exist.

Now, since \(H_{TM}\) already exists we can use this machine to
construct another Turing Machine \(D_{TM_H}\) which has \(H_{TM}\) as a
subroutine (hence the sub-subscript notation).

Construction of \(D_{TM_H}\):

Input : String \(<M>\), where \(M\) is a Turing machine
Runs : Simulates \(<M, <M>>\) on \(H_{TM}\)
Accepts : \(<M>\) if \(H_{TM}\) rejects \(<M, <M>>\), i.e. if \(M\) rejects \(<M>\)
Rejects : \(<M>\) if \(H_{TM}\) accepts \(<M, <M>>\), i.e. if \(M\) accepts \(<M>\)

Now, what happens if we run \(D_{TM_H}\) on \(<D_{TM_H}>\) ?

By the above Accept and Reject conditions,

If \(D_{TM_H}\) accepts \(<D_{TM_H}>\), then it means that \(H_{TM}\)
rejected \(<D_{TM_H}, <D_{TM_H} >>\) which means that \(D_{TM_H}\)
rejects \(<D_{TM_H}>\)
If \(D_{TM_H}\) rejects \(<D_{TM_H}>\), then it means that \(H_{TM}\)
accepted \(<D_{TM_H}, <D_{TM_H} >>\) which means that \(D_{TM_H}\)
accepted \(<D_{TM_H}>\)

This is a contradiction because it implies that \(D_{TM_H}\) accepts
itself if it rejects itself.

Hence our initial assumption about the existence of \(H_{TM}\) must be
wrong. Hence \(H_{TM}\) can not exist.

There is another proof for this that uses the Cantor's diagonalisation argument¶

Conclusion¶

This means that

There does not exist a single algorithm that can us if another
algorithm will halt or not

Static analyzers try and do solve some of these limitations but yes,
they are not 100% accurate, because they are mathematically guaranteed
to not be 100% accurate.

This post is part of a series of posts that I have planned. In the
next one we will talk about Godels Incompletelness Theorems and
Hilberts Problems.