Copy Link
Add to Bookmark
Report
AIList Digest Volume 8 Issue 099
AIList Digest Tuesday, 11 Oct 1988 Volume 8 : Issue 99
Mathematics and Logic - The Ignorant assumption (6 messages)
----------------------------------------------------------------------
Date: 16 Sep 88 01:58:53 GMT
From: garth!smryan@unix.sri.com (Steven Ryan)
Subject: Re: The Ignorant assumption
>" ... We all know (I hope) formal systems are either
>" incomplete or inconsistent.
>
>I don't know that. Can you show this for predicate logic?
Either a system is too simple (like propositional calculus) to
do number theory (which is equivalent to everything else) or it's
powerful enough in which Godel's theorem come into play: any
system powerful enough for number theory is either incomplete or
omega-inconsistent.
Simple systems like propositional calculus are complete within their domain,
but their domain is incomplete with respect to number theory and all
other formal system.
(Predicate calculus includes quantifiers; propositional calculus does not.)
------------------------------
Date: 26 Sep 88 23:09:07 GMT
From: grad3!nlt@cs.duke.edu (Nancy L. Tinkham)
Subject: Re: The Ignorant assumption
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
------------------------------
Date: 27 Sep 88 15:07:41 GMT
From: firth@sei.cmu.edu (Robert Firth)
Subject: Re: The Ignorant assumption
In a previous article, 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]
------------------------------
Date: 28 Sep 88 05:45:56 GMT
From: bbn.com!aboulang@bbn.com (Albert Boulanger)
Subject: Re: The Ignorant assumption
In <13763@mimsy.UUCP> Darren F. Provine writes
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?
Yup, Quantum Computers! (Half Serious :-))
Let me quote the abstract of the following paper: "Quantum Theory, the
Church-Turing Principle and the Universal Quantum Computer", D.
Deutsch, Proc. R. Soc. Lond. A400 97-117 (1985)
"It is argued that underlying the Church-Turing hypothesis there is an
implicit physical assertion. Here, this assertion is presented explicitly as a
physical principle: 'every finitely realizable physical system can be
perfectly simulated by a universal model computing machine operating by finite
means'. Classical physics and the universal Turing machine, because the former
is continuous and the latter discrete, do not obey the principle, at least in
the strong form above. A class of model computing machines that is the quantum
generalization of the class of Turing machines is described, and is shown that
quantum theory an the 'universal quantum computer' are compatible with the
principle. Computing machines resembling the universal quantum computer could,
in principle, be built and would have remarkable properties not reproducible
by any Turing machine. These do not include the computation of non-recursive
Functions, but they do include 'quantum parallelism', a method by which
certain probabilistic tasks can be performed faster by a universal quantum
computer than any classical restriction of it. The intuitive explanation of
these properties places an intolerable strain on all interpretations of
quantum theory other than Everett's. (Multiple-Worlds interpretation - ed)
Some of the numerous connections between quantum theory of computation and the
rest of physics are explored. Quantum complexity theory allows a physically
more reasonable definition of the 'complexity' or 'knowledge' in a physical
system than does classical complexity theory."
For 1 one page description of this paper, see John Maddox's News and Views
"Towards the Quantum Computer?", Nature Vol 316, 15 August 1985, 573.
For a perspective and a readable account of why Deutsch reasons that universal
quantum computers support the Many-Worlds interpretation of Quantum Mechanics,
see the chapter on Deutsch in the book, "The Ghost in the Atom", P.C.W.
Davies, & J.R. Brown eds, Cambridge University Press, 1986 (Chapter 6).
I should also mention that thinking along these lines have led others to
investigate the ultimate randomness in quantum mechanics. See "Randomness in
Quantum Mechanics - Nature's Ultimate Cryptogram?", T. Erber & S. Putterman,
Nature, Vol 317, 7 Nov. 1985, 41-43. Since this report, they have actually
analyzed data from NBS ionic-trap data, and so far QM checks out to be really
random.
Now to some, this stuff about quantum computers may sound MAX flaky, but
consider the fact that intuitive people like Feynman wrote papers on the topic.
A key new theory that helps put the question of randomness and the question of
determinism (to some extent) into perspective is algorithmic complexity
theory. In this theory, one can assign a measure of randomness to a number
string, by using as a metric the shortest algorithm that could produce that
string. If one considers the decimal expansion of the reals, than "most" of
the the number line is dominated by numbers with infinite algorithmic
complexity. Furthermore, these numbers are inaccessible in any way to
"classical" Turing machines in finite time or space.
By the way, Erber & Putterman point out in their paper that "the axiomatic
development (of QM) is deliberately silent concerning any requirements that the
measurable functions be non-determinate or that the elements of probability
space correspond to inherently unpredictable or erratic events."
The way I think of nondeterminism is operational. For example, if I were to be
given an infinite-complexity number like Chaitin's omega, and an infinite
resource universal computer I could use it as a seed to a random number
generator (ie a chaotic system) and generate truly non-repeating random
numbers. But since the initial seed required infinite resources, I could never
realize it on a 'classical' computer. The important question is whether nature
has access to such numbers.
Albert Boulanger
aboulanger@bbn.com
BBN Systems & Technologies, Inc.
------------------------------
Date: 29 Sep 88 14:51:41 GMT
From: firth@sei.cmu.edu (Robert Firth)
Subject: Re: The Ignorant assumption
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
------------------------------
Date: 30 Sep 88 01:31:58 GMT
From: nau@mimsy.umd.edu (Dana S. Nau)
Subject: Re: The Ignorant assumption
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
------------------------------
End of AIList Digest
********************
