RE: What Computationalism is and what it is *not*

From: Lee Corbin <lcorbin.domain.name.hidden>
Date: Tue, 6 Sep 2005 21:25:59 -0700

Norm writes

> You [Hal Finney] say, ". . . the Church Thesis, which I would paraphrase
> as saying that there are no physical processes more computationally
> powerful than a Turing machine, or in other words that the universe could
> in principle be simulated on a TM. I wouldn't be surprised if most people
> who believe that minds can be simulated on TMs also believe that
> everything can be simulated on a TM."
>
> I'm out of my depth here, but this doesn't make sense to me. My
> understanding is that the Turing Machine is a hypothetical device.

Unfortunately, the "Turing Machine" is often taken to be either one
of *two* possibilities.

One is, as you say, a "device". All the usual paraphernalia of a normal
computer is abstracted away, leaving the least possible behavior that
could still do computing. Turing, of course, began with the simplest
operations that he could conceive of a human "computer" doing.

In this first view, we arrive at the usual picture of a little box on
wheels which scans a tape one square at a time, and either writes a
zero or a 1, and then moves left or right on the tape depending also
on what it scanned.

But there is a second meaning to "Turing Machine" that is also used
extensively in the literature. This has utterly nothing to do with
devices. Mathematically, a Turing Machine is a set of quintuples
(quadruples in many treatments, e.g. Boolos and Jeffrey). These
quintuplets have only mathematical or platonic existence. Yet one
can see that by their nature were they implemented in the flesh, so
to speak, they could accomplish a specific computation as spelled
out by the entries in the five slots of each quintuplet. (Four
slots, slightly simpler, are composed of two that specify the
current state you're in and the current symbol you're reading,
and two composed of the output: the symbol you write and the next
state you go to.)

Sometimes discussions ensue when one party is talking about an
actual (though theoretical) device, and the other is talking about
the mathematical description. So beware the term "Turing Machine",
unless it's clear which interpretation is meant.

> If one could be built that operated at faster-than-light or infinite
> speed, maybe it could, in principle, simulate the universe. However,
> this isn't possible. Does this mean that the Church Thesis, hence
> computationalism, is, in reality, false?

No, this doesn't affect Church's Thesis, as probably some here will
explain better than I. Sometimes one does encounter "Zeno machines"
in the literature, which can solve a harder class of problems because
it's assumed that they can complete an infinite number of steps in
finite time.

But Church's Thesis merely says that every effective computation (that
anyone has been able to think of) can be calculated by a Turing machine.
It turns out that this specification of Turing machine is completely
equivalent to several other reasonable ways calculations can in principle
be done, e.g., Post-production strings, recursive functions, "abacus
computable functions", and so on. The "thesis" part is that this whole
class of equivalent capability is *all* that a computation can be.

"Computationalism" is yet another claim. It's the notion that all of
our own thoughts as well could be implemented on a Turing Machine in
a way that would deliver to us just as much experiential satisfaction.

Lee
Received on Wed Sep 07 2005 - 00:24:40 PDT