HDTenEightyP/NetNews huggingface dataset:
From: an3842@anon.penet.fi
Subject: solution or information needed
Organization: Anonymous contact service
X-Anonymously-To: comp.theory
Date: Wed, 13 Jan 1993 00:18:39 GMT



Hello,

   Does anybody have the solutions to the exercises in the classic
computer theory book?  "Introduction to automata theory, languages, and
computation" by Hopcroft and Ullman in 1979.  If you have any, please
post your reply or send it to me by e-mail.  Thank you.

Enrico
  
-------------------------------------------------------------------------
To find out more about the anon service, send mail to help@anon.penet.fi.
Due to the double-blind system, any replies to this message will be anonymized,
and an anonymous id will be allocated automatically. You have been warned.
Xref: sparky comp.theory:2858 comp.programming:3443
From: chchmeds@otago.ac.nz
Newsgroups: comp.theory,comp.programming
Subject: Hamming codes algorithm needed
Date: 12 Jan 93 16:00:04 +1300
Organization: University of Otago, Dunedin, New Zealand

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.

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.

TIA for any pointers.
Gordon
---
Gordon Findlay
Christchurch School of Medicine
Gordon@chmeds.ac.nz
chchemds@otago.ac.nz
From: fischer-michael@cs.yale.edu (Michael Fischer)
Newsgroups: comp.theory
Subject: Re: Probabilistic Turing Machines
Date: 6 Jan 93 03:33:54 GMT
Reply-To: fischer-michael@cs.yale.edu (Michael Fischer)
Organization: Yale University Computer Science Dept., New Haven, CT 06520-2158
X-Newsreader: TIN [version 1.1az (for az) PL8]

Nick Maclaren (nmm1@cus.cam.ac.uk) wrote:

: Consider standard deterministic Turing machines with a fixed, finite program
: and an arbitrary input tape (i.e. the input is deemed separate from the
: program.  Consider probabilistic versions with the program extended to
: allow the generation of a true random bit.

: Clearly the second model is strictly more powerful than the first, but I
: am interested (for now) only in deterministic problems - that is ones
: where the output and termination (if any) depend solely on the input tape.

: 1) Is it known whether there are any deterministic problems that can be
: solved by probabilistic Turing machines but not by deterministic ones?

: 2) Is it known that there are no such algorithms?

: 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".  To say that a probabilistic machine's output and
termination depend solely on the input tape means that its behavior is
the same on all sequences of bits that might result from the random
bit generator.  In particular, its output and termination will be the
same on the sequence of all 0's.  By fixing each random bit to 0, it
is easy to convert the probabilistic Turing machine into an equivalent
deterministic one.

==================================================
| Michael Fischer <fischer-michael@cs.yale.edu>  |
==================================================
Xref: sparky comp.theory:2828 sci.crypt:6534 sci.math:17832 rec.puzzles:8283
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 14:47:30 GMT
Reply-To: mdm@math3.sma.usna.navy.mil (Mark D. Meyerson -- math  FACULTY <mdm@sma.usna.navy.mil>)
Followup-To: comp.theory

This method fails.  There is a minor error in that letting
p=0 and using modular arithmetic gives zero values outside
of the subscript range of the arrays.  This is easily 
patched.  But a major error is that  k mod b  won't 
distinguish between different k.  The first example of this
failure is for N=4 and k=4 or 16 (N!=24 so both k values occur.)
Then   k mod b  is the same for either  k  and for any
b  from  1  to  N .  Thus when  N=4  this algorithm repeats
certain permutations  (arrays  w ) and so misses some
permutations.
From: klaus@hal.nta.no (Klaus Gaarder FNI)
Newsgroups: comp.theory
Subject: Re: Probabilistic Turing Machines
Date: 6 Jan 93 14:14:49 GMT
Organization: Norwegian Telecom Research

Consult the paper

"Computational Complexity of Probabilistic Turing Machines" by John GILL,
SIAM J of Computing, vol 6, no 4, 1977.

THere are also numerous papers on the subject (or related to it) in the
cryptographic litterature on Zero-Knowledge Interactive Proof systems, documented
in eg Springer LNCS proceedings from CRYPTO and EUROCRYPT confs, and the ACM STOC
and FOCS proceedings of later years. Key authors are

	S. Goldwasser

	S. Micali

	C. Rackoff

	O. Goldreich

	A. Widgerson

	G. Brassard

	C. Crepeau

often in collaboration.

Klaus


*-------------------------------*
| Klaus Gaarder, cand. scient.	|
| Research Scientist		|
| Norwegian Telecom Research	|
| Po Box 83, N-2007 Kjeller	|
| Norway.			|
| Tel: +476 809871		|
| Fax: +476 810076		|
*-------------------------------*

-- 
    __o   
  _`\<,_  
 (*)/ (*) Claudio Caputti
+++++++++++++++++++++++++++++++++++++++^++++++++++++++++++++++++++++++++++++++
Free will - the result of chaotic amplification of quantum events in the brain.
------------------------------------------------------------------------------
From: jmr@cs.anu.edu.au (Mike Robson)
Newsgroups: comp.theory
Subject: Re: Suggstion: (was: Re: P=NP; the proof)
Date: 8 Jan 1993 15:34:07 +1100
Organization: Computer Science Department, ANU, Australia
Distribution: inet
NNTP-Posting-Host: nunki.anu.edu.au
Keywords: Collapse of hierarchy

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

[historical allusions deleted]

>When you come up with a P=NP proof, first make sure you can translate it to
>several of the other known NP-complete problems.  Each conversion should lead
>to some significant result and insight if the original proof is correct.
>Also, you'd get far more attention by simultaneously publicising polynomial
>algorithms for 10 to 20 NP-complete problems, and a single tenuous and
>highly abstract proof.  The conversions are in the literature, so it's
>a trivial bookkeeping process to develop 20 algorithms from one.

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

>If you're refereeing journals or otherwise trying to determine the validity
>of P=NP proofs, reject all alleged proofs that don't meet the two criteria
>above.

Thanks for the suggestion.

I've just come up with a fantastic n^12 algorithm for the subset sum
problem which translates into a n^24 algorithm for SAT which gives me
a n^48 algorithm for graph isomorphism. As soon as I have tested this
on a few non trivial pairs of nonisomorphic graphs I'll submit
it to CACM (or whatever journal seesm appropriate in 100993).


More seriously: we all know about the conversions so why bother
elaborating them. If it turns out that P=NP (I doubt it today),
then it is the fact that matters.


Mike Robson.
From: reeds@alice.att.com (Jim Reeds)
Newsgroups: comp.theory
Subject: Re: P=NP; the proof
Summary: Mike wants more than G&S claim!
Keywords: Collapse of hierarchy
Date: 7 Jan 93 16:00:01 GMT
Article-I.D.: alice.24567
Distribution: inet
Organization: AT&T Bell Laboratories, Murray Hill NJ



jmr@cs.anu.edu.au (Mike Robson) writes:

>[...]
>I'll go back to trying to decide if the current Gismondi and Swart
>linear programming formulation has the required property (that every
>solution covers a permutation). If that claim is true, then I think
>my approach is a good way to try and prove it.

This is rather more than G&S themselves state.  If every point in the
feasible region covers a permutation, then the extreme points of the
feasible region are exactly the permutations, and hence every point in
the feasible region is expressible as a convex combination of permutations.

But all G&S claim is that any solution is expresible as an affine
combination of permutations, with AT MOST ONE NEGATIVE COEFFICIENT.
(I would like to see a real proof that any solution is expressible
as an affine combination of permutations, regardless of sign.  Equivalently,
I'd like to know the dimension of the affine hull of the G&S feasible
region.)
Jim
Newsgroups: comp.theory
From: marcel@ADS.COM (Marcel Schoppers)
Subject: Re: Suggstion: (was: Re: P=NP; the proof)
Keywords: Collapse of hierarchy
Organization: Advanced Decision Systems, Mtn. View, CA (415)960-7300
Distribution: inet
Date: Sat, 9 Jan 1993 00:14:06 GMT

In article <1ij07vINN2f6@nunki.anu.edu.au> jmr@cs.anu.edu.au (Mike Robson) writes:
>markh@csd4.csd.uwm.edu (Mark) writes:
>>When you come up with a P=NP proof, first make sure you can translate it to
>>several of the other known NP-complete problems.  Each conversion should lead
>>to some significant result and insight if the original proof is correct.
>>Also, you'd get far more attention by simultaneously publicising polynomial
>>algorithms for 10 to 20 NP-complete problems, and a single tenuous and
>>highly abstract proof.  The conversions are in the literature, so it's
>>a trivial bookkeeping process to develop 20 algorithms from one.
>
>>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.
>
>>If you're refereeing journals or otherwise trying to determine the validity
>>of P=NP proofs, reject all alleged proofs that don't meet the two criteria
>>above.
>>Mark
>
>Thanks for the suggestion.
>
>I've just come up with a fantastic n^12 algorithm for the subset sum
>problem which translates into a n^24 algorithm for SAT which gives me
>a n^48 algorithm for graph isomorphism. As soon as I have tested this
>on a few non trivial pairs of nonisomorphic graphs I'll submit
>it to CACM (or whatever journal seesm appropriate in 100993).
>Mike Robson.

Better yet:  I've just come up with a beautiful n^2 algorithm for graph
isomorphism, but the actual execution time is 10^100 * n^2 seconds.
Marcel
From: kpierce@andre.d.umn.edu (Keith Pierce)
Newsgroups: comp.theory
Subject: Need info on NP-complete problem
Date: 8 Jan 93 19:58:55 GMT
Organization: University of Minnesota, Duluth
NNTP-Posting-Host: andre.d.umn.edu

I would like to find out more information on the problems
   [MS17] Fault Detection in Logic Circuits
   [MS18] Fault Detection in Directed Graphs
  
The numbers are from the Garey-Johnson text. That text cites only one
old reference [Ibarra and Sahni 1975] and one unpublished manuscript
[Ibaraki, Kameda, Toida 1977].

Does anyone have any further information on this class of problems?


Keith Pierce, Professor
Department of Computer Science 
University of Minnesota, Duluth
Duluth, MN 55812-2496

internet: kpierce@d.umn.edu
bellnet:  218-726-7194
Newsgroups: comp.theory
From: butrfeld@cs.tcd.ie (Andrew Butterfield)
Subject: Re: Real Numbers vs. Rational Numbers?
Followup-To: comp.theory
Organization: Dept. of Comp. Sci., TCD
Distribution: inet
Date: Wed, 6 Jan 1993 16:11:53 GMT

In article <1993Jan5.161955.11237@tom.rz.uni-passau.de>,
boerncke@kirk.fmi.uni-passau.de (Frank-Roland Boernke) wrote:
> 
> 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.
> 
When you say "handles real numbers", do you mean that it can write real
numbers
into a single box on the tape ? If this is the case then your "R-Turing"
machine is different to a classic one, which has a potentially infinite
tape,
but only a finite set of symbols that it can write on the tape.

The R-Turing machine has an uncountably infinite set of symbols. It would
also need an uncountably infinite transition function to exploit the power
of its symbol set.

A classic Turing machine can "handle" real numbers in the same way as any
other computing devices, by working with finite approximations of those
real numbers.
Newsgroups: comp.theory,sci.crypt,sci.math,rec.puzzles
From: roth@3d.enet.dec.com (Jim Roth)
Subject: Re: Looking for random permutation generation algorithms
Organization: Digital Equipment Corporation
Date:  6 JAN 93 19:24:11    


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.  

A coset algorithm works very well for uniformly choosing an element
of a group (in this case the symmetric group.)

   initialize n element array a(i) = i

   for i = 1 to n-1
       j = random integer from i to n inclusive
       exchange a(i) and a(j)
       (it is possible that i = j and no exchange takes place above)
   end

   now a contains a random permutation of n elements

This is far nicer than approaches I've seen (such as generating a random
list of numbers, sorting them, and returning the resulting permutation!)

- Jim
Xref: sparky comp.theory:2852 comp.edu:2290
From: bdm@cs.anu.edu.au (Brendan McKay)
Newsgroups: comp.theory
Subject: Is this NP-complete?
Date: 10 Jan 93 15:48:18 GMT
Distribution: inet
Organization: Australian National University
NNTP-Posting-Host: tyl.anu.edu.au

A generalised regular family (GRF) of sets is represented by a 
vector (bot;top[1],...,top[n]) where bot and each top[i] are sets, 
and each top[i] is a superset of bot.  The GRF consists of all  
sets X such that bot <= X <= top[i] for some i, where "<=" means 
"subset".  A _simple_ GRF is one with n=1.

INSTANCE:  A GRF F; and integer K >= 0.
QUESTION:  Is F equal to the disjoint union of at most K
           simple GRFs?

What is the complexity of this problem?  I suspect it is NP-complete
but can't rule out some simple dynamic program (or something).
This problem arose from a graph computation that runs faster
if GRFs can be quickly split into a small number of simple GRFs.

Thanks,
Brendan McKay.
Newsgroups: comp.theory.cell-automata
From: hmasum@alfred.carleton.ca (Hassan Masum)
Subject: 1D computation-universal CAs
Organization: Carleton University
Date: Fri, 8 Jan 1993 21:27:59 GMT

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!


-- 

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
                  Hassan Masum...hmasum@ccs.carleton.ca
              "Artificial Intelligence Beats Real Stupidity"
 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Newsgroups: comp.theory.cell-automata
From: MCINTOSH@unamvm1.dgsca.unam.mx ("Harold V. McIntosh")
Subject: WireWorld AND.
X-Unparsable-Date: Mon, 11 Jan 93 21: 18:22 MEX
Organization: The Internet
Distribution: inet
Date: Tue, 12 Jan 1993 04:19:01 GMT

Those who were looking for WireWorld hints might try to improve the
following AND gate, which delivers its result in two clock cycles, or
12 ticks (this one doesn't need an explicit clock).
 -
 -   ...............
 -   .a...bxx.......
 -   ..x.....xxx....
 -   ...x.x.x...x...
 -   ....xxx....x...
 -   .....x.x.x.x...
 -   ........xxx....
 -   .........x.xxc.
 -   ...............
 -
 Evidently, the identity used here is
     (a'b)'b = (a+b')b
             =  ab + bb'
	     =  ab = c.
-
Harold V. McIntosh             |Depto. de Aplicaci'on de Microcomputadoras
MCINTOSH@UNAMVM1.BITNET        |Instituto de Ciencias/UAP
mcintosh@unamvm1.dgsca.unam.mx |Apdo. Postal 461
(+52+22)43-6330                |72000 Puebla, Pue., MEXICO
Newsgroups: comp.theory.cell-automata
From: MCINTOSH@unamvm1.dgsca.unam.mx ("Harold V. McIntosh")
Subject: Wire World.
X-Unparsable-Date: Fri, 08 Jan 93 21: 26:47 MEX
Organization: The Internet
Distribution: inet
Date: Sat, 9 Jan 1993 03:31:47 GMT

Roger Knobbe <roger(at)TRIPLEX.SOCAL.COM> says:
>
> 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?
-
Not knowing wire-pc.c it is hard to say what's better. But CellMaster is good]
-
-      Sintar Software
-      1001 4th Avenue, Suite 3200       (data valid in 1990)
-      Seattle, Washington 98154
-      (206) 625-1213
-
Very helpful is the screen editor which is included.
-
In any program, it is a good idea to build up tiles which can be traversed
in one clock period. A period 6 clock is conservative.
-
-       .......
-       ..oo...
-       .o..ooo   an electron head at the extreme left
-       ..oo...   enters a tile to the right each 6 ticks.
-       .......
-
-       ......
-       ...o..    a barrier. electron head entering either side
-       oooooo    gets stopped cold.
-       ...o..
-       ......
-
-       ......
-       ..oo..    a diode. electron head entering left emerges
-       ooo.oo    on right six ticks later, but one entering right
-       ..oo..    gets stopped.
-       ......
-
-       .......c
-       ......o   (a and not b) gate. A fundamental construct. the
-       .....o.   electron arrives at c 6 ticks later if a=1; b=0;
-       ..o.o..   any other initial combination and nothing emerges.
-       booo...
-       ..o.o..
-       .....a.
-
Harold V. McIntosh             |Depto. de Aplicaci'on de Microcomputadoras
MCINTOSH@UNAMVM1.BITNET        |Instituto de Ciencias/UAP
mcintosh@unamvm1.dgsca.unam.mx |Apdo. Postal 461
(+52+22)43-6330                |72000 Puebla, Pue., MEXICO
Newsgroups: comp.theory.cell-automata
From: rucker@sjsumcs.SJSU.EDU (Rudy Rucker)
Subject: RE: "A dude...!"
Organization: The Internet
Distribution: inet
Date: Sat, 9 Jan 1993 03:49:57 GMT


There should be a software method for simple access to a FAQ (frequently
asked question) list such as "What is a CA?"

But I'll try an answer.  A  CA (cellular automaton) is a *parallel* computation
characterized by being i) homogeneous (each of the parallel processors
has the same data-intake pattern, the same algorithm, and the same data-output
channel) ii) parallel (meaning that there are lots of the processing or
computing sites.  Ordinarily "parallel" is taken to mean "synchronistic"
as well,menaing that all the parallel sites update at the same times.  
Everybody inhales, everybody thinks, everybody exhales.)  iii) local
( the data-intake, or inhale, only draws information from a finite number
of other processors in the CA).  

This definition appear in Margolus and Toffoli's CELLULAR AUTOMATON
MACHINES and in my CA LAB MANUAL.  

I'm not entirely sure its the best possible definition.

One assumption implicit in the ordinary idea of a CA is that the sites
stay spatially fixed.  Something I wonder about is whether a moving
alife program such as vants, turmites, sims, critters, bugs etc. might
not also be thought of as a CA in a general sense.
Newsgroups: comp.theory.cell-automata
From: mark_a@cix.compulink.co.uk (Mark Atkinson)
Subject: k
Cc: mark_a@cix.compulink.co.uk
Reply-To: mark_a@cix.compulink.co.uk
Date: Thu, 7 Jan 1993 18:10:00 +0000

The evolving CA idea is very interesting....

One thing occurs to me about Packard's "Disneyworld" proposal - 2D CAs have a
very strong propensity to either die out of descend into chaos (of the
uninteresting type).  As Langton et al. have shown, the "best" (here,
aesthetic) rules are balanced procariously on the "edge of chaos".

How are we proposing to constrict the ruleset(s) such that our evolving
pattern does not die?  Is the correspondence between aesthetics and balanced
entropy sufficient to ensure the observer selection-driven evolution will
ensure our pattern will not go too far off-track?

Perhaps using a class of CA which is less prone to these possiblities would
be the answer. Any usual 8SUM (Toffoli's terminology) rule (even a very
well-balanced one, like Conway's Life) would tend to stabilise after some
time due the inevitable increase or decrease in its entropy level.  I would
propose using a time-reversible rule to avoid these problems.

On the side of the genetic algorithm (GA), careful attention should be paid
to the schema; that is to say, no small number of selections (which could
potentially be contrived or even malicious here) should cause the pattern to
diverge drastically from its current state.  The evolution must proceed in
very small steps if it is to achieve good results, but no so small as the
users to not see feedback within their short attention span.  There is a
difficult dilemma here.


On the "alternatives" front, IFS codes (Iterated Function Systems) are a good
bet - aesthetically pleasing, small codes giving rise to complex structures,
robust/similar under mutation/recombination.  On the minus side, they use
real numbers, but this isn't too much of an issue.

I have written a "Blind Watchmaker" type selector for IFS patterns, and the
results _are_ nice.

=============================================================================
Mark Atkinson
mark_a@cix.compulink.co.uk
-----------------------------------------------------------------------------
"This statement is true, but you cannot prove it." - Kurt Godel.
My opinions are shareware - if you like them, please fax me $25.
=============================================================================

>>>MATRIX version  1.21c
Newsgroups: comp.theory.cell-automata
From: a18672@itesocci.gdl.iteso.mx (Burgos Qui#onez Jesus Mariano)
Subject: A dude...!
Organization: The Internet
Distribution: inet
Date: Sat, 9 Jan 1993 00:57:45 GMT


  Hi there:

     I am studying computing science, i am in this list but i don't
know what exactly it is, i learned about automatas but cellular automata ?
Can somebody explain this to me ?  The think is that it sounds so interes-
ting.  

       Thanks.
                   Vurghoz.    a18672@itesocci.bitnet
                               a18672@itesocci.gdl.iteso.mx