q u a n t -p h /9502011 14 F e b 1995December 14,1994LBL-36346
Is Mental Process Non-Computable?∗
Henry P.Stapp Lawrence Berkeley Laboratory University of California Berkeley,California 94720Abstract It has recently been claimed that certain aspects of mental processing cannot be simulated by computers,even in principle.The argument is examined and a lacuna is identified.
Disclaimer
This document was prepared as an account of work sponsored by the United States Gov-ernment.While this document is believed to contain correct information,neither the United States Government nor any agency thereof,nor The Regents of the University of California, nor any of their employees,makes any warranty,express or implied,or assumes any legal liability or responsibility for the accuracy,completeness,or ufulness of any information,ap-paratus,product,or process disclod,or reprents that its u would not infringe privately owned rights.Reference herein to any specific commercial products process,or rvice by its trade name,trademark,manufacturer,or otherwi,does not necessarily constitute or imply its endorment,recommendation,or favoring by the United States Government or any agency thereof,or The Regents of the University of California.The vie
ws and opinions of authors expresd herein do not necessarily state or reflect tho of the United States Government or any agency thereof or The Regents of the University of California and shall not be ud for advertising or product endorment purpos.
Lawrence Berkeley Laboratory is an equal opportunity employer.
ii
1.Introduction
Roger Penro has recently published an argument1that eks to establish that mathematicians,when they come to know mathematical truths,cannot in all cas be relying solely on process that can be adequately simulated by ideal-ized computers.Within the framework of science this is a startling claim,for contemporary mainstream scientific thought holds that mental processing inso-far as it leads to overt behaviour is an aspect of physical process happening mainly in the brain,and that the process are governed by the mathematical laws of classical and quantum physics,and hence should be able to be simulated to arbitrary accuracy,at least in principle,by computers,provided no practical limitations whatsoever are impod.Penro’s argument eks to refute this. Moreover,the argument is claimed to be clo to rigorous.Thus it is cla
imed, in effect,that almost rigorous argumentation is able to demolish some tenets of mainstream scientific thought,and to demonstrate that fundamentally new ideas are therefore required.This conclusion,if valid,would be a breakthrough of major importance in science.
2.Penro’s Argument
1.Let C q(n),for q ranging over some infinite t R q,be a listing of all computational process that depend on one natural-number argument n.For each pair(q,n)the computational process C q(n)either stops,or never stops. (Example.C7(n)might be:Find the smallest integer N≥0that is not a sum of n numbers each of which is a square of a natural number,0,1,2,3,....For n≥4no systematic arch for N will ever stop,according to a theorem due to Lagrange)
2.Proceed by reductio ad absurdum:Assume that if,for some pair(q,n), we can know that C q(n)can never stop then we can know this only by means of some reasoning process that,becau it is the reflection of an underlying brain process,can be assumed to be a computational process that yields an answer, and thus stops(becau it can be programmed to stop when it yields an answer). Thus the reductio ad absurdum assumption is that if,for some pair(q,n),we can know that C q(n)can never stop then there must be some computational process A(q,n)such that:
‘A(q,n)stops’implies‘C q(n)can never stop’.
1
3.If A(q,n)is defined for every pair(q,n)(e below)then A(n,n)is a computational process that depends on one argument,n.Then there must be an index k such that:
A(n,n)=C k(n).
4.Therefore,according to the assumption of line2,
‘C k(k)stops’implies‘C k(k)can never stop’.
5.Therefore,
C k(k)can never stop.
6.But(by line3)C k(k)=A(k,k),and hence(by line5)‘A(k,k)can never stop’.
7.Thus we have found out that‘C k(k)can never stop’,yet the knowledge that‘C k(k)can never stop’is not entailed by line2.
8.We conclude that the A(k,k)occurring in line2for the ca(q,n)= (k,k)is not unique:there must be an A1(k,k)=A(k,k)who stopping entails that‘C k(k)never stops’.(Penro specifies that the stopping of A(q,n)is merely a sufficient condition for C(q,n)never to stop,not a necessary and sufficient one. Hence there might be veral different process A m(k,k)any one of which could rve as the A(k,k)in line2.)
9.If there were only afinite number of process A m(k,k)such that the stopping of any one of them would allow us to know that C k(k)can never stop then one could define the A(k,k)in line2to be the process that stops if and only if any one of the A m(k,k)’s stops.Then one would get the desired contradiction:We would know(by line5)that‘C k(k)can never stop’,yet(by line6)that the unique computational process who stopping would(according to line2)allows us to know this fact can never stop.
Penro1has argued that all of the A m(q,n)who stoppings can allow us to know that C(q,n)can never stop,as specified in line2,can indeed be amalgamated into one single A(q,n).In this ca,the assumption in line2 becomes:for any pair(p,n),if“‘C p(n)can never stop’is knowable”then “A(q,n)stops”,and,converly,for any pair(p,n),if“A(p,n)stops”then“‘C(p,n)can never stop’is knowable”Thus we have the equivalence:for every pair(p,n),
2
“A(p,n)stops”iff“‘C(p,n)never stops’is knowable”
Since whatever is knowable is(presumably)true the argument can then proceed as indicated above,with a contradiction appearing after line6.However, there is a question about line3,to which we now turn.
3.Indices and Arguments
Let us consider a t of process S q(n),where q ranges over an infinite t R q.It is uful to make a distinction between an index,reprented by a subscript,and an argument,reprented by a variable enclod by parenthes. The dependence on an argument is suppod to be one in which somefinitely-stated rule covers the infinite t of values that the argument(for example,the natural number n)is allowed to take on,whereas the dependence on an index is suppod to be one that is expresd by means of a ca-by-ca listing of the infinite t of individual cas.In the former ca,the various possible values of the argument are elements of a coherent mathematical ,the t of natural numbers),which makes it possible for onefinitely-stated rule to cover the infinite number of possible values of the argument.But in the latter ca the full identity of the ind
ex is specified,say,by its shape:the symbol is identified exclusively by an intrinsic identifying characteristic,not by means of the logical connections of this symbol to the other ones.Thus one could u*, !,?,[,...for the intrinsically characterized symbols,instead of0,1,2,3,..., to indicate their lack of logical relatedness to one another.
The process C q(n)were introduced by Penro by listing all of the different computational process C(n)that are functions of the single(natural-number) argument n:
C0(n),C1(n),C2(n),C3(n),C4(n),C5(n),....
This way of introducing the t of C q(n)might suggest that q is an index,and hence that,in my notation,it is properly written as a subscript,which is how Penro writes it.
In this ca,where the t of all possible C q(n)is indexed by the t of subscripts q,where q ranges over a t R q of pure symbols,the t of process A(q,n)should be written rather as A q(n):the t of symbols q would be merely
3
a t of indices,each of which has an identity,but no logical relationship(apart from‘different from’)to t
he others.Hence no rule apart from direct ca-by-ca listing is possible for specifying the dependence on q.
If one were to adhere to this point of view,that the symbols q are merely indices,then Penro’s argument would collap.For,it would make no n to say that a pure symbol,say∗,is equal to some natural number n.If one were,in spite of this logical point,simply to t up a convention whereby the pure symbols were reprented by natural numbers in some haphazard way then one could not expect to derive anything uful.One could then,to be sure, formally consider the t of process A n(n),as n runs over the t of natural numbers.But this t could not coincide,for some k,with the t of C k(n)’s, for all n,becau the dependence of A n(n)upon the subscript n is not of the argument type,whereas for each value of q the dependence of C q(n)upon n is of the argument type,by definition.Thus a key step in Penro’s argument, namely line3,would fail.
Penro certainly recognized that he would not obtain a valid argument if the symbol q were an index-type of variable:he specified that q must be regarded as an argument-type of variable,but did so without ever writing down C(q,n).Once one writes C(q,n)instead of C q(n)a question immediately aris: How can one confirm that there is,in fact,a computational process C(q,n) that depends on two arguments,and has the property that,as q runs over the natural numbers,the process C(q,n)runs ove
r the complete t of process that are functions of the other argument n?Specifically,if the t of all computable process of one(natural number)argument n is the t of C p(n),with p running over its range R p,then how does one construct afinitely described computational process C(q,n)that acts on two(natural-number)arguments q and n,such that for every p in R p there is a natural number q p such that C(q p,n)=C p(n).
Penro1answers this question satisfactorily.He considers a G¨o del-type of construction whereby one imagines that there is some rule whereby the quence of mathematical symbols that express the form of each computational process C p(n)is transcribed into some corresponding natural number q p,in such a way that C p(n)=C(q p,n)for each p in R p.
Let it be granted,therefore,that C q(n)can,in my notation,be replaced
4
