HDTenEightyP/NetNews huggingface dataset:
From: slh@naucse.cse.nau.edu (Steven Harvey)
Newsgroups: comp.theory.cell-automata
Subject: ANTS prog
Date: 17 Nov 92 14:31:39 GMT
Organization: Northern Arizona University, Flagstaff AZ

I am looking for a IBM program called [I think]
ANTS 21.   It was written by a class on alife under
the direction of Rudy Rucker & consists of 2-D
Turing machines evolving & competing for food etc.
I lost it some months ago in a disk crash &
can't remember where I got it in the first place.
I would appreciate a pointer to a ftp site where I can find it.
THANX!

-- 
STEVEN L HARVEY			slh@naucse.cse.nau.edu
GO REDS!   TAKE STATE!!
Newsgroups: comp.theory.cell-automata
From: hurd@math.gatech.EDU (Lyman Hurd)
Newsgroups: comp.theory.cell-automata
Subject: Undecidability of configurations/progression
Date: 21 Nov 92 17:08:51 GMT
Distribution: inet
Organization: The Internet

>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.

Whoaaa.  This is certainly NOT true.  There are two different properties of
a CA:

1) The CA is surjective, i.e., for all configurations y there exists (at
least one) configuration x such that F(x)=y.  A CA is surjective (or
``onto'') if and only if it has no GOE's.

2) The CA is injective, i.e., for all configurations x not = y, F(x) not =
F(y). 

For a general set map there exists a third condition:

3) A map is bijective if 1) and 2) hold.  In this case there exists an
inverse map.

For CA, however, 2 implies 3.  Also if a CA has a set-theoretic inverse,
that inverse is also a CA.  Reference Hedlund.

It is NOT the case that 1 implies 2.  Take the 1-d rule Wolfram's
elementary rule 90 with 2 states per site and each site in the next
generation takes the values of the mod 2 sum of its neighbors (but not its
predecessor).

In one dimension lots of proofs have been given of the fact that
injectivity (=bijectivity) and surjectivity are decidable.

In his thesis, however, Kari showed that BOTH questions are undecidable for
a general 2-D CA.  The proof is highly non-trivial and required
strengthening Berger's Theorem on the undecidability of plane tilings

Lyman Hurd
Iterated Systems, Inc.
Newsgroups: comp.theory.cell-automata
From: IQTI400@INDYCMS.IUPUI.EDU (macphil)
Subject: Artificial Life and Genetic Algorithms
Organization: IUPUI
Date: Fri, 20 Nov 92 18:07:40 EST

Wanted: other parties interested in artificial life and genetic
algorithms.
 
Could you get in touch (directly) ?  Thanks!
 
 
 
 
Newsgroups: comp.theory.cell-automata
From: mbutts@mbutts.mentorg.com (Mike Butts)
Subject: Re: Symmetric Life rules
Date: Mon, 23 Nov 1992 23:18:56 GMT
Organization: mentor
Keywords: cam
Followup-To: 

(mailing to you bounced)

I'd like to hear more about your hardware!  How are you managing the memory?
Will you bounce between two memories, or is there a cleverer way?  Will you
be displaying in real time?  Do you know of any papers or other references
to CA hardware, such as the CAMs I've heard of?   I have access to 
programmable hardware and it's a good opportunity to work with hardware life
machines.  Thanks and good luck!

-- 
Mike Butts     KC7IT     Research Engineering Manager     mbutts@qcktrn.com
Quickturn Systems, Inc., Mentor Graphics Campus,        voice: 503-685-1302
8005 SW Boeckman Road, Wilsonville, Oregon 97070-7777     fax: 503-685-7987
My opinions are my own, and aren't necessarily shared by Quickturn Systems.
Newsgroups: comp.theory.cell-automata
From: eeklund@nyx.cs.du.edu (Eivind Eklund)
Subject: Re: Symmetric Life rules
X-Disclaimer: Nyx is a public access Unix system run by the University
	of Denver for the Denver community.  The University has neither
	control over nor responsibility for the opinions of users.
Organization: Nyx, Public Access Unix at U. of Denver Math/CS dept.
Date: Wed, 18 Nov 92 19:17:44 GMT

In article <1992Nov17.122445.14209@odin.diku.dk> torbenm@diku.dk (Torben AEgidius Mogensen) writes:
[...]
>I have found such a set of rules and carried out some experiments with
>these. The rules are also interesting in that the central cell in the
>3x3 neighbourhood counts the same as the other cells.

Well, that is just another way of writing rules.  Conrad's Gam of Life can
be written like this:

 0 .
 1 .
 2 .
 3 O
 4 O (If set)
 5 .
 6 .
 7 .
 8 .
 9 .

And this is also nice for doing FAST implementations - see if you can find
out how... (This might be common knowledge allready, but I have a hack
which 
I believe to be VERY fast - somebody tell me how many cells/second they
are able to do on what kinds of computers 8-)
I am able to do approx 1.3 million cells/second on a 1 MIPS Amiga.
(7.14 Mhz 68000)

Eivind Eklund AKA Vishnu CRB
eeklund@nyx.cs.du.edu or phone +47-(0)-9-944946 (BBS, shout to get ME)

Newsgroups: comp.theory.cell-automata
From: rif@athena.mit.edu (rif)
Subject: Public Domain CA packages for the CM-2
Organization: Massachusetts Institute of Technology
Date: Mon, 23 Nov 1992 13:05:23 GMT

Is anyone aware of any public domain CA simulation packages that
run on the CM2?  ftp sites would be appreciated.

Thanks in advance.

rif
From: cy0q+@andrew.cmu.edu (Chad O. Yoshikawa)
Newsgroups: comp.theory.cell-automata
Subject: DFA/NFA verification
Date: 21 Nov 92 22:45:53 GMT
Article-I.D.: andrew.8f3oX1G00WBOI0YVIm
Organization: Junior, Electrical and Computer Engineering, Carnegie Mellon, Pittsburgh, PA

...
Does anyone have a program (for Mac, Unix (DEC,sun) or even 
SGI, any other platform) that will do DFA/NFA/regular expression
verification, transforms, etc?  

Thanks in advance,

Chad
From: csg068@cch.coventry.ac.uk (** DECKER **)
Subject: Re: ANTS prog
Organization: Coventry University
Date: Wed, 18 Nov 1992 12:41:52 GMT

In article <5876@naucse.cse.nau.edu> slh@naucse.cse.nau.edu (Steven Harvey) writes:
>I am looking for a IBM program called [I think]
>ANTS 21.   It was written by a class on alife under

Apologies for the "me too" nature of this posting, but I would like this
information too. Thanks.

-- 
 =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
 : DECKER : csg068@uk.ac.coventry.cch : Dept. of Computer Science, Cov Uni  :  
 : "Butter is the devil's vomit" (Issued by the Margarine Marketing Board)  :
 =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
From: 100010.2243@CompuServe.COM (Joe Pritchard)
Newsgroups: comp.theory.cell-automata
Subject: BBS
Date: 18 Nov 92 22:03:04 GMT
Distribution: inet
Organization: The Internet

My BBS on Chaos and CA is available on the follwing UK phone number:

		0742 325872

Protocol is 2400 baud, 8 bit, 1 stop, no parity.  It's available 0730
to 2300 hrs GMT.  Sorry about the delay; did post a message up last
week but it appears to have got lost.

I'll try and post a file list as well, and am investigating putting the
files into an FTP site if I can find one willing.

Cheers
Joe
Newsgroups: comp.theory.cell-automata
From: hiebeler@santafe.EDU
Subject: Re:  Missed posts of parts of Spaceships in Conway's Life
Organization: The Internet
Distribution: inet
Date: Sun, 15 Nov 1992 21:40:20 GMT

  I would simply tell you to FTP those messages from the archive
of the CA newsgroup/mailing-list, but unfortunately the archives
had some problems and got erased a few times.  Last week I was just
starting to have them restored from tape though, so if you wait a
few days, those articles will hopefully be available for FTP.  I'll
send out a note when it happens.

--
Dave Hiebeler
Thinking Machines Corporation, and Santa Fe Institute
hiebeler@think.com, hiebeler@santafe.edu
From: rseymour@reed.edu (Robert Seymour)
Newsgroups: comp.theory.cell-automata
Subject: Re: popularizations ofcomplexity.
Date: 16 Nov 92 07:59:37 GMT
Article-I.D.: reed.1992Nov16.075937.19475
Reply-To: rseymour@reed.edu
Organization: Reed College, Portland, OR

In article <BxJo6I.43s@news.cso.uiuc.edu> gaylord@ux1.cso.uiuc.edu (Richard J.  
Gaylord) writes:
> 
> recent popularizations on the subject of complexity, a-life, ca's.
> 
> "Complexity" by Roger Lewin
> 
> "Complexity" by Waldrop
> 
> "Artifical Life" by Levy.
> 
> i hope the guys at Santa Fe must keep their machines running while they
> give out all these interviews. well, i guess it pays to  advertise.
> 
> btw - levy's book is okay, waldrop's book is absolutely awful and lewin's
> book has  pictures of the guys, discusssions of who did what first, and 
> 60's style pseudo-scientific/philosophical babble. 
> basically, they all just discuss the people and not the subject  (which
> is probably too 'complex'  for them to understand).
> 
> suggestion: you might get levy's book for christmas but skip waldrop  and
> lewin. save your money for some better 'technical' books on the subject .

	As an all around introduction to Artificial Life, Levy's book is very  
good. It's not a technical description, but gives a good history and  
interesting anecdotes on the major advances in alife from pre1987 - early 1992.  
It's a lot like Gleick's book on Chaos. I haven't read Lewin's, but Waldrop's  
book didn't impress me.

--
Robert Seymour				rseymour@reed.edu
Departments of Physics and Philosophy
Artificial Life Project			Reed College
Reed Solar Energy Project (SolTrain)	Portland, OR
Newsgroups: comp.theory.cell-automata
From: tolman%asylum.cs.utah.edu@cs.utah.edu (Kenneth Tolman)
Subject: What is the information content of cellular automata?
Date: 20 Nov 92 16:20:17 MST
Organization: University of Utah, CompSci Dept


 What is the information content of a particular configuration for a CA?
 What are references which would discuss this? (see below)


 One could define the information content for a cellular automata to be 
-log(probability of state)  Is this correct?

 In S. Amoroso he suggests that the information content
does not change for a reversible deterministic CA, which seems agreeable.
This would also correspond to the above metric, for any later state would
have the same probability as its predecessor. (1)

 In T. Toffoli, he suggests that the information content depends
on the initial state for irreversible deterministic CA.  If one has enough
detail to construct the initial state, then one has preserved the information
but if there is not enough to reconstruct then one has lost information. (2)

 Wolfram suggests that the "entropy" of a CA can be given by the logarithm
of the "average number of possible states of a system", or as

  SUM p(i) log (p(i))

  Then he shows a graph with the entropy decreasing for an irreversible
CA, which is based on the probabilities for each of the possible states the
system can be in.....  this is not entirely clear to me, for the INITIAL
state would appear to have an equal distribution, and any later states would
have an unequal probability distribution.. so is he calculating probabilities
on the infinite limit of that state or what? (the alternative is of course
that he calculates the probability for a state from all possible initial
states for a particular time interval)  It appears here that the information
content of a particular state then WOULD be the -log(probability of state) (3)

  So what IS the information content of a particular state in a cellular 
automata?


1 S. Amoroso, Journal Comp. Sys. Sciences, Vol 6, pp. 448-464.

2 T. Toffoli, Journal Comp. Sys. Sciences, Vol. 15, pp. 213-231

3 S. Wolfram, Rev. Mod. Phys. Vol. 55, No. 3, July 1983, pp. 601-644
From: james@panix.com (James Britt)
Newsgroups: comp.theory.cell-automata
Subject: CA program and source code posted.
Date: 17 Nov 92 06:11:20 GMT
Article-I.D.: panix.1992Nov17.061120.16028
Organization: PANIX Public Access Unix & Internet, NYC

I"ve written a cellular automata program that I think many people would
find interesting.  It's a 2-state line automata taknr from Stephan
Wolfram's book, Theory and Applications of Cellular Automata.  

I'm posting both the ms-dos executable and the C source code, and would
welcome any comments on it.

James Britt
-- 
:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
Just another speed-metal vegetarian anarchist cyberhippie Zen Socratic...
Diblo Rules!                                        Hack The Wetware!
james@panix.com  .............................................................
Newsgroups: comp.theory.cell-automata
From: J.Gallagher@unsw.EDU.AU (Jason Gallagher)
Subject: Re: Symmetric Life rules
Summary: yay! life in 74F chips!
Keywords: Gronk!
Organization: Psychology Department, University of N.S.W
Date: Mon, 23 Nov 1992 01:06:34 GMT

In article <1992Nov18.191744.16470@mnemosyne.cs.du.edu> eeklund@nyx.cs.du.edu (Eivind Eklund) writes:
>From: eeklund@nyx.cs.du.edu (Eivind Eklund)
>Subject: Re: Symmetric Life rules
>Date: Wed, 18 Nov 92 19:17:44 GMT
>In article <1992Nov17.122445.14209@odin.diku.dk> torbenm@diku.dk (Torben AEgidius Mogensen) writes:
>[...]
>Well, that is just another way of writing rules.  Conrad's Gam of Life can
>be written like this:
>
> 0 .
> 1 .
> 2 .
> 3 O
> 4 O (If set)
> 5 .
> 6 .
> 7 .
> 8 .
> 9 .
>
>And this is also nice for doing FAST implementations - see if you can find
>out how... (This might be common knowledge allready, but I have a hack
>which 
>I believe to be VERY fast - somebody tell me how many cells/second they
>are able to do on what kinds of computers 8-)
>I am able to do approx 1.3 million cells/second on a 1 MIPS Amiga.
>(7.14 Mhz 68000)
>
I presume you're doing this with the blitter? does it run standard life at
50 fps? if so at what res....
Thought about doing this myself for some time now, but instead i have been 
building a machine of my own (out of 74F/LS series chips only!) to calculate
arbitrary 3x3 neighbourhood rules at 50fps on a 256x192 grid... It's now in 
the final stages of construction... seems like it's a bit small, but should
be fun to watch when randomly seeded (which is where most other things fall 
down). Anyone want to hear more about it?

Jason
/----------------------------------------------------Jason Gallagher-\
| INet: J.Gallagher@unsw.edu.au        | "The eyes aren't too big!"  |
|       jasong@hydra.maths.unsw.edu.au |           -Me               |
\--------------------------------------------------------------------/
Newsgroups: comp.theory.cell-automata
From: rucker@sjsumcs.SJSU.EDU (Rudy Rucker)
Subject: Re: Re: ANTS prog
Organization: The Internet
Distribution: inet
Date: Thu, 19 Nov 1992 16:50:47 GMT


Ant21 is a shareware program that I mailed out on disk to those requesting
it in the spring of, I think, 1991.  Based on Dewdney's Turmites and 
Langton's Vants, ant21 shows 2D Turing machines with genetically evolving
lookup tables.  I am not mailing it out anymore, but I believe some
copies of it have made their way onto BBSes.  The first ant1 was written
during the teaching of a C class at San Jose State.

For the last year and a half I've been bringing an extension of ant21
into Windows.  It is now called BUGLAND, and may be available in
Fall 93 --- I'll certainly alert this list if and when.
From: thieloph@crypt3.cs.uni-sb.de (Christoph Thiel)
Newsgroups: comp.theory
Subject: Thank you for sending the Swart-Reports (NP=P)
Date: 19 Nov 92 13:18:08 GMT
Organization: Universitaet des Saarlandes, Saarbruecken



I want to thank everybody who sended or offered to send the reports
of E.R. Swart (P=NP) to me.

Christoph Thiel
From: pacolley@ember.UUCP (Paul Colley)
Newsgroups: comp.theory
Subject: Re: Reassembling a checkerboard jigsaw
Date: 21 Nov 92 18:57:25 GMT
Reply-To: pacolley@ember.UUCP (Paul Colley)
Organization: Ember---private system

In article <rreiner.722360646@yorku.ca> rreiner@nexus.yorku.ca
(Richard Reiner) writes:

>    - Given an n x n checkerboard which has been cut into pieces of
>      varing size along the edges of its squares (i.e. no diagonal
>      cuts),
>
>      Efficiently reassemble the pieces into an n x n board (the rebuilt
>      board need not deploy the pieces exactly as the original did,
>      although this would be preferable; ideally, I would like to be
>      able to enumerate *all* the ways of rearranging the pieces into an
>      n x n board).

The problem, "given a set of integers that sum to S, find a subset that
sum to 0.5 S" is NP-complete.

This problem can be reduced to the stated checkerboard problem as
follows:

Make an (S+1) x (S+1) square.

For each of the integers i,  Create a rectangular piece that is 2i long
by 0.5 S wide.

Add an additional piece that is T-shaped, with the "bars" one unit
wide, such that the T's total height is S+1 and total width is S+1.

I will give a small example to clarify the construction:

	Integers:  1,2,2,3 (sum S=8)

The pieces for the integers:

	XX    XXXX    XXXX    XXXXXX
	XX    XXXX    XXXX    XXXXXX
	XX    XXXX    XXXX    XXXXXX
	XX    XXXX    XXXX    XXXXXX
 
The T-shaped piece:

	XXXXXXXXX
	    X
	    X
	    X
	    X
	    X
	    X
	    X
	    X

And the 9x9 board:

	 .........
	 .........
	 .........
	 .........
	 .........
	 .........
	 .........
	 .........
	 .........

The extra T-shaped piece only fits in one way (modulo rotations), dividing the
board into two equal areas, like so:

	 ........X
	 ........X
	 ........X
	 ........X
	 XXXXXXXXX
	 ........X
	 ........X
	 ........X
	 ........X

The remaining pieces can be fitted in if and only if there is a subset
that adds to 0.5 S (proof let as an exercise for the reader :-) ).

Thus the checkerboard problem is NP-complete.

Now, the original poster wasn't clear about whether the colouring
of the squares was important (i.e., colour the pieces black and
white in a checkerboard pattern when you create them, and be able
to reassemble them back into a checkerboard colouring).

The reduction I gave is still valid if colouring is important; Each
piece is an even number of units wide ("2i"), and the orientation
that the pieces will be put in is known (if there is a solution,
there is a solution with the T bar dividing the board horizontally
and the pieces being placed with the 2i side against the dividing
bar of the T).  So we can just colour the pieces so that they match
a checkerboard when placed this way (and an even distance from the
edge of the board)).

----------

Thus the checkerboard problem is NP-hard.

- Paul Colley
University:  colley@qucis.queensu.ca
Home:        pacolley@ember.uucp   watmath!ember!pacolley  +1 613 545 3807
<Ring> [...] "Sorry, I'm all booked up." "Who was that?" "The library." - B.C.
Newsgroups: comp.theory
From: neto@cs.toronto.edu (David Neto)
Subject: Gismondi & Swart 
Keywords: harmless bug, typo
Organization: Department of Computer Science, University of Toronto
Date: 19 Nov 92 16:22:35 GMT

On page 6 of Gismondi and Swart, report CIS92-D4, the first condition
on unimodularity is stated incorrectly.  They write:

"Each column must contain at most two non-negative elements"

It should read:

"Each column must contain at most two non-zero elements"

This is a harmless bug because this theorem is not used in the paper.

David Neto
neto@cs.toronto.edu
Newsgroups: comp.theory
From: vashti@concave.cs.wits.ac.za (Vashti Galpin)
Subject: Re: Human Computers....
Organization: CS Dept, University of the Witwatersrand
Date: 23 Nov 92 08:34:42 GMT

In <1992Nov14.200401.24530@ariel.ec.usf.edu> mccolm@darwin.math.usf.edu. (Gregory McColm) writes:
>Most communicative computer books are really part of the 
>old GOLEM genre (a Medieval Jewish tale of an alchemist 
>who created an artificial man who ran amok).  Some golems 
>are good (eg, Rink-a-tink of Oz, Isaac Asimov's Robot series), 
>but most are Frankenstein types.  

An interesting book that combines both the original golem idea and
that of a human computer is Marge Piercy's Body of Glass (1991 or
1992). It also deals with virtual reality and has good characterisation.
I don't have the full details, but I can email them.

(BTW, is this really the right group for this discussion?)

---------------------------------------------------------------
Vashti Galpin                      vashti@concave.cs.wits.ac.za
Department of Computer Science, University of the Witwatersrand
2050 Wits, South Africa.  Tel 27(11)716-3295 Fax 27(11)403-1926
Xref: sparky comp.theory:2521 sci.math:15440 sci.crypt:5215
From: jmount+@CS.CMU.EDU (John Mount)
Newsgroups: comp.theory,sci.math,sci.crypt
Subject: Re: Cryptography and P=NP
Keywords: NP
Date: 23 Nov 92 23:02:24 GMT
Article-I.D.: cs.By6yo0.173.2
Followup-To: comp.theory
Organization: Carnegie Mellon University

In article <1244@zogwarg.etl.army.mil>, hoey@zogwarg.etl.army.mil (Dan Hoey) writes:
|> Yes, P=NP implies such a machine i exists.  But you might not be able
|> to prove it can recognize an NP-complete language, in spite of the
|> fact that it does.  In fact, you might not be able to prove of any
|> particular machine that it recognizes an NP-complete language in
|> polynomial time.
|> 
|> You might not even be able to prove of any particular polynomial that
|> it is the time bound for such a machine, even though you have proven
|> that the machine and the polynomial must exist.
|> 
|> Dan Hoey
|> Hoey@AIC.NRL.Navy.Mil

Please see my post in sci.crypt (Message-ID:<By2v5F.DCM.2@cs.cmu.edu>, 
Date: Sat, 21 Nov 1992 17:56:03 GMT) for a proof of how if P=NP you
can build a machine that recognizes an NP Complete language (halts
accepting on instances in the language, doesn't accept instances not
in the language- but may not halt as in Garey&Johnson "Computers and
Intractability: A guide to the Theory of NP-Completeness" 1979 pp.
24-25).  With only a proof that P=NP (you do not need to know the
index of any machine that solves NP complete problems in poly time or
even what the polynomial bounding some such machine is).

Of course this machine is SLOW, and you still have no idea how long it
is going to take (only that it is less than some, unknown,
polynomial).

-- 
--- It is kind of strange being in CS theory, given computers really do exist.
John Mount: jmount+@cs.cmu.edu               (412)268-6247
School of Computer Science, Carnegie Mellon University, 
5000 Forbes Ave., Pittsburgh PA 15213-3891
Xref: sparky comp.theory:2441 sci.math:15083 sci.crypt:4888
From: clong@remus.rutgers.edu (Chris Long)
Newsgroups: comp.theory,sci.math,sci.crypt
Subject: Re: Cryptography and P=NP
Date: 16 Nov 92 21:59:47 GMT
Followup-To: comp.theory
Organization: Rutgers Univ., New Brunswick, N.J.

In article <15115@ember.UUCP>, Paul Colley writes:

> If he means that anyone who believes P MIGHT be equal to NP is "an
> idiot", then I think Chris should retract his statement.

Nope.

> The problem is open.

Sure, but P=NP and P<>NP are certainly not equally likely.  The a priori
evidence that P<>NP is *overwhelming*; to claim that P=NP has a chance
of being true is worse than claiming that there is a chance of only a
finite number of twin primes existing.  Both are unproven, but there are
*very* strong reasons for believing them to be true.  So strong that
anyone who believes otherwise must be either ignorant or a crackpot.
-- 
Chris Long, 265 Old York Rd., Bridgewater, NJ  08807-2618