TITLE: A Reflection on Alan Turing, Representation, and Universal Machines
AUTHOR: Eugene Wallingford
DATE: April 06, 2012 4:29 PM
DESC:
-----
BODY:
The day after Douglas Hofstadter spoke here on
assertions, proof's and Gödel's theorem,
he gave a second public lecture hosted by the philosophy
department. Ahead of time, we knew only that Hofstadter
would reflect on Turing during
his centennial.
I went in expecting more on
the Turing test,
or perhaps a popular talk on Turing's proof of
The Halting Problem.
Instead, he riffed on Chapter 17 from
I Am a Strange Loop.
In the end, we are self-perceiving, self-inventing,
locked-in mirages that are little miracles of
self-reference.
Turing, he said, is another peak in the landscape occupied
by Tarski and Gödel, whose work he had discussed the
night before. (As a computer scientist, I wanted to add
to this set contemporaries such as
Alonzo Church
and
Claude Shannon.)
Hofstadter mentioned Turing's seminal paper about
the Entscheidungsproblem
but wanted to focus instead on the model of computation for
which he is known, usually referred to by the name "Turing
machine". In particular, he asked us to consider a key
distinction that Turing made when talking about his model:
that between dedicated and universal machines.
A dedicated machine performs one task. Human history is
replete with dedicated machines, whether simple, like the
wheel, or complex, such as a typewriter. We can use these
tools with different ends in mind, but the basic work is
fixed in their substance and structure.
The 21st-century cell phone is, in contrast, a universal
machine. It can take pictures, record audio, and -- yes --
even be used as a phone. But it can also do other things
for us, if we but go to the app store and download another
program.
Hofstadter shared a few of his early personal experiences
with programs enabling line printers to perform tasks for
which they had not been specifically designed. He recalled
seeing a two-dimensional graph plotted by "printing"
mostly blank lines that contained a single
*. Text had been turned into graphics.
Taking the idea further, someone used the computer to print
a large number of cards which, when given to members of the
crowd at a football game, could be used to create a massive
two-dimensional message visible from afar. Even further,
someone used a very specific layout of the characters
available on the line printer to produce a print-out that
appeared from the other side of the room to be a
black-and-white photograph of Raquel Welch. Text had been
turned into image.
People saw each of these displays as images by virtue of
our eyes and mind interpreting a specific configuration of
characters in a certain way. We can take that idea down a
level into the computer itself. Consider this transformation
of bits:
0000 0000 0110 1011 → 0110 1011 0000 0000
A computer engineer might see this as a "left shift" of 8
bits. A computer programmer might see it as multiplying the
number on the left by 256. A graphic designer might see us
moving color from one pixel to another. A typesetter may see
one letter being changed into another. What one sees depends
on how one interprets what the data represent and what
the process means.
Alan Turing was the first to express clearly the idea that
a machine can do them all.
"Aren't those really binary numbers?", someone asked.
"Isn't that real, and everything else interpretation?"
Hofstadter said that this is a tempting perspective, but we
need to keep in mind that they aren't numbers at all. They
are, in most computers, pulses of electricity, or the states
of electronic components, that we interpret as 0s and
1s.
After we have settled on interpreting those pulses or states
as 0s and 1s, we then interpret configurations of 0s and 1s
to mean something else, such as decimal numbers, colors, or
characters. This second level of interpretation exposes the
flaw in popular claims that computers can do "only" process
0s and 1s. Computers can deal with numbers, colors, or
characters -- anything that can be represented in
any way -- when we interpret not only what the data mean but
also what the process means.
(In the course of talking representations, he threw in a cool
numeric example: Given an integer N, factor
it as 2^a * 3^b * 5^c *7^d ... and use
[a.b.c.d. ...] to stand for N.
I see a programming assignment or two lying in wait.)
The dual ideas of representation and interpretation take us
into a new dimension. The Principia Mathematica
describes a set of axioms and formal rules for reasoning
about numeric structures. Gödel saw that it could be
viewed at a higher level, as a system in its own right --
as a structure of integers. Thus the Principia
can talk about itself. It is, in a sense, universal.
This is the launching point for Turing's greatest insight.
In I Am a Strange Loop, Hofstadter writes:
Inspired by Gödel's mapping of PM into itself,
Alan Turing realized that the critical threshold for this
kind of computational universality comes exactly at the
point where a machine is flexible enough to read and
correctly interpret a set of data that describes its own
structure. At this crucial juncture, a machine can, in
principle, explicitly watch how it does any particular
task, step by step. Turing realized that a machine that
has this critical level of flexibility can imitate any
other machine, no matter how complex the latter is. In
other words, there is nothing more flexible than
a universal machine. Universality is as far as you can
go!
Thus was Turing first person to recognize the idea of a
universal machine, circa 1935-1936: that a Turing machine
can be given, as input, data that encodes its own
instructions. This is the beginning of perhaps the
biggest of the Big Ideas of computer science:
the duality of data and program.
We should all be glad he didn't patent this idea.
Turing didn't stop there, of course, as I wrote in
my recent entry on the Turing test.
He recognized that humans are remarkably capable and efficient
representational machines.
Hofstadter illustrates this with the idea of "hub", a
three-letter word that embodies an enormous amount of
experience and knowledge, chunked in numerous ways and
accreted slowly over time. The concept is assembled in our
minds out of our experiences. It is a representation. Bound
up in that representation is an understanding of ourselves as
actors in certain kinds of interactions, such as booking a
flight on an airplane.
It is this facility with representations that distinguishes
us humans from dogs and other animals. They don't seem
capable of seeing themselves or others as representations.
Human beings, though, naturally take other people's
representations into their own. This results in a range of
familiarities and verisimilitude. We "absorb" some people
so well that we feel we know them intimately. This is what
we mean when we say that someone is "in our soul". We use
the word 'soul' not in a religious sense; we are referring
to our essence.
Viewed this way, we are all distributed beings. We are "out
there", in other people, as well as "in here", in ourselves.
We've all had dreams of the sort Hofstadter used as example,
a dream in which his deceased father appeared, seemingly as
real as he ever had been while alive. I myself recently
dreamt that I was running, and the experience of myself was
as real as anything I feel when I'm awake. Because we are
universal machines, we are able to process the representations
we hold of ourselves and of others and create sensations that
feel just like the ones we have when we interact in the world.
It is this sense that we are self-representation machines
that gives rise to the title of his book, "I am a strange
loop". In Hofstadter's view, our identity is a representation
of self that we construct, like any other representation.
This idea underlies the importance of the Turing test. It
takes more than "just syntax" to pass the test. Indeed,
syntax is itself more than "just" syntax! We quickly recurse
into the dimension of representation, of models, and a need
for self-reference that makes our syntactic rules more than
"just" rules.
Indeed, as self-representation machines, we are able to have
a sense of our own smallness within the larger system. This
can be scary, but also good. It makes life seem precious,
so we feel a need to contribute to the world, to matter
somehow.
Whenever I teach our AI course, I encounter students who are,
for religious or philosophical reasons, deeply averse to the
idea of an intelligent machine, or even of scientific
explanations of who we are. When I think about identity in
terms of self-representation, I can't help but feel that, at
an important level, it does not matter. God or not, I am in
awe of who we are and how we got to here.
So, we owe Alan Turing a great debt. Building on the work of
philosophers, mathematicians, and logicians, Turing gave us
the essential insight of the universal machine, on which
modern computing is built. He also gave us a new vocabulary
with which to think about our identity and how we understand
the world. I hope you can appreciate why celebrating his
centennial is worthwhile.
~~~~
IMAGE 1: a photo of Douglas Hofstadter speaking at UNI,
March 7, 2012. Source:
Kevin C. O'Kane.
IMAGE 2: the Alan Turing centenary celebration. Source:
2012 The Alan Turing Year.
-----
