HDTenEightyP/NetNews huggingface dataset:
From: MARCHESF@PACEVM.BITNET ("Dr. Francis T. Marchese")
Subject: Call for Participation
Organization: The Internet
Distribution: inet
Date: Sat, 7 Nov 1992 21:25:28 GMT



*** Call For Participation ***

Conference on Understanding Images

Spons
ored By

NYC ACM/SIGGRAPH 
     and
Pace University's 
School of Computer S
cience and Information Systems

To Be Held at:

Pace University
New York Ci
ty, New York
May 21-22,1993



Artists, designers, scientists, engineers an
d educators share the problem
of moving information from one mind to another.
Traditionally, they have
used pictures, words, demonstrations, music and dance
to communicate
imagery.  However, expressing complex notions such as God and in
finity
or a seeminglywell defined concept such as a flower can present
challen
ges which far exceed their technical skills.

The explosive use of computers a
s visualization and expression tools has
compounded this problem.  In hypermedi
a, multimedia and virtual reality
systems vast amounts of information confront
the observer or participant. 
Wading through a multitude of simultaneous images
 and sounds in
possibly unfamiliar representations, a confounded user asks: Wha
t does
it all mean?

Since image construction, transmission, reception, decip
herment and
ultimate understanding are complex tasks strongly influenced by
ph
ysiology, education and culture; and since electronic media radically
amplify e
ach processing step, then we, as electronic communicators, must
determine the f
undamental paradigms for composing imagery for
understanding.

Therefore, the
 purpose of this conference is to bring together a breadth
of disciplines, incl
uding, but not limited to, the physical, biological and
computational sciences,
 technology, art, psychology, philosophy and
education, in order to define and
discuss the issues essential to image
understanding within the computer graphic
s context.  To this end we seek
proposals for individual presentations, panel d
iscussions, static displays,
interactive environments, performances and beyond.


Submissions:
Contributors are requested to submit a one page proposal by Ja
nuary 15,
1993.  Accepted presentations
will be included in the proceedings.


Direct all inquires and submissions to:
Professor Francis T. Marchese
             Phone:  212 346-1803
Department of Computer Science
   Fax:    212 346-1933
Pace University                                 Email:

MARCHESF@PACEVM.Bitnet          
New York, NY 10038  USA
From: gaylord@ux1.cso.uiuc.edu (Richard J. Gaylord)
Newsgroups: comp.theory.cell-automata
Subject: Re: Looking for Wolfram paper
Date: 5 Nov 92 17:06:16 GMT
Article-I.D.: news.Bx966J.9o5
Organization: University of Illinois
X-Xxdate: Thu, 5 Nov 92 11:06:52 GMT
X-Useragent: Nuntius v1.1.1d12
X-Xxmessage-Id: <A71EB0CC95029B17@mm-mac23.mse.uiuc.edu>

you don't have to go to singapore. the book can be ordered from world
scientific at

800-227-7562

201-487-9655 [this is in new jersey which though certainly a strange
place is located somewhere in the states]

btw - the pb  is $24, the hardcover is >$50
From: tolman%asylum.cs.utah.edu@cs.utah.edu (Kenneth Tolman)
Subject: Undecidability of configurations/progression
Date: 8 Nov 92 21:02:19 MST
Organization: University of Utah, CompSci Dept

  There are some things which must be undecidable for cellular automata...
see if you agree!

1) Decaying into a cycle.  For any CA capable of supporting universal
  computation, it could be set up to perform some computation.  If that
  computation fell into a cycle, it would be non halting, and thus we
  would have a decision procedure for halting or non halting for Turing
  machines.  Thus, for at least a certain class of CA, there can be no
  decision procedure determining whether they go into a cycle or not.
  (perhaps for weaker CA as well?)

2) Whether a configuration is garden of eden (as demonstrated by previous
  poster)

3) Whether given state A will evolve to given state B... as before, this
  could not be decidable for we would have a decision procedure for
  halting or non halting.


What other things are not decidable for CA?



Newsgroups: comp.theory.cell-automata
From: frank@Cookie.secapl.com (Frank Adams)
Subject: Re: Undecidability of configurations/progression
Date: Wed, 11 Nov 1992 17:38:07 GMT
Organization: Security APL, Inc.

In article <POLLACK.92Nov9133140@dendrite.cis.ohio-state.edu> pollack@cis.ohio-state.edu writes:
>>2) Whether a configuration is garden of eden (as demonstrated by previous
>>  poster)
>
>there are 3 different problems:
>
>1)  Given a SPECIFIC finite configuration, we can run a deterministic
>limited-neighborhood CA BACKWARDS one step.  Generally, one would get
>lots of previous states, but a GoE would have 0 previous states.
>The size of the previous states would expand at the speed of light.

This depends on exactly how you define a GoE pattern.  If I have a pattern
which fits in an n by m rectangle, there are two questions I can ask:

(1) is there any previous pattern whose next step, restricted to that
rectangle, is the specified pattern?

(2) is there any previous pattern whose next step is the specified pattern,
with everything outside the rectangle being blank?

Question (1) can be answered as described; however I believe question (2) is
the standard definition of a GoE.  And question (2) is, in fact,
undecidable.

(*Very* brief outline of proof: one can make a CA for a given Turing machine
such that a cell disappears iff it is (locally) part of a computation of the
TM (with successive times in adjacent rows).  A row will be GoE iff the
computation starting with it does not halt.  Hence the GoE problem is
reducible to the halting problem.  (Note that if you allow infinite
patterns, you can simply refuse to erase the halting state, inverting the
result: a pattern is GoE iff the computation starting with it *does* halt.))

>2) Finding a GoE which gives rise to a PARTICULAR configuration is a
>much harder problem, as it would require searching through the space
>generated by operator 1. Unless the question were asked: "is this
>configuration less than K generations from a GoE", it is undecideable.

It is undecideable anyhow.

>3) finally, whether or not any GoE's EXIST for a particular CA rule
>might be even harder. 

However, if I remember the Scientific American article where I first
encountered GoE patterns, this problem is easy: a CA has a GoE pattern iff
it is not invertible.  An invertible CA A is one where there is an inverse
CA B such that if A takes pattern X to pattern Y, B takes Y to X, and vice
versa.

>A more interesting question might involve whether the current state in
>the smallest bounding box, could have arisen from a "smaller" state.
>
>Then one could invert CA's to build data compression systems:
>
>   Start with 1011 and run rule 247 for 16325 generations,
>   then run rule 343 for 932 generations, and ta da: the Mona Lisa!

You can't compress the data to less than it's information-theoretic content.
A "data-compression" scheme which doesn't attack the redundencies in the
original message is not likely to accomplish anything.
From: burt@aupair.cs.athabascau.ca (Burt Voorhees)
Newsgroups: comp.theory.cell-automata
Subject: Re: Undecidability of configurations/progression
Date: 9 Nov 92 21:30:29 GMT

>fraserc@dcs.glasgow.ac.uk (Campbell Fraser) writes:

>>In article <1992Nov8.210220.29731@hellgate.utah.edu>, tolman%asylum.cs.utah.e
du@cs.utah.edu (Kenneth Tolman) writes:
>>>   There are some things which must be undecidable for cellular automata...
>>> see if you agree!

>>> 2) Whether a configuration is garden of eden (as demonstrated by previous
>>>   poster)

>>Surely this is. If the 'world' has length x and height y then there are 2^(x.
y)
>>possible states. Try every one and if none lead to the alleged garden of eden

>>then it is a garden of eden. If one does then make it the starting state and
>>then the alleged garden is reached proving that it isn't.
>>Of course the problem is probably intractable.


>For any given configuration, you can probably determine this.  The problem is
>to find a general algorithm that say yes for this config, and no for that
>config, that works for any config whatsoever.

>CA worlds are generally unbounded, so the world has length oo and height oo.

For any finite configuration, however, there is a proceedure which will
say whether or not it is GofE.  A very computationally intensive proceedure...
If I take a state space of half-infinite 0,1 strings then one of these
will be Gof E if it contains any finite string which has no pre-image,
that seems to say that it will not be GofE if it contains no such finite
substrings, although I am no longer entirely certain about that.
For looking at finite strings and determining whether or not they have
pre-images, however, there is a graph theoretic based proceedure.  I've
had a paper sitting at Physica D for over a year now which describes this
(they must be having some kind of editorial problems there, they used
to give reports rather quickly...).  Anybody who is interested send me
a snail mail address and I'll forward a pre-print.
Burton Voorhees
Faculty of Science
Athabasca University
Box 10,000
Athabasca, AB
CANADA   T0G 2R0
burt@aupair.cs.athabascau.ca
Newsgroups: comp.theory.cell-automata
From: tolman%asylum.cs.utah.edu@cs.utah.edu (Kenneth Tolman)
Subject: Re: commuting CA rules
Date: 10 Nov 92 13:56:54 MST
Keywords: cellular automata, commutation of rules
Organization: University of Utah, CompSci Dept

>  Given a global CA rule F:E-->E it is possible to find a set of
>non-linear Diophantine equations whose solution set determines all
>rules (of a given neighborhood size) which commute with F.
>(Commutation of Cellular Automata Rules, Burton Voorhees, preprint)
>
>Is anybody aware of a use for this information, other than as a bit
>of interesting theory?

The major use of such tidbit is that it ties together previously?
uncoupled domains.  Proving something equivalent to something else is
meaningless in and of itself, unless you know something (or think you could
figure something) in the other domain that it maps into.  This particular
tidbit probably has some important ramifications... Diophantine equations
have been studied for thousands of years, and there are many results
about unsolvability and so forth.  The trick is to learn (or find someone)
that knows a lot about previous results for Diophantine equations and then
use these results to say things about CA. Finding isomorphisms in general
is very important for advancement, because it allows one to consider things
in another light.
From: burt@cs.athabascau.ca (Burt Voorhees)
Newsgroups: comp.theory.cell-automata
Subject: commuting CA rules
Keywords: cellular automata, commutation of rules
Date: 9 Nov 92 22:58:08 GMT
Organization: Athabasca University


  Given a global CA rule F:E-->E it is possible to find a set of
non-linear Diophantine equations whose solution set determines all
rules (of a given neighborhood size) which commute with F.
(Commutation of Cellular Automata Rules, Burton Voorhees, preprint)

Is anybody aware of a use for this information, other than as a bit
of interesting theory?

Burton Voorhees
Faculty of Science
Athabasca University
Box 10,000
Athabasca, AB
CANADA   T0G 2R0
burt@aupair.cs.athabascau.ca
Newsgroups: comp.theory.cell-automata
From: baljeual@uther.calvin.edu (Alan Baljeu)
Subject: Re: Undecidability of configurations/progression
Organization: Calvin College
Date: Mon, 9 Nov 1992 17:54:36 GMT

fraserc@dcs.glasgow.ac.uk (Campbell Fraser) writes:

>In article <1992Nov8.210220.29731@hellgate.utah.edu>, tolman%asylum.cs.utah.edu@cs.utah.edu (Kenneth Tolman) writes:

>>   There are some things which must be undecidable for cellular automata...
>> see if you agree!
>>
>... 
>> 
>> 2) Whether a configuration is garden of eden (as demonstrated by previous
>>   poster)
>> 
>...

>Surely this is. If the 'world' has length x and height y then there are 2^(x.y)
>possible states. Try every one and if none lead to the alleged garden of eden 
>then it is a garden of eden. If one does then make it the starting state and
>then the alleged garden is reached proving that it isn't.

>Of course the problem is probably intractable.

>Excuse me if this is wrong and naive but I only just peeked at this newsgroup
>and don't know a lot about CA.

For any given configuration, you can probably determine this.  The problem is 
to find a general algorithm that say yes for this config, and no for that 
config, that works for any config whatsoever.

CA worlds are generally unbounded, so the world has length oo and height oo.
From: hurd@math.gatech.EDU (Lyman Hurd)
Newsgroups: comp.theory.cell-automata
Subject: reference
Date: 7 Nov 92 22:10:18 GMT
Distribution: inet
Organization: The Internet

Last reference was:

``Formal Language Characterizations of Cellular Automata Limit Sets.''
Complex Systems 1.

also

``Non-recursive Cellular Automata Limit Sets'' also in Complex Systems.

Lyman
Newsgroups: comp.theory.cell-automata
From: MCINTOSH@UNAMVM1.BITNET ("Harold V. McIntosh")
Subject: subshifts of finite type.
X-Unparsable-Date: Tue, 10 Nov 92 23: 28:46 MEX
Organization: The Internet
Distribution: inet
Date: Wed, 11 Nov 1992 07:20:51 GMT

In his recent contribution to the lore of the Garden of Eden, Lyman Hurd
(<hurd(at)MATH.GATECH.EDU>) comments:
-
> The distinction between 1 and 2D is again vast.  In 1-d one way to specify
> a set of configurations is to exclude a finite set of substrings.  The
> resultant sequences form what is known as a subshift of finite type and has
> a regular language description as all bi-infinite walks through a specific
> labeled directed graph.  In 2D the undecidability of the tiling problem
> says that given a finite set of excluded blocks, one cannot decide whether
> the set described is non-empty.
-
One of the things which has puzzled me has been to know why the emphasis has
been placed on 'subshifts of finite type' rather than on what is now called
a 'sofic system.' Roy Adler and Leopold Flatto, in an expository article in
the Bulletin of the American Mathematical Society, October 1991, pp 239-334,
give the idea that the difference is due to the nature of the graph in which
the bi-infinite walks are taken.
-
The difference is important, because sofic systems correspond to one
dimensional
cellular automata and subshifts of finite type apparently do not. The question
is whether this is a historical matter, in which the knowledge of these systems
gradually developed along a certain path, which was later seen not to have been
the most convenient one? Or whether there is some fundamentally important
difference which one has failed to comprehend?
-
The article in question contains an explanation of the relationship between
topology and combinatorics for shift dynamical systems (and automata as well)
in which the way that one defines open sets and requires commutativity with the
shift operation leads naturally to the role of the functions by which automata
evolve as the continuous functions for the topology.
-
It is not that one cannot comprehend the formal proofs in this area; it is the
usual difficulty of understanding the motivations behind the mathematician's
accustomed elegance. Often knowing WHY the mathematician did something is much
more important than knowing HOW it was done.
-
Would any of the persons who have worked in this area care to comment on their
experiences?
-
Harold V. McIntosh             |Depto. de Aplicaci'on de Microcomputadoras
MCINTOSH@UNAMVM1.BITNET        |Instituto de Ciencias/UAP
mcintosh@unamvm1.dgsca.unam.mx |Apdo. Postal 461
(+52+22)43-6330                |72000 Puebla, Pue., MEXICO
From: tilley@kodak.com (Dave Tilley)
Newsgroups: comp.theory.cell-automata
Subject: Re: Looking for Wolfram paper
Date: 5 Nov 92 13:32:22 GMT
Reply-To: tilley@kodak.com (Dave Tilley)
Organization: Image Processing Algorithms Laboratory, Eastman Kodak Co.

In article <1992Nov2.224457.6654@awdprime.austin.ibm.com>, guccione@f87cont1.austin.ibm.com writes:
|> 
|> 
|> I am interested in finding a copy of the paper (book?), "Twenty
|> Problems in the Theory of Cellular Automata" by Stephen Wolfram.
|> Hillis references it in his book "The Connection Machine" with only
|> the title, author and "Institute for Advanced Study, 1984."
|> 
|> I have also seen a reference to this paper which places it in in the
|> journal "Physica Scripta" (1984), but it does not appear there.  I've
|> also checked Physical Abstracts from 1981 to 1988.  Wolfram has
|> several articles, but not this one.
|> 
|> Does anyone know how to get a copy of this?
|> 
|> Thanks,
|> 
|> -- Steve
|> -- 11/2/92

I just found the beast in the library.

ISBN 9971-50-123-6
ISBN 9971-50-124-4	 pbk

Published by World Scientific Publishing Co. Pte. Ltd.
P.O. Box 128 Farrer Road Singapore 9128

Great Book!

Dave
From: dseal@armltd.co.uk (David Seal)
Newsgroups: comp.theory.cell-automata
Subject: Re: What is Garden of Eden?
Date: 6 Nov 92 10:37:18 GMT
Distribution: comp
Organization: A.R.M. Ltd, Swaffham Bulbeck, Cambs, UK

In article <1992Nov5.083342.23825@usage.csd.unsw.OZ.AU>
brianm@plod.cbme.unzw.oz.au (Brian Murray) writes:

>What is this "Winning Ways" book to which you refer? Does it contain
>much more life stuff?

"Winning Ways", by Berlekamp, Conway and Guy - sorry, don't have my copy
handy, so can't give publisher details or ISBN numbers. It's in 2 volumes,
and is a standard reference for mathematical games and puzzles.

Volume 2 contains a reasonably large chapter about Life, which in particular
includes a sketch of how a universal computer can be assembled out of glider
guns, eaters, etc. This computer can be programmed to completely
self-destruct: a consequence of this is that no algorithm can exist which
determines whether an arbitrary Life configuration will ultimately die out
completely. (If there were such an algorithm, it could be presented with the
Life universal computer, programmed to run a given program and to
self-destruct when the program halts. This Life configuration would die out
completely if and only if the given program halts: thus an algorithm to
solve the "Life dying out" problem could be used to solve the halting
problem. Since the halting problem is provably insoluble, such an algorithm
cannot exist.)

David Seal
dseal@armltd.co.uk

All opinions are mine only...
Newsgroups: comp.theory.cell-automata
From: hurd@math.gatech.EDU (Lyman Hurd)
Subject: subshifts of finite type.
Organization: The Internet
Distribution: inet
Date: Thu, 12 Nov 1992 01:53:14 GMT

Funny, a friend, Mike Boyle, has been trying to convince me to generalize
from cellular automata to SFT's!  Basically the general consensus if that
subshifts of finite type are horizontal and cellular automata vertical.

What I mean by that is that is that a cellular automaton is a map commuting
with the shift, whereas a subshift of finite type is defined as a shift
map.

A sofic system by definition is the image of a subshift of finite type
under a cellular automaton map.  All sofic systems arise this way, although
not all arise as images of the full shift.

Some SFT's do arise in CA dynamics.  In many such cases the cellular
automaton stabilizes:

F^n(X) = F^m(X) as sets for all n,m>N.

I was able to show (it is not hard) that if the limit set (the intersection
of forward images) is a subshift of finite type, the rule must stabilize in
this manner.  I conjectured that the converse was true---that whenever a
rule stabilized it must do so as a subshift of finite type.  Boyle and I
later showed this conjecture is false.  The subject of stable limit sets
appears to be deep.

The motivation for studying subshifts of finite type belongs to the ergodic
theorists and I have forwarded your inquiry in the hopes of getting that
persepctive.


Lyman Hurd
Iterated Systems, Inc.
From: MSW@MPLVAX.SRI.COM (Mark S. Williams - Ag213)
Newsgroups: comp.theory.cell-automata
Subject: new (to me) cooperative cell-automata
Date: 12 Nov 92 03:09:22 GMT
Organization: Molecular Physics Laboratory, SRI International, Menlo Park, CA


Hi,

Does anyone know anything more about the cooperative type
cellular-automata discussed in the October 29 issue of NATURE?
Has anyone experimented with them?

Thanks,
Mark Williams
msw@mplvax.sri.com

Newsgroups: comp.theory.cell-automata
From: levine@symcom.math.uiuc.edu (Lenore Levine)
Subject: Gacs Rule -- Summary of Related Papers
Organization: University of Illinois at Urbana
Date: Tue, 10 Nov 1992 21:43:32 GMT


The first paper on the Gacs rule was published in Problems of
Transmission of Information, in 1978. The Russian journal has been
translated into English. There are two co-authors, Kurdyumov and Levin.

Here are two or three later papers that are probably related:

1983       STOC         Gacs, Reliable Computation with Cellular Automata
1986   32  JCSS         Gacs, Reliable Computation with Cellular Automata
1989    5  ADVCR        Gacs, Self-Correcting Two-Dimensional Arrays
1985       STOC         Gacs & Reif, A Simple Three-Dimensional Real-Time Reliable Cellular Array
1988   36  JCSS         Gacs & Reif, A Simple Three-Dimensional Real-Time Reliable Cellular Array

 One piece of further work is this:
 @ARTICLE{DeSaMaes92
  ,AUTHOR = {de S\'a, Paula Gonzaga and Maes, Christian}
  ,TITLE  = "The {G}\'acs-{K}urdyumov-{L}evin {A}utomaton Revisited"
  ,JOURNAL = "Journal of Statistical Physics"
  ,VOLUME = 67
  ,NUMBER = {3/4}
  ,PAGES = "607-622"
  ,YEAR = 1992
  ,Month = May

Some related papers:

This is Gray's proof of ergodicity for continuous-time monotonic
nearest-neighbor rules.

 @ARTICLE{Gray82
  ,AUTHOR = {Gray, Lawrence F.}
  ,TITLE  = {The Positive Rates Problem for Attractive Nearest
Neighbor Spin Systems on {\bf Z}}
  ,JOURNAL = {Z.\ Wahrscheinlichkeitstheorie verw.\ Gebiete}
  ,VOLUME = 61
  ,PAGES = {389-404}
  ,YEAR = 1982
 }

This is Gray's proof for discrete time.

 @inproceedings{Gray87
   ,author = "Gray, Lawrence F."
   ,title = "The Behavior of Processes with Statistical Mechanical Properties"
   ,booktitle = "Percolation Theory and Ergodic Theory of Infinite
Particle Systems"
   ,year = "1987"
   ,pages = "131--167"
   ,publisher= {Springer-Verlag}
   }

 This is a relatively simple proof of Toom's rule.

@inproceedings{BermSim88,
   author = "Berman, Piotr and Simon, Janos",
   title = "Investigations of Fault-Tolerant Networks of Computers",
   booktitle = "Proc. of the 20-th Annual ACM Symp. on the Theory of
Computing",
   year = "1988",
   pages = "66 -- 77"
   }

  This is my Gacs' 1 dimensional construction.

 @ARTICLE{g1dim86
  ,AUTHOR = {G\'acs, Peter}
  ,TITLE  = {Reliable computation with cellular automata}
  ,JOURNAL = {Journal of Computer System Science}
  ,VOLUME = 32
  ,NUMBER = {1}
  ,MONTH = {February}
  ,PAGES = {15-78}
  ,YEAR = 1986
 }

 This is a 2-dimensional construction which may help understanding the
difficult 1-dimensional paper and has a little more general
discussion.

 @INCOLLECTION{g2dim89
 ,AUTHOR = {G\'acs, Peter}
 ,TITLE = {Self-correcting Two-dimensional Arrays}
 ,BOOKTITLE= {Randomness in Computation}
 ,SERIES = {Advances in Computing Research (a scientific annual)}
 ,VOLUME = 5
 ,EDITOR = {Silvio Micali}
 ,PUBLISHER = {JAI Press}
 ,ADDRESS = {Greenwich, Conn.}
 ,YEAR = {1989}
 ,PAGES = {223-326}
 }