HDTenEightyP/NetNews huggingface dataset:
From: hiebeler@think.com (Dave Hiebeler)
Newsgroups: comp.theory.cell-automata
Subject: Re: Cellsim - simulator info please
Date: 8 Oct 92 12:26:22
Organization: Thinking Machines Corporation
Distribution: inet
NNTP-Posting-Host: custard.think.com
In-reply-to: rpatil@nmsu.edu's message of Mon, 5 Oct 1992 20:57:36 GMT


In article <RPATIL.92Oct5135736@pylos.nmsu.edu> rpatil@nmsu.edu (Raj Patil) writes:

> I have Cellular Automata Simulator written by Chris Langton and David
> Hiebeler. It runs under sunview. I would like to know if anyone has 
> ported it to X11.

  Quite some time ago, I started trying to do an X11 version in my
rare spare time.  I got as far as having the very simple basics
working, so I could display a 2-D image in black&white, load a rule
and image, and run.  But very little else was in there, and I never
get time to work on it any more.  Also, I don't know anything about
doing colors in X11.  So I can't really say whether an X11 version
will ever be released.

--
Dave Hiebeler                  | hiebeler@think.com
Thinking Machines Corporation  | (617) 234-4070
From: gavin@firebird.newcastle.edu.au (Gavin Turner)
Newsgroups: comp.theory.cell-automata
Subject: request for references.
Summary: request for refernce titles to fuel new interest.
Keywords: references, CA, cell-automata
Date: 14 Oct 92 07:46:07 GMT
Organization: Uni of Newcastle, Australia

I have recently become interested in CA theory
and would greatly appreciate a reference listing -
preferably journal articles. 

Since I am just starting out, Could anyone suggest
early core-work papers?? eg Von-Neuman, etc.

Any assistance would be great.

Gavin.
--------------------------------------------------
Gavin Turner gavin@cs.newcastle.edu.au
Phd Student University of Newcastle (Australia).
Newsgroups: comp.theory.cell-automata
From: rpatil@nmsu.edu (Raj Patil)
Subject: Rules collection...help
Organization: Computing Research Lab
Distribution: comp.theory.cell-automata
Date: Wed, 14 Oct 1992 05:25:25 GMT


Hi:

Does anyone know of aly library of interesting rules for Cellsim. I am
looking for one which can skeletonize a given binary image.

Regards

raj patil
NMSU-CRL, USDA-ARS
Las Cruces, NM 88003
Newsgroups: comp.theory.cell-automata
From: Richard J. Gaylord <gaylord@ux1.cso.uiuc.edu>
Subject: Re: mathematica
X-Xxdate: Fri, 9 Oct 92 04:05:37 GMT
X-Useragent: Nuntius v1.1.1d11
Organization: University of Illinois
Date: Fri, 9 Oct 1992 09:03:29 GMT
X-Xxmessage-Id: <A6FAB5919C019B14@mm-mac20.mse.uiuc.edu>

there is the game of life package that comes with Mathematica and i have
written a number of others such as the sandpile model.
Newsgroups: comp.theory.cell-automata
From: tolman%asylum.cs.utah.edu@cs.utah.edu (Kenneth Tolman)
Subject: What grad schools study CA?
Date: 9 Oct 92 12:48:27 MDT
Organization: University of Utah, CompSci Dept

  What graduate programs in computer science have active research programs
in CA?  Princeton suggests they do in their literature, but I have seen
no others..... 

  Any information would be greatly appreciated.
From: fukuda@sys.titech.ac.jp (naoki FUKUDA)
Newsgroups: comp.theory.cell-automata
Subject: Re: Looking for Stephen Wolfram... (refs)
Date: 6 Oct 92 16:47:04 GMT
Organization: Tokyo Institute of Technology, Yokohama, Japan.


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

 >>   Hi, I am looking for work done by Stephen Wolfram.  I have a lot of
 >> good stuff from before 86, but would like to look at more recent work
 >> by him.  Anybody got a good lead off article?

  I heard that he retired his investigation on about 1986 and
engaged in the work at Wolfram Research, Inc.
  But I also heard that he came back to the investigation on CA
this spring.
  If there are any, I also want his recent articles.

  Thanks.

==========  Naoki FUKUDA  ==========
====  Dept. of Systems Science  ====
======  Tokyo Inst. of Tech.  ======
=============  Japan  ==============
=  E-mail: fukuda@me.titech.ac.jp  =
From: hwstock@snll-arpagw.llnl.gov (stockman harlan w)
Newsgroups: comp.theory.cell-automata
Subject: Re: What grad schools study CA?
Date: 11 Oct 92 20:04:15 GMT
Organization: Sandia National Labs, Livermore, CA

>
>	MIT has profs working on CA in Project MAC (CS), mathematics,
>	and geophysics.
>
>I am terrible at remember names, but they have papers in MIT Press books
>on CAs

In geophysics, contact Dan Rothman (dan@segovia.mit.edu). He is
currently on leave in France, working on CA models for multiphase flow.
His interests are "practical" application of CA -- modeling real
physical phenomena.
Newsgroups: comp.theory.cell-automata
From: fawg@epcc.ed.ac.UK (Felicity George)
Subject: Re: Cellsim - simulator info please]
Organization: The Internet
Distribution: inet
Date: Fri, 9 Oct 1992 08:51:05 GMT

> In article <RPATIL.92Oct5135736@pylos.nmsu.edu> rpatil@nmsu.edu (Raj Patil) writes:
> 
> > I have Cellular Automata Simulator written by Chris Langton and David
> > Hiebeler. It runs under sunview. I would like to know if anyone has 
> > ported it to X11.
> 
>   Quite some time ago, I started trying to do an X11 version in my
> rare spare time.  I got as far as having the very simple basics
> working, so I could display a 2-D image in black&white, load a rule
> and image, and run.  But very little else was in there, and I never
> get time to work on it any more.  Also, I don't know anything about
> doing colors in X11.  So I can't really say whether an X11 version
> will ever be released.
> 
> --
> Dave Hiebeler                  | hiebeler@think.com
> Thinking Machines Corporation  | (617) 234-4070
> 

I've forwarded this information on to Raj Patil already, but in case
anyone is interested, I have written an X11 version of Cellsim, which
runs in black and white. It has not been extensively tested, as I have
not had time to work on it, but if anyone wants a copy, I'll fix bugs as
they come up.

Felicity George (fawg@uk.ac.ed.epcc)

Applications Scientist
Edinburgh Parallel Computing Centre.
From: faraghec@cognos.com (Chad Faragher)
Subject: Fluid Dynamics
Organization: Cognos Incorporated, Ottawa CANADA
Date: Thu, 15 Oct 1992 12:30:40 GMT

I heard that CA can be used for visualization of Fluid Dynamics.  Is this
true?  Can anyone provide information on this?
Newsgroups: comp.theory.cell-automata
From: Richard J. Gaylord <gaylord@ux1.cso.uiuc.edu>
Subject: Re: Looking for Stephen Wolfram... (refs)
X-Xxdate: Wed, 7 Oct 92 03:33:25 GMT
X-Useragent: Nuntius v1.1.1d11
Organization: University of Illinois
Date: Wed, 7 Oct 1992 08:31:18 GMT
X-Xxmessage-Id: <A6F80B0563029B13@mm-mac19.mse.uiuc.edu>

Re: Looking for Stephen Wolfram... (refs)

there will be a book on cellular automata by s. wolfram in the
not-too-distant future.  i'm sure the group will hear of it when its
published.

if its anything like as his Rev.Mod.Phys. article or his "Mathematica"
text, it should be amazing.
From: lmh@theory.lcs.mit.edu (Minghsun Liu)
Newsgroups: comp.theory.cell-automata
Subject: Re: What grad schools study CA?
Date: 10 Oct 92 08:35:24 GMT
Organization: MIT Laboratory for Computer Science

>>>>> On 9 Oct 92 20:55:41 GMT, stgprao@st.unocal.COM (Richard Ottolini) said:

ll> In article <1992Oct9.124828.17269@hellgate.utah.edu> tolman%asylum.cs.utah.edu@cs.utah.edu (Kenneth Tolman) writes:
>  What graduate programs in computer science have active research programs
>in CA?  Princeton suggests they do in their literature, but I have seen
>no others..... 


ll> 	MIT has profs working on CA in Project MAC (CS), mathematics,
ll> 	and geophysics.

ll> I am terrible at remember names, but they have papers in MIT Press books
ll> on CAs

Norman Margolus is one of the people studying CA here.

- Minghsun Liu
  lmh@MedG.LCS.MIT.Edu
  lmh@Genome.WI.Edu
Newsgroups: comp.theory.cell-automata
From: mittle@siena.watson.ibm.com (Josh Mittleman)
Subject: Re: Graph-theory question
Date: Tue, 13 Oct 92 17:43:44 GMT
Distribution: usa
Organization: IBM T. J. Watson Research

>  Given 2 PLANAR graphs G1(e1,v1) and G2(e2,v2), where e1
>  and e2 are the number of edges and v1 and v2 are the 
>  number of vertices (assume e1>e2 and v1>v2). What is
>  the complexity of answering the question: 
>  
>  Does there exist a copy of G2 in G1?

This problem is NP-complete.  Let G2 be a k-clique, and you see that your
problem is identical to the clique problem.

===========================================================================
Josh Mittleman (mittle@watson.ibm.com)
J2-C28 T.J. Watson Research Center, PO Box 704, Yorktown Heights, NY  10598
From: sunil@calypso.unl.edu ("", Sunil Shende)
Newsgroups: comp.theory
Subject: Univ of Nebraska/Lincoln C.S. Faculty recruiting advertisement
Date: 8 Oct 92 15:51:44 GMT
Reply-To: "(Sunil Shende)" <sunil@calypso.unl.edu>


            UNIVERSITY  OF  NEBRASKA-LINCOLN

    FACULTY POSITION IN COMPUTER SCIENCE AND ENGINEERING


The Computer Science and Engineering Department invites applications
for tenure-track faculty positions from persons holding or completing
a Doctorate in Computer Science, Computer Engineering or closely
related disciplines. The Department is particularly interested in
applicants with a strong commitment to research and teaching in
the areas of Networks and Distributed Computing. However, outstanding
candidates in other areas will also be considered.

The CSE department currently has 19 full-time faculty who are active
in research and teaching in algorithms, artificial intelligence,
automata theory, combinatorics, complexity theory, computer algebra,
computer vision, cryptography, database, digital testing and design
automation, fault-tolerant computing, formal languages, graph theory,
human-computer interface, information retrieval, neural networks,
parallel processing architectures, pattern recognition, scheduling,
software engineering, and VLSI design. The department offers B.S.,
M.S., and Ph.D. degrees in computer science and a B.S. degree in
computer engineering. Currently over 90 students are enrolled in
the graduate program and about 350 in the undergraduate program.

UNL has a wide variety of computing resources linked by a comprehensive
campus-wide network. It is the lead institution in the NSF-funded
regional network, MIDnet, and a node on the NSFnet backbone. On the
university-wide network there are several mainframes and many
workstations. The department also has more than 40 workstations and
a PC-based laboratory. A 10-node transputer system is also available
for research in parallel processing. A number of departmental faculty
are active participants in two state-supported research centers, the
Center for Communication and Information Sciences and the Center for
Technology Management and Decision Sciences.

Apply by February 1, 1993 for appointments starting in August, 1993.
However, applications will continue to be accepted until the position
is filled. Send resume, names of three references, and a letter describing
current teaching and research interests to:


Stuart W. Margolis, Search Committee Chair
Department of Computer Science and Engineering
UNIVERSITY OF NEBRASKA-LINCOLN
Lincoln, NE  68588-0115.
Email: search@lovelace.unl.edu
From: sarnath@acsu.buffalo.edu (Ramnath Sarnath)
Newsgroups: comp.theory
Subject: lower bounds on graph diameter
Date: 9 Oct 92 21:00:31 GMT
Organization: State University of New York at Buffalo/Comp Sci


I am looking for references to lower bounds on the diameter 
of graphs, i.e, lower bounds on the longest "shortest path"
in a graph, when bounds are placed on the degree.


thanx,

sarnath
Newsgroups: comp.theory
From: goos@cs.ruu.nl (Goos Kant)
Subject: Re: graph planarization
Date: Wed, 7 Oct 1992 07:22:22 GMT
Organization: Utrecht University, Dept. of Computer Science

In <9210061320.AA04370@enet-gw.pa.dec.com> mek@hydrox.enet.dec.com (Mark Klamerus) writes:

>	Does anyone have any references for graph planarization?

Here again my posting on comp.theory, from sep. 25, 1991. 

There are some results on finding planar subgraphs of nonplanar
graphs G (so called planarization). Maximal planarization means finding
a planar subgraph G' of G such that adding an edge e of G - G' destroys
the planarity:

[1] J.Cai, X.Han & R.E. Tarjan, "An O(m log n)-Time Algorithm for the 
    Maximal Planar Subgraph Problem, TR, Courant Inst. New York, 1991.
[2] G. Di Battista & R. Tamassia, "Incremental Planarity Testing", 
    Proc. FOCS 89, pp. 436-441.
[3] G. Kant, "An O(n^2) Maximal Planarization Algorithm Based on 
    PQ-Trees", TR RUU-CS-92-03, Dept. of Comp. Science, Utrecht Univ, 1992.

The first paper describes an O(m log n) algorithm to find a maximal 
planar subgraph of a graph, based on the Hopcrof-Tarjan planarity testing 
algorithm. The second describes the PQSR-datastructure. With this structure
you can test in O(log n) time whether adding an edge preserves the planarity
(yielding also an O(m log n) maximal planarization algorithm). New incremental
planarity testing algorithms are known nowadays, working in O(a(m,n)) time per
edge, where a(m,n) is the functional inverse of Ackermann's function (e.g.,
see ICALP'92). The title of the third paper is clear and seems to delete 
less edges in general than the other two (A pascal program of the main part 
of this algorithm is available, as well as the planarity testing algorithm). 

A good survey on drawing (non)planar graphs is given in: 

[1] Eades, P., and R. Tamassia, "Algorithms for automatic graph drawing:
    an annotated bibliography", TR. no CS-89-09, Dept. of Comp. Science, 
    Brown Univ, 1989.

I hope this will help you,


Goos Kant (goos@cs.ruu.nl)

Newsgroups: comp.theory
From: tolman%asylum.cs.utah.edu@cs.utah.edu (Kenneth Tolman)
Subject: Seeking work on computers/information
Date: 11 Oct 92 14:42:07 MDT
Organization: University of Utah, CompSci Dept

  Hi,

  I am doing research on the relationship between computers and information
theory.  Specifically, I am looking for work done on information loss
during computation, and on the creation of information in computation.
Any work at all related to these topics would be greatly appreciated.
I have discovered most of the work by Chaitin, Landauer, Bennett, Fredkin,
Toffoli and of course the original works of Shannon and Kolmogrov.  If you
also are a researcher in this field, feel free to talk with me via e-mail.

Thank you for any references or suggestions!






Newsgroups: comp.theory
From: tzeng@ccsun5.cc.nctu.edu.tw (Wen-Guey Tzeng)
Subject: strongly regular graph
Organization: National Chiao Tung University
Date: Wed, 14 Oct 1992 03:01:36 GMT

Does any body know where I can get data of "strongly
 regular graph" or programs which generate them.

I need them to test a graph isomorphism program.

Thanks for your help in advance.

Wen-Guey Tzeng
tzeng@weber.cis.nctu.edu.tw

Newsgroups: comp.theory
From: ped@csc.liv.ac.uk (Paul Dunne)
Newsgroups: comp.theory
Subject: Re: Kernighan-Lin like program (graph) partitioning
Date: 8 Oct 92 09:49:21 GMT
Organization: Computer Science, Liverpool University
X-Newsreader: TIN [version 1.1 PL6]

Jan Bosch (bosch@cs.utwente.nl) wrote:
> Dear theorists,
> 
> I am supposed to test our new heuristic algorithm against some others (heaviest
> edge first, communication minima, etc) One of these algorithms is refered
> to as 'Kernighan-Lin like partitioning'. I scanned the citation index, but
> did not find anything useful. My question is (obvious):
> 
> 	Could some please send me a reference to this algorithm?
> 
> or perhaps a (short) description of the algorithm. The first, but especially
> the second, will be very much appreciated.
> 
> Thanx in advance.
> 
> Cheers,
> 
> Jan Bosch
> 
> -- 
> Jan Bosch		| Spaarnestraat 73, 7523 VK, Enschede, Netherlands
> bosch@cs.utwente.nl	| voice: +31-(0)53-354614
> i------------------- We have to tri harder! - (athlon)--------------------i

The reference you want is:


B.W. Kernighan and S. Lin
An Efficient Heuristic Procedure for Partioning Graphs
Bell Systems Technical Journal (1970) pp. 291-307
-----------------------------------------------------------------------------

Paul E. Dunne
Univ. of Liverpool
From: gtall@ogre.cica.indiana.edu (Gerry Allwein)
Subject: Re: word problems on lattices
Keywords: lattice, word problems, complexity, decidability
Organization: Indiana University
Date: Fri, 16 Oct 1992 21:44:38 GMT

See Birkhoff, Lattice Theory, pg 145 of the third edition.

Gerry

Newsgroups: comp.theory
From: twarnow@cs.sandia.gov (Tandy Warnow)
Newsgroups: comp.theory,sci.math
Subject: Announcement of tutorial and workshop on Nov. 5 and 6, 1992 in Computational Biology
Keywords: Computational Biology, Algorithms, Sequence Alignment
Date: 16 Oct 92 17:48:16 GMT
Article-I.D.: cs.1992Oct16.174816.12178
Organization: Sandia National Laboratories, Albuquerque, NM


                      Tutorial and Workshop on
             Algorithms for Molecular Sequence Alignment


                         Nov. 5 - 6, 1992
              University of New Mexico, Albuquerque, NM

Sandia National Laboratories and the Computer Science Department at 
the University of New Mexico are pleased to announce a tutorial and 
workshop on {\em Algorithms for Molecular Sequence Alignment}, to be 
held on Nov. 5 and 6, 1992, at the University of New Mexico, in 
Albuquerque, NM.  The tutorial is designed to introduce the problem 
of molecular sequence alignment, while the workshop will focus on new 
algorithmic techniques for this fundamental problem in computational 
biology.  The tutorial and workshop will be free and open to the public.
Graduate students and postdocs are especially encouraged to attend.

Thursday, Nov. 5: Tutorial


       Topics to be covered include:
            biological background, optimal pairwise alignments,
            global and local alignment, suboptimal pairwise alignments,
            distance vs. similarity, scoring matrices, database searching, 
            and multiple alignment: trees and profiles.

 Instructor: Martin Vingron
             Department of Mathematics
             University of Southern California


Friday, Nov. 6:  Workshop

Lectures: 


"On Suboptimal Alignments of Biological Sequences" 
        Dalit Naor
        Department of Biochemistry
        Stanford University

"Multiple Alignment with Guaranteed Error Bounds" 
        Pavel Pevzner
        Department of Computer Science
        Pennsylvania State University

"Scoring Systems for Macromolecular Sequence Comparison"
        Stephen Altschul
        National Institute of Health

Title to be announced
        John Kececioglu
        Department of Computer Science
        University of California at Davis


"Analysis and Biological Evaluation of Parametric Sequence Alignments"
        Martin Vingron
        Department of Mathematics
        University of Southern California


"Dinucleotide Simple Sequence Repeats in Human DNA"
        David Torney
        Los Alamos National Laboratories

"3-D Profile Method and its Application in Protein Secondary Structure Prediction"
        Kam Zhang
        Molecular Biology Institute
        University of California at Los Angeles


For further information, please contact Tandy Warnow at (505) 845-7604
or by email at twarnow@cs.sandia.gov.
From: torbenm@diku.dk (Torben AEgidius Mogensen)
Newsgroups: comp.theory
Subject: Re: Gates vs Turing machines
Date: 16 Oct 92 11:05:44 GMT
Organization: Department of Computer Science, U of Copenhagen

tolman%asylum.cs.utah.edu@cs.utah.edu (Kenneth Tolman) writes:

>  How could a linear collection of gates simulate a Turing machine?
>Or, how could a boolean expression simulate a Turing machine?

>The Turing machine is an interesting object (and gets the halting uncertainty)
>only because it does not always move in one direction, it cycles and
>repeats sometimes.  However a linear collection of gates clearly could
>not do anything but come to its end, how can it simulate a Turing machine?
>What else is needed to make the gates function as a real computer, besides
>them hooked together?

A non-circular combination of gates can simulate a single step of a
finite tape Turing machine, and if you loop the output into the input
via a latch, you can simulate a running Turing machine. When the
output stabilizes, it corresponds to a halting state of the Turing
machine. It is obviously not possible to simulate an infinite state
Turing machine using finite resources.

	Torben Mogensen (torbenm@diku.dk)
From: markh@csd4.csd.uwm.edu (Mark)
Newsgroups: comp.theory
Subject: Re: Accepting sequences?
Date: 11 Oct 1992 16:06:02 GMT
Organization: Computing Services Division, University of Wisconsin - Milwaukee
Distribution: inet
NNTP-Posting-Host: 129.89.7.4

In article <1992Oct02.165008.37497@Cookie.secapl.com> frank@Cookie.secapl.com (Frank Adams) writes:
>In any event, programs which run indefinitely do not generally do *a*
>computation; instead they act as servers, performing and completing multiple
>computations.

There is no such thing as a program that runs indefinitely.  Sooner or later
(actually sooner) someone's either going to turn off the machine, reboot it,
or else it will eventually wear out or the Sun will bloat up, and consume the
Earth and everything on the planet with it.  Nothing lasts forever.
From: akyildiz@vax.oxford.ac.uk
Newsgroups: comp.theory,sci.math,sci.math.symbolic
Subject: Re: Recurrence relations
Date: 14 Oct 92 15:20:05 GMT
Organization: Oxford University VAX 6620



In article <1992Oct13.214306.2605@babbage.ece.uc.edu>, dsims@leo.ece.uc.edu (David Sims) writes:
> Does there exist software for finding a closed form expression given a
> recursive function?
> 
> I would expect such a program to use recurrence relations to solve the
> recursive functions.  Any pointers to software packages would be greatly
> appreciated.
> 
> Thanks in advance.
> -- 
> David Sims              Dept. of Electrical and Computer Engineering
> david.sims@uc.edu       University of Cincinnati
> (513) 556-2499          Cincinnati OH  45221-0030
>                         USA


	Try the Mathematica pacakage RSolve.m in version 2.0 or later
	in Mma software from Wolfram R.I.
Newsgroups: comp.theory
From: markh@csd4.csd.uwm.edu (Mark)
Newsgroups: comp.theory,sci.math
Subject: Why Church's Thesis fails (was: Re: Turing's Halting problem revisited)
Date: 11 Oct 92 17:16:16 GMT
Distribution: inet
Organization: Computing Services Division, University of Wisconsin - Milwaukee
NNTP-Posting-Host: 129.89.7.4

In article <Oct09.020143.90256@yuma.ACNS.ColoState.EDU> ld231782@LANCE.ColoState.Edu (L. Detweiler) writes:
>Other approaches to `solving' the halting problem (or at least avoiding
>Turing's contradiction) besides H2(x,y) are conceivable.  One possibility
>is that there are other computational processes besides those modelled by
>Turing machines.  The position of the famous `Church-Turing thesis' and
>widely-held conventional wisdom is that this is not the case.  Nevertheless,
>if such machines exist, they might be modelled by new axioms describing their
>behavior.

Conventional wisdom would be seriously wrong.

There is no computational process in reality that cannot be modelled by a
finite state machine.  As humans, we have finite and bounded memory capacity,
and finite and bounded lifetimes (regardless of whether we like to accept our
mortality or not).  Computers all have finite and bounded memory capacity and
lifetimes.

You can't even get a mere piddling lowly Push Down Automaton out of that,
much less a Turing Machine!

The only reason they are used are:

          (1) They form convenient idealizations of reality
          (2) They allow real computations to be more concisely described.

Furthermore, ANYTHING that satisfies these two criteria must be regarded
equally, regardless of whether it's more powerful than a Turing Machine or
not -- because they're all fictional anyhow.

Since "conventional wisdom" has already allowed things that don't exist to be
called real, then anything goes, as long as it's convenient (satisfies (1) and
(2)).  Otherwise, the onus is on proponents of Church's Thesis to justify
calling things real that don't exist.

Therefore Church's Thesis fails on that account too.


Therefore, I agree with the intent of the rest of your article to attempt to
model a non Turing form of "computation" :)