HDTenEightyP/NetNews huggingface dataset:
From: hoppie@nemesis.East.Sun.COM (Tom Hopkins)
Newsgroups: comp.theory.cell-automata
Subject: Re: Undecidability of configurations/progres
Date: 14 Nov 1992 02:59:17 GMT
Organization: Sun Microsystems, Inc., Billerica, MA. 
Distribution: world
Reply-To: hoppie@nemesis.East.Sun.COM
NNTP-Posting-Host: nemesis.east.sun.com

(A note to the readers:  I am about to dive off into an area I have
little or no knowledge or experience about, and if what I say sounds
like the ravings of an idiot, there is good reason for it.)

In article 100765@Cookie.secapl.com, frank@Cookie.secapl.com (Frank Adams) writes:
>This depends on exactly how you define a GoE pattern.  If I have a pattern
>which fits in an n by m rectangle, there are two questions I can ask:
[...question (1) deleted...]
>(2) is there any previous pattern whose next step is the specified pattern,
>with everything outside the rectangle being blank?
>
>Question (1) can be answered as described; however I believe question (2) is
>the standard definition of a GoE.  And question (2) is, in fact,
>undecidable.
[...Proof concerning (2) deleted...]

Suppose I have a 3x3 rectangle, in which I have placed a diamond.  I
can tell you, with certainty, that there is a pattern with everything
outside the 3x3 rectangle blank for which the diamond is the next
step.  Thus for a specific configuration, of a certain size, question
(2) is decidable.

Have I missed the point of this line of discussion entirely, or is
there some size limit below which the halting problem is solvable?

Tom Hopkins <hoppie@turbo.east.sun.com>
(I reiterate:  I could be saying something wholly idiotic.  If this is
so, please explain to me that this is so.)


Newsgroups: comp.theory.cell-automata
From: brianm@plod.cbme.unzw.oz.au (Brian Murray)
Subject: Re: What is Garden of Eden?
Organization: none
Date: Thu, 5 Nov 1992 08:33:42 GMT

In article <1992Nov3.182235.6709@wdl.loral.com> mab@wdl39.wdl.loral.com (Mark A Biggar) writes:
>The following is a GOE:
>
>************** ******************
>* * * * * * **** ** *** *** ** **
>************* * * *** *** *** ** 
>* * * * * * ** ***** *** *** ****
> * * * * * * *** * *** *** ** * *
>************** **** *** *** *****
> * * * * * * *** **** *** *** * *
>* * * * * * * * * ** *** *** * **
>*********************************
>
>Page 282, "Winning Ways" Vol 2
>
>--
>Mark Biggar
>mab@wdl1.wdl.loral.com
>

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

----------------------------------------------------- BM
brianm@cbme.unsw.edu.au
From: fraserc@dcs.glasgow.ac.uk (Campbell Fraser)
Newsgroups: comp.theory.cell-automata
Subject: Re: Undecidability of configurations/progression
Date: 9 Nov 92 13:00:14 GMT
Organization: Glasgow University Computing Science Dept.

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

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

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

Of course the problem is probably intractable.

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

Campbell



-- 
Hi, I'm a .signature virus. Copy me to yours and then wipe all your files.
Campbell Fraser: fraserc@dcs.glasgow.ac.uk
Computing Science Department, University of Glasgow, Glasgow G12 8QQ
From: hurd@math.gatech.EDU (Lyman Hurd)
Newsgroups: comp.theory.cell-automata
Subject: What is Garden of Eden?
Date: 7 Nov 92 22:08:35 GMT
Distribution: inet
Organization: The Internet


   Date: 2 Nov 92 15:50:48 MST
   From: tolman%asylum.cs.utah.edu@cs.utah.edu (Kenneth Tolman)
   Organization: University of Utah, CompSci Dept
   Newsgroups: comp.theory.cell-automata
   Sender: ca-request@Think.COM

   What is the Garden of Eden?  What was Moore's theorem about these 
   configurations?

   I have been assuming that a Garden of Eden configuration is some state which
   can only exist during the first time interval of a CA.... such as a 
   grid of entirely on cells for the game of life.  Is this a correct
   intepretation?  Are there important implications for these configurations?


This is correct.  Specifically if the state space of the CA is X and the
rule represented by a global function F: X --> X, then a configuration c in
X is a GOE if and only if c in X - F(X).

From my own persppective, what are interesting are the complements of the
GOE's.  or a physical system, it seems reasonable to assume that it is in
steady state and therefore one assumes that even if the dynamics are
irreversible one can assume that an observed state has a semi-infinite
sequence of predecessors (by no means unique).

In one dimension, the GOE's for a given iteration (those configurations
which can occur at time step N but not at time step N+1) collectively form
a recursively enumerable set (in a sense made precise in the paper cited
below but which can be explained if asked).

In [1]  showed that the set need not be recursive.  Hence it was undecidable
whether a given configuration was GOE for ALL n although it IS decidable in
1-D for a specific N.  The question in 2-d is actually somewhat easier
because less is true.  The undecidability of the Tiling problem (Berger's
Theorem) has wide-ranging implications for 2D CA.

I thought I would throw this in since I assume that my perspective is
fairly peculiar in this regard.  The notation comes from Moore's Garden of
Eden Theorem for which I hope someone will jump in with a reference.  Also
there are some papers of Golze which generalize the problem in several
ways.  Once again I will try to dig up references but other people shoould
feel free to jump in.

Hope this helps,

Lyman Hurd
Iterated Systems, Inc.
harel
Newsgroups: comp.theory
Subject: "Algorithm"
From: harel@nufar.wisdom.weizmann.ac.il (Harel David)
Date: Thu, 12 Nov 1992 13:19:58 GMT
Organization: Weizmann Institute of Science, Computation Center



Roll over, al-Khowarizmi!!   I just heard this great new explanation
of the word "algorithm" (due to Fred Landman, a linguistics professor
at Cornell):


 "an Al Gore rhythm is what Bill Clinton plays on the saxophone"


David Harel
Dept. of Applied Mathematics and Computer Science
The Weizmann Institute of Science, Rehovot 76100, ISRAEL
email:  harel@wisdom.weizmann.ac.IL
Newsgroups: comp.theory,sci.math
From: thompson@atlas.socsci.umn.edu (T. Scott Thompson)
Subject: Re: Uniform noise in a d-sphere
Reply-To: thompson@atlas.socsci.umn.edu
Organization: Economics Department, University of Minnesota
Date: Fri, 6 Nov 1992 18:03:53 GMT

murphy@sscdaq.phy.bnl.gov (Michael Murphy) writes:


>I am trying to compute uniformly random noise inside a d-dimensional 
>sphere.  I have identified two ways of doing so:

[stuff about how to generate uniform noise deleted.]

>I believe that method two works.  However, when I project a large number of
>points in a high dimensional space (e.g. 25) onto the plane (by ignoring all
>but two coordinates), I get something that resembles a square.  My advisor
>is not so sure that this is correct and I can only give an intuitive
>argument as to why it may be true.

>Consider a set of 10,000 points inside a ball (3-d).  Projecting this ball
>into the x,y plane, one would expect to see something whose convex hull
>resembles a circle, but with more points in the middle than on the sides
>because the ball is fatter in the middle.  

>I claim that as the dimension increases, one would expect this middle section
>to get more and more dense, with the bulk of the points falling inside the
>largest square inscribable in the circle.  I would like to try the Monte Carlo
>method as a sanity check, but it take too long to generate points in a high
>dimensional space.

Other posters have commented on the validity of the generation
methods, but I haven't yet seen any response to this argument about
how to check the output.

I think that your claim is invalid.  If your distribution on the unit
ball is radially symmetric, as the uniform distribution must be, then
so should be the "projection" that you describe.  That is, the
distribution of (x_1,x_2) should be unaffected by rotations of R^d.
But some rotations of R^d correspond exactly to rotating (x_1,x_2) in
the plane, leaving other coordinates invariant.  So your projection to
R^2 should be invariant to rotations of the plane.  Clearly a square
does not satisfy this criteria, so your claim cannot be correct.
--
T. Scott Thompson              email:  thompson@atlas.socsci.umn.edu
Department of Economics        phone:  (612) 625-0119
University of Minnesota        fax:    (612) 624-0209
From: taylor@tivoli.com (Eric Taylor)
Newsgroups: comp.theory
Subject: Is this an Np-Complete Problem
Date: 14 Nov 92 03:29:57 GMT

This is a fairly practical problem but is probably
a good exercise:

Suppose I have "n" rectangles of varying width.
I want to fit them into another rectangle of constant
width called "W" and infinite height.
I want to lay these rectangles into a matrix in
Row-Major order where the difference between the
total width of the columns and "W" is at a non-positive minimum.
The rectangles will form columns (you can't just pack
rectangles in until they don't fit).

Is there a polynomial solution to this problem?
If you pick a number "c" for the
number of columns, it is concievable that a larger
value of "c" could result in a smaller width.
Am I wrong in this assumption?  If I am wrong
then a simple binary search for the optimal "c" will
work.  (n log n for the total problem).
Newsgroups: comp.theory
From: wft@math.canterbury.ac.nz (Bill Taylor)
Subject: Re: Human Computers....
Organization: Department of Mathematics, University of Canterbury
Date: Sun, 8 Nov 1992 23:09:18 GMT

|>  I'm looking for examples in fiction literature
|> of super sophisticated communicative computers a la HAL.

The classic example, very like HAL, is the computer in 
"The Moon Is a Harsh Mistress", by Robert Heinlein.

Incidentally, this book is worth reading, not just for the relationship
between the hero and the computer, but also for the marvellous sense of
realism engendered by the thickness of the peripheral details and comments;
a thickness sadly lacking in most science fiction.
---
      CB CB CB CB
---
Bill Taylor
Newsgroups: comp.theory
From: matwesx@gsusgi2.gsu.edu (William E. Sadler)
Subject: Re: Human Computers....
Organization: Georgia State University
Date: Sun, 8 Nov 1992 14:48:55 GMT

sahle@csgrad.cs.vt.edu (Eskinder Sahle) writes:

>Hello all:

>I need some help....  I'm looking for examples in fiction literature
>of super sophisticated communicative computers a la HAL. That is,
>computers that talk and communicate like humans.  I'm not so much 
>interested in those instances where it's a robot that cannot be
>distinguished from a human being as in computers sounding human without
>being almost totally human-like....  .

Ahmed,

Try Robert A. Heinlein's "The moon is a harsh mistress"  -  You get to follow
a super computer from its waking day to its dissolution.


-- 
/**************************************************************************/
/* William E. Sadler          |       Internet: matwesx@gsusgi2.gsu.edu   */
/* 717 Stephenson Ridge       |               : acmwes@gsusgi2.gsu.edu    */
/* Stone Mountain, GA  30087  |               : 71005.1241@compuserve.com */
/* (404) 413-1957             |            CI$: 71005,1241                */
/*------------------------------------------------------------------------*/
/* Who beat their swords into plowshares, will plow for those who don't   */
/**************************************************************************/
From: burt@aupair.cs.athabascau.ca (Burt Voorhees)
Newsgroups: comp.theory
Subject: Re: Human Computers....
Date: 8 Nov 92 02:50:22 GMT

sahle@csgrad.cs.vt.edu (Eskinder Sahle) writes:

>I need some help....  I'm looking for examples in fiction literature
>of super sophisticated communicative computers a la HAL. That is,
>computers that talk and communicate like humans.  I'm not so much
>interested in those instances where it's a robot that cannot be
>distinguished from a human being as in computers sounding human without
>being almost totally human-like....  .

There is lots of this in science fiction.  The Asimov robot stories are
classics, and Heinlein has many computers who could pass off as human:
particular books that come to mind are The Moon Is A Harsh Mistress;
Time Enough For Love; The Cat Who Walked Through Walls; To Sail Beyond
The Sunset.  You might also get a kick out of Zelazny's Creatures of Light
and Darkness.
bv
Newsgroups: comp.theory
Subject: Re: Synthesizing loop invariants -- unsolvable?
From: jeremy@cs.aukuni.ac.nz (Jeremy Gibbons)
Date: Fri, 6 Nov 1992 05:35:49 GMT
Organization: Computer Science Dept. University of Auckland
Cc: jeremy@cs.aukuni.ac.nz

In <1992Nov5.230648.23466@babbage.ece.uc.edu> dsims@don.ece.uc.edu (David Sims) writes:

>I've been thrashing about with the problem of automatically generating
>loop invariants for the purposes of program verification.  Is the general
>case of automatically synthesizing a loop invariant for any given loop
>unsolvable?
>
>I suspect it is but cannot come up with a proof.  Any help would be
>appreciated.

Of course it's solvable; "true" is an invariant of every loop. :-)

Seriously, the halting problem reduces to finding a *variant*, so you can't
write a program to find variants. Presumably the question you meant to ask
was, is the problem of finding an invariant sufficiently strong to
establish a given postcondition, assuming termination, computable? (This is
equivalent to checking partial correctness of while-programs, right?) My
intuition is also that it is uncomputable, but I too can't come up with a
proof off the top of my head.

Jeremy

---
Jeremy Gibbons <jeremy@cs.aukuni.ac.nz>         tel: +64 9 373 7599
   Department of Computer Science,              fax: +64 9 373 7453
   University of Auckland, Private Bag 92019, Auckland, New Zealand.


Newsgroups: comp.theory
From: kolount@cauchy.stanford.edu (Mihail N Kolountzakis)
Subject: Is the following problem in NP?
Originator: kavraki@Xenon.Stanford.EDU
Keywords: NP, polynomials, equations, solvability
Organization: CS Department, Stanford University, California, USA
Date: Tue, 10 Nov 1992 08:45:11 GMT


INPUT: a polynomial F(x_1, ... , x_N) of bounded degree (say 10)
and integer coefficients (also bounded by say 100).

OUTPUT: YES iff there are _real_ numbers x_1, ... , x_N that satisfy F=0.

Please reply to "kolount@cauchy.stanford.edu".

Mike Kolountzakis
From: billj@astro.ocis.temple.edu (Bill Jones)
Newsgroups: comp.theory
Subject: Re: Human Computers....
Date: 13 Nov 92 14:26:38 GMT
Organization: Temple University
X-Newsreader: Tin 1.1 PL5

Eskinder Sahle (sahle@csgrad.cs.vt.edu) wrote:
: Hello all:
: 
: I need some help....  I'm looking for examples in fiction literature
: of super sophisticated communicative computers a la HAL. That is,
: computers that talk and communicate like humans.  I'm not so much 
: interested in those instances where it's a robot that cannot be
: distinguished from a human being as in computers sounding human without
: being almost totally human-like....  .
: 
: Thanks in advance.
: Ahmed 


I'm not sure how informative it would be, but an entertaining suggestion would
be ME by Thomas T. Thomas.

BJ.
Newsgroups: comp.theory
From: marcel@ADS.COM (Marcel Schoppers)
Subject: Re: #nodes in avg.tree of given depth?
Keywords: binary tree size
Organization: Advanced Decision Systems, Mtn. View, CA (415)960-7300
Date: Thu, 5 Nov 1992 22:49:38 GMT

>In article <96222@netnews.upenn.edu> rymon@linc.cis.upenn.edu (Ron Rymon)
>  writes:
>I second the naturality of random (uniformly distributed) binary trees of
>depth at most d. However, the analysis of the NUMBER of such trees suggest
>a way to draw such trees.

Hmmm, OK...  Here's what I'm up to.  I'm doing an analysis of the expected
size of a certain kind of program that happens to be analyzable as a
decision tree.  Hence binary trees are a suitable abstraction of those
programs.  Read program size as number of nodes in the corresponding tree.
We are told the number of world-states (or objects) that the decision tree
must classify; call that number W.

It can be shown that on average (uniform distribution over all possible
partitions of W objects) the W states to be classified will fall into
O(W/log W) classes, i.e. that's how many leaves the binary tree should have.
Hence we immediately know how many internal nodes it has.  Further, we also
know (from Knuth) that the expected height/depth of the tree is
	D = O( sqrt(W / log W) )

However, the real classification programs I am dealing with turn out to be
very much smaller, i.e. they are not average, and I've managed to prove
mathematically that the cause of their small size is that the programs contain
dynamically bindable variables.  That results (at least for some domains I
have analyzed) in trees that have
	O( (log W / loglog W)^P )
leaves, where P is something small like 2 or 3.

So, now I have an average-case estimate (way too large) and some actual-case
figures (much smaller) and the restriction causing the difference (the
existence of variables in the programs being modelled), and now want to find
a way to do an average-case analysis for the *restricted* set of programs.

It turns out that the presence of variables in my programs has the following
effect on tree structure:  the depth of the trees stays about the same, but
the trees become much thinner "horizontally" because the variables effectively
allow to replace a list of identical subtrees by only one such subtree (OK, so
the depth of the list decreases by the number of subtrees in the list minus 1).

Hence, my first idea was to find out the number of nodes in the average tree
of a fixed depth D.  The answer, O(2^D), for D = O( sqrt(W / log W) ) as above,
would give me N = O(2 ^ sqrt(W / log W)) nodes, which is way too big, and so
reveals that indeed, the restricted set of thinned trees I'm concerned about
is very far away from being a uniformly distributed set of trees with depth D.

Obviously, I need to come up with a suitably restricted set of binary trees,
and then figure out the expected number of nodes in that set as a function of:
the known depth, the number of subtrees in each list, and the density (and
placements?) of such lists.  (Such lists can be nested, i.e. a subtree in a
list can contain another list.)

Marcel
From: diderich@di.epfl.ch (Claude Diderich)
Newsgroups: comp.theory
Subject: How to obtain a report from UCSC?
Date: 13 Nov 92 21:18:56 GMT
Reply-To: diderich@di.epfl.ch (Claude Diderich)
Followup-To: dierich@di.epfl.ch
Organization: Ecole Polytechnique Federale de Lausanne

Hi,

Does anybody know how to join any of the authors of the following report
or how to obtain a copy of it.

P.G.Kolaitis, M.N.Thakur, "Logical definability of NP optimization
problems", Tech.report UCSC-CRL-90-48, Board of Studies in Computer and
Information Sciences, University of California at Santa Cruz.

Thanks in advance,
Claude

 
---------------------------------------------------------------------------
Claude G. Diderich                            Internet: diderich@di.epfl.ch
30, Avenue S.Reymondin  --  CH-1009 Pully (VD)  --  Switzerland  --  Europe

``Imagination is more important than knowledge''            Albert Einstein
---------------------------------------------------------------------------
From: schuch@phx.mcd.mot.com (John Schuch)
Subject: Re: Human Computers....
Organization: Motorola Computer Group, Tempe, Az.
Date: Wed, 11 Nov 1992 13:32:59 GMT

In article <3739@creatures.cs.vt.edu> sahle@csgrad.cs.vt.edu (Eskinder Sahle) writes:
>Hello all:
>
>I need some help....  I'm looking for examples in fiction literature
>of super sophisticated communicative computers a la HAL. That is,
>computers that talk and communicate like humans.  I'm not so much 
>interested in those instances where it's a robot that cannot be
>distinguished from a human being as in computers sounding human without
>being almost totally human-like....  .

Don't forget COLOSUS, the computer from "The Forbin Project". If you
liked the movie, hit your local old book store and find the novel and
its two sequals.

John

-- 
| ONE LINE NOVEL: She backed away from the corpse slowly, not so much out  |
| of fear, but simply unsure of what the crowd expected her to do with it. |
+--------------------------------------------------------------------------+
| John R. Schuch  -  Motorola Computer Group  -  Manufacturing Engineering |
Newsgroups: comp.theory
From: bs@gauss.mitre.org (Robert D. Silverman)
Subject: Re: Uniform noise in d-sphere
Organization: Research Computer Facility, MITRE Corporation, Bedford, MA
Date: Fri, 6 Nov 1992 20:23:48 GMT

In article <thompson.721070817@daphne.socsci.umn.edu> thompson@atlas.socsci.umn.edu writes:
:jcbhrb@nic.cerf.net (Jacob Hirbawi) writes:
:
:>In sci.math <1992Nov5.211723.26238@bnlux1.bnl.gov>
:>Michael Murphy <murphy@sscdaq.phy.bnl.gov> writes:
:
:>> I am trying to compute uniformly random noise inside a d-dimensional 
:>> sphere.  I have identified two ways of doing so:
:>>
:>> [...]
:
:>A third method might be the following: use spherical coordinates and
:>pick uniform random numbers for each of the coordinates with the appropriate
:>ranges. In three dimensions this would be:
:
:>   (1) radius  uniform over (0,d)
:>   (2) angle1  uniform over (0,2 pi)
:>   (3) angle2  uniform over (0,  pi)
:
:>This seems to be *too* simple but since I can't think of any point within the
:>sphere being more favored than any other point I would think that the 
:>distribution is in fact uniform. 
:
:This does _not_ produce a uniform distribution since (2) and (3) do
:not generate a uniform (on the sphere) distribution of directions.

Somewhat more technically, it is clear that (r, theta1, theta2) all uniform
do not yield a uniform distribution. To see this just look at the Jacobian
of the transformation to Cartesian coordinates. It produces a non-linear
map to (x,y,z), so if (r,theta1,theta2) are uniform (x,y,z) are not.

If this still isn't clear, look at 2 dimensions (r, theta) --> (x,y)
means  x = r cos theta,  y = r sin theta.  It is clear that even if 
theta being uniform resulted in cos theta being uniform (it does not),
one would have that x was the PRODUCT of two uniform r.v.'s. and this
is definitely not uniform.

Check any elementary book on statistical theory, e.g. Hogg & Craig, 
or Mood, Graybill, Boes.

--
Bob Silverman
These are my opinions and not MITRE's.
Mitre Corporation, Bedford, MA 01730
"You can lead a horse's ass to knowledge, but you can't make him think"
Newsgroups: comp.theory
From: alopez-o@neumann.uwaterloo.ca (Alex Lopez-Ortiz)
Subject: Re: Random generation of simple polygons
Organization: University of Waterloo
Date: Mon, 9 Nov 1992 20:58:30 GMT

In article <1992Nov9.123707.12110@kum.kaist.ac.kr>,
flow@gayakum.kaist.ac.kr (Paek In-Hyeok) writes:
> 
> Hi!
> I'm looking for papers, source code, or refernces to random
> generation of simple polygons.
> If anyone could e-mail me, I would greatly appreciate.

I've done some work on this area (together with some friends) and
what it really boils down to is :

What distribution are you looking for?

Say do you want to generate n vertex polygons or polygons with expected 
number of vertices n (under normal distribution)?

Say you are generating rectangles, are you looking for a uniform 
distribution on the position of the corners, or for a uniform distribution
on the area of the rectangle?


It really depends on what you have in mind..


Alex

-- 
Alex Lopez-Ortiz                              alopez-o@maytag.UWaterloo.ca
Department of Computer Science                      University of Waterloo
Waterloo, Ontario                                                   Canada
Newsgroups: comp.theory