HDTenEightyP/NetNews huggingface dataset:
From: rucker@sjsumcs.SJSU.EDU (Rudy Rucker)
Subject: evolving cas
Organization: The Internet
Distribution: inet
Date: Fri, 1 Jan 1993 21:45:34 GMT


The idea of evolving CA rules is an interesting one --- it would not
be too hard to create a "Blind Watchmaker" style program where the
user clicks on one of, say, 6 small CA patches to choose to see 6
mutations of that one, etc.  Automated evolution would also be
reasonable, one might choose a certain entropy level as the fitness
target.  Charles Bennett showed me a rule for the Margolus and Toffoli
CAM6 which lets the user flip between two active CAs and choose one,
then see two mutants of that one, etc.  I don't know of any other
existing program that does this kind of thing.  There was a paper by
Norman Packard, I believe, in which he did an automatic evolution of
a 1D CA towards some goal --- the reference has appeared on this
newsgroup before.  If I get time, I'll try and put an evolving CA
feature into the "Bugland" program which I am now developing for
distribution next fall.

Newsgroups: comp.theory.cell-automata
From: MCINTOSH@unamvm1.dgsca.unam.mx ("Harold V. McIntosh")
Subject: 3-d ZB's.
X-Unparsable-Date: Fri, 01 Jan 93 23: 27:01 MEX
Organization: The Internet
Distribution: inet
Date: Sat, 2 Jan 1993 05:29:23 GMT

Rudy Ruckler comments:
>
> There is a lovely photo of a 3D Belusov-Zhabotinsky type CA (scrolls)
> on p. 111 of the coffee-table paperback FRACTALS THE PATTERNS OF CHAOS
> by John Briggs (Simon & Schuster Touchstone Books 1992).  The image
> ...
>
By pure chance a copy of the June, 1974 issue of Scientific American is
sitting here beside the machine; the cover picture is entitled 'Rotating
Chemical Reactions,' illustrating Arthur T. Winfree's article on pages
82-95. Among other things he discusses the forms that the famous spirals
might take in three dimensions.
-
Picturing any kind of 3-d automata on PC-level equipment is something of
a challenge, but there must be some interesting rewards for those who manage
to do so; this is evidently one of them.
-
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
Newsgroups: comp.theory.cell-automata
From: ninassup@athena.mit.edu (Nikos I Nassuphis)
Subject: WireWorld
Organization: Massachusetts Institute of Technology
Date: Sun, 3 Jan 1993 03:29:03 GMT

I just finished implementation of WireWorld, and I wonder
if there are any interesting circuits out there that I
could try it on...

Thanx
NN
ninassup@athena.mit.edu

Newsgroups: comp.theory.cell-automata
From: rucker@sjsumcs.SJSU.EDU (Rudy Rucker)
Subject: 3D BZ
Organization: The Internet
Distribution: inet
Date: Fri, 1 Jan 1993 21:50:39 GMT


There is a lovely photo of a 3D Belusov-Zhabotinsky type CA (scrolls)
on p. 111 of the coffee-table paperback FRACTALS THE PATTERNS OF CHAOS
by John Briggs (Simon & Schuster Touchstone Books 1992).  The image
is by Mario Markus, a physicist at the Max Planck Institute in Dortmund,
Germany.  This is the first such picture I've ever seen, and I'd love
to see more.  I've written Mario Markus but haven't heard back yet.
Does anyone know anything more about this picture or about other pictures
of 3D CAs?
From: wjs@doc.ic.ac.uk (Bill Sharp)
Newsgroups: comp.theory.cell-automata
Subject: Life: Garden of Eden
Date: 30 Dec 1992 17:59:37 -0000
Organization: Imperial College, London
Distribution: world
NNTP-Posting-Host: oak22.doc.ic.ac.uk
Keywords: life

As far as I can find, there are only two currently known 'garden of eden' 
states in life, which have no predecessor. I already have one of these, but
would be gratefull if anyone can give me pointers towards the other one and 
any new ones about.

Thanks

Bill
-- 
     _\|/_          
    /.\ /.\	He said that there was death and taxes, and taxes was worse,
    \_/v\_/        because at least death didn't happen to you every year
      \-/                                                
Newsgroups: comp.theory.cell-automata
From: twallace@gmuvax2.gmu.edu (Todd Wallace)
Subject: Re: Autodesk CA
Keywords: evolve, evolution
Organization: George Mason University, Fairfax, Va.
Date: Wed, 30 Dec 1992 17:03:14 GMT

I am looking for information on cellulary automata which use a
simulation of genetic material -- I want cellular automata which can
evolve abilities not anticipated by the programmer.

Any help/hints greatly appreciated.
From: heitkoet@lusty.informatik.uni-dortmund.de (Joerg Heitkoetter)
Newsgroups: comp.theory.cell-automata
Subject: Re: 3D BZ
Date: 2 Jan 93 14:37:49 GMT
Distribution: inet
Organization: CS Department, Dortmund University, Germany
NNTP-Posting-Host: lusty.informatik.uni-dortmund.de

In article <199301012150.AA20881@sjsumcs.SJSU.EDU>, rucker@sjsumcs.SJSU.EDU
(Rudy Rucker) writes:
|> 
|> There is a lovely photo of a 3D Belusov-Zhabotinsky type CA (scrolls)
|> on p. 111 of the coffee-table paperback FRACTALS THE PATTERNS OF CHAOS
|> by John Briggs (Simon & Schuster Touchstone Books 1992).  The image
|> is by Mario Markus, a physicist at the Max Planck Institute in
|> Dortmund,
|> Germany.
Well that's my old working group, the biomathematics research group ;-)

It seems that every book on chaos, etc. gets a picture of our little
institute: eg. the German version of Paul Davis' book also carries a 3D
picture of the BZ reaction, but of a different numerical model.

|>  This is the first such picture I've ever seen, and I'd love
|> to see more.  I've written Mario Markus but haven't heard back yet.
Try to reach him by email: markus@mpi-dortmund.mpg.dbp.de should should
work...if you do not succeed he might be visiting his hometown:
Santiago de Chile (he is Chilean).

The Institut has neither a News feed, nor a properly set up finger(1)
service, unfortunately.

|> Does anyone know anything more about this picture or about other pictures
|> of 3D CAs?
One of the first was introduced by A.K. Dewdney in Scientific American,
by Charter Bayon a 3D version of life(1)...he also wrote an article on
this in Complex Systems, as far as I remember.

In article MCINTOSH@unamvm1.dgsca.unam.mx ("Harold V. McIntosh") writes:
|> Picturing any kind of 3-d automata on PC-level equipment is something of
|> a challenge, but there must be some interesting rewards for those who manage
|> to do so; this is evidently one of them.
As stated above: this will not be the picture of a cellular-automaton, but
of a numerical model. The original program of Charter Bay ran and displayed
it's
state on a Macintosh.

Mario's picture was probably computed using the MPI's compute server:
a CONVEX 20xx Supermini...

	-joke

--
Joerg Heitkoetter
Systems Analysis Group
University of Dortmund, Germany
(joke@ls11.informatik.uni-dortmund.de).
Newsgroups: comp.theory.cell-automata
From: MCINTOSH@unamvm1.dgsca.unam.mx ("Harold V. McIntosh")
Subject: WireWorld circuitry.
X-Unparsable-Date: Sun, 03 Jan 93 22: 42:55 MEX
Organization: The Internet
Distribution: inet
Date: Mon, 4 Jan 1993 04:46:11 GMT

Nikos I Nassuphis <ninassup(at)ATHENA.MIT.EDU> inquires:
-
> I just finished implementation of WireWorld, and I wonder
> if there are any interesting circuits out there that I
> could try it on...
-
If anyone recalls Peter Rony's BugBooks from early microcomputer days,
they are full of simple circuitry. A word of warning: IC's are based on
NAND gates, whereas WireWorld seems to work better with NOR gates. So you
get to reinvent the wheel (microcircuitry) all over again.
-
The closest Wireworld comes to boolean constants are pulse trains, so the
place to begin is first with clocks, then with the traditional boolean
functions, finally create delays, and crossovers. From then on, it is just
one huge construction project.
-
Some simple, but cute circuits:
-
1) an electron mirror - sends a single pulse back where it came from.
2) single pulser - only lets the first pulse of a train get through.
3) pulse doubler - emits two pulses for each arrival.
4) train trigger - emits continuous pulses once triggered.
-
After that, there is the whole family of flip-flops (D, J, K, ...), binary
counters, incrementers, adders, ... (even your own Intel 8080).
-
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: roeland@wins.uia.ac.be.uia.ac.be (Tom Roelandts)
Newsgroups: comp.theory.cell-automata
Subject: xlife
Date: 24 Dec 92 12:47:19 GMT
Organization: U.I.A.
X-Newsreader: Tin 1.1 PL5

Hi there,

I would very much like to use the program xlife. The problem is however that I
cannot get it compiled.  The Makefile seems to give an incorrect option to the
C-compiler.  Removing this option doesn't help, the compiler can't find all
of its header-files either.  I am working on a Sun-OS computer, not exactly an
obscure little-heard of system.

I hope somebody can help me with this problem.

Tom.
Newsgroups: comp.theory.cell-automata
From: 100020.2727@CompuServe.COM (Andrew Wuensche)
Subject: evolving CAs
Organization: The Internet
Distribution: inet
Date: Sat, 2 Jan 1993 12:23:39 GMT

Evolving CAs
------------
A program for mutating and evolving 1-d, 5 neighbour CA rules is part
of the software included with my book "The Global Dynamics of Cellular
Automata"*.
  As the CA's space-time pattern generates, a key press will flip one
bit at a random position in the 32 bit rule table (another key flips
back if the result does not look promising, other keys reset the
CA's state).
  Using this method of random mutation and artificial selection
without stopping the CA, I have evolved many examples of "complex
rules" (with interacting gliders,  glider guns etc) supposed to be rare
in rule space. 

* "THE GLOBAL DYNAMICS OF CELLULAR AUTOMATA, An Atlas of Basin of
Attraction Fields of One-Dimensional Cellular Automata"
Andrew Wuensche and Mike Lesser, (PC diskette included)
foreword by Christopher Langton.
Santa Fe Institute Studies in the Sciences of Complexity, Reference Vol
1, Addison-Wesley, Reading MA, phone:(800) 447 2226, IBSN 0-201-55740-1
1992  Hardcover, 250 pages, $53.75

  Andrew Wuensche                 contact address:
  Santa Fe Institute and          48 Esmond Road, London W4 1JQ
  University of Sussex            tel 081 995 8893, fax 081 742 2178
  wuensch@santafe.edu             email 100020.2727@compuserve.com
From: pollansw@cse.fau.edu (Warren Pollans)
Newsgroups: comp.theory
Subject: POPL airfares
Date: 22 Dec 92 23:30:36 GMT
Organization: Florida Atlantic University, Boca Raton, FL, USA

USAir has a set of special rates for POPL attendees.  When making
reservations you should ask for the GOld File number for our
conference.  I am on vacation, using a friends login, and don't
have the number, but the reservationist should be able to look it
up.

One warning - if you are staying over a Saturday night you will do
better with regular rates.

Dee Medley
dmedley@admin.ac.edu
Newsgroups: comp.theory
From: hossain@sol.cs.wmich.edu (Moazzem)
Subject: Approximation Algorithms
Organization: Western Michigan Univ. Comp. Sci. Dept.
Date: Tue, 22 Dec 1992 19:15:34 GMT

I am interested in finding references on approximation algorithms for 
NP-complete graph-theory problems, set theory problems, number theory problems etc.

If you have written any paper on approximation algorithms in any area or you 
know of any reference, please mail me the references.

I will post the summary of all the references on this group. 

Thank you.

Moazzem
e-mail: hossain@cs.wmich.edu
From: markh@csd4.csd.uwm.edu (Mark)
Newsgroups: comp.theory
Subject: Re: Real Numbers vs. Rational Numbers?
Date: 26 Dec 1992 18:31:27 GMT
Organization: Computing Services Division, University of Wisconsin - Milwaukee
Distribution: inet
NNTP-Posting-Host: 129.89.7.4

In article <1992Dec17.142150.7932@tom.rz.uni-passau.de> boerncke@kirk.fmi.uni-passau.de (Frank-Roland Boernke) writes:
>How is it possible to work with irrationals in a table? Of course you cannot store
>them digit by digit as there is an infinite number. But if you choose a finite 
>representation e.g. two letters P and I for the sequence 3.141592654... how can 
>you calculate say PI * PI? 

Calculate PI * PI.
Answer: PI*PI.

Since "PI*PI" is a finite representation of PI * PI from which one can
algorithmically computer any of its digits in finite time, this counts as a
valid answer.

If you don't consider this valid, then neither will you consider this valid:

Calculate: 2 / 5
Answer: 2/5.

So then on that account, computers can't even work with fractions.
Newsgroups: comp.theory
From: pgupta@femto.cs.umn.edu (Prosenjit Gupta)
Subject: generating function of CFL
Organization: University of Minnesota
Date: Sun, 27 Dec 1992 23:41:24 GMT

Keywords: 

Hi!
A friend of mine wants a pointer to the proof of the
following theorem :

" The Generating Function of an unambiguous context-
free language is an algebraic function"
The theorem is due to Chomsky and Schutzenberger.

thanks

prosenjit

pgupta@cs.umn.edu
From: shiva@mpii01042.NoSubdomain.NoDomain (Shiva Chaudhuri)
Newsgroups: comp.theory
Subject: Sorting/Routing on hypercubes
Keywords: sorting, routing, hypercube, butterfly
Date: 27 Dec 92 16:41:12 GMT
Organization: Max-Planck-Institut fur Informatik


I am looking for  references to recent work on sorting and routing on 
bounded and fixed degree networks like the hypercube and the butterfly.
If anyone has a survey, or pointers to recent work,  I would
appreciate a copy.

Thanks,
Shiva Chaudhuri.
shiva@mpi-sb.mpg.de
From: nodine@lcs.mit.edu (Mark H. Nodine)
Newsgroups: comp.theory
Subject: Re: Sorting/Routing on hypercubes
Keywords: sorting, routing, hypercube, butterfly
Date: 28 Dec 92 19:04:07 GMT
Organization: MIT Laboratory for Computer Science

Your best bet is "Introduction to Parallel Algorithms
and Architectures" by Tom Leighton (Morgan Kaufmann).

	--Mark
From: jmr@cs.anu.edu.au (Mike Robson)
Newsgroups: comp.theory
Subject: Swart and Gismondi Graph Isomorphism algorithm
Date: 31 Dec 1992 08:46:05 +1100
Organization: Computer Science Department, ANU, Australia
Distribution: inet
NNTP-Posting-Host: nunki.anu.edu.au
Keywords: Maybe its right

With their new version of the discredited main theorem, I currently
believe that their algorithm can be proved correct. I'll post details
when I've thought them out a bit more and when I have time.
Newsgroups: comp.theory
From: kamin@cs.uiuc.edu (Sam Kamin)
Subject: Info. about upcoming POPL
Organization: University of Illinois, Dept of Computer Science
Date: Mon, 21 Dec 1992 14:20:30 GMT

Two messages about the upcoming POPL:

You can get the POPL'93 program in postscript by ftp from    nuri.inria.fr
           ftp  nuri.inria.fr
           login: anonymous
           pass: your e-mail address
           cd   INRIA/publication/ChLoE
           binary
           get  POPL-prog93.ps.Z


You will get a compressed file, which you can uncompress with:
   zcat POPL-prog93.ps.Z > POPL-prog93.ps

If you have any problem, or for other POPL information, send e-mail to
Bernard.Lang@inria.fr
===============================

Dee Medley, local arrangements chair for POPL, asked me to post this
information:  You can get cheaper rates on USAir flights to Charleston
if you mention ACM-POPL when you get your tickets.

(I don't have any more details than that - like how much you'll
save, or what to do if you've already bought tickets -  so all I can
say is to give it a try.  You can contact Dee at dmedley@uscn.uga.edu.)

- Sam Kamin


Newsgroups: comp.theory
From: rpatil@nmsu.edu (Raj Patil)
Subject: Computatibility and Chaos
Organization: Computing Research Lab
Date: Fri, 1 Jan 1993 09:44:23 GMT


Does anyone know of any work done in the area of Chaos and Cumputability.
My basic question is: Is Chaos more powerful then Turing Machine. Now here 
i am assuming that the real Chaos (infinite precision) is not computed
using a TM.

Regards

Raj Patil
Newsgroups: comp.theory
From: ejxue@ntuix.ntu.ac.sg (Xue JingLing)
Subject: Linear and Integer Programming Software
Organization: Nanyang Technological University Singapore
Date: Mon, 28 Dec 1992 04:53:20 GMT

Dear All,

I am looking for a linear and integer programming software package.
Could anyone email me any site where I can ftp such a package, for
free?

Thanks in advance.

Jingling Xue                       <e-mail>  ejxue@ntuix.ntu.ac.sg
School of EEE                                   home: +65 791 4284
Nanyang Technological Univ.        <telephone>
Singapore 2263                                  office: +65 799 1236
-- 
Dr Jingling Xue                       <e-mail>  ejxue@ntuix.ntu.ac.sg
School of EEE                                   home: +65 791 4284
Nanyang Technological Univ.        <telephone>
Singapore 2263                                  office: +65 799 1236
Newsgroups: comp.theory
From: boerncke@kirk.fmi.uni-passau.de (Frank-Roland Boernke)
Subject: Re: Real Numbers vs. Rational Numbers?
Organization: University of Passau, Germany
Date: Mon, 21 Dec 1992 10:35:27 GMT

In article <7111@tivoli.UUCP>, taylor@foraker.NoSubdomain.NoDomain (Eric Taylor) writes:
|> In article <1992Dec16.095412.19570@tom.rz.uni-passau.de>, boerncke@kirk.fmi.uni-passau.de (Frank-Roland Boernke) writes:
|> |> In lectures we talked about the RAM, a formal machine-model that is proved
|> |> to be as powerful as turing-machines(TM) and vice versa, according to the
|> |> Church-Turing-Thesis. This seems to be ok until you say, that the RAM allows
|> |> only natural numbers in its registers (or rational-numbers, since they are 
|> |> countable). Our professor told us, that RAMs are allowed to store REAL numbers
|> |> too AND they are  still as powerful as an ordinary turing machine. I claimed, this
|> |> can`t be true, since there isn`t any possibility to work with irrational 
|> |> numbers in TMs. 
|> 
|> REAL numbers are always RATIONAL numbers and vice-versa.

I dont't agree.

|> 
|> Any rational number can be represented by the division
|> of 2 integers ...

This is the point: There are REAL number (the irrational ones) that cannot
be represented by the division of 2 integers (e.g. PI or e).



-------------------------------------------------------------------------
Frank Boerncke                       ,,,   University of Passau - Germany
boerncke@kirk.fmi.uni-passau.de     (.~.)            phone: +49 0851 2267
--------------------------------oOO--(_)--OOo---------------------------
From: aet@mullian.ee.mu.OZ.AU (bert thompson)
Subject: Re: Real Numbers vs. Rational Numbers?
Organization: Computer Science, University of Melbourne, Australia
Distribution: inet
Date: Sat, 2 Jan 1993 03:30:25 GMT

markh@csd4.csd.uwm.edu (Mark) writes:

>In article <1992Dec17.142150.7932@tom.rz.uni-passau.de> boerncke@kirk.fmi.uni-passau.de (Frank-Roland Boernke) writes:
>>How is it possible to work with irrationals in a table? Of course you cannot store
>>them digit by digit as there is an infinite number. But if you choose a finite 
>>representation e.g. two letters P and I for the sequence 3.141592654... how can 
>>you calculate say PI * PI? 

>Calculate PI * PI.
>Answer: PI*PI.

>Since "PI*PI" is a finite representation of PI * PI from which one can
>algorithmically computer any of its digits in finite time, this counts as a
>valid answer.

>If you don't consider this valid, then neither will you consider this valid:

>Calculate: 2 / 5
>Answer: 2/5.

>So then on that account, computers can't even work with fractions.

In case you are interested in exact real arithmetic...

Hans Boehm has written a simple calculator that performs arithmetic on
constructive real numbers. 

his calculator is called C_calc.

you can look it up on archie, or i can tell you where to get it. 

	bert.

---------------------------------------------------------------------------
bert thompson	aet@munagin.ee.mu.oz.au.
SITEE		school of information technology and electrical engineering
		university of melbourne
---------------------------------------------------------------------------
     g e t  t h e  p o i n t 
---------------------------------------------------------------------------
Newsgroups: comp.theory
From: djimenez@ringer.cs.utsa.edu (Daniel Jimenez)
Subject: Re: Real Numbers vs. Rational Numbers?
Organization: University of Texas at San Antonio
Date: Thu, 24 Dec 1992 09:46:57 GMT

In article <1277@zogwarg.etl.army.mil> hoey@zogwarg.etl.army.mil (Dan Hoey) writes:
>One interesting complexity non-result is the open question:
>
>    Is the travelling salesman problem with cities on an integer
>    lattice in NP?
>
>The numbers are non only real, but algebraic.  Not only algebraic, but
>constructible!

Hmm.  I think you mean P, not NP (obviously it's in NP).  Anyway, it seems
like this problem is NP-complete, since you could use it to get 
arbitrarily close approximations to the "real" (pun intended) TSP.
-- 
Daniel Jimenez                     djimenez@ringer.cs.utsa.edu
"I've so much music in my head" -- Maurice Ravel, shortly before his death.
"                             " -- John Cage
Newsgroups: comp.theory
From: cyli@cs.cuhk.hk (LI Chung-Yuen)
Subject: Re: Are type 0 languages recursive?
Organization: Faculty of Engineering, The Chinese U. of Hong Kong
Date: Tue, 22 Dec 1992 13:34:24 GMT

lombardo@ghost.dsi.unimi.it (franco lombardo) writes:
>Are type 0 languages recursive? If the answer is yes, where can I find
>a prove of it? Otherwise, can you show an example of  a type 0 
>language which is not recursive?
>Are type 0 languages "recursivly numerable"?

Type 0 languages are, by definition, recursively enumerable.
The universal language (Introduction to Automata Theory, Languages and
Computation, Hopcroft & Ullman, p.183) is recursively enumerable but not
recursive.
The set of recursive languages is a proper subset of the set of
recursive renumerable languages.

--
Li Chung Yuen    cyli@cs.cuhk.hk    (852)609-7734
Room 121 Lady Shaw Building The Chinese University of Hong Kong HONG KONG
Organization: University of Haifa - Mt. Carmel Haifa, Israel.
Date: Thursday, 31 Dec 1992 15:02:53 IST
From: Dan Gordon <RSMA410@HAIFAUVM.BITNET>
Newsgroups: comp.theory
Subject: Re: Automata & Chomsky Hierarchy
 <92357.182747RSMA410@HAIFAUVM.BITNET> <1992Dec30.084134.833@news.unige.ch>

In article <1992Dec30.084134.833@news.unige.ch>, swann@divsun.unige.ch (SWANN
philip) says:
>
>In article <92357.182747RSMA410@HAIFAUVM.BITNET>, Dan Gordon
><RSMA410@HAIFAUVM.BITNET> writes:
>> In article <1992Dec15.162545.25338@news.unige.ch>, swann@divsun.unige.ch
>(SWANN
>> Philip) says:
>
>>>>PREVIOUS EXCHANGES DELETED<<<<

>Sorry, my question was vague. I've now found the original
>reference.... The classification is of the limiting behavior of
>*one-dimensional* automata as:

>>>>material deleted<<<<

I forgot to mention that my proof of Wolfram's conjecture also
deals with *one-dimensional* cellular automata.  The original
definition of totalistic cellular automata, and the conjecture,
are due to Wolfram.

Dan Gordon.