HDTenEightyP/NetNews huggingface dataset:
From: swann@divsun.unige.ch (SWANN Philip)
Subject: Automata & Chomsky Hierarchy 
Organization: University of Geneva, Switzerland
Date: Tue, 15 Dec 1992 16:25:45 GMT


In Casti's book "Alternative Realities" there's a conjecture
that Wolfram's classification of Cellular Automata into classes
can be mapped into Chomsky's Hierarchy of Formal Languages. He
cites Wolfram on this. Is there any recent work on the subject?

Philip Swann
University of Geneva
Newsgroups: comp.theory
From: jab@tellabs.com (Jeff Brooks)
Subject: Are Knuth's "Art of Computer Programming" books still worth reading?
Keywords: Knuth books
Organization: Tellabs, Inc.
Date: Wed, 16 Dec 1992 23:13:20 GMT


I've recently completed my first couple of classed towards a Masters in CS
and was told by one of my professors that Knuth's multi-volume set of books
"The Art of Computer Programming" are THE classic computer science books.

My questions are, are these books still worth reading or are they outdated?
The copy of volume 1 I found has a copyright date of 1973, so, should I
just read them as a historical reference or is most of the technical content
still applicable to today's programming methods?

Thanks in advance for your opinion or any other references that you can
recommend instead.

--Jeff Brooks
  CS expert wanabee
From: grove@triangle.Berkeley.EDU (Eddie Grove)
Newsgroups: comp.theory
Subject: Re: Real Numbers vs. Rational Numbers?
Date: 17 Dec 1992 18:59:36 GMT
Organization: University of California, Berkeley
Distribution: inet
NNTP-Posting-Host: triangle.berkeley.edu

In article <1992Dec16.095412.19570@tom.rz.uni-passau.de> boerncke@kirk.fmi.uni-passau.de (Frank-Roland Boernke) writes:
>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. 

The assumption of a RAM that uses real numbers is that you can store a real 
number in one memory location.

It all comes down to whether you allow constants.  

If you do allow constants, consider the real number U whose i^th bit is
true if (in some standard encoding) the i^th turing machine halts when
given i as input.

Given U, and the ability to do standard arithmetic operations on intermediate
results (mult by 2, compare to integer, subtract integer from) you can 
decide the language {i : machine i does not halt on i}, which is beyond 
the range of an ordinary TM.

If you do not allow real constants, you can simulate the "REAL" RAM by an
ordinary TM.

Eddie Grove
From: taylor@foraker.NoSubdomain.NoDomain (Eric Taylor)
Newsgroups: comp.theory
Subject: Re: Real Numbers vs. Rational Numbers?
Date: 19 Dec 92 20:24:25 GMT

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.
The terminology "REAL number", I believe, is not a formal
one, but one borrowed from something like FORTRAN where
they are simply meant to represent floating point
numbers.

Any rational number can be represented by the division
of 2 integers and are therefore easily handled by a
RAM or Turing machine.
From: ian@ohm.york.ac.uk (I Stephenson)
Newsgroups: comp.theory.cell-automata
Subject: Re: Cellular Automaton toolkit?
Date: 14 Dec 92 12:39:52 GMT
Reply-To: ian@ohm.york.ac.uk
Organization: Electronics Department, University of York, UK

In article <1992Dec11.145433.25107@daimi.aau.dk> brian@next (Brian Mayoh)  
writes:
> In article <1g8r1gINN11o@morrow.stanford.edu> fiddle@faddle.foodle.com  
writes:
> > A couple of weeks ago I saw a post from someone who had  
> > developed what looked like a fairly general toolkit for  
> > specifying and implementing a variety of CAs on the NeXT  
> > platform (i.e., in Objective C under NeXTStep), including  
> > networks of chemical reactions. I unfortunately lost the  
> > posting, so if anyone else knows whom to contact or where,  
> > please let me know (preferably by email). 
> > 
> > --
> >  
> > Eric Minch         Any resemblance to the opinions of persons
> > Epistemic Artisan  or organizations other than myself--living,
> > Stanford Genetics  dead, or imaginary--is purely fortuitous.
>        System is called CINC made by ian@ohm.york.ac.uk
> 	Iam most impressed by my first trials of it.
>	Regards   Brian Mayoh

Cinc isn't actually CA, though it should be of interest to those who are  
interested in the field. Cinc is the NeXT implementation of "Creatures", a  
system which attempts to address ome of the problems which arise from the  
spacial nature of CA without loosing the features we all know and love. The  
software may be ftp'd from sonata.cc.purdue.edu  
pub/next/submissions/CincDist.tar.Z. Papers may be obtained from  
shiraz.ohm.york.ac.uk. I've included part of the README file below.

The Creatures project is currently looking for beta test sites, so feedback is  
welcome, and limited technical support is available.

Ian Stephenson
Adaptive systems Engineering
Dept of Electronics
University of York
England

Cinc - The NeXT Creatures Simulator

Cinc is an implementation of the Creatures processing model for the NeXT.  
Creatures attempts to retain many of the attractive features of CA while  
allowing dynamic systems to be studied more easily. This is done by describing  
the active elements of a system, rather than the space in which they live.

Consider a simple model of road traffic - on a CA we must describe roads as  
either holding cars or not, then passing cars between them. The negotiation to  
support this rappidly swamps and cnsideration of what the CARS are doing. With  
Creatures we describe the cars - after all everyone knows what a car does!

The net result of this is a simulation environment that allows emergent  
behaviour to be studied easily, and models to be built rapidly without a great  
deal of programming experience - just describe what all the bits do, and what  
they do when they meet.

Once written and debugged on a NeXT, the same (or at least VERY similar) code  
may be run on  a CM-2(pretty fast) or a MasPar(very fast). This allows you to  
test models when very large numbers of elements are active.
Newsgroups: comp.theory.cell-automata
From: a.triulzi@imperial.ac.uk (Arrigo G.B. Triulzi)
Subject: Re: Creating a Life Computer? How do you design?
Organization: Imperial College Mathematics Department
Date: Mon, 14 Dec 92 13:43:23 GMT

I suggest reading "Winning ways for your mathematical plays" Vol. II -
Berlekamp, Conway, Guy where the "Life computer" is explained, or "The
Recusive Universe" - W. Poundstone - OUP.
Both books have large amounts of diagrams concerning the Life computers.

Arrigo

-- 
Arrigo G.B. Triulzi (a.triulzi@imperial.ac.uk) - PGP 2.0 sig. available
Mathematics Dept. - Imperial College of Science and Tech., London - UK
Newsgroups: comp.theory.cell-automata
From: brianm@plod.cbme.unzw.oz.au (Brian Murray)
Subject: Re: WireWorld (was Re: creating a life computer)
Organization: none
Date: Fri, 18 Dec 1992 07:23:45 GMT

There was a Computer Recreations (scientific american) article
explaining wireworld and giving examples of gates and memory cells etc.
I can't recall which issue, but it was around '88-'89 or so.
Anyone shed further light? I could dig it out of my collection if 
i could find it ......

-------------------------------------------------------- BM
brianm@cbme.unsw.edu.au
From: torbenm@diku.dk (Torben AEgidius Mogensen)
Newsgroups: comp.theory.cell-automata
Subject: Re: Creating a Life Computer? How do you design?
Date: 14 Dec 92 11:54:57 GMT
Organization: Department of Computer Science, U of Copenhagen

u2119737@csdvax.csd.unsw.edu.au writes:


>Recently I read somewhere about the idea of creating a simple computer
>using Life - having gliders as bit streams, with a factory as the clock.

>Can anyone out there design a Life object which accepts two glider streams 
>(At a determined clock pulse) and NANDs them? Ie if one or zero gliders enter
>at the time of a pulse, it emits a new glider, but if two gliders enter, it
>does not.

>How difficult is it to design objects like this for Life? I'd be very
>interesting to see any references to articles relating to methods of designing
>an object in Life. How were the original factories designed, for example?

Once you have a few components designed (which I believe some people
have), the rest can be obtained by combining these. These components
are, however VERY large and quite slow. There are other simple
cellular automata that are much better suited for this purpose. Wire
World is a good example. It uses the same 8-cell neighbourhood as
Life, but has 4 different values per cell. These are called
background (.), wire (+), electron head (#) and electron tail (*). The
rules are simple:

1) Background always stay background.

2) Electron heads always change to electron tails.

3) Electron tails always change to wire.

4) If a wire cell has 1 or 2 neighbours that are electron heads, it
becomes an electron head. Otherwise it stays a wire.

Thus a signal consisting of an electron head and an electron tail will
travel along a wire:

........
+++*#+++
........

changes to 

........
++++*#++
........

An OR gate is extremely simple, a diode is easy, XOR is not too bad
and AND can be designed in relatively little space. NOT needs power,
so must be clocked by an external signal (which can be provided by a
simple periodic circuit). Memory cells, binary adders and many more
circuits has been constructed.

Circuits can be build entirely from background and wires, needing just
a single signal to start working.

Purists might consider it cheating to use four different values, so it
might be interesting to find a variant Life rule that uses only two
values and an 8-cell neighbourhood, but is easier to build circuits
from than traditional Life.

	Torben Mogensen (torbenm@diku.dk)
Newsgroups: comp.theory.cell-automata
From: jwilliam@stsci.EDU (John Williams)
Subject: Autodesk CA
Reply-To: jwilliam@stsci.EDU (John Williams)
Organization: Space Telescope Science Institute
Date: Fri, 18 Dec 1992 20:28:07 GMT

--
I understand that Autodesk has a CA program they sell.  Can anyone tell 
me anything about it?  What about PD programs that run under UNIX or 
on a PC?  Thanks.

John

*****************************************************************************
*John Williams - jwilliam@stsci.edu      The universe is full of magical*
*Space Telescope Science Institute       things patiently waiting for	 *
*Baltimore, MD.			 our wits to grow sharper.	 *
From: mcneely@korg16.ColumbiaSC.NCR.COM (Alan.McNeely)
Newsgroups: comp.theory.cell-automata
Subject: Re: Creating a Life Computer? How do you design?
Date: 15 Dec 92 20:34:31 GMT
Organization: /usr/lib/news/organization

In article <1992Dec14.115457.918@odin.diku.dk> torbenm@diku.dk (Torben AEgidius Mogensen) writes:
>
>cellular automata that are much better suited for this purpose. Wire
>World is a good example. It uses the same 8-cell neighbourhood as
>Life, but has 4 different values per cell. These are called
>background (.), wire (+), electron head (#) and electron tail (*). The
>rules are simple:
>

This sounds very interesting.  Could someone point me to a good reference
on Wire World? 

Thanks in advance,
 
Alan McNeely
mcneely@bigb.columbiasc.ncr.com
Newsgroups: comp.theory.cell-automata
From: brian@next (Brian Mayoh)
Subject: VELLIG
Organization: DAIMI: Computer Science Department, Aarhus University, Denmark
Date: Thu, 17 Dec 92 14:50:59 GMT

Anyone know anything about a simulation system called VELLIG?
The referee of one of my student's papers - on a new reaction-diffusion
CA systems for biological modelling(papers on "penguins in Antartica"...-
keeps citing VELLIG but even a Wais search has dredged up nothing.
				Anticipating  info					Brian Mayoh
From: u2119737@csdvax.csd.unsw.edu.au
Newsgroups: comp.theory.cell-automata
Subject: Creating a Life Computer? How do you design?
Date: 14 Dec 92 00:10:47 +1000
Organization: University of New South Wales


Recently I read somewhere about the idea of creating a simple computer
using Life - having gliders as bit streams, with a factory as the clock.

This sounds fascinating, and also quite workable, so I'd like to throw the
idea open for discussion.

I suppose the best place to start would be in the design of a NAND gate.

Can anyone out there design a Life object which accepts two glider streams 
(At a determined clock pulse) and NANDs them? Ie if one or zero gliders enter
at the time of a pulse, it emits a new glider, but if two gliders enter, it
does not.

How difficult is it to design objects like this for Life? I'd be very
interesting to see any references to articles relating to methods of designing
an object in Life. How were the original factories designed, for example?

Please post, as this account is about to disappear into the void, and your
email will go with it, if you send any.

Malcolm

-- 
 +--------------------------------------------------------------+ 
 | Malcolm Ryan - U2119737@csdvax.csd.unsw.edu.au               |
 | Computer Science, University of New South Wales. AUSTRALIA.  |
 | "The rest of this quote is..."                               |
 +--------------------------------------------------------------+
From: jb7m+@andrew.cmu.edu (Jon C. R. Bennett)
Newsgroups: comp.theory.cell-automata
Subject: Looking for a person
Date: 11 Dec 92 10:37:29 GMT
Article-I.D.: andrew.cf_Dk9u00WD5MeKX1p
Organization: Robotics Institute, Carnegie Mellon, Pittsburgh, PA


I was having a conversation that reminded me of a piece of mail somone who
reads this board sent me, and then relised that i could not find it, so if
you work(ed) at Evans & Sutherland (i think) and in response to a post i
made about a year ago offered me a job (also about a year ago), could you
send me some mail since ive lost your address.....

jon bennett
author Xlife

p.s. i know this sounds strange, but thats what i get for over purging my
mail :-(
From: minch@lotka.stanford.edu
Newsgroups: comp.theory.cell-automata
Subject: bad address (was:Re: Cellular Automaton toolkit?
Date: 11 Dec 1992 21:05:39 GMT
Organization: Stanford University
NNTP-Posting-Host: lotka.stanford.edu

Sorry about the unreachable return address; I stepped on it. My  
real address is:

	minch@lotka.stanford.edu
Newsgroups: comp.theory.cell-automata
From: afoiani@nmsu.edu (Anthony Foiani)
Subject: Looking for the good Life... (on a mac)
Organization: NMSU Computer Science
Distribution: usa
Date: Fri, 18 Dec 1992 23:56:42 GMT


My apologies if this is the incorrect group, but this should be quick:
What is a good implentation (or a bad implementation, at that) of
Conway's "Life" game for the Macintosh?  I have poked around the usual
places, and I haven't seen one yet...

Thanks for any replies.  I'll summarize if I find anything useful.

Thanks again,
Tony
--
Tony Foiani  a.k.a. Tkil  (afoiani@nmsu.edu) or (tkil@acca.nmsu.edu)
Supporting:  Unix / DOS / VMS / Macintosh / "What's this?"
   Current favorite song: "Take To The Sky", Tori Amos, _Winter_ [CD5]
Organization: University of Illinois at Chicago
Date: Saturday, 19 Dec 1992 16:09:30 CST
From: <U54294@uicvm.uic.edu>
Newsgroups: comp.theory.cell-automata
Subject: Re: Autodesk CA

   The Autodesk software set for "Chaos: Making of a New Science" (as per
James Gleick's book of the same name) includes a whole package for 2D
cellular automata. The automata rules are almost completely customizable.
The only drawback is the somewhat small cellular space, even at the lowest
resolution. It's my understanding that this portion of Chaos is a stripped-
down version of Autodesk's CALab (I think that's the name). I got Chaos for
$39.95 at Egghead. Besides, you get all that Mandelbrot/Julia/Attractor
stuff with it ;)
   For Unix, I really like Xlife. Many different rules sets are possible,
but only for 2-state automata. It runs surprisingly fast, even on 386
unix. I've also compiled it on HP-UX on an HP-9000/817. It's of course
fully X-capable, and you get source. I believe I obtained it from
export.lcs.mit.edu.
                              Nick G.
                              U54294@uicvm.uic.edu     <-- Best
                              GEONI02@hera.cai.com
From: jb7m+@andrew.cmu.edu (Jon C. R. Bennett)
Newsgroups: comp.theory.cell-automata
Subject: Re: Game of Life
Date: 12 Dec 92 20:00:03 GMT
Article-I.D.: andrew.sf_h5Xe00WD5MeKYFe
Organization: Robotics Institute, Carnegie Mellon, Pittsburgh, PA

a.triulzi@imperial.ac.uk (Arrigo G.B. Triulzi) writes:
>         I have written something like this in C but I don't have the multiple
> object facility which means that I have immense load files if I need a
> complicated initial setup.

if i undersatnd what you mean my "multiple object facility" correctly,
then you should find that Xlife satisfies your needs, you can get a copy
from export.lcs.mit.edu

jon
From: wright-rebecca@cs.yale.edu (Rebecca Wright)
Newsgroups: comp.theory
Subject: roommate needed for SODA
Date: 15 Dec 1992 13:19:50 -0500
Organization: Yale University Computer Science Dept., New Haven, CT 06520-2158
Distribution: inet
NNTP-Posting-Host: birch.theory.cs.yale.edu

I am looking for a nonsmoking, female roommate for the upcoming Soda
conference in Austin, TX as a way to cut costs.  I have reserved a
double room for the nights of Saturday, January 23 through Wednesday,
January 27, but don't necessarily have to find a roommate for all of
those nights.

If interested, please contact me at wright-rebecca@cs.yale.edu.

Thank you,
Rebecca Wright
wright-rebecca@cs.yale.edu

Newsgroups: comp.theory
From: as@cs.brown.edu (Apratim Sarkar)
Subject: NP-completeness question
Organization: Brown University Department of Computer Science
Date: Tue, 15 Dec 1992 04:43:07 GMT


I need to know whether the following problem is 
NP-complete. Seems like that to me - but I can 
not prove it.
-----------------------------------------------
Given an undirected unweighted graph (V,E) and
given a subset R of V, delete the minimum number
of edges so that all cycles involving at least 1
node from R are deleted. That is, in the final
solution, there may be cycles remaining in the
graph, but none involving nodes from R.

When R=V, this is equivalent to finding the
spanning tree of the graph and take the edge
complement of it. This kills all the cycles in 
the graph. 

When R={a} for some node a, it is equivalent to
deleting d(a) - 1 adjacent incident edges of a,
where d(a) is the degree of a. This kills all the
cycles through a.

So the two extremes are P, but what about in the
middle?

Any suggestions?

Thanks,
Apra.
----------------------------------------------------------------------------------
Apratim Sarkar 	    	      	   	     	       fone  (401)-863-7667 (off)    
Brown University, Box 1910     	   	     	       	     (617)-262-5515 (home)
Department of Computer Science	   	     	       fax   (401)-863-7657
From: un027705@wvnvms.wvnet.edu (Jon Beck)
Newsgroups: comp.theory
Subject: Building a Lattice
Date: 15 Dec 92 18:09:34 GMT
Organization: West Virginia Network for Educational Telecomputing

Can anyone point me to an algorithm for building a lattice? I
happen to be specifically interested in a lattice whose meet is
set intersection, whose join is set union, and whose partial
ordering function is subset, but of course that shouldn't matter to
the algorithm. It seems to me as though a compiler for a language
which has multiple inheritance should have such an algorithm for
building the inheritance hierarchy, which for multiple inheritance is
a lattice, but I haven't been able to find anything in compiler
literature.

I have an algorithm which works, but it's hairy and smells bad; I
was looking for something a bit prettier and which won't leave
spots on the rug.

-- 
Jon Beck, Research Assistant
Department of Statistics and Computer Science
West Virginia University
beck@cs.wvu.wvnet.edu
Newsgroups: comp.theory
From: belkacem@fa.ibp.fr (Zerrouk BELKACEM)
Subject: Knuth Books
Organization: Laboratoire MASI, Paris, France
Date: Thu, 17 Dec 1992 09:51:20 GMT

Hi,

Jeff Brooks writes:

/*

"The Art of Computer Programming" are THE classic computer science books.

My questions are, are these books still worth reading or are they outdated?
The copy of volume 1 I found has a copyright date of 1973, so, should I
just read them as a historical reference or is most of the technical content
still applicable to today's programming methods?

*/


A friend said me that Knuth Books are a Treasure Wells. I agree
with him, because I think that " we can change computers but not
the mind of the art of computing"


Belk
-- 
......................................
Belkacem ZERROUK                        
CAO_VLSI/MASI UPMC PARIS VI            
e-mail: zerrouk@masi.ibp.fr
From: brendan@june.cs.washington.edu (Brendan Mumey)
Newsgroups: comp.theory
Subject: SODA roommate needed
Date: 15 Dec 92 22:18:06 GMT
Article-I.D.: june.BRENDAN.92Dec15141806
Organization: UW-CSE


That reminds me, I need to find a roommate too.  I am a nonsmoking male.
I have yet to book a room but will do so in the next couple of days, 
from Sunday night through Tuesday night.

Brendan Mumey
brendan@cs.washington.edu
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: Wed, 16 Dec 1992 22:26:28 GMT


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. 
>
>Of course, e.g. you can compute Pi up to as many digits as you want, but in every
>step  of computation you only have an approximation - a rational number.
>
>Therefore, a machine-model, that allows real numbers, must be more powerful
>than another one that does not. My professor said, that isn`t a problem but
>I don`t agree. Who is right?
>
>If I am wrong, please let me know where the fault is.

How about this: 
Maybe the model could conceivably represent the reals, but how would any
irrational number get into the machine in the first place?  There are 
uncountably many irrationals, so a table look-up won't do.  You could
try to calculate them, but how do you calculate, say, pi, with only 
Turing-machine-like operations?

So, at first glance, it looks like this machine is equivalent to the RAM
model with rationals plus a finite number of irrationals you could have in
a table.  This is equivalent to a Turing machine.

Anybody buy that?
-- 
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