Copy Link
Add to Bookmark
Report
AIList Digest Volume 1 Issue 091
AIList Digest Monday, 7 Nov 1983 Volume 1 : Issue 91
Today's Topics:
Parallelism,
Turing Machines
----------------------------------------------------------------------
Date: 1 Nov 83 22:39:06-PST (Tue)
From: hplabs!hao!seismo!rlgvax!cvl!umcp-cs!israel @ Ucb-Vax
Subject: Re: Parallelism and Conciousness
Article-I.D.: umcp-cs.3498
[Initial portion missing. -- KIL]
a processing unit that we can currently build. If you mean 'at the
exact same time', then I defy you to show me a case where this is
necessary.
The statement "No algorithm is inherently parallel", just means that
the algoritm itself (as opposed to the engineering of putting it
into practice) does not necessarily have to be done in parallel.
Any parallel algorithm that you give me, I can write a sequential
algorithm that does the same thing.
Now, if you assume a finite number of processors for the parallel
algorithm, then the question of whether the sequential algorithm will
work under time constraints is dependent on the speed of the
processor worked on. I don't know if there has been any work
done on theoretical limits of the speed of a processor (Does
anyone know? is this a meaningful question?), but if we assume
none (a very chancy assumption at best), then any parallel algorithm
can be done sequentially in practice.
If you allow an infinite number of processors for the parallel
algorithm, then the sequential version of the algorithm can't
ever work in practice. But can the parallel version? What
do we run it on? Can you picture an infinitely parallel
computer which has robots with shovels with it, and when the
computer needs an unallocated processor and has none, then
the robots dig up the appropriate minerals and construct
the processor. Of course, it doesn't need to be said that
if the system notices that the demand for processors is
faster than the robots' processor production output, then
the robots make more robots to help them with the raw materials
gathering and the construction. :-)
--
^-^ Bruce ^-^
University of Maryland, Computer Science
{rlgvax,seismo}!umcp-cs!israel (Usenet) israel.umcp-cs@CSNet-Relay (Arpanet)
------------------------------
Date: 31 Oct 83 19:55:44-PST (Mon)
From: pur-ee!uiucdcs!uicsl!dinitz @ Ucb-Vax
Subject: Re: Parallelism and Conciousness - (nf)
Article-I.D.: uiucdcs.3572
I see no reason why consciousness should be inherently parallel. But
it turns out that the only examples of conscious entities (i.e. those
which nearly everyone agrees are conscious) rely heavily on parallelism
at several levels. This is NOT to say that they derive their
consciousness from parallelism, only that there is a high corelation
between the two.
There are good reasons why natural selection would favor parallelism.
Besides the usually cited ones (e.g. speed, simplicity) is the fact
that the world goes by very quickly, and carries a high information
content. That makes it desirable and advantageous for a conscious
entity to be aware of several things at once. This strongly suggests
parallelism (although a truly original species might get away with
timesharing).
Pushing in the other direction, I should note that it is not necessary
to bring the full power of the human intellect to bear against ALL of
our environment at once. Hence the phenomenon of attention. It
suffices to have weaker processes in charge of uninteresting phenomena
in the environment, as long as these have the ability to enlist more of
the organism's information processing power when the situation becomes
interesting enough to demand it. (This too could be finessed with a
clever timesharing scheme, but I know of no animal that does it that
way.)
Once again, none of this entails a connection causal connection between
parallelism and consciousness. It just seems to have worked out that
nature liked it that way (in the possible world in which we live).
Rick Dinitz
...!uiucdcs!uicsl!dinitz
------------------------------
Date: 1 Nov 83 11:53:58-PST (Tue)
From: hplabs!hao!seismo!rochester!blenko @ Ucb-Vax
Subject: Re: Parallelism & Consciousness
Article-I.D.: rocheste.3648
Interesting to see this discussion taking place among people
(apparently) committed to an information-processing model for
intelligence.
I would be satisfied with the discovery of mechanisms that duplicate
the information-processing functions associated with intelligence.
The issue of real-time performance seems to be independent of
functional performance (not from an engineering point of view, of
course; ever tell one of your hardware friends to "just turn up the
clock"?). The fact that evolutionary processes act on both the
information-processing and performance characteristics of a system may
argue for the (evolutionary) superiority of one mechanism over another;
it does not provide prescriptive information for developing functional
mechanisms, however, which is the task we are currently faced with.
Tom
------------------------------
Date: 1 Nov 83 19:01:59-PST (Tue)
From: hplabs!hao!seismo!rlgvax!cvl!umcp-cs!speaker @ Ucb-Vax
Subject: Re: Parallelism and Conciousness
Article-I.D.: umcp-cs.3523
No algorithm is inherently parallel.
The algorithms you are thinking about occur in the serial world of
the Turing machine. Turing machines, remember, have only only one
input. Consider what happens to your general purpose turing machine
when it must compute on more than one input and simultaneously!
So existence in the real world may require parallelism.
How do you define simultaneously? If you mean within a very short
period of time, then that requirement is based on the maximum speed of
a processing unit that we can currently build. If you mean 'at the
exact same time', then I defy you to show me a case where this is
necessary.
A CHALLENGE!!! Grrrrrrrr......
Okay, let's say we have two discrete inputs that must
be monitored by a Turing machine. Signals may come in
over these inputs simultaneously. How do you propose
to monitor both discretes at the same time? You can't
monitor them as one input because your Turing machine
is allowed only one state at a time on its read/write head.
Remember that the states of the inputs run as fast as
those of the Turing machine.
You can solve this problem by building two Turing machines,
each of which may look at the discretes.
I don't have to appeal to practical speeds of processors.
We're talking pure theory here.
--
- Speaker-To-Stuffed-Animals
speaker@umcp-cs
speaker.umcp-cs@CSnet-Relay
------------------------------
Date: 1 Nov 83 18:41:10-PST (Tue)
From: hplabs!hao!seismo!rlgvax!cvl!umcp-cs!speaker @ Ucb-Vax
Subject: Infinite loops and Turing machines...
Article-I.D.: umcp-cs.3521
One of the things I did in my undergrad theory class was to prove that
a multiple-tape Turing machine is equivalent to one with a single tape
(several tapes were very handy for programming). Also, we showed that
a TM with a 2-dimensional tape infinite in both x and y was also
equivalent to a single-tape TM. On the other hand, the question of
a machine with an infinite number of read heads was left open...
Aha! I knew someone would come up with this one!
Consider that when we talk of simultaneous events... we speak of
simultaneous events that occur within one Turing machine state
and outside of the Turing machine itself. Can a one-tape
Turing machine read the input of 7 discrete sources at once?
A 7 tape machine with 7 heads could!
The reason that they are not equivelent is that we have
allowed for external states (events) outside of the machine
states of the Turing machine itself.
--
- Speaker-To-Stuffed-Animals
speaker@umcp-cs
speaker.umcp-cs@CSnet-Relay
------------------------------
Date: 1 Nov 83 16:56:19-PST (Tue)
From: hplabs!hao!seismo!philabs!linus!security!genrad!mit-eddie!rlh @
Ucb-Vax
Subject: Re: Parallelism and Conciousness
Article-I.D.: mit-eddi.885
requirement is based on the maximum speed of
a processing unit that we can currently build. If you mean 'at the
exact same time', then I defy you to show me a case where this is
necessary.
The statement "No algorithm is inherently parallel", just means that
the algorithm itself (as opposed to the engineering of putting it
into practice) does not necessarily have to be done in parallel.
Any parallel algorithm that you give me, I can write a sequential
algorithm that does the same thing.
Consider the retina, and its processing algorithm. It is certainly
true that once the raw information has been collected and in some way
band-limited, it can be processed in either fashion; but one part of
the algorithm must necessarily be implemented in parallel. To get
the photon efficiencies that are needed for dark-adapted vision
(part of the specifications for the algorithm) one must have some
continuous, distributed attention to the light field. If I match
the spatial and temporal resolution of the retina, call it several thousand
by several thousand by some milliseconds, by sequentially scanning with
a single receptor, I can only catch one in several-squared million
photons, not the order of one in ten that our own retina achieves.
------------------------------
Date: 2 Nov 83 19:44:21-PST (Wed)
From: pur-ee!uiucdcs!uicsl!preece @ Ucb-Vax
Subject: Re: Parallelism and Conciousness - (nf)
Article-I.D.: uiucdcs.3633
There is a significant difference between saying "No algorithm is
inherently parallel" and saying "Any algorithm can be carried out
without parallelism." There are many algorithms that are
inherently parallel. Many (perhaps all) of them can be SIMULATED
without true parallel processing.
I would, however, support the contention that computational models
of natural processes need not follow the same implementations, and
that a serial simulation of a parallel process can produce the
same result.
scott preece
ihnp4!uiucdcs!uicsl!preece
------------------------------
Date: 2 Nov 83 15:22:20-PST (Wed)
From: hplabs!hao!seismo!philabs!linus!security!genrad!grkermit!masscom
p!kobold!tjt @ Ucb-Vax
Subject: Re: Parallelism and Conciousness
Article-I.D.: kobold.191
Gawd!! Real-time processing with a Turing machine?!
Pure theory indeed!
Turing machines are models for *abstract* computation. You get to
write an initial string on the tape(s) and start up the machine: it
does not monitor external inputs changing asynchronously. You can
define your *own* machine which is just like a Turing machine, except
that it *does* monitor external inputs changing asynchronously (Speaker
machines anyone :-).
Also, if you want to talk *pure theory*, I could just enlarge my input
alphabet on a single input to encode all possible simultaneous values
at multiple inputs.
--
Tom Teixeira, Massachusetts Computer Corporation. Littleton MA
...!{harpo,decvax,ucbcad,tektronix}!masscomp!tjt (617) 486-9581
------------------------------
Date: 2 Nov 83 16:28:10-PST (Wed)
From: hplabs!hao!seismo!philabs!linus!security!genrad!grkermit!masscom
p!kobold!tjt @ Ucb-Vax
Subject: Re: Parallelism and Conciousness
Article-I.D.: kobold.192
In regards to the statement
No algorithm is inherently parallel.
which has been justified by the ability to execute any "parallel"
program on a single sequential processor.
The difference between parallel and sequential algorithms is one of
*expressive* power rather than *computational* power. After all, if
it's just computational power you want, why aren't you all programming
Turing machines?
The real question is what is the additional *expressive* power of
parallel programs. The additional expressive power of parallel
programming languages is a result of not requiring the programmer to
serialize steps of his computation when he is uncertain whether either
one will terminate.
--
Tom Teixeira, Massachusetts Computer Corporation. Littleton MA
...!{harpo,decvax,ucbcad,tektronix}!masscomp!tjt (617) 486-9581
------------------------------
Date: 4 Nov 83 8:13:22-PST (Fri)
From: hplabs!hao!seismo!ut-sally!ut-ngp!utastro!nather @ Ucb-Vax
Subject: Our Parallel Eyeballs
Article-I.D.: utastro.784
Consider the retina, and its processing algorithm. [...]
There seems to be a misconception here. It's not clear to me that "parallel
processing" includes simple signal accumulation. Astronomers use area
detectors that simply accumulate the charge deposited by photons arriving
on an array of photosensitive diodes; after the needed "exposure" the charge
image is read out (sequentially) for display, further processing, etc.
If the light level is high, readout can be repeated every few milliseconds,
or, in some devices, proceed continuously, allowing each pixel to accumulate
photons between readouts, which reset the charge to zero.
I note in passing that we tend to think sequentially (our self-awareness
center seems to be serial) but operate in parallel (our heart beats along,
and body chemistry gets its signals even when we're chewing gum). We
have, for the most part, built computers in our own (self)image: serial.
We're encountering real physical limits in serial computing (the finite
speed of light) and clearly must turn to parallel operations to go much
faster. How we learn to "think in parallel" is not clear, but people
who do the logic design of computers try to get as many operations into
one clock cycle as possible, and maybe that's the place to start.
Ed Nather
ihnp4!{ut-sally,kpno}!utastro!nather
------------------------------
Date: 3 Nov 83 9:39:07-PST (Thu)
From: decvax!microsoft!uw-beaver!ubc-visi!majka @ Ucb-Vax
Subject: Get off the Turing Machines
Article-I.D.: ubc-visi.513
From: Marc Majka <majka@ubc-vision.UUCP>
A Turing machine is a theoretical model of computation.
<speaker.umcp-cs@CSnet-Relay> points out that all this noise about
"simultaneous events" is OUTSIDE of the notion of a Turing machine. Turing
machines are a theoretical formulation which gives theoreticians a formal
system in which to consider problems in computability, decidability, the
"hardness" of classes of functions, and etc. They don't really care whether
set membership in a class 0 grammer is decidable in less than 14.2 seconds.
The unit of time is the state transition, or "move" (as Turing called it).
If you want to discuss time (in seconds or meters), you are free to invent a
new model of computation which includes that element. You are then free to
prove theorems about it and attempt to prove it equivalent to other models
of computation. Please do this FORMALLY and post (or publish) your results.
Otherwise, invoking Turing machines is a silly and meaningless exercise.
Marc Majka
------------------------------
Date: 3 Nov 83 19:47:04-PST (Thu)
From: pur-ee!uiucdcs!uicsl!preece @ Ucb-Vax
Subject: Re: Parallelism and Conciousness - (nf)
Article-I.D.: uiucdcs.3677
Arguments based on speed of processing aren't acceptable. The
question of whether parallel processing is required has to be
in the context of arbitrarily fast processors. Thus you can't
talk about simultaneous inputs changing state at processor speed
(unless you're considering the interesting case where the input
is directly monitoring the processor itself and therefore
intrinsically as fast as the processor; in that case you can't
cope, but I'm not sure it's an interesting case with respect to
consciousness).
Consideration of the retina, on the other hand, brings up the
basic question of what is a parallel processor. Is an input
latch (allowing delayed polling) or a multi-input averager a
parallel process or just part of the plumbing? We can also, of
course, group the input bits and assume an arbitrarily fast
processor dealing with the bits 64 (or 128 or 1 million) at a
time.
I don't think I'd be willing to say that intelligence or
consciousness can't be slow. On the other hand, I don't think
there's too much point to this argument, since it's pretty clear
that producing a given level of performance will be easier with
parallel processing.
scott preece
ihnp4!uiucdcs!uicsl!preece
------------------------------
End of AIList Digest
********************
