Understanding Computation (49 page)

We’ve seen that
general-purpose computers are universal: we can design a
Turing machine that is capable of simulating any other Turing machine,
or write a program that can evaluate any other program. Universality is
a powerful idea that allows us to use a single adaptable machine for a
variety of tasks rather than many specialized devices, but it also has
an inconvenient consequence: any system that’s powerful enough to be
universal will inevitably allow us to construct computations that loop
forever without halting.

So why must every universal system bring nontermination along for
the ride? Isn’t there some ingenious way to restrict Turing machines so
that they’ll always halt, without compromising their usefulness? How do
we know we won’t someday design a programming language that’s just as
powerful as Ruby but doesn’t have infinite loops in it? There are all
sorts of specific examples of why this can’t be done, but there’s also a
more general argument, so let’s go through it.

Ruby is a universal programming language, so it must be possible to write Ruby code that
evaluates Ruby code. In principle, we can define a method called
#evaluate
, which takes the source code of a Ruby program and a string to
provide to that program on standard input, and returns the result (i.e., the string sent to
standard output) of evaluating that program with that input.

The implementation of
#evaluate
is far too complicated to be contained within this chapter, but here’s
the broadest possible outline of how it would work:

def
evaluate
(
program
,
input
)
# parse program
# evaluate program on input while capturing output
# return output
end

#evaluate
is essentially a Ruby
interpreter written in Ruby. Although we haven’t given its
implementation, it’s certainly possible to write it: first turn
program
into a sequence of tokens and parse
them to build a parse tree (see
Parsing with Pushdown Automata
),
then evaluate that parse tree according to the operational semantics of
Ruby (see
Operational Semantics
). It’s a large and
complex job, but it can definitely be done; otherwise, Ruby wouldn’t
qualify as universal.

For simplicity, we’ll assume that our imaginary implementation of
#evaluate
is bug-free and won’t crash while it’s evaluating
program
—if we’re going to imagine some code, we may as
well imagine that it’s perfect. Of course it might return some result that indicates that
program
raised an exception while it was being
evaluated, but that’s not the same as
#evaluate
itself
actually crashing.

require
'stringio'
def
evaluate
(
program
,
input
)
old_stdin
,
old_stdout
=
$stdin
,
$stdout
$stdin
,
$stdout
=
StringIO
.
new
(
input
),
(
output
=
StringIO
.
new
)
begin
eval
program
rescue
Exception
=>
e
output
.
puts
(
e
)
ensure
$stdin
,
$stdout
=
old_stdin
,
old_stdout
end
output
.
string
end

>>
evaluate
(
'print $stdin.read.reverse'
,
'hello world'
)
=> "dlrow olleh"

The existence of
#evaluate
allows us to define another method,
#evaluate_on_itself
, which returns the result
of evaluating
program
with
its own source
as input:

def
evaluate_on_itself
(
program
)
evaluate
(
program
,
program
)
end

This might sound like a weird thing to do, but it’s totally
legitimate;
program
is just a string,
so we’re perfectly entitled to treat it both as a Ruby program and as
input to that program.
Code is data
,
right?

>>
evaluate_on_itself
(
'print $stdin.read.reverse'
)
=> "esrever.daer.nidts$ tnirp"

Since we know we can implement
#evaluate
and
#evaluate_on_itself
in Ruby, we must therefore
be able to write the complete Ruby program
does_it_say_no.rb
:

def
evaluate
(
program
,
input
)
# parse program
# evaluate program on input while capturing output
# return output
end
def
evaluate_on_itself
(
program
)
evaluate
(
program
,
program
)
end
program
=
$stdin
.
read
if
evaluate_on_itself
(
program
)
==
'no'
print
'yes'
else
print
'no'
end

This program is a straightforward application of existing code: it defines
#evaluate
and
#evaluate_on_itself
, then reads another Ruby program from standard input and
passes it to
#evaluate_on_itself
to see what that program
does when run with itself as input. If the resulting output is the string
'no'
,
does_it_say_no.rb
outputs
'yes'
, otherwise, it outputs
'no'
. For example:
^[
69
]

$
echo
'print $stdin.read.reverse'
| ruby does_it_say_no.rb
no

That’s the result we expected; as we saw above, when we run
print $stdin.read.reverse
with itself as input, we get the output
esrever.daer.nidts$ tnirp
, which is not equal to
no
. What about a program that
does
output
no
?

$
echo
'if $stdin.read.include?("no") then print "no" end'
| ruby does_it_say_no.rb
yes

Again, just as expected.

So here’s the big question: what happens when we run
ruby does_it_say_no.rb <
does_it_say_no.rb
?
^[
70
]
Bear in mind that
does_it_say_no.rb
is a real program—one that
we could write out in full if we had enough time and enthusiasm—so it
must do
something
, but it’s not immediately obvious
what that is. Let’s try to work it out by considering all the
possibilities and eliminating the ones that don’t make sense.

First, running this particular program with its own source as input can’t possibly
produce the output
yes
. By the program’s own logic, the
output
yes
can only be produced when running
does_it_say_no.rb
on its own source produces the output
no
, which contradicts the original premise. So that’s
not the answer.

Okay, so maybe it outputs
no
instead. But again, the
structure of the program means that it can only output
no
if exactly the same computation
doesn’t
output
no
—another contradiction.

Is it conceivable that it could output some other string, like
maybe
, or even the empty string? That would be contradictory too: if
evaluate_on_itself(program, program)
doesn’t return
no
then the program prints
no
, not something different.

So it can’t output
yes
or
no
, it can’t output something else, and it can’t crash unless
#evaluate
contains bugs, which we’re assuming it doesn’t. The
only remaining possibility is that it doesn’t produce any output, and that can only happen
if the program never finishes:
#evaluate
must loop
forever without returning a result.

This might seem like an unnecessarily complicated way of demonstrating that Ruby lets us
write nonhalting programs. After all,
while true do end
is much a simpler example that does the same thing.

But by thinking about the behavior of
does_it_say_no.rb
, we’ve shown that nonhalting programs are an inevitable
consequence of universality, regardless of the specific features of the system. Our argument
doesn’t rely on any particular abilities of Ruby other than its universality, so the same
ideas can be applied to Turing machines, or the lambda calculus, or any other universal
system. Whenever we’re working with a language that is powerful enough to evaluate itself,
we know that it must be possible to use its equivalent of
#evaluate
to construct a program that never halts, without having to know
anything else about the language’s capabilities.