HDTenEightyP/NetNews huggingface dataset:
From: roger@triplex.socal.com (Roger Knobbe)
Date: 7 Jan 93 15:35:42 GMT
Newsgroups: comp.theory.cell-automata
Subject: Re: WireWorld circuitry.
Distribution: inet
Organization: ICS Triplex, Torrance CA

In article <9301040445.AA20227@Early-Bird.Think.COM> MCINTOSH@unamvm1.dgsca.unam.mx ("Harold V. McIntosh") writes:
>Nikos I Nassuphis <ninassup(at)ATHENA.MIT.EDU> inquires:
>-
>> I just finished implementation of WireWorld, and I wonder
>> if there are any interesting circuits out there that I
>> could try it on...
>-
>The closest Wireworld comes to boolean constants are pulse trains, so the
>place to begin is first with clocks, then with the traditional boolean

Ok, I figured out a couple of simple oscillators, e.g.
  -
 =#=
  -
with a period of 3,

and
  -
 = #
  =
with a period of 4.

>functions, finally create delays, and crossovers. From then on, it is just

and I figured out delays (sort of) by just varying the lengths of wire
from various contacts on a clock to get 3 staggered pulses from a single
oscillator.

However, I haven't figured out the more sophistcated circuits, yet.  Can
anybody give me some tips?  Is there a better wire-world than the wire-pc.c
program that shows up on archie?

rog.
Newsgroups: comp.theory.cell-automata
From: mab@wdl39.wdl.loral.com (Mark A Biggar)
Newsgroups: comp.theory.cell-automata
Subject: Re: 1D computation-universal CAs
Date: 11 Jan 93 23:31:01 GMT
Organization: Loral Western Development Labs

In article <hmasum.726528479@cunews> hmasum@alfred.carleton.ca (Hassan Masum) writes:
>What classes of 1-dimensional CAs have been shown to be capable of
>supporting universal computers?  I've read about 2 or 3 specific
>examples, but I'm more interested in any general results.  Also it
>would be nice to know the 'simplest' 1D CA so far discovered with this
>property.
>Any answers, pointers, etc welcome!

There is an obvious transformation of a N state by M symbol turing machine
into a N+M state 1D CA with a neighbor of size 4.  Most of the 1D CA is used
to similate the turing machine tape with one cell simulating the turing 
machines head and internal state.  All cells except the head cell and the 
cell imediately to its left and right are quiesent.  Those two cell are 
active and only depend on the states of themselves, the cel to the left and 
the 2 cells to their right.  Given the 7 state by 5 symbol universal turing 
machine in "Finite Machines" by Minsky, that shows the existence of a 12 
state size 4 neighborhood 1D CA that is universal.  

You can get a CA with a neighborhood of size 3 by using (N+1)*M states, 
where again most of the CA simulates a tape, but one cell must encode both 
a tape space and the machine state.  

There are also methods of encoding a N state 1D CA into a binary 1D CA with 
a much larger neighborhood by using more then one cell in the new CA to 
simulate a cell in the original CA and expanding the neighborhood accordingly.
For example, supose you have a 4 state 3 neighborhood 1D CA with states
{A, B, C, D}.  If we use the codes {000,100,010,001} to encode those states,
we can lay out a CA like so:

     ...10ddd0110ddd0110ddd0110ddd0110ddd01...
                      aaaaaaa
                bbbbbbbbbbbbbbbbbbb

where the cells marked 'a' simulate a cell in the original CA, the 'd's are one
of the above codes and the 'b's delineate the neighborhood.  The sequence 0110, 
which cannot appear in any of the state encodings, acts as a registration 
mark to show where the simulated cells are.  Using this method, the described 
universal 1D CA above, when transformed into a binary CA, would require a 
neighborhood size of 58 cells.

--
Mark Biggar
mab@wdl1.wdl.loral.com
From: reeds@alice.att.com (Jim Reeds)
Newsgroups: comp.theory
Subject: Re: P=NP; the proof
Summary: Not!
Keywords: Collapse of hierarchy
Date: 6 Jan 93 22:40:53 GMT
Article-I.D.: alice.24563
Distribution: inet
Organization: AT&T Bell Laboratories, Murray Hill NJ



Mike Robson writes

> Who can shoot down this alleged proof that P=NP?
  [...]
> Claim 2: If T is a solution to $LP$, it covers a permutation vector
> $Q sub pi$.

Maybe I can.  The T matrix displayed in section 3 of Gismondi and Swart's
isomorphism paper (sept 1992) covers no permutation vector.  (There
are only 24, so you can check by brute force, if you want.)

Claim 2, if true, would imply that the feasible region for Robson's
linear programming problem had precisely the set of permutation vectors
as its extreme points.  This is clearly out of step with the discussion
in G&S section 3.  I think G&S introduce their whole rigamarole of U vectors
and actions of permutations on triples of symbols to get around this
problem.

Newsgroups: comp.theory
From: jamie@cs.sfu.ca (Jamie Andrews)
Subject: Benj. C. Pierce address / _Basic Cat. Theory_ errata?
Organization: CSS, Simon Fraser University, Burnaby, B.C., Canada
Date: Tue, 5 Jan 1993 00:16:31 GMT

     Does anyone know of an e-mail address for Benjamin C. Pierce,
or know if a list of errata has been published for his book _Basic
Category Theory for Computer Scientists_ (MIT Press, 1991)?

thanks
--Jamie.
  jamie@cs.sfu.ca
From: serdar@fawlty8.eng.monash.edu.au (Serdar Boztas)
Subject: Re: Hamming codes algorithm needed
Organization: Monash University, Melb., Australia.
Date: Tue, 12 Jan 1993 05:40:07 GMT

chchmeds@otago.ac.nz writes:

>I need an algorithm to solve the following problem:

>Find a set of 32-bit binary numbers such that the Hamming distance
>between every pair of them is (at least) a given constant (say 16).
>We can stop finding numbers after we have 256 of them, but not before.

>The Hamming distance between two numbers is the number of bits in which they
>differ. 

>It is easy enough to get two numbers which differ in 16 positions. Getting
>a third which differs from *both* the previous two is a little more
>time-consuming, but not much.  But after 20 of them, it gets very sluggish
>indeed using a brute-force ("pick a random nunmber and try it") technique.

The problem you described is very hard to solve in general. There are
some bounds on the maximum number of codewords that a code may have
given a length and minimum hamming distance. I recommend looking
at chapter 17 of MacWilliams & Sloane, 'The Theory of Error Correcting
Codes' for a start.

Since I have the book handy, for your specific problem, Theorem 11 of
that chapter states that 'Provided suitable Hadamard matrices
exist, (i.e. not in general, but in fortunate cases, which n=32
is one) then

	A(4*d,2*d)=8*d

where

	A(n,d') = maximum number of codewords of any code with
                                                 ^^^ 
		 length n and minimum distance d'

while in your case

	n=4*d=32 ==> d=4

directly implies that the most codewords you can have is 8*d=64,
not 256 as you wanted.

>You may recognize such a set of numbers as a Hamming code. There are
>well-known methods for generating Hamming codes of distance 3 to 6; 
>unfortunately they don't generalise to other distances.

Such a set of numbers is just a binary code, a Hamming code is a
specific type of binary code. The term 'Hamming distance' is what
confuses people at first.

>Gordon
>Gordon Findlay
>Christchurch School of Medicine
>Gordon@chmeds.ac.nz

Serdar
>chchemds@otago.ac.nz
-- 
Serdar Boztas 
serdar@fawlty8.eng.monash.edu.au
From: diderich@di.epfl.ch (Claude Diderich)
Newsgroups: comp.theory
Subject: Re: Suggstion: (was: Re: P=NP; the proof)
Keywords: Collapse of hierarchy
Date: 12 Jan 93 12:53:11 GMT
Organization: Ecole Polytechnique Federale de Lausanne

In article <gordon.726823495@ningaui>, gordon@cs.uwa.oz.au (Gordon Royle) writes:
> In <pcw.726468672@digex> pcw@access.digex.com (Peter Wayner) writes:
> 
> >core of the problem. We already have neat algorithms that get close to
> >the right answer on NP-complete problems like the travelling salesman.
> >For all practical intents and realistic purposes, this is enough.It's
> >really just an academic question now.
> 
> 
> Is this true? I am not aware of any decent algorithms for Travelling 
> Salesman at all. In fact G&J show that there cannot be any polynomial
> time approximation algorithms for Travelling Salesman that achieve
> ANY given multiple of the optimal solution (page 147).   
> Does this not contradict the above statement, or am I labouring under a 
> delusion? 
> 
> 
> Gordon
Peter Wayer's statement is not true. We do have algorithms that give in general
good solutions for the TSP, but we cannot say anything about the quality in
general of any solution produced. Indeed such algorithms may in 95% of the cases
approach the optimal solution by 90%. But we cannot guarantee 100% of the cases.
Furthermore, we do not have any possibility to check if a given solution is
within the 95% of good solutions or not.

But TSP is not the only NP-complete problem. There are other problems like Max
Clique that even cannot be approximated within any constant, e.g. approxiating is
as hard as solving.

Therefore I think the P?=NP question is not ony of theoretical interesed.

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: alpope@skids.Eng.Sun.COM (Alan L. Pope)
Newsgroups: comp.theory
Subject: Re: PROTOLO A FUTURISTIC OBJECT-CODE FORMAT
Date: 7 Jan 93 18:45:54 GMT
Reply-To: alpope@skids.Eng.Sun.COM
Organization: Sun Microsystems, Inc.
NNTP-Posting-Host: skids

In article 15335@csi.uottawa.ca, cbbrowne@csi.uottawa.ca (Christopher Browne) writes:
>
>This sounds very much like some languages that already exist:

>The basic idea was that they generated compiler front ends (very
>similar to the GCC idea described above) that would produce as output
>a "machine independent" language.  In this case, it was a "stack
>oriented" language.  (FORTH and PostScript are examples of stack
>oriented languages, but have many more op-codes than Tanembaum's
>system.)

Not that it matters much but Digital Research had a lot of Hype out in the
early 1980's (82?) about the Universal Compiler.  Basically the same thing.
The idea is very much older than even that.
Newsgroups: comp.theory,comp.compilers
From: levine@jadoube.mcs.anl.gov (David Levine)
Subject: Approximation algorithm paper
Organization: Argonne National Laboratory, Chicago, Illinois
Distribution: comp.theory
Date: Mon, 11 Jan 1993 22:55:42 GMT

Could someone provide a reference (or email address of an author(s)) to the
work by S. Arora, M. Sudan, R. Motwani, C. Lund, and M. Szegedy mentioned in
New Scientist 12/12/92:  "Their result implies that if P != NP, then there is
a threshold beyond which it is just as hard to find a good approximation
algorithm that will always work as it is to find a good solution."

Thanks --dave

Newsgroups: comp.theory
From: karr@cs.cornell.edu (David Karr)
Subject: Re: Looking for random permutation generation algorithms
Organization: Cornell Univ. CS Dept, Ithaca NY 14853
Date: Thu, 7 Jan 1993 16:59:39 GMT

In article <1993Jan6.014749.15323@ee.ubc.ca> rayw@ee.ubc.ca (raymond w m woo) writes:
>Hi, does anyone know, or can provide any pointer in the literature to, any 
>random permutation generation algorithm that can be easily implemented as a 
>function in a computer program?  
>
>Ideally, this function would be computationally effective, and the input 
>that this function takes would be some kind of index/rank number of the
>permution to be generated.  

How about the following (I am trying to generate all permutations of the
integers 1, ..., N):

Start with an array v[1..N] with v[i]=i for each i.  The input is an
integer k from 1 to N! (N factorial).  Set t=N (highest entry in v)
and p=0 (first open slot in output array w[1..N]).

Now for b = N down to 2, take i = k mod b.  Copy v[i] to w[p],
increment p, copy v[t] to v[i], decrement t.  Essentially this has
just removed the i-th element of v, adding it to the output and
shrinking v accordingly.

When this is done there will be only one unused element left in v, at
v[1].  Copy it to w[N].

The running time of this algorithm should be approximately
proportional to N.

This should produce all N! possible orderings of the integers 1,...,N,
and any input in the legal range produces a unique permutation.  If
you like you can replace the integers 1 to N in array v with some
other data that you wish to permute, but the permutations will be
unique only if your data contains no duplicates.

-- David Karr (karr@cs.cornell.edu)
From: steven@cogsci.ed.ac.uk (Steven Bird)
Newsgroups: comp.theory
Subject: NFA -> Regexp mapping
Date: 11 Jan 93 12:55:51 GMT
Organization: Centre for Cognitive Science, Edinburgh, UK

Does anyone know if there are any algorithms for converting an NFA
into a (preferrably compact) regular expression?  Please reply by mail
and I'll summarise to the net.

-- 
Steven Bird.            <Steven.Bird@edinburgh.ac.uk>
University of Edinburgh, Centre for Cognitive Science
2 Buccleuch Place, Edinburgh  EH8 9LW, Scotland, U.K.
Telephone: (031) 650-4421/4432.  Fax: (031) 650-4587.
From: dgg900@anusf.anu.edu.au (David G Green)
Newsgroups: comp.theory
Subject: Re: Computatibility and Chaos
Date: 5 Jan 1993 01:03:32 GMT
Organization: ANU Supercomputer Facility
Distribution: world
NNTP-Posting-Host: 150.203.5.2
Keywords: Computatibility Chaos
Originator: dgg900@anusf


Raj Patil writes 

> Does anyone know of any work done in the area of Chaos and Cumputability.

See, for starters ...

Langton, C. (1990). Computation on the edge of chaos. 
Physica D 42(1-3), 12-37. 

Langton, C. (1992). Life on the edge of chaos. 
In "Artificial Life II" (ed. C.Langton et al.) 
Addison-Wesley, New York. 

Newsgroups: comp.theory
From: schweika@unipas.fmi.uni-passau.de (Andreas Schweikardt)
Subject: dynamic and static separators
Organization: University of Passau, Germany
Date: Sat, 9 Jan 1993 15:26:21 GMT

Hi,

I have a problem (and want it solved ;-)):

Does anyone know the relationship between the two versions of 
graph separators ?

Keywords: separator, vertex separator, pathwidth, node search number

Thomas Lengauer described in his article "Black-White Pebbles and 
Graph Separation" (Acta Informatica 16, 465-475 (1981))
the well-known "static" version of graph separators and he introduced
a "dynamic" version.

Can anyone give me a hint to the relation between the "dynamic" and the
"static" separator ?

The static version:

An undirected graph G=(V,E) with n vertices has a f(n) separator iff
V can be separated in three disjunct sets A, B and S, A and B have 
no edges in common, (1/3)n <= #A <= (2/3)n, (1/3)n <= #B <= (2/3). 
S contains no more than f(n) vertices. A and B have also a 
f(n) separator (recursively applied on A and B).


The dynamic version: 

I give here T. Lengauer's definition:
"... The above definition of a separator is a 'static' one. We will here
define a corresponding(*) 'dynamic' notion of a separator. The definition
will be in terms of a pebble game on undirected graphs called the Vertex
Separator Game (VSG).
The VSG is played on undirected graphs G according to the following rules.

(i)   All vertices start out pebble-free.
(ii)  All vertices end up pebbled.
(iii) A move consists of placing a pebble on a pebble-free vertex.

The Vertex Cut after the i-th move consists of all vertices that are pebble-
free and adjacent to a pebbled vertex after the i-th move. Let S be a
strategy for VSG on G [G is the graph], i.e. a permutation of the vertices 
of G that represents a sequence of moves (applications of rule (iii)) in
VSG. ..."
(*) Well, that's my problem "corresponding".

And the vertex cut of a strategy is the maximum vertex cut after every move.
The dynamic or vertex separator is the minumum vertex cut of all strategies
for the graph.
Related graph theoretic topics are the node search number and pathwidth
of an undirected graph. 
That is  node search number -1 = pathwidth = dynamic separator.

Is it possible to transform a "static" to a "dynamic" separator and 
vice versa ?

Please send any ideas or hints to my address. Thanks ! 
Email-address: schweika@trillian.fmi.uni-passau.de

Thank you
                Andreas Schweikardt
-- 
Andreas Schweikardt * Ingling 17 * 4784 Schardenberg * Austria
                    trillian@fmi.uni-passau.de
From: pcw@access.digex.com (Peter Wayner)
Newsgroups: comp.theory
Subject: Re: Suggstion: (was: Re: P=NP; the proof)
Date: 8 Jan 93 04:51:12 GMT
Organization: Express Access Online Communications, Greenbelt MD USA
Distribution: inet
NNTP-Posting-Host: access.digex.com
Keywords: Collapse of hierarchy

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


>Second, test the thing out before publicising it, by running the algorithms on
>actual cases and then using these test cases to exemplify the algorithms when
>you do publicise them.

I believe G+S did this. But this is a difficult experiment to run. "Most"
3SAT formulas are easy to solve. The tricky ones are excedingly difficult
to find. And if you could find them (and prove you had a method for showing
these were guaranteed to be hard) you might be better off trying to
turn this procedure into a proof that P<>NP. 

What if the polynomial was O(n^6)? It would be hard to find data points
for complex cases as n got above 10. How would you know you had O(n^6)
performance and not just exponential time growth with a bit of error
thrown in? 

Although I think that every author of a P=NP proof should have a
running version of the algorithm, I still think it is hard to draw
many conclusions from this. It shows that the guy can construct
something that comes close, but it doesn't cut to the mathematical
core of the problem. We already have neat algorithms that get close to
the right answer on NP-complete problems like the travelling salesman.
For all practical intents and realistic purposes, this is enough.It's
really just an academic question now.


Newsgroups: comp.theory
From: pdc@dcs.ed.ac.uk (Paul Crowley)
Subject: Re: Probabilistic Turing Machines
Reply-To: pdc@dcs.ed.ac.uk (Paul Crowley)
Organization: Edinburgh University
Date: Sat, 9 Jan 1993 00:53:14 GMT

Quoting fischer-michael@cs.yale.edu (Michael Fischer) in article <1993Jan6.033354.4587@cs.yale.edu>:
>
>: 3) Assuming (2), are there any deterministic problems that have a lower
>: complexity for probabilistic Turing machines than deterministic ones?
>
>: 4) Is is known that there are no such problems?

>If I understand your questions, the answers to (2) and (4) are both
>trivially "no".

What happens if we ask only that the probability that the program fails
to complete within the lower time bound tends to zero as the size of the
problem tends to infinity?
  __                                _____
\/ o\ Paul Crowley pdc@dcs.ed.ac.uk \\ //
/\__/ "I'm the boy without a soul."  \X/
Newsgroups: comp.theory
From: neto@cs.toronto.edu (David Neto)
Subject: Re: P=NP; the proof
Organization: Department of Computer Science, University of Toronto
Distribution: inet
Date: 6 Jan 93 18:16:03 GMT

In article <1993Jan6.161440.25658@eng.cam.ac.uk> ptb@eng.cam.ac.uk (P.T. Breuer) writes:
>jmr@cs.anu.edu.au (Mike Robson) writes:
>> Who can shoot down this alleged proof that P=NP?
>> The ideas are taken from the Gismondi and Swart papers but the
>> algorithms are simplified and the proofs are completely new.
>> If you haven't read their papers, you will probably not follow this.
>> I'll post a more detailed version soon unless anyone has convinced
>> me I'm wrong (in which case I will post a retraction).
>> The following document is in eqn|troff -ms format and is
>> copyright (C) J. M. Robson 1993.
>> [troff omitted]
>
>For my own edification, I translated Mikes document into LaTeX.
>I added some comments to the proofs. I believe Mike made a serious
>mistake in the proof of 2, getting confused over left/right inverses of
>matrices -- the transformational view is much more helpful -- but I
>think I've mended it. Claims 1 and 2 seem to be proved now. I haven't
>checked 3 and 4. Are we getting closer to P=NP?
>

I just want to point out a couple of typos.

The first typo occurs in the P.T. Breuer's inserted comments in the proof
of Claim 2.
>[text omitted]
>So $S+x\delta S$ solves (\ref{C 1}) for any $x$. By slowly increasing
>the size of $x$ from zero and changing $N$ to $N+\delta N=M(S+x\delta S)$
>[text omitted]

I believe the above should read
	 "...changing $N$ to $N+\delta N=M^{-1}(S+x\delta S)$".
However, I don't follow his argument this when it is changed in this
way, but that may just be my own problem.

The second typo occurs in the proof of Claim 3.
>[text omitted]
>If $B_i =0$, then $T_i A =0$ and clearly also $Q_i A =0$ also
>since the positive elements of $Q_i$ are a subset of those of $A_i$.
>[text omitted]

The above should read "... are a subset of those of $T_i$."
Mike Robson's posting had this typo in it as well.  I _do_ follow this
argument when it is changed in this way.


In any case, this is an interesting development.


-- David Neto
neto@cs.utoronto.ca
Newsgroups: comp.theory
From: steve@hubcap.clemson.edu ("Steve" Stevenson)
Subject: Re: Real Numbers vs. Rational Numbers?
Organization: Clemson University
Distribution: inet
Date: Tue, 5 Jan 1993 18:33:18 GMT

boerncke@kirk.fmi.uni-passau.de (Frank-Roland Boernke) writes:

>So what does this mean in the end? When I introduced this subject, I asked,
>whether a Turing Machine, that handles not only bits or naturals but also 
>real numbers is more powerful, than a turing machine, that only works 
>with natural numbers. 

>My professor said, both types of Turing Machines are the same concerning
>their power of computability. I claimed that can't be true, refering to
>ideas  like the ones mentioned in the quotes at the beginning of this side.

>Who is right?

The Turing machine that puts a bit (1 or blank) in each square of its tape
and can represent the digits of \pi in base 2 and then multiplies them
does not terminate---your machine with its infinite capacity is different
from the conventional definition. Ergo, the difference is fundamentally a
philosophical difference. Hard core intuitionists would probably not accept
your machine as valid; hard core formalists would not see anything wrong.
This is an apples and oranges thing until you get some agreement on the
rules of the game.

-- 
===============================================================================
Steve (really "D. E.") Stevenson           steve@hubcap.clemson.edu
Department of Computer Science,            (803)656-5880.mabell
Clemson University, Clemson, SC 29634-1906
Newsgroups: comp.theory,sci.crypt,sci.math,rec.puzzles
From: mdm@math3.sma.usna.navy.mil (Mark D. Meyerson -- math  FACULTY <mdm@sma.usna.navy.mil>)
Newsgroups: comp.theory,sci.crypt,sci.math,rec.puzzles
Subject: Re: Looking for random permutation generation algorithms
Date: 8 Jan 93 21:33:46 GMT
Reply-To: mdm@math3.sma.usna.navy.mil (Mark D. Meyerson -- math  FACULTY <mdm@sma.usna.navy.mil>)
Followup-To: comp.theory

In article <1993Jan8.163909.20820@cs.cornell.edu>, karr@cs.cornell.edu
(David Karr) writes:
|> This is really the major omission from the algorithm.  I had meant
|> to compute both k mod b *and* k div b.  k mod b is used to index the
|> array for the current selection; k div b is then copied to k for the
|> next round.
|> 

I agree now.  This seems to be equivalent to the 
straightforward but perhaps harder to code recursive
method.  I've coded and checked Karr's algorithm
for N=1 to 6.
     Mark D. Meyerson
Newsgroups: comp.theory,sci.crypt,sci.math,rec.puzzles