Xref: utzoo talk.religion.misc:7864 comp.ai:2312
Path: utzoo!utgpu!water!watmath!clyde!att!osu-cis!tut.cis.ohio-state.edu!mailrus!ames!haven!mimsy!nau
From: nau@mimsy.UUCP (Dana S. Nau)
Newsgroups: talk.religion.misc,comp.ai
Subject: Re: The Ignorant assumption
Message-ID: <13791@mimsy.UUCP>
Date: 30 Sep 88 01:31:58 GMT
References: <1369@garth.UUCP> <2346@uhccux.uhcc.hawaii.edu> <1383@garth.UUCP> <372@quintus.UUCP> <1390@garth.UUCP> <388@quintus.UUCP> <7059@aw.sei.cmu.edu> <1929@aplcomm.jhuapl.edu> <7202@aw.sei.cmu.edu>
Reply-To: nau@mimsy.umd.edu.UUCP (Dana S. Nau)
Organization: U of Maryland, Dept. of Computer Science, Coll. Pk., MD 20742
Lines: 65

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