Path: utzoo!utgpu!jarvis.csri.toronto.edu!clyde.concordia.ca!mcgill-vision!quiche!utility
From: utility@quiche.cs.mcgill.ca (Ronald BODKIN)
Newsgroups: comp.ai
Subject: Re: Algorithms, Turing, Semantics
Message-ID: <2007@quiche.cs.mcgill.ca>
Date: 18 Jan 90 23:51:49 GMT
References: <12883@phoenix.Princeton.EDU> <91Eq02wy7eX=01@amdahl.uts.amdahl.com> <12945@phoenix.Princeton.EDU>
Reply-To: utility@quiche.cs.mcgill.ca (Ronald BODKIN)
Organization: SOCS, McGill University, Montreal, Canada
Lines: 25

In article <12945@phoenix.Princeton.EDU> kpfleger@phoenix.Princeton.EDU (Karl Robert Pfleger) writes:
>Lastly, there is no proof that physical systems have an infinite number
>of states. Space could be discrete. Time could be discrete. Either could
>be finite.
	I think that the ultimate test of the Church-Turing thesis is
whether a Turing Machine exists which could compute the universe's
behaviour.  If so then, naturally, everything which is "really" computible
is Turing-Computible and, indeed, strong AI is 1000% correct.  As
for whether a Turing Machine could do this, its a hard question -- I
think that given discrete space/time that does not extend infinitely (although
my best knowledge of modern physics is that such a description is incredibly
simplistic) it could certainly be done.  However, I would contend that
if the universe (as it does not currently appear) is in any way infinite,
then it is not Turing computible.  And then there is an algorithm for
deciding things which is not Turing computible, so the thesis fails (I
consider the universe to be a massive algorithm that decides things).  And
as for questions of randomness, everyone knows that Deterministic Turing
machines can similuate non-Deterministic ones, andprobability densities
can likewise be carried around for given events, and no operation can create
a number out of two finitely-representable ones which is not itself finitely
representable (e.g. from 1,5 I can get sin(6) but that SIN(6) is a finite
representation).
	Has anyone heard mention of the universe in relation to the old
Church-Turing thesis?
			Ron