Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/5/84; site yetti.UUCP
Path: utzoo!utcs!mnetor!yetti!peter
From: peter@yetti.UUCP (Runge)
Newsgroups: net.ai
Subject: Re: Re: AI and Turing's Thesis
Message-ID: <185@yetti.UUCP>
Date: Sun, 26-May-85 16:57:57 EDT
Article-I.D.: yetti.185
Posted: Sun May 26 16:57:57 1985
Date-Received: Mon, 27-May-85 13:25:10 EDT
References: <113@nvuxf.UUCP> <388@linus.UUCP> <1647@psuvax1.UUCP>
Organization: York University Computer Science
Lines: 40

> Hewitt's
> examples of asynchronous parallel computation can be easily simulated by a 
                                                        ^^^^^^
> Turing machine - it will be less efficient, but Church's thesis says nothing
> about efficiency.

I agree with everything in this article except the point about simulating
asynchronous parallel computation.  In almost all of the literature,
the TM models are "clocked"; the entire system changes state synchronously.

The only *easy* way I know of simulating an asynchronous process on a TM 
requires the ASSUMPTION that all the events  in the asynchronous process can be
clocked by a global clock.  (Imagine what a mess it would be if they couldn't
be! How would we know how many states the process as a whole actually had?
How could we define temporal orderings between parts of the whole process
which are not in direct communication? Think of the number of times in which
your site has received a followup to an article before you got the article.
Are you confident you could design the software so that this could NEVER
happen without appealing to a Universal Time stamp?)

What justifies the assumption that universal synchronization is always
possible?

Note that my objection is to the word "easily", not to Church's thesis.
I believe that C. Petri (of Petri net fame) constructed an asynchronous
model of a TM in which each square of the tape was a finite automaton
connected asynchronously to its neighbors and to the read/write head. This
was a Ph. D. thesis (in German) from University of Bonn in the early
60's.   It was translated (by a man named Green, I believe) but I don't
know where the English version appeared.  My recollection was that Petri
showed that the asynchronous TM could carry out any TM computation, even
in the face of indefinite delays  in the signals between its components.
Of course, for Church's thesis, it's the converse that is important.
Anybody know of any more recent rigorous results on this issue?
[This really belongs in net.automata!]

-- 

   Peter H. Roosen-Runge, Department of Computer Science, York University
                          Toronto (Downsview), Ontario