Understanding Computation (51 page)

We’ll assume that
$stdin.read
always immediately
returns a value—namely, that every program’s standard input is finite and
nonblocking—because we’re interested in the internal behavior of the program, not its
interactions with the operating system.

The fundamental difficulty is that it’s hard to predict what a program will do without
actually running it. It’s tempting to run the program with
#evaluate
to see whether it halts, but that’s no good: if the program doesn’t halt,
#evaluate
will run forever and we won’t get an answer from
#halts?
no matter how long we wait. Any reliable
halting-detection algorithm must find a way to produce a definitive answer in a finite
amount of time just by inspecting and analyzing the text of the program, not by simply
running it and waiting.

Let’s pretend temporarily that the halting problem is decidable. In this imaginary
world, it’s possible to write a full implementation of
#halts?
, so a call to
halts?(program,
input)
always comes back with a
true
or
false
answer for any
program
and
input
, and that answer always
correctly predicts whether
program
would halt if it was
run with
input
on standard input. The rough structure
of the
#halts?
method might be something like
this:

def
halts?
(
program
,
input
)
# parse program
# analyze program
# return true if program halts on input, false if not
end

If we can write
#halts?
, then we can construct
does_it_halt.rb
, a program that reads another
program as input and prints
yes
or
no
depending on whether that program halts when it reads the
empty string:
^[
75
]

def
halts?
(
program
,
input
)
# parse program
# analyze program
# return true if program halts on input, false if not
end
def
halts_on_empty?
(
program
)
halts?
(
program
,
''
)
end
program
=
$stdin
.
read
if
halts_on_empty?
(
program
)
print
'yes'
else
print
'no'
end

Once we have
does_it_halt.rb
, we can use it to solve very
difficult problems. Consider this famous claim made
by Christian Goldbach in 1742:

This is
the
Goldbach conjecture
, and it’s
famous because nobody has been able to prove whether it’s true or
false. The evidence suggests that it’s true, because an even number
picked at random can invariably be broken apart into two primes—12 = 5
+ 7, 34 = 3 + 31, 567890 = 7 + 567883 and so forth—and computers have
been used to check that this can be done for all even numbers between
four and four quintillion (4,000,000,000,000,000,000). But there are
infinitely many even numbers, so no computer can check them all, and
there’s no known proof that every even number must break apart in this
way. There is a possibility, however small, that some very large even
number is
not
the sum of two primes.

Proving the Goldbach conjecture is one of the holy grails of number theory; in the
year 2000, the publisher
Faber and Faber offered a million-dollar prize to anyone who could produce a
proof. But wait: we already have the tools to discover whether the conjecture is true! We
just need to write a program that searches for a counterexample:

require
'prime'
def
primes_less_than
(
n
)
Prime
.
each
(
n
-
1
)
.
entries
end
def
sum_of_two_primes?
(
n
)
primes
=
primes_less_than
(
n
)
primes
.
any?
{
|
a
|
primes
.
any?
{
|
b
|
a
+
b
==
n
}
}
end
n
=
4
while
sum_of_two_primes?
(
n
)
n
=
n
+
2
end
print
n

This establishes a connection between the truth of the Goldbach
conjecture and the halting behavior of a program. If the conjecture is
true, this program will never find a counterexample no matter how high
it counts, so it will loop forever; if the conjecture’s false,
n
will eventually be assigned the
value of an even number that isn’t the sum of two primes, and the
program will halt. So we just have to save it as
goldbach.rb
and run
ruby does_it_halt.rb < goldbach.rb
to
find out whether it’s a halting program, and that will tell us whether
the Goldbach conjecture is true. A million dollars is ours!
^[
76
]

Well, obviously this is too good to be true. To write a program
that can accurately predict the behavior of
goldbach.rb
would require a proficiency in
number theory beyond our current understanding. Mathematicians have
been working for hundreds of years to try to prove or disprove the
Goldbach conjecture; it’s unlikely that a bunch of avaricious software
engineers could construct a Ruby program that can miraculously solve
not only this problem but
any
unsolved
mathematical conjecture that can be expressed as a looping
program.

So far we’ve seen strong evidence that the halting problem is
undecidable, but not conclusive proof. Our intuition may say it’s
unlikely that we can prove or disprove the Goldbach conjecture just by
turning it into a program, but computation can be pretty
counterintuitive at times, so we shouldn’t allow ourselves to be
convinced solely by arguments about how improbable something is. If
the halting problem really is undecidable, as opposed to simply very
difficult, we should be able to prove it.

Here’s why
#halts?
can never
work. If it
did
work, we’d be able to construct a
new method
#halts_on_itself?
that
calls
#halts?
to determine what a
program does when run with its own source code as input:
^[
77
]

def
halts_on_itself?
(
program
)
halts?
(
program
,
program
)
end

Like
#halts?
, the
#halts_on_itself?
method will always finish and return a Boolean value:
true
if
program
halts when run with itself as input,
false
if it loops
forever.

Given working implementations of
#halts?
and
#halts_on_itself?
, we can write a program
called
do_the_opposite.rb
:

def
halts?
(
program
,
input
)
# parse program
# analyze program
# return true if program halts on input, false if not
end
def
halts_on_itself?
(
program
)
halts?
(
program
,
program
)
end
program
=
$stdin
.
read
if
halts_on_itself?
(
program
)
while
true
# do nothing
end
end

This code reads
program
from
standard input, finds out whether it would halt if run on itself, and
promptly does the exact opposite: if
program
would halt,
do_the_opposite.rb
loops forever; if
program
would loop forever,
do_the_opposite.rb
halts.

Now, what does
ruby do_the_opposite.rb
< do_the_opposite.rb
do?
^[
78
]
Just as we saw earlier with
does_it_say_no.rb
, this question creates an
inescapable contradiction.

#halts_on_itself?
must return
either
true
or
false
when given the source of
do_the_opposite.rb
as an argument. If it
returns
true
to indicate a halting
program, then
ruby do_the_opposite.rb <
do_the_opposite.rb
will loop forever, which means
#halts_on_itself?
was wrong about what would
happen. On the other hand, if
#halts_on_itself?
returns
false
, that’ll make
do_the_opposite.rb
immediately halt, again
contradicting
#halts_on_itself?
’s
prediction.

It’s wrong to pick on
#halts_on_itself?
here—it’s just an innocent
one-liner that delegates to
#halts?
and relays its answer. What we’ve really shown is that it’s not
possible for
#halts?
to return a
satisfactory answer when called with
do_the_opposite.rb
as both
program
and
input
arguments; no matter how hard it
works, any result it produces will automatically be wrong. That means
there are only two possible fates for any real implementation of
#halts?
:

So a fully correct implementation of
#halts?
can never exist: there must be
inputs for which it makes either an incorrect prediction or no
prediction at all.

Remember the definition of decidability:

We’ve proved it’s impossible to write a Ruby program that
completely solves the halting problem, and since Ruby programs are
equivalent in power to Turing machines, it must be impossible with a
Turing machine too. The Church–Turing thesis says that
every
algorithm can be performed by a Turing
machine, so if there’s no Turing machine for solving the halting
problem, there’s no algorithm either; in other words, the halting
problem is undecidable.