HDTenEightyP/NetNews huggingface dataset:
From: lowry@watson.ibm.com (Andy Lowry)
Subject: Re: Accepting sequences?
Date: Sun, 4 Oct 1992 18:35:35 GMT
Disclaimer: This posting represents the poster's views, not necessarily those of IBM
	<1992Sep28.224552.100936@Cookie.secapl.com>
	<1992Oct2.093930.1372@nntp.nta.no>
	<1992Oct02.165008.37497@Cookie.secapl.com>
Organization: IBM T.J. Watson Research Center

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.

This is a fairly limiting view of long-lived programs.  It may be a
fairly common view currently, partly due to the success to date of the
client-server paradigm for distributed computing.  But I think this is
a case of a partial solution (to the problem of developing distributed
systems) turning around and redefining the problem by obscuring the
parts of it that it doesn't address.  People will have a need for
long-lived, largely autonomous programs that have varied, dynamic
interactions with other programs.  Many of these programs will act as
servers, but many will not.  Examples are easily had by considering
programs that carry on long-term intractions with the physical
environment, like online market analysis programs.  The state of such
a program at any given point in time is determined by its entire
history of interactions, not by some recently initiated client
interaction.  It's intended to run "forever," but it cannot be
characterized as "completing multiple computations."  (At least not in
the sense that I believe was intended above... clearly, each
instruction might be viewed as an isolated computation, and then every
program completes multiple computations; I assume the intended meaning
was something along the lines of multiple *unrelated* or at most
*loosely related* computations.)

With that, I'll repeat a query I made recently to this group: What
can/should computing theorists be contributing in the way of models
for the behavior of such systems and their development.  A
particularly challenging problem in this area is: how will we upgrade
this sort of program without interrupting its execution or that of any
of the other running programs with which it is interacting?  Clearly
it's conceivable to transfer all access rights and that sort of thing
to a new process running the upgraded software, but how about
transferring current state in a reasonable manner?  The new and old
programs might not have conformable state.  Can the old state be
automatically translated to its new form?  Are there programming
models that will ensure this is possible?  Will it be necessary to
"quiesce" certain dynamic behaviors before attempting such a
switch-over?  Etc.
--
Andy Lowry, lowry@watson.ibm.com, (914) 784-7925
IBM Research, P.O. Box 704, Yorktown Heights, NY  10598
Xref: sparky comp.theory:2136 uw.cs.theory:6
From: schmidtg@iccgcc.decnet.ab.com
Newsgroups: comp.theory
Subject: Calculating a CRC of other CRCs
Date: 5 Oct 92 10:31:44 EST



I am looking for a mechanism to quickly compare two programs.  Each program
will reside on a different CPU and the programs may be large, so a direct byte
by byte comparison would be too time consuming.  I only need to know whether
the two programs are identical or they are different -- I will not be generating
difference listings.  I would like to use a CRC computed on the entire program
as a means of comparison.

In addition, the program is organized as "chunks" and a chunk may be
independently edited.  However, when the chunk is edited, I would like to
avoid having to recalculate the CRC for the entire program.  I would like to
somehow "incrementally" update the CRC based on a small change.  I doubt this
is possible, so an alternative is to calculate a CRC for each chunk and then
calculate the CRC for the entire program by calculating a CRC on all of the
"chunk CRCs".  In that way, I can avoid having to examine the entire program
each time a chunk has changed.

However, I don't know how reasonable it is to calculate "a CRC of other CRCs".
There may be some statistical pitfalls in doing this which may reduce the
effectiveness of the CRC and introduce the possibility of error.

Does anybody have any thoughts on this?


Thanks in advance,


Greg Schmidt		schmidtg@iccgcc.decnet.ab.com
Newsgroups: comp.theory
From: tolman%asylum.cs.utah.edu@cs.utah.edu (Kenneth Tolman)
Subject: Accepting sequences?
Date: 28 Sep 92 11:59:38 MDT
Organization: University of Utah, CompSci Dept

  What on earth does accepting sequences have to do with computability?
In a standard CS text, the definition of a computation is a Turing machine
that accepts a sequence, and then halts.  Here are a number of problems with
it:

1) It opposes what Turing himself defined.  Turing define numbers like pi, and
e to be computable- all nonterminiating computations.  These are by definition
noncomputable by the "new and improved" definition.

2) The new definition has nothing to do with reality.  A real computation 
on a universal Turing machine would read in a sequence and then COMPUTE
something- possibly halting or not.  The COMPUTABLE thing would be the
purely defined output of the machine... talk to me more if you want a 
rigorous definition for purely defined.  Suffice it to say the number 4
would be a computable number, which an accepting machine has nothing to 
do with. 

So what is the deal?  Why this weird obscure definition which has nothing
to do with reality?
From: markh@csd4.csd.uwm.edu (Mark)
Newsgroups: comp.theory
Subject: Re: Accepting sequences?
Date: 29 Sep 1992 14:37:59 GMT
Organization: Computing Services Division, University of Wisconsin - Milwaukee
Distribution: inet
NNTP-Posting-Host: 129.89.7.4

In article <1992Sep28.115938.15203@hellgate.utah.edu> tolman%asylum.cs.utah.edu@cs.utah.edu (Kenneth Tolman) writes:
>  What on earth does accepting sequences have to do with computability?
>In a standard CS text, the definition of a computation is a Turing machine
>that accepts a sequence, and then halts.  Here are a number of problems with
>it:
>
>1) It opposes what Turing himself defined.  Turing define numbers like pi, and
>e to be computable- all nonterminiating computations.  These are by definition
>noncomputable by the "new and improved" definition.

Pi is considered computable solely in virtue of the fact that any finite
portion of its decimal expansion can be calculated in finite time.  (i.e.,
the nth decimal can be calculated in finite time).

So computing pi is a terminating computation.  What's infinite isn't the
computation but the number of different possible inputs (N, for Nth decimal).

An unending process isn't a computation.
From: jcm@CS.STANFORD.EDU ("John C. Mitchell")
Newsgroups: comp.theory
Subject: Anon FTP file for conference scheduling
Date: 2 Oct 92 22:19:04 GMT
Reply-To: "John C. Mitchell" <jcm@cs.stanford.edu>

The purpose of this message is to announce a file for posting
tentative and confirmed conference announcements. The current
orientation is towards conferences and workshops in areas related
to logic in computer science or overlapping with logic-related
conferences in some way. However, if other people start using it,
the scope may expand.

The file of conference names and dates is

   pub/conferences

on the machine

  theory.stanford.edu

This may be read by anyone by anonymous ftp. The protocol for
posting an announcement is described below, in a message that
is stored in conferences-README in the same directory.

This scheme will work only if (1) conference organizers use it,
and (2) postings are of the correct format so that the time involved
in maintaining the list is kept to a minimum.

John Mitchell



--------------------- conferences-README ----------------------


The file ``conferences'' in this directory contains tentative and
confirmed dates of conferences and workshops, primarily in areas
related to logic in computer science or overlapping with logic-related
conferences in some way. Each entry contains the date of the conference
itself and the submission date.

The reasons for establishing this file are

(1) to provide an up-to-date on-line calendar for researchers
   who might want to participate in the meetings themselves,

(2) to provide a mechanism for scheduling conferences. Organizers
  are encouraged to post TENTATIVE dates WELL IN ADVANCE and
  check for conflicts before setting firm dates. It is not the
  intention of the maintainers of this list to negotiate
  dates, but merely to help conference organizers identify
  possible conflicts.

Since one goal is to avoid conflicting dates, posting of meetings
with restricted attendace is encouraged. Even if a workshop is
by invitation only, it may be important for organizers of another
meeting to know about it.

Protocol for submitting dates:

Send a one or two-line message of the form illustrated by
the following examples to conferences@theory.stanford.edu.

Feb 13-15, 92: STACS, Paris (SUBMIT AUG 15 1991)
Feb 24-28, 92: CAAP_ESOP (SUBMIT NOV 12, 91)
Mar 18-20, 92: Theorem Proving with Analytic Tableaux, Lautenbach,
        Germany, fronhoef@informatik.tu-muenchen.de
Mar 19-22, 92: ASL Annual Mtng, Durham, NC

It is helpful to include an email address or other contact point.
From: gil@cc.gatech.edu (Gil Neiger)
Newsgroups: comp.theory
Subject: Re: The Last Word on Brown Eyes, Blue Eyes
Date: 30 Sep 92 12:36:35 GMT
Reply-To: gil@cc.gatech.edu (Gil Neiger)
Organization: College of Computing, Georgia Institute of Technology

In article <Sep.26.08.07.59.1992.24360@remus.rutgers.edu>
clong@remus.rutgers.edu (Chris Long) writes:
>In article <1992Sep25.132133.7259@cc.gatech.edu>, Gil Neiger writes:
>
>> ... summary of my explanation of the role of knowledge
>>     in the problem's solution ...
>
>You are absolutely wrong.  The original problem, as stated, is
>inconsistent since the inhabitants are assumed to be logical
>and the blue-eyed individuals have not deduced their status
>yet (assuming the island has a sufficient history).  For a
>better statement of this puzzle which avoids this problem see
>the rec.puzzles FAQ.

Mr. Long does not make it clear where I am wrong.  He only criticizes
the original statement of the problem, which was not mine.  In my
posting, I made it clear that I never saw this original statement and
was only speaking of the problem as I knew it.

					- Gil Neiger
Newsgroups: comp.theory
From: seody@geo1.eecs.nwu.edu (Dae Y. Seo)
Subject:  Approximation algorithm for capacitated spanning tree problem 
Organization: EECS Department, Northwestern University
Date: Mon, 5 Oct 1992 20:15:28 GMT

The (geometric) capacitated spanning tree problem is NP-complete.
[Papadimitriou 76] and well defined in pp206-207 [garey and Johnson 79]
 
Is there any performance guareented approximation algorithm for above
problem?
How about the case that the total cost is bounded by that of 
the (euclidean) MST?

Any information about the reference or your result would be appreciated.

PLS send e-mail to seody@eecs.nwu.edu. Thank you in advance.
-D. Y. Seo



Newsgroups: comp.theory
From: hil@cs.brown.edu (Hsueh-I Lu)
Subject: Re: Approximation bound on degree-constrained MST 
Organization: Brown University Department of Computer Science
Date: Tue, 6 Oct 1992 16:12:10 GMT


Try this one:

%A Martin F\"urer
%A Balaji Raghavachari
%T Approximating the minimum degree spanning tree to within one from the optimal
 degree
%J SODA
%V 4
%D 1992
%P 317-324
%K min degree spanning tree, approximation algorithm

Newsgroups: comp.theory
From: pjyamamo@watdragon.uwaterloo.ca
Subject: Re: ******************* FIND THE ERROR ! ************************
Organization: University of Waterloo
Date: Fri, 2 Oct 1992 20:17:16 GMT

In article <92Oct1.174911edt.168199-2@watdragon.uwaterloo.ca> pjyamamo@watdragon.uwaterloo.ca (Peter Yamamoto) writes:
>In article <1992Sep30.200435.20497@cc.umontreal.ca> you write:
>>
>> Just for the fun of it, I challenge anyone to find the error on page 129 of the
>>
>> book : Theory of Computation
>>   by : Derick Wood (University of Waterloo)
>>        Wiley publications
>>
>> Challenge your analytical skills.... I can assure you that there is indeed an error,
>>
>> who will be the first to find it ???
>
>Which error?
>
>Errata: Theory of Computation
>Derick Wood
>Data Structuring group
>Research Report CS-88-35
>September, 1988

My mistake. the latest edition has those corrections.

The poster is apparently referring to another error.

Peter
Newsgroups: comp.theory
From: tolman%asylum.cs.utah.edu@cs.utah.edu (Kenneth Tolman)
Subject: Halting problem
Date: 4 Oct 92 23:16:43 MDT
Organization: University of Utah, CompSci Dept

  Let us suppose we construct a Turing machine which will solve the halting
problem.  It is special in that it recognizes its own coding sequence, and
stops with a special output character when it sees its own sequence.  This
Turing machine is not susceptible to the self reference paradox which
normally kills it.  What is wrong with this?
From: eemrw@cc.newcastle.edu.au
Newsgroups: comp.theory
Subject: EQUATION PARSER
Date: 6 Oct 92 01:40:43 GMT
Organization: University of Newcastle, AUSTRALIA

I am looking for a algorithm and/or c code
to do equation parsing. If Anyone
can help please email.

Mark West
University of Newcastle Australia
email : EEMRW@cc.newcastle.edu.au
From: sjha+@cs.cmu.edu (Somesh Jha)
Newsgroups: comp.theory
Subject: Complexity of a problem related to permutation groups?
Date: 2 Oct 92 19:38:29 GMT
Article-I.D.: cs.BvIEK6.9r8.2
Organization: School of Computer Science, Carnegie Mellon



Hi Folks:

What is the complexity of the following problem? Given a permutation
group G (acting on a set of size n) and two 0-1 vectors x and y of
length n, find if x = perm y where perm is permutation in the
permutation group G. I have a strong intuition that the problem is
NP-complete (I know it is NP), but I haven't been able to prove it.

Thanks a lot.

Somesh Jha
From: burley@geech.gnu.ai.mit.edu (Craig Burley)
Newsgroups: comp.theory
Subject: Re: Halting problem
Date: 5 Oct 92 13:35:43 GMT
Organization: Free Software Foundation 545 Tech Square Cambridge, MA 02139
In-reply-to: tolman%asylum.cs.utah.edu@cs.utah.edu's message of 5 Oct 92 05:16:43 GMT

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

     Let us suppose we construct a Turing machine which will solve the halting
   problem.  It is special in that it recognizes its own coding sequence, and
   stops with a special output character when it sees its own sequence.  This
   Turing machine is not susceptible to the self reference paradox which
   normally kills it.  What is wrong with this?

Hmm, I'm no theorist, but isn't the very wording of the halting problem one
that requires a YES or NO answer?  E.g. "given a program and input for that
program, will the program halt?"  If outputting a special character, which
sounds to me like an answer other than YES or NO, is legitimate, then there
are other ways to solve the "problem", right?

Another issue is that just because the machine recognizes it's own coding
sequence (whatever that means) doesn't mean it will recognize the coding
sequences of all programs that attempt to determine whether a given program
halts given particular input.

But this all just reminds me that the halting problem seems to be just a
case of figuring out that we don't always ask the right questions.  And
that reminds me why I'm no Computer-Science theorist.  :-)
--

James Craig Burley, Software Craftsperson    burley@gnu.ai.mit.edu
Member of the League for Programming Freedom (LPF)
From: paulh@minster.york.ac.uk
Newsgroups: comp.theory
Subject: Re: Kernighan-Lin like program (graph) partitioning
Date: 6 Oct 92 11:48:39 GMT
Organization: Department of Computer Science, University of York, England
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

Jan,

    I think that the reference you are looking for is

%T An Efficient Heuristic Procedure for Partitioning Graphs
%A B. W. Kernighan
%A S. Lin
%J Bell Systems Technical Journal
%V 49
%N 2
%D 1970
%P 291-307

    you may also like to check out the algorithm reported below

%T Efficient algorithm for graph-partitioning problem using a problem
transformation method
%A Lee, C.-H.
%A Park, C.-I.
%A Kim, M.
%X Shows that the uniform k-way partitioning problem can be transformed into
the max-cut problem using a graph modification technique. An iterative
algorithm, based on the Kernighan-Lin method, for partitioning graphs is
presented that exploits the problem equivalence property. The algorithm deals
with nodes of various sizes without any performance degradation. The computing
time per pass of the algorithm is O(kN/sup 2/), where N is the number of nodes
in the given graph. In practice, only a small number of passes are typically
needed, leading to a fast approximation algorithm for k-way partitioning.
Experimental results show that the proposed algorithm outperforms the KL
algorithm in the quality of solutions
%K graph-partitioning problem, problem transformation method, uniform k-way
partitioning problem, max-cut problem, graph modification technique, iterative
algorithm, Kernighan-Lin method, problem equivalence property, nodes, computing
time, passes, approximation algorithm
%J Computer Aided Design
%V 21
%N 10
%P 611-18
%D Dec. 1989

    H

Paul Hatcher			PHONE    +44 904 432771
Department of Computer Science	JANET    paulh@uk.ac.york.minster
University of York		INTERNET paulh@minster.york.ac.uk
Heslington, York, Y01 5DD	UUCP	 {mcsun,uknet}!minster!paulh
From: gaylord@ux1.cso.uiuc.edu (Richard J. Gaylord)
Newsgroups: comp.theory.cell-automata
Subject: SimLife game
Date: 6 Oct 92 07:26:28 GMT
Article-I.D.: news.BvovC5.IDv
Organization: University of Illinois
X-Xxdate: Tue, 6 Oct 92 02:28:34 GMT
X-Useragent: Nuntius v1.1.1d11
X-Xxmessage-Id: <A6F6AA52CD019B13@mm-mac19.mse.uiuc.edu>

has anyone looked at "SimLife" the new game by Broderbund (Maxis)?

it was developed by ken katsaros who wrote the CASIM program [which is
pretty nice]. it costs $70 in the stores (available now). i know it runs
on the Mac but i don't know about platforms.

this is not an ad for the  product which i have only seen in the beta
test version. i am wondering if anyone thinks it has educational value.
From: dseal@armltd.co.uk (David Seal)
Newsgroups: comp.theory.cell-automata
Subject: No more please! (was Re: Spaceships in Conway's Life (Part 4a))
Date: 28 Sep 92 15:04:13 GMT
Distribution: comp
Organization: A.R.M. Ltd, Swaffham Bulbeck, Cambs, UK

In article <7390@armltd.uucp> I wrote:

>We don't appear to have received part 3 of this excellent series of
>articles. Has anyone else? If so, could some kind person please email it to
>me?

I have now got part 3 of David Bell's series, so please don't send any more
copies! Many thanks to those who responded.

David Seal
dseal@armltd.co.uk

All opinions are mine only...
From: dseal@armltd.co.uk (David Seal)
Newsgroups: comp.theory.cell-automata
Subject: Re: Spaceships in Conway's Life (Part 4a)
Date: 28 Sep 92 10:07:20 GMT
Distribution: comp
Organization: A.R.M. Ltd, Swaffham Bulbeck, Cambs, UK

In article <1992Sep25.130013.6430@pdact.pd.necisa.oz.au>
dbell@pdact.pd.necisa.oz.au (David I. Bell) writes:

>		Spaceships in Conway's Life (Part 4)

We don't appear to have received part 3 of this excellent series of
articles. Has anyone else? If so, could some kind person please email it to
me?

I'd also like to thank David Bell for writing and posting the articles -
they're one of the best things I've ever seen on the net.

David Seal
dseal@armltd.co.uk

All opinions are mine only...
Newsgroups: comp.theory.cell-automata
From: rpatil@nmsu.edu (Raj Patil)
Subject: Cellsim - simulator info please
Organization: Computing Research Lab
Distribution: comp.theory.cell-automata
Date: Mon, 5 Oct 1992 20:57:36 GMT


Hi: 

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. If anyone has done this or have ideas about doing
this, I would appreciate if they can give me some info on how to do it
or are willing to give me the code.

Thanks in advance.

Best Regards

Raj Patil
NMSU-CRL, USDA-ARS
Las Cruces, NM 88003
Newsgroups: comp.theory.cell-automata
From: schnitzi@cs.ucf.edu (Mark Schnitzius)
Subject: An idea I had
Organization: University of Central Florida
Distribution: comp
Date: Thu, 1 Oct 1992 19:36:08 GMT

Here's an idea I came up with a while ago (although
it probably was invented before): LIFE on a hex sheet.
I tinkered with it a while but was never able to come
up with a good set of rules.  Using 2222 rules (by
standard convention [I think], the first digit is the 
max number of neighbor a cell can have to survive,
the second digit is the min number of neighbors a cell
must have to survive, the third is the max number of
neighbors an empty cell can have to cause a birth, and
the last digit is the min number of cells it must have
for a birth), the results weren't too interesting,
except that brother (who beat me to coding it) managed
to find two blinkers, which I list below:

   . . . . . .          . . . . . . .
	. . o . .            . . . o . .
   . . . . . .          . . o . . . .
	. . o . .            . . o . o .
   . . . . . .          . . . . . . .
	. . . . .            . . . . . .

Can anyone find anything else interesting with these
rules?  Can you find a better set of rules that yield
more interesting results (possible by extending the
range of nieghbors to all cells within a distance of
two)?

Mark Schnitzius
schnitzi@eola.cs.ucf.edu
Univ. of Central Florida
From: dwp+@cs.cmu.edu (Doug Philips)
Newsgroups: comp.theory.cell-automata
Subject: Re: SimLife game
Summary: something salient, shortly stated, sadly seldom satoric
Date: 6 Oct 92 13:55:26 GMT
Article-I.D.: cs.BvpDCn.Cpv.1
Organization: EIEI-U

In article <BvovC5.IDv@news.cso.uiuc.edu> gaylord@ux1.cso.uiuc.edu (Richard J. Gaylord) writes:
+has anyone looked at "SimLife" the new game by Broderbund (Maxis)?
+
+it was developed by ken katsaros who wrote the CASIM program [which is
+pretty nice]. it costs $70 in the stores (available now). i know it runs
+on the Mac but i don't know about platforms.
+
+this is not an ad for the  product which i have only seen in the beta
+test version. i am wondering if anyone thinks it has educational value.

There has been some talk about (and a review of) it in the macintosh games
group:  comp.sys.mac.games

-Doug
From: tomc@siesoft.co.uk (Tom Crossland)
Newsgroups: comp.theory.cell-automata
Subject: Re: Spaceships in Conway's Life (Part 4a)
Date: 28 Sep 92 14:34:22 GMT
Reply-To: tomc@siesoft.co.uk
Distribution: comp
Organization: Siemens Nixdorf Information Systems Ltd.

dseal@armltd.co.uk (David Seal) writes:
 
: I'd also like to thank David Bell for writing and posting the articles -
: they're one of the best things I've ever seen on the net.
 
: All opinions are mine only...

No they're not - It is my opinion also that they're some of the most
interesting postings I've seen on the net ;-) Thanks David B.

--
___ _ __   "Beep beep blip beep bibble beebeeep blip bibble beep" - Altern8
  ((_))))...  Tom Crossland, Sysop of DarcWorld IES, [+44] [0]8675 77724.
         Hi! I am a .signature virus. Copy me into your .signature to join in!