Copy Link
Add to Bookmark
Report
AIList Digest Volume 8 Issue 100
AIList Digest Tuesday, 11 Oct 1988 Volume 8 : Issue 100
More on ... The Ignorant assumption (6 messages)
----------------------------------------------------------------------
Date: 30 Sep 88 07:51:15 GMT
From: quintus!ok@unix.sri.com (Richard A. O'Keefe)
Subject: Re: The Ignorant assumption
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!
------------------------------
Date: 30 Sep 88 14:00:44 GMT
From: uhccux!lee@humu.nosc.mil (Greg Lee)
Subject: Re: The Ignorant assumption
>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.edu
------------------------------
Date: 30 Sep 88 20:34:32 GMT
From: garth!smryan@unix.sri.com (Steven Ryan)
Subject: Re: The Ignorant assumption
>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.
------------------------------
Date: 1 Oct 88 04:36:59 GMT
From: romeo!nlt@cs.duke.edu (N. L. Tinkham)
Subject: Re: The Ignorant assumption
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
------------------------------
Date: 3 Oct 88 05:18:16 GMT
From: vax5!w25y@cu-arpa.cs.cornell.edu
Subject: Re: The Ignorant assumption
The Church-Turing thesis deals with relations that always give the same
output value for a given input value. Any quantum-generated random function
would not have this property.
-- Paul Ciszek
W25Y@CRNLVAX5 Bitnet
W25Y@VAX5.CCS.CORNELL.EDU Internet
------------------------------
Date: 5 Oct 88 15:31:43 GMT
From: shire!ian@psuvax1.psu.edu (Ian Parberry)
Subject: Ignorance about the ignorant assumption
In article <7202@aw.sei.cmu.edu> firth@bd.sei.cmu.edu (Robert Firth) writes:
>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.
Have I missed something here? Theoretical Computer Scientists have
been stepping beyond the bounds of the Church-Turing thesis for years.
The obvious question which was first asked a long time ago (I believe that
Michael Rabin was amongst the first to do so) is whether the kind of
randomness described above helps computation.
An obvious answer is that it sometimes helps speed things up.
For example, there are several polynomial time probabilistic primality testing
algorithms, but no deterministic one is known (although it must be admitted
that one exists if the Riemann Hypothesis is true).
The Church-Turing thesis is not and never has been a sacred cow amongst
Theoretical Computer Scientists. Most view it as a handy rule of thumb,
and nothing else. It's not hard to invent machines which violate the
Church-Turing thesis. The hard part is developing a non-trivial,
entertaining, elegant and useful theory of computation around them.
My favourite work of this kind is on non-uniform circuit complexity.
Curiously, many lower-bounds proved to date hold for non-uniform
(read non-Church-Turing- thesis) circuits, and have matching uniform
(read Church-Turing-thesis) upper-bounds.
Most of the postings I've seen to date have been from non-TCS people.
However, since the Church-Turing thesis is a part of Theoretical
Computer Science, it is worth finding out what the TCS'ers have had
to say about it.
For a ton of reading, look for articles that mention the key words
probabilistic algorithm, RP, BPP, RNC in the proceedings from the IEEE
Symposium on Foundations of Computer Science and the ACM Symposium on the
Theory of Computing for the last decade. For more polished but less
up-to-date material, consult theory journals such as SIAM J. Computing,
Journal of the ACM, Theoretical Computer Science, Journal of Computer
and System Sciences, Journal of Algorithms, Information Processing Letters.
Of course, I'm not saying that Theoretical Computer Scientists have
all of the answers. But they do seem to have made a good try
at addressing the obvious questions.
-------------------------------------------------------------------------------
Ian Parberry
"The bureaucracy is expanding to meet the needs of an expanding bureaucracy"
ian@psuvax1.cs.psu.edu ian@psuvax1.BITNET ian@psuvax1.UUCP (814) 863-3600
Dept of Comp Sci, 333 Whitmore Lab, Penn State Univ, University Park, Pa 16802
------------------------------
End of AIList Digest
********************
