jwm@stdc.jhuapl.edu (Jim Meritt) (09/22/88)
In article <7059@aw.sei.cmu.edu> firth@bd.sei.cmu.edu (Robert Firth) writes: }In article <388@quintus.UUCP> ok@quintus.UUCP (Richard A. O'Keefe) writes: } }>But is there any reason to suppose that the universe _is_ a Turing machine? } }None whatever. The conjecture is almost instantly disprovable: no Turing }machine can output a true random number, but a physical system can. Since }a function is surely "computable" if a physical system can be constructed }that computes it, the existence of true random-number generators directly }disproves the Church-Turing conjecture. Love it! If the universe is random, you can have uncaused events. If the universe is not random, it is (a type of) Church-Turing machine... Disclaimer: Individuals have opinions, organizations have policy. Therefore, these opinions are mine and not any organizations! Q.E.D. jwm@aplvax.jhuapl.edu 128.244.65.5 (James W. Meritt)
nlt@grad3.cs.duke.edu (Nancy L. Tinkham) (09/27/88)
Robert Firth offers the following proposed refutation of the Church-Turing thesis: > The conjecture is almost instantly disprovable: no Turing > machine can output a true random number, but a physical system can. Since > a function is surely "computable" if a physical system can be constructed > that computes it, the existence of true random-number generators directly > disproves the Church-Turing conjecture. The claim of the Church-Turing thesis is that the class of functions computable by a Turing machine corresponds exactly to the class of functions which can be computed by some algorithm. The notion of an algorithm is a somewhat informal one, but it includes the requirement that the computation be "carried forward deterministically, without resort to random methods or devices, e.g., dice" (Rogers, _Theory of Recursive Functions and Effective Computability_, p.2). If it is demonstrated that a physical system, by using randomness, can generate the input-output pairs of a function which cannot be computed by a Turing machine, we have merely shown that there exists a non-Turing-computable function whose output can be generated by non-algorithmic means -- hardly surprising, and not relevant to the Church-Turing thesis. Nancy Tinkham {decvax,rutgers}!mcnc!duke!nlt nlt@cs.duke.edu
firth@sei.cmu.edu (Robert Firth) (09/27/88)
In article <12512@duke.cs.duke.edu> nlt@grad3.cs.duke.edu (Nancy L. Tinkham) writes: > The claim of the Church-Turing thesis is that the class of functions >computable by a Turing machine corresponds exactly to the class of functions >which can be computed by some algorithm. No it isn't. The claim is that every function "which would naturally be regarded as computable" can be computed by a Turing machine. At least, that's what Turing claimed, and he should know. [A M Turing, Proc London Math Soc 2, vol 442 p 230]
kilroy@mimsy.UUCP (Darren F. Provine) (09/28/88)
In article <7167@aw.sei.cmu.edu>, firth@sei.cmu.edu (Robert Firth) writes: /* * In article <12512@duke.cs.duke.edu> nlt@grad3.cs.duke.edu (Nancy L. Tinkham) * writes: * * > The claim of the Church-Turing thesis is that the class of functions * >computable by a Turing machine corresponds exactly to the class of * >functions which can be computed by some algorithm. * * No it isn't. The claim is that every function "which would naturally * be regarded as computable" can be computed by a Turing machine. At * least, that's what Turing claimed, and he should know. */ I do not see any point to this reply. You have merely restated the definition she provided and did nothing to answer her objection. You see, ``every function "which would naturally be regarded as computable"'' and ``the class of functions which can be computed by some algorithm'' are pretty much the same thing. Do you have some way of computing a function without an algorithm that nobody else in the entire world knows about? If so, do go and get your Turing Award & your Ph.D., and then tell us how it works. If not, go reread the requirement that the algorithm used for computation must be deterministic, and tell us how a random process is relevant to the discussion. And you'll also need a definition of "random function" -- if it is random, then how can it be a function, or even a mapping? [ All of this ignores, of course, the fact that some people believe that physical processes cannot act randomly (and that quantum randomness is a misperception). Sadly, we cannot prove this either way. ] Darren ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Darren F. Provine UUCP: uunet!mimsy!kilroy University of Maryland ARPA/CSNET: kilroy@mimsy.umd.edu
firth@sei.cmu.edu (Robert Firth) (09/29/88)
Somehow, I get the feeling that our machines are better at forward chaining than we are. Please let me run this Turing machine stuff by you once again. (Translation: this post says nothing new, merely recapitulates.) ---- The question that originally prompted me to speak was this one [ <388@quintus.UUCP> ok@quintus.UUCP (Richard A. O'Keefe)] >But is there any reason to suppose that the universe _is_ a Turing machine? As I understood it, the question referred to the physical world, as imperfectly revealed to us by science, and so I replied [ <7059@aw.sei.cmu.edu> firth@bd.sei.cmu.edu (Robert Firth) ] >None whatever. The conjecture is almost instantly disprovable: no Turing >machine can output a true random number, but a physical system can. To elaborate: I can build a box, whose main constituents are a supply of photons and a half-silvered mirrir, that, when triggered, will emit at random either the value "0" or the value "1". This can be thought of as a mapping {0,1} => 0|1 where I introduce "|" to designate the operator that arbitrarily selects one of its operands. The obvious generalisation of this - the function that selects an arbitrary member of an input set - is surely not unfamiliar. Nobody has denied that a Turing machine can't do this. The assertion that a physical system can do it rests on the quantum theory; in particular on the proposition that the indeterminacy this theory ascribes to the physical world is irreducible. Since every attempt to build an alternative deterministic theory has foundered, and no prediction of the quantum theory has yet been falsified, this rests on pretty strong ground. Now, it is not my job to supply an "algorithm" for this function: as the physicist I have given you a specification and a model implementation; as the computer scientist it is your job to give me an equivelent program. However, being a kind-hearted soul, I shall point you to an algorithm; it is given as equation (3.1) in the paper [Deutsch: Proc Roy Soc A vol 400 pp 97-117] Naturally, it uses primitive operations that you won't find in a classical computing engine, which is why the title reads "Quantum theory, the Church-Turing principle, and the universal quantum computer". Turning now to that "principle": The formulation I learned was, briefly, that any function that would naturally be regarded as computible can be computed by a universal Turing machine. Once again, I made my opinion on this absolutely clear [art. cit.]: Since a function is surely "computable" if a physical system can be constructed that computes it, ... from which, I submit, the conclusion follows: ... the existence of true random-number generators directly disproves the Church-Turing conjecture. Granted, one can readily evade this conclusion. It is necessary merely to redefine "natural", "computable", "function", or some other key term. For example, one could stipulate A function is to be regarded as computable only if it can be described by an algorithm written in a programming language implementable on a universal Turing machine. In which case, the conjecture becomes vacuously true, and the discipline of AI becomes vacuously futile. For the point of "artificial intelligence", surely, is accurately to reproduce, in some computing engine, the behaviour of certain physical systems, especially those that show goal- directed behaviour, judgement, creativity, or whatever else one means by "intelligence". If this is to be remotely feasible, then the model of the computation process must be at least general enough to embrace the known basic operational features of physical systems. After all, if your programming tools cannot reproduce so simple a physical system as my random Boolean generator, the chance of their being able to reproduce a complicated physical system - the brain of a flatworm, for instance - must be very close to zero. Robert Firth
nau@mimsy.UUCP (Dana S. Nau) (09/30/88)
In article <7202@aw.sei.cmu.edu> firth@bd.sei.cmu.edu (Robert Firth) writes: < ... I can build a box, whose main constituents are a supply < of photons and a half-silvered mirrir, that, when triggered, will emit < at random either the value "0" or the value "1". This can be thought < of as a mapping < < {0,1} => 0|1 < < where I introduce "|" to designate the operator that arbitrarily selects < one of its operands. The obvious generalisation of this - the function < that selects an arbitrary member of an input set - is surely not unfamiliar. As far as I can see, what you have defined is not a function. A function is normally defined to be a set F of ordered pairs (x,y) such that for each x, there is at most one y such that (x,y) is in F (and this y we normally call F(x)). Until all of the ordered pairs that comprise F have been unambiguously determined, you have not defined a function. Note that this does NOT mean that you have to tell us what all of the ordered pairs are or how to compute them, or that you know what they are, or that it is even possible to compute them (for some interesting examples, see page 9 of Hartley Rogers' book, "Theory of Recursive Functions and Effective Computability). It just means that it must be unambiguous what they are. If your mapping "|" is a function, then it must be one of the following: | = {(0.0), (1,0)} | = {(0.0), (1,1)} | = {(0.1), (1,0)} | = {(0.1), (1,1)} If it were unambiguous WHICH function "|" was, then "|" WOULD be Turing-computable. In fact, it would even be primitive recursive. But if we assume that the output of your box is truly random, then your definition leaves it indeterminate which of the above functions "|" actually is. Thus, as a function, "|" is ill-defined. < ... The formulation I learned was, briefly, < that any function that would naturally be regarded as computible can be < computed by a universal Turing machine. Once again, I made my opinion < on this absolutely clear [art. cit.]: < < Since a function is surely "computable" if a physical < system can be constructed that computes it, ... < < from which, I submit, the conclusion follows: < < ... the existence of true random-number generators directly < disproves the Church-Turing conjecture. I disagree. The point of my above argument is that true random-number generators do not satisfy the definition of a function, so the theory of Turing computability does not apply to them. Just one other point, to avoid possible confusion: A random variable IS normally defined as a function. However, it is not a function such as "|", but is instead the function which maps the sample space of a random experiment into the set of real numbers. In your example, the sample space is the set {0,1}, so to map this into the set of real numbers you can simply use the identity function. -- Dana S. Nau ARPA & CSNet: nau@mimsy.umd.edu Computer Sci. Dept., U. of Maryland UUCP: ...!{allegra,uunet}!mimsy!nau College Park, MD 20742 Telephone: (301) 454-7932
ok@quintus.uucp (Richard A. O'Keefe) (09/30/88)
In article <7202@aw.sei.cmu.edu> firth@bd.sei.cmu.edu (Robert Firth) writes: > Since a function is surely "computable" if a physical ******** > system can be constructed that computes it, ... >from which, I submit, the conclusion follows: > ... the existence of true random-number generators directly > disproves the Church-Turing conjecture. >Granted, one can readily evade this conclusion. It is necessary merely >to redefine "natural", "computable", "function", or some other key term. It is not necessary to REdefine "function", only to use the usual meaning. Given the same inputs, a function must always yield the same output(s). The kind of physical system Firth has described is a realisation of a(n indexed) random variable, and it has been held for many years that "true random numbers" are not computable. (See section 3.5 ("What is a random sequence") of Knuth's "The Art of Computer Programming, Vol 2", this statement is implicit in definition R6. The original question was a purely rhetorical one (I _don't_ believe that the universe is a Turing machine), but it's worth pointing out that we only have a finite set of imprecise observations, so that a sufficiently good simulation of a quantum-mechanical system (with top-notch pseudo- random number generation!) *might* be fooling us. You can only appeal to phsyical random number generators to disprove the Church-Turing hypothesis if you assume that the quantum-mechanical laws a really true, which is to say if you already assume that the universe is not running on a Turing machine. I believe it, but a circular "proof" like that is no proof!
lee@uhccux.uhcc.hawaii.edu (Greg Lee) (09/30/88)
From article <13791@mimsy.UUCP>, by nau@mimsy.UUCP (Dana S. Nau):
" In article <7202@aw.sei.cmu.edu> firth@bd.sei.cmu.edu (Robert Firth) writes:
" ...
" < of as a mapping
" <
" < {0,1} => 0|1
" ...
" As far as I can see, what you have defined is not a function. A function is
There are a couple (>=2) of things I don't understand about this discussion:
Why does it matter whether Turing machines compute functions? If one
wants to compute non-functional relations, why not just define the
machines accordingly? If there's a terminological problem, then call
the machines something else.
What does it matter to Church's thesis whether what is computed is
a function? Sometimes the thesis is phrased using the word function,
but is that essential to the thesis?
And anyhow, why can't `0|1' be considered a single value?
Greg, lee@uhccux.uhcc.hawaii.edusmryan@garth.UUCP (Steven Ryan) (10/01/88)
>random number generation!) *might* be fooling us. You can only appeal to >phsyical random number generators to disprove the Church-Turing hypothesis >if you assume that the quantum-mechanical laws a really true, which is to >say if you already assume that the universe is not running on a Turing machine. >I believe it, but a circular "proof" like that is no proof! Well, just to keep things straight, I'm the one who mentionned TM and CT. I used them as a conditionals, `If the universe was a TM, then such and such would follow.' It wasn't intended to assert, prove, or disprove CT, but just engage in withywanderring philosophical speculation. To me, the Ignorant Assumption is not any particular theory or religion, but the meta-assumption that assumptions are unnecessary.
nlt@romeo.cs.duke.edu (N. L. Tinkham) (10/01/88)
I have no objection to the formulation "any function that would naturally
be regarded as computable can be computed by a universal Turing machine", as
long as it is clear that being "naturally...regarded as computable" includes
the list of conditions associated with algorithms. Setting aside those
conditions would introduce a broader definition of "computable" than is in
common use; such a definition may well be interesting to consider, but it might
reduce confusion to use a different term (say, "q-computable").
The claim that "a function is surely 'computable' if a physical system
can be constructed that computes it" is the disputed point. In order to
believe that a function f is computable, I will require that I be shown that
there is an algorithm by which f may be computed. This algorithm need not be
a Turing-machine program (if that were the case, the thesis would indeed be
trivial), but it should conform to the general requirements of an algorithm:
ability to be specified in a description of finite length, computation in
discrete steps, and so forth. And one of these requirements is that the
computation should not use random methods. (Reference, again, is to chapter 1
of Rogers' text.
Falsifying the Church-Turing thesis would require presenting a function f
for which such an algorithm exists, and then showing that f cannot be computed
on a Turing machine.
[We have drifted quite far from religion here. Followups are directed to
comp.ai.]
Nancy Tinkham
{decvax,rutgers}!mcnc!duke!nlt
nlt@cs.duke.edu