...IRREVERSIBILITY

We are indebted to Bill Rapaport, Pat Hayes, Ken Ford, Marvin Minsky, Jim Fahey, two anonymous referees (who provided particularly insightful comments), and many Rensselaer students. These people provided trenchant objections which saw to the evolution of the present version from a rather inauspicious primogenitor.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...computation.

But due to space constraints, nowhere in this paper do we provide a detailed, comprehensive account of Computationalism. Such an account would probably need to include careful versions of at least the following five propositions.

1. A function f is effectively computable if and only if f is Turing-computable (Church's Thesis).
2. Proposition 1.
3. The Turing Test is valid.
4. Computationalists will succeed in building persons.
5. Computationalists will succeed in building Turing Test-passing artifacts. (This proposition is presumably entailed by its predecessor.)

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...precise,

Formally, keeping in mind that after a while, in both directions, the tape is populated by infinitely many blanks, a configuration is a member of the set 11#11{h}12#12

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...1's.

To the uninitiated, this computation will doubtless sound remarkably unimpressive, but initiated ought to note that this machine is the result of Genetic Algorithm-powered search (engineered by Gordon Greene) in the (enormous) space of 6-state TMs for ``Busy Beaver" candidates in the ``quaduple" formalism. (Currently, the most productive known 6-state machine can produce 21 1's. The machine - built by Chris Nielsen - can be seen (in flow graph form) and obtained by linking through Bringsjord's web site (URL above), under the course Symbolic Logic. Alternatively, go directly to http://csli-www.stanford.edu/hp/Beaver.html.) In the ``Busy Beaver" function, 23#23 (N here denotes the natural numbers), 24#24 yields the greatest number of 1's an n-state TM, starting on a black tape, can leave after halting. This function, and the corresponding proof that it's uncomputable, is due to Rado [32], who used 25#25 for 26#26. Busy Beaver candidates are those n-state TMs which appear to produce 24#24 1's.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...TM.

See [2f] for a discussion of the consequences of this fact for AI.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...one.

The interested reader can consult an octet of books we find useful: For broad coverage of the basic material, see [24], [15], [9], and [21]. For a nice comprehensive discussion of computability theory that includes succinct coverage of uncomputability, including the Arithmetic Hierarchy, see [10] and the difficult but rewarding [40]. [29] contains a very nice discussion of the Chomsky Hierarchy. And, of course, there's always the classic [33].

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...World"41#41,

The ``Turing's World"41#41 software comes with [3].

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...theorem:

Note that by Church's Thesis Theorem 1 is interchangeable with this theorem (which is easy to prove without CT):

Theorem 1'. For every computation 42#42, there exists a computation 43#43 which can be obtained from the original computation via some TM 44#44.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...consciousness.

This is borne out by, among other things, looking at proposed comprehensive models of cognition in cognitive science: these models often include some component claimed to account for consciousness. For example, Schacter [34] gives us the the picture of cognition shown in Figure 2. For a survey of models like this one, see [1]; for a penetrating analysis of such models (including Schacter's) see [8]. For those interested in charting the first-order formalization of our argument, the relevant sentence in first-order logic would be a full symbolization of 50#50, where `cognizing' is understood to indicate the full scope of human cognition as purportedly captured in models like Schacter's.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...life.

It's important to realize that we're talking about your mental life: we're not talking about reversing some sequence of physical actions which can be described in such as way as to imply that it is a discrete chain. For example, suppose that you move block a from on top of block b to a position next to block c, and then move block c to on top of block b. You might say that this sequential action is easily reversed by first moving block c to its original position, and then moving block a on top of block b. Though as a matter of fact - as we shall see below - you haven't truly reversed the sequence qua physical process, the present point is that we are concerned with reversing a stretch of conscious experience, not a sequence of ostensibly discrete bodily actions.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...possible.

Compare this sort of indivisibility with the type Descartes famously ascribed (perhaps incorrectly) to the mind when he said:

In order to begin this examination, then, I here say, in the first place, that there is a great difference between mind and body, inasmuch as body is by nature always divisible, and the mind is entirely indivisible. For, as a matter of fact, when I consider the mind, that is to say, myself inasmuch as I am only a thinking thing, I cannot distinguish in myself any parts, but apprehend myself to be clearly one and entire; and although the whole mind seems to be united to the whole body, yet if a foot, or an arm, or some other part, is separated from my body, I am aware that nothing has been taken away from my mind. ([13], p. 196)

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...irreversible.

Additional objections are possible, but not powerful. For example, someone might claim that appeals to thermodynamics have no place here since neither Max nor the system being manipulated need be closed. The short answer to this is that only equilibrium thermodynamics requires closed systems. Indeed, our arguments depend on recognizing important differences between equilibrium and non-equilibrium situations. Consciousness necessarily involves departure from equilibrium; computation doesn't.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...brains.

One of us (Bringsjord) conducts a lot of ``Weak" AI, in the form of an attempt to engineer systems capable of autonomously generating stories. See, for example, the programs featured in [2a].

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...computation.

We make veiled reference here to a distinction between simulation and replication. Details of the distinction aren't necessary for this paper; a rough-and-ready characterization suffices. Accordingly, we say that to simulate some human chess player via AI techniques would be to produce a computer program whose overt behavior (i.e., actual chess moves) resembles that of some human, whereas to replicate Kasparov would be to construct an artifact that literally has the same inner life he has, the same emotions, plans, experiences, mental images, memories, etc.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...consciousness,

In [2g] we devise and exploit a variation on the classic brain-in-a-vat gedankenexperiment in order to make the case for this view. In [2c] one of us (Bringsjord) argues, contra Harnad [17], that Turing Testing, in order to test for consciousness, needn't include a test for the ability of a would-be AI to interact with its environment.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...M.

One method for such encoding comes via gödel numbers. For example, see [15].

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...2.

We place scare quotes around `Theorem' because we describe the result very informally. For a more precise statement of the theorem, as well as a more precise account of the proof than what we provide below, see [24].

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...true.

We leave aside a complexity-based construal of `power.' Obviously, a physical TM with multiple tapes could sometimes solve problems faster than an ordinary one-tape TM. However, there are no problems which are unsolvable by a standard TM yet solvable by a multi-tape machine.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...TM.

It's easy enough to imagine the details of this conversion in some cases. For example, suppose that we present you with a 4-tape TM roughly in the the form of a model railroad set. That is, suppose that: the tapes are divided into squares; the read/write head, for each tape, is a lone boxcar; there is some way to give simple instructions to this railroad TM; etc. Now imagine converting this physical TM to a one-tape TM via the trick at the heart of Theorem 2. You would have to find some way to link the tracks together into one unit. If you have any experience with model railroading, you probably can visualize yourself tackling the process.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...(iii)}.

This is as good a place as any to point out that our argument is of necessity a good deal trickier than this one: ``TMs are abstract entities that do not exist in space/time and between which only logical relations obtain, while minds are causal systems in space/time. Logical processes are reversible wile causal processes are not). Therefore minds are not TMs." Our argument is trickier because Computationalism doesn't hold that minds (or persons) are abstract entities. On the contrary, computationalists as a rule hold that minds are physical things. They must also hold, however, that minds, as physical things, abide by the principles of computation - and this is what gets them into trouble, as we are in the process of showing. The simplest distillation of our argument is that it is a proof of inconsistency holding between four propositions, as we indicated at the outset, and as we explain in more detail in the present section.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...1''.

They are not free to reject Theorem 1, however. Two different and determinate levels may be addressed by Theorem 1 (and the like): perhaps there is the purely mathematical level of the theorem itself, and and then perhaps also what might be called the ``logic gate level" of computer engineering - a level indispensable for Weak AI. Computer engineers have on hand physical instantiations of Turing Machines which they can combine in order to generate increasingly sophisticated computational artifacts, but there is no guarantee, say, that such engineers will be familiar with the purely formal set theoretic definition of a TM and a TM configuration. Nonetheless, both theoretical computer science and computer engineering is constrained and informed by Theorem 1 and its relatives. Work in AI and Cog Sci, whether of the ``Weak" or ``Strong" variety, is carried out at both of these levels. To abandon these levels and carry out a research program which in its entirety is ``below" them, say research exclusively at the neuromolecular level, is to abandon AI for a variant on bio-engineering.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...processes.

Again, for a detailed discussion of Max, ballistic computers, and other, similar devices, see [6] and [4].

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...impotent.

This is as good a place as any to register our prediction that at this juncture those desperate to dodge our argument might say about the Sandra thought-experiment what those who defend the coherence of time travel have said about the so-called ``Grandfather Paradox" (GP, in a word, being that if time travel if possible, then you could go back in time and kill your grandfather, but then how could you be around to do the killing?), namely that the Sandra case just won't ever happen. This move is laughably ad hoc. Besides, Sandra's P-consciousness isn't really any different than garden variety stretches of P-consciousness evoked by watching a movie played from a VCR whose digital clock keeps normal time.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...anyway).

One of us (Bringsjord) distinguishes between various sorts of computationalists and connectionists in [2f].

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...disguise.

This paper is based on the classic statement of connectionism given by Paul Smolensky [38], [39].

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...otherwise.

McCulloch and Pitts [27] showed long ago that such a simple activation function allows for the representation of the basic Boolean functions of AND, OR and NOT.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...action.

The machine itself, as a series of quadruples (with 0 for blank, 1 for filled, R and L for ``right" and ``left," resp., A for ``any," etc.) is (read left to write, top to bottom):

91#91

The implementation of this machine - in Turing's World41#41 - sent upon request.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...pyrotechnics).

Readers wanting to see some of them are encouraged to consult Poundstone's [30] classic discussion of Conway's [7] Game of Life.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...it.

Don't worry about how the chess board and pieces got there in the first place. Perhaps our props were launched into space centuries ago, when the human race still existed. Perhaps the board and the pieces were formed from mud by the random winds invoked below104#104

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...evaporates.

It is at any rate undeniable, given this gedankenexperiment, that the ontological status of chess games is a bit mysterious.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...taking.

It is the route one of us (Bringsjord) follows in the attempt to engineer systems which appear to be creative; see [2a].

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.