Hmm, not very creative of the automated puzzle generator.  It seems to have
lazily put up last week's problem, and even more lazily left off the
condition "infinite".  I'll have to debug it firmly.  I notice it also
doesn't seem to have much respect for the value of money.

Well, here's the puzzle it came up with anyway, FWIW.  Good luck with it!

JANUARY 31, 2003:  PUZZLE 1.5

Does there exist a nondiscrete T1 binary comonoid?  (Definitions below.)

The first correct and soundly reasoned answer posted to
theory-edge@yahoogroups.com will win its submitter US$500.

Definitions.

1.  A word over an alphabet S is a pair (A,f) where A is a set called the
*length* of the word, and f is a function f: A -> S giving the letters
of the word.  Example.  S = 2 = {0,1}, A is the set of reals, and f: A ->
S is the function mapping rationals to 1 and irrationals to 0.

2-4.  As for puzzle 1.4.

Remark. As two people noted, "infinite word" as defined in last week's
puzzle was strictly speaking "countably infinite word." There are other
infinite sets than the natural numbers. As previously noted, crossword
existence is independent of the order of word positions: a dictionary D
has a crossword iff D' has a crossword where D' is derived from D by say
interchanging the first two letters of every word.  Mark's solution to
puzzle 1.4 therefore applies to any word of countable length A, meaning
a word in the above sense for which A is a countable set, i.e. a set in
one-to-one correspondence with the set N of natural numbers.

Hence this week's puzzle asks to extend Mark's result to words of length
strictly longer than N, i.e. uncountably long words.

Hint. First solve the problem for A the set of real numbers. Any solution
that works for this example of an uncountable length is almost certainly
going to work for any length.

A word of length R over {0,1} is a function from R to 2. This is the same
thing as a subset of R, which you can visualize as dots along the real
line, one dot per real in the subset, totally unrestricted as to density
or distribution. You can put no dots, or dots everywhere along the line,
or dots just at integers, or just at the rationals, etc.

A dictionary of words of length R is therefore nothing more or less than a set
of sets of reals, such as {{1.4, 3}, {2.78, 9.1}} (but of course that's merely
a finite example).  Equivalently it is a set of arbitrarily dotted lines.

A crossword then amounts to dots in the plane, such that for each vertical
or horizontal line, the dots on that line are those of some word in the
dictionary. The problem asks about the line y = x: must the dots along it
form a dictionary word?

Hmm, that last sentence is wrong: correct it to:

The problem asks about the line y = x: if the dots along it always form a
dictionary word, is there a word (subset of R) that the dictionary can omit?

Naughty automated puzzle generator.  I updated the web page accordingly
just now.

Vaughan Pratt

I was hoping to post some additional motivating notes about comonoids
and such before the automatic problem generator dreamed up a problem
and valued it suitably, but I think it's going to beat me to it.  I'll
let you know what it came up with when it does.

Vaughan

hi all. passed on to me by a friend,]
some hot/fascinating links on bioinformatics.

determining the shape of
proteins is now being called
"structural genomics". heres
a very interesting article on
"dickersons formula" which seems
to be biochemistry's equivalent
of moores law: the number of new protein
shapes (conformations)
successfully determined each year.
from a newsletter apparently on high performance
computing.

http://www.npaci.edu/envision/v18.1/moore.html

this is another article that shows how the
massive genomics program will shift into
the protein folding problem. on funding &
an "assembly line system".

Im disappointed
that no mention is made of software techniques,
this seems to suggest that physical xray
crystalography has the heavy edge in
progress & scientific grants.

Determining Protein Structures with High-Throughput Techniques

http://www.npaci.edu/envision/v18.1/protein.html

hi all. heres some new leads on "the power parasite"..
for your amusement or edification


author jon ronson has some fun ideas in his new
book "Them"

a nice review that just appeared on CNN

http://asia.cnn.com/2003/SHOWBIZ/books/01/30/ronson.them/


excerpt on this site from his book, on the bilderburgers etc

http://books.guardian.co.uk/extracts/story/0,6761,449284,00.html


heres his home page

http://www.jonronson.com/index.html

before anyone tells me the homeland security eye-in-keyhole
logo is not genuine, plz hit these links.
the logo appeared on a US patent office newsletter
advertising new "homeland security" technologies such as biometrics
etc, but the Reason article below suggests its an official logo.



Artifact: No Go Logo
Creepy agency casts evil eye on Planet Earth
By Jesse Walker
October 2002
http://reason.com/0210/artifact.shtml


USPTO Patent Examiners Advance Homeland Security
Pulse April 2002 - Volume 10 Number 4
http://www.uspto.gov/web/offices/ac/ahrpa/opa/pulse/epulse/pulse0204_home.htm




see also

Watching Your Every Move
by William F. Jasper
The New American - Vol. 19, No. 02
January 27, 2003

Comprehensive government databases and new invasive technologies threaten o
ur system of checks and balances, presenting an unprecedented potential for
tyranny.
...


http://www.thenewamerican.com/tna/2003/01-27-2003/vo19no02_watching.htm



Feds Building Internet Monitoring Center
By Brian Krebs, washingtonpost.com Staff Writer
Friday, January 31, 2003; 12:00 AM

The Bush administration is quietly assembling an Internet-wide monitoring
center to detect and respond to attacks on vital information systems and key
e-commerce sites.

The center, which has been in development for the past 15 months, is a key
piece of the White House's national cybersecurity strategy and represents a
major leap in the federal government's effort to achieve real-time tracking
of the Internet's health.



http://www.washingtonpost.com/wp-dyn/articles/A3409-2003Jan30.html

hi all. I just saw the homeland security & total information
awareness program logos on this site. really creepy & odious stuff.

http://www.unknownnews.net/miranda0123.html

we are wise to remember our history.
heres an article that reminds us of the episode of the NSA
& its clipper chip.

so I wonder, how soon before a govt agent contacts me about what
I write here??

strange how political technology has become these days. one
might think it is just bits flowing down infopipes but that would
be quite misleading.

I personally think in the battle of cyberspace freedom
vs the spooks, the spooks have already lost & are gonna lose
in the future.

although the author doesnt even mention biometic technology..



Spook humor: Playing Americans for laughs

       by Miranda

       The offensive Homeland Security logo* - a creepy roving eye
       looking through a keyhole - is not the first time our government's
       spooks have given "we the people" their one-fingered salute.

       Almost ten years ago, the National Security Agency (NSA)
       announced its inclusion of the so-called "Tessera" PCMCIA
       card for use with laptop computers, using the Skipjack algorithm
       to encrypt data. This is similar to the infamous Clipper Chip that
       the Clinton administration tried to place in all voice
       communications systems built in the U.S. (The debate centered
       on speculation that the NSA retained back-door encryption keys
       that allowed them to intercept encrypted data, a suspicion
       reinforced by the fact that the government refused to open up the
       technology to civilian peer-review.)

       A "tessera" is defined by the Oxford Unabridged Dictionary and
       Starr's History of the Classical World as: "An identity chit or
       marker. Tessereae were forced on conquered peoples and
       domestic slaves by their Roman occupiers or owners. Slaves or
       Gauls who refused to accept a tesserea were branded or maimed
       as a form of identification."

       The NSA spooks obviously thought they were having a cynical
       little joke at the expense of the American people.

       When cyber nerds realized this, there was a great hue and cry on
       the Internet. Since that time the NIST changed the chip's name
       from "Tessera" to "Fortezza", ostensibly to avoid a trademark
       infringement.

       Our government and its minions appear to see themselves as
       conquerors dominating the masses. The Homeland Security logo
       is yet another example of the elephant-balled arrogance of our
       leaders. It is a blatant screw-you to all Americans. After all,
       where do you find a keyhole? In the front door of your home, the
       one place that has traditionally been the most private. The logo's
       message is clear: the government is ready and willing to invade
       your private sanctuary.

       I can only hope that the logo was designed to distract attention
       away from the other problems with Poindexter's spy proposal.
       But no doubt there are plenty of government spooks out there
       having a malicious snicker about it. Keep laughing. If I see a
       roving eye on the other side of my keyhole, I'm stubbing my
       cigarette out on it.


                             © 2003, by the author.

--- In theory-edge@yahoogroups.com, "Mike N. Christoff
<mchristoff@s...>" <mchristoff@s...> wrote:
> --- In theory-edge@yahoogroups.com, "Klaus D. Witzel
<kwitzel@c...>"
> <kwitzel@c...> wrote:
> > Hi Michael!
> >
> > Just in case you still haven't given up, here's a situation your
> > algo doesn't take care of:
> >
> > Let s be (...i j...)
> > and t be (...j i...)
> >
> > There are at least a quadratic number of cases st (or ts), that is
> > on input (...i j...),(...i j...),k=2 your algo fails.
> >
>
> Thanks a lot Klaus!  I appreciate it.  And no I haven't given up
just
> yet.  I still have a few promising avenues to look down and your
> example template will be a great help in testing.  So let me get
this
> straight.  You're saying, in the terminology of the original
> question, if p = (...i j...), q=(...i j...) and t=2, where the
actual
> f = (...i j...)(...j i...), then it won't work?  (sorry - I'm
pretty
> slow).

Yes, that is what I meant (of course the dots have to compare to
equal).

> Some may wonder why I'm pursuing it when so many people far smarter
> than I have all used gcd.  But I think that maybe it is not that
> people have not been able to avoid using gcd, its just that gcd can
> be calculated quickly and leads to a simple algorithm - so why not
> use it?  ie:  No one's even explored an alg w/o gcd because there
is
> simply no reason not to use it outside of academic curiosity.  In
> other words, this may be a small area where I can actually make an
> even smaller (if not insignificant) mark.

No, [if nobody else then at least] I think it is significant. The
problem you address is about independence which [at least for me] is
of importance and of relevance for SAT solvers.

> And VZ, rest easy.  Although I needed to respond to Klaus I won't
be
> posting hourly updates of my progress.  Only one post when (if) its
> done.

Vlad always supports discussion when it is about theory :) But if
you'd like to discuss the progress of your Java implementation, feel
free to drop me an email.

/Klaus

> l8r, Mike N. Christoff

this is a kind of sketchy rant below, but it proposes
what Ive been imagining, i.e.
that the bush administration wants to develop
a means to control & restrict information over the internet
(particularly any dissident politics)
via the homeland security office. certainly
easy to imagine.

not a chance in **** of it
ever happening, if you ask me. but.. more big IFMIO
kindling.. a showdown seems inevitable to me.


"end of internet freedom?" by kurt nimmo

http://www.alternet.org/story.html?StoryID=14865


>Bush and his Machiavellian minions will no longer put up with you
>roaming free into dangerous territory on the internet. You need to
>be corralled, electronically tethered, kept away from sites
>promoting conspiracy theories – in other words, information the
>corporate media, the official US Ministry of Disinformation, does
>not want you to read or see. It's now increasingly obvious the
>Bushites want to lock us up in a hermetically sealed informational
>box and throw away the key. All the information they consider
>worthwhile will be pumped in through a one-way hole.
...

yep!! thanks MNC, very cool, good news,
I noticed & was really psyched to
get a link from fortnow--I presume he added
it after you mentioned theory-edge & KLVEs list
in his guestbook.  (anyone else, feel free also
to add links wherever!)

Ive been a huge fan of fortnow
ever since I discovered him within the last few
years & wrote up a short bio/plug for theory-edge
archives. I highly recommend his papers, they're
all 1strate and very compelling. his weblog has lots
of interesting material. fortnow could arguably
be the premiere and most prolific
complexity theorist of his age.

I added a few comments on fortnow's
home page form. I asked him about his neat proof
with von melkebeek that gives almost the only
known nontrivial lower time/space bounds
on NP class. it would sure be great if other scientists
had web logs & as much enthusiasm for tutoring &
promotion. even better .. maybe he might post a msg here
or on KLVEs list some day. Im sure we'd have lots
to talk about. on the other hand fortnow seems
to be one of the busiest scientists out there.

--- In theory-edge@yahoogroups.com, "Michael N. Christoff"
<mchristoff@s...> wrote:
> Hey VZ, Kurt.  Did you notice that Lance has added direct links to
your
> respective groups on his homepage?  Very cool.  Check it out - its
on the
> main page under the heading "Discussion Groups".
>
> http://fortnow.com/lance/complog/
>
>
>
> l8r, Mike N. Christoff

Hey VZ, Kurt.  Did you notice that Lance has added direct links to your
respective groups on his homepage?  Very cool.  Check it out - its on the
main page under the heading "Discussion Groups".

http://fortnow.com/lance/complog/



l8r, Mike N. Christoff

tim berners lee's semantic web project.. is this going anywhere yet?

http://www.washingtonpost.com/wp-dyn/articles/A62329-2003Jan29.html


freeman dyson says "the future needs us" in response to bill joy and
michael chrichton

http://www.nybooks.com/articles/16053


concern over economic espionage in silicon valley.. just a new
pie for big brother?

http://www.cnn.com/2003/TECH/biztech/01/30/silicon.spies.ap/index.htm
l

technology journalists cant get job so they auction themselves
on ebay

http://www.wired.com/news/business/0,1367,57472,00.html


CIA launches terrorist datamining program

http://dc.internet.com/news/article.php/1576771



net plays increasing role in online life

http://www.wired.com/news/culture/0,1284,57491,00.html

--- In theory-edge@yahoogroups.com, "Klaus D. Witzel <kwitzel@c...>"
<kwitzel@c...> wrote:
> Hi Michael!
>
> Just in case you still haven't given up, here's a situation your
> algo doesn't take care of:
>
> Let s be (...i j...)
> and t be (...j i...)
>
> There are at least a quadratic number of cases st (or ts), that is
> on input (...i j...),(...i j...),k=2 your algo fails.
>

Thanks a lot Klaus!  I appreciate it.  And no I haven't given up just
yet.  I still have a few promising avenues to look down and your
example template will be a great help in testing.  So let me get this
straight.  You're saying, in the terminology of the original
question, if p = (...i j...), q=(...i j...) and t=2, where the actual
f = (...i j...)(...j i...), then it won't work?  (sorry - I'm pretty
slow).

Some may wonder why I'm pursuing it when so many people far smarter
than I have all used gcd.  But I think that maybe it is not that
people have not been able to avoid using gcd, its just that gcd can
be calculated quickly and leads to a simple algorithm - so why not
use it?  ie:  No one's even explored an alg w/o gcd because there is
simply no reason not to use it outside of academic curiosity.  In
other words, this may be a small area where I can actually make an
even smaller (if not insignificant) mark.

And VZ, rest easy.  Although I needed to respond to Klaus I won't be
posting hourly updates of my progress.  Only one post when (if) its
done.



l8r, Mike N. Christoff

hi all.. I just noticed that the good will hunting screenplay
is in a book sold on amazon with other information in
it, such as on background of authors etcetera.
won an oscar for best screenplay of the year.
I just bought a copy & will post later!! hard to believe
its 5 years old now, seems like yesterday. (uh well yeah
I did just rent it in DVD again a few weeks ago haha)

http://www.amazon.com/exec/obidos/tg/detail/-/0786883448/


I also saw "PI" last wknd which some friends had told me about
after hearing about my interest in analyzing the stock
market. I **disrecommend** this movie!! very dark & shocking!!
I was hoping to see the protagonist get rich off of his discovery in the
typical hollywood cliche story,
but the movie went the exact opposite direction!! yikes!!
I was fooled by a decent review by ebert. oh well.

yes, open problems are the fuel of all science and
especially mathematics.
just to add a little snippet to this thread.
all this talk about open problems
reminds me of a famous story about a student
solving a teacher's open problems, which apparently
really happened in the case of george dantzig, and apparently
was a major inspiration in the movie "good will hunting".
(sorry about the formatting on this, see the original page
for a nice format.)


http://www.snopes.com/college/homework/unsolvab.htm



        Legend:   A student arrives late to math class and finds two problems
written on the chalkboard.
        Assuming they're homework problems, he jots them down in his notebook and
works on the equations
        over the next few days before turning his solutions in to the instructor.
Several weeks later,
        the professor turns up at the student's door with the student's work
written up for publication.
        The two problems were not a homework assignment; they were problems
previously thought to be
        unsolvable which the instructor had used as examples in his lecture that
day.

        Variations:

               One version of this story involves a student who arrives late for
an exam and finds three
               problems to solve written on the blackboard. He solves the first
two quite easily but has
               to struggle until time has almost run out to solve the third.
Later that evening the
               student receives a phone call from his instructor, who explains
that the third problem was
               not part of the test but was an example of a problem that
mathematicians had been trying
               to solve for years without success.

        Origins:   This has to be one of the ultimate academic wish-fulfillment
fantasies: a student not
        only proves himself the smartest one in his class, but also
        bests his professor and every other scholar in his field of
        study.

        As far as we know, this legend is based upon a true incident.
        (That is, a version of this legend that antedates a known true
        incident has not yet been discovered). George B. Dantzig, then a
        graduate student at the University of California, Berkeley,
        arrived late for a statistics class one day and found two
        problems written on the board. Not knowing they were examples of
        "unsolvable" statistics problems, he solved them as a homework
        assignment. Dantzig, who later became a staff mathematician at
        Stanford University, recounted his solving two "unsolvable"
        problems in a 1986 interview for College Mathematics Journal,
        and his solutions to the two problems can be found in the journal
articles listed in the Sources
        section below.

        Sightings:   This legend is used as the setup of the plot in the 1997
movie Good Will Hunting.
        As well, one of the early scenes in the 1999 film Rushmore shows the main
character daydreaming
        about solving the impossible question and winning approbation from all.

        Last updated:   11 February 2001


                         The URL for this page is
http://www.snopes.com/college/homework/unsolvab.htm
                                       Click here to e-mail this page to a friend

                                       Urban Legends References Pages © 1995-2003
                                           by Barbara and David P. Mikkelson
                                  This material may not be reproduced without
permission


        Sources:

         Albers, Donald J.   "An Interview of George B. Dantzig: The Father of
Linear Programming."
                College Mathematics Journal.   Volume 17, Number 4; 1986   (pp.
293-314).

         Brunvand, Jan Harold.   Curses! Broiled Again!
                New York: W. W. Norton, 1989.   ISBN 0-393-30711-5   (pp.
278-283).

         Dantzig, George B.
                "On the Non-Existence of Tests of 'Student's' Hypothesis Having
Power Functions Independent of Sigma."
                Annals of Mathematical Statistics.   No. 11; 1940   (pp.
186-192).

         Dantzig, George B. and Abraham Wald.   "On the Fundamental Lemma of
Neyman and Pearson."
                Annals of Mathematical Statistics.   No. 22; 1951   (pp. 87-93).







from this page, "anecdotes about famous scientists"

http://www.xs4all.nl/~jcdverha/scijokes/10.html


---

This story is told with several different protagonists. (Who knows the
truth?):

1) Another "true" story, kinda like the aforementioned urban legend: Enrico
Fermi, while studying in college, was bored by his math classes.  He walked
up to the professor and said, "My classes are too easy!"  The professor
looked at him, and said, "Well, I'm sure you'll find this interesting."
Then the professor copied 9 problems from a book to a paper and gave the
paper to Fermi.  A month later, the professor ran into Fermi, "So how are
you doing with the problems I gave you?"  "Oh, they are very hard.  I only
managed to solve 6 of them."  The professor was visibly shocked, "What!?
But those are unsolved problems!"

From: lrmead@... (Lawrence R. Mead)
2) Very nearly this exact story was told to me (or I read it) about the
mathematician David Hilbert when *he* was a grad student. Can anyone here
confirm this?

From: columbus@... (Michael Weiss)
3) Well now, I heard the same thing about John Milnor.  Moreover the
unsolved problem was showing that any smooth closed curve in 3-space of
total curvature <= 4pi is unknotted, and Milnor *did* prove that as an
undergraduate.

From: visser@... (Boudewijn W. Ch. Visser)
4) It was not Fermi,but George Danzig.

The story as told in news:alt.folklore.urban (see the FAQ from there) tells
about a student,not paying attention.  At the end of the lecture,the
professor writes down 8 problems,and the student,waking up, thinks it is
homework.  At the next class,the student apologizes for having finished
only 4 problems ,and having an idea about 2 more.  Turns out the problems
were famous unsolved problems.  The student was George Danzig.

From: sidles@... (John Sidles)

The soon-to-be-famous student who solved a previously unsolved problem, in
the mistaken belief that it was a homework assignment, was indeed...

****** George Dantzig ******.

His first-person account can be found (along with many other fascinating
accounts) in the book "More Mathematical People".

Here is the full reference; this book is highly recommended....

~Title: More mathematical people : contemporary conversations / edited
by Donald J. Albers, G.L. Alexanderson, Constance Reid.
Edition: 1st ed.  Pub. Info.: Boston : Harcourt Brace Jovanovich, c1990.
Phy Descript: 375 p.  Notes: Includes bibliographical references.  LC
Subject: Mathematicians -- Interviews.
Mathematicians -- Biography.  Other Author: Albers, Donald
J., 1941-.
Alexanderson, Gerald L.
Reid, Constance.  Library Loc.: Mathematics.  Status:
Mathematics Research General Stacks
QA28 .M67 1990 CHECK THE SHELVES

He got that right.  That was certainly how I got into theory after starting
out in AI (natural language parsing).  I wasn't even solving problems "for
the fun of it," these were problems I kept running into when trying to build
a system that efficiently produced a plausible ranking of possible parse
trees for English sentences encountered in practice.  That and compiler
writing exposed me to a wide range of fundamental problems and after three
years of practice I was finding I could even solve the unsolved
problems.

Vaughan

-----Kurt's message-----
  If you keep proving stuff that others have done, getting confidence,
  increasing the complexities of your solutions - for the fun of it -
  then one day you'll turn around and discover that nobody actually
  did that one! And that's the way to become a computer scientist.

  --- Richard Feynmann, in Feynmann Lectures on Computation.

Hi all,

I can't resist one more post on this topic (but I promise to give it
a rest for a while after this).

Each issue of the quarterly ACM SIGACT News begins with a quotation
of relevance to theoretical computer science.  They (the quotations)
can be found online at: http://sigact.acm.org/sigactnews/quotes/ .
One of these struck me as being particularly appropriate, from the
June 2001 issue:

  If you keep proving stuff that others have done, getting confidence,
  increasing the complexities of your solutions - for the fun of it -
  then one day you'll turn around and discover that nobody actually
  did that one! And that's the way to become a computer scientist.

  --- Richard Feynmann, in Feynmann Lectures on Computation.


-Kurt

Hi,

--- In theory-edge@yahoogroups.com, sterten@a... wrote:
>
> you can always find enough puzzles, hard or easy that's not the
point.
> You must somehow filter them so that only the interesting or
important
> ones survive.

History is the 'filter' that usually determines which problems are
interesting or important, but by the time a problem passes that test
(like P vs. NP), it's not likely to be a good candidate for a puzzle
contest.

But I agree that picking the right sorts of problems is crucial,
which is why the person(s) who sponsor the contest would need to have
a keen insight into this.  In addition to being easy to state, the
problems should have some chance of actually being solvable.  This
would rule out problems that have already been looked at by a lot of
people over a long period of time (extreme example: Goldbach's
conjecture).  Instead, good candidates might be conjectures that have
been proposed only recently, and which remain unsolved mainly because
they haven't been tackled vigorously.  Another idea might be to take
some known result and see if it can be strengthened by tweaking the
conditions.

Algorithmics could be another source of problems:  Is there a faster
way to compute such-and-such.  In fact, to follow your suggestion
about protein-folding, didn't the entire puzzle contest evolve out of
a thread about genome sequencing?

-Kurt

Hi Michael!

Just in case you still haven't given up, here's a situation your
algo doesn't take care of:

Let s be (...i j...)
and t be (...j i...)

There are at least a quadratic number of cases st (or ts), that is
on input (...i j...),(...i j...),k=2 your algo fails.

/Klaus

Kurt,

Careful what you ask for.

Vaughan

>Vaughan (if he's game, or else some other benefactor) intersperses puzzles
>with known answers, with open problems.

Hi all,

Here is an interesting site I just saw mentioned on usenet: Robert
Hochberg's "Open Problems for Undergraduates" page at DIMACS.  URL:
http://dimacs.rutgers.edu/~hochberg/undopen/ .  These are open
problems which can be understood without an advanced mathematical
background, and which (presumably) are easier than problems like P vs. NP.

This got me to thinking a little bit (always a dangerous thing).
Since people here are having fun solving puzzles, maybe they would be
interested in tackling some that don't have answers yet?  This isn't
anything new, of course.  For example, a while back Jerry Spinrad
posted an open question in graph theory; but I don't recall that it
generated a very strong response.

But (and here is the key), Vaughan has shown that just a modest prize
can really crank up the interest level.  This could be combined with a
little bit of motivational psychology used by casinos and lotteries,
as follows:  Vaughan (if he's game, or else some other benefactor)
intersperses puzzles with known answers, with open problems.  The open
problems need to be obscure enough that they aren't recognized as
such, and the other puzzles need to be sufficiently difficult that
they aren't immediately seen to be solvable.  Finally, the prize
amount would probably have to be kicked up just a little to guarantee
that people are motivated.

The beauty of this scheme is that people would be motivated to work on
all the puzzles, because they wouldn't want to miss out on solving one
of the 'easy' ones and winning the prize.  And because the easy ones
can't be readily distinguished from the hard ones, people would tackle
the open problems without any preconceptions about it being too hard
to solve.

Well, I suppose the whole idea may seem a little sophmoric, but there
it is.  Who knows--it might actually work!

-Kurt

hi all. the last issue of wired is
very interesting. the cover story is the
future (or lack of) the music business.
here's a really fun & wild article about
kazaa & a cat-and-mouse game its founders
are playing with international law & the music
biz. kazaa which is morphing very quickly
into a napster replacement but which
is already far,far larger than napster.

http://www.wired.com/wired/archive/11.02/kazaa.html

there is a remote possibility it could morph
into the future standard music delivery
system over the internet. and these systems
are likely to merge with a video-on-demand
service eventually too, I would guess (its all
bits!!), although
for now the two lines are developing separately.

the kazaa vs international court system/lawyers
fight will be a very key battle to watch
in the nearterm future. so far kazaa looks like
its pluckily eluded a crackdown, but how much longer can
its luck run for?? or will it be impossible to
shut it down??

the case also shows the inherent advantage of
cyberspace over the legal system, the latter of
which is glacial, the former of which is
"cyberspatial".. running in nanosecond time. IFMIO,
irresistible force meets immovable object.
quite the fireworks in the collision. kaboom!!

its all also very reminiscent of this
amusing year 2000 article on cypherpunk ryan lackey & "sealand"

http://www.wired.com/wired/archive/8.07/haven.html

wired on kasparov

http://www.wired.com/news/infostructure/0,1377,57459,00.html

msnbc

http://www.msnbc.com/news/863920.asp?0si=-

cnn

http://www.cnn.com/2003/TECH/fun.games/01/29/chess.kasparov.reut/inde
x.html

popular science on two legged (bipedal) robots

http://www.popsci.com/popsci/computers/article/0,12543,412296,00.html


how to be a programmer, free book, covered on slashdot,
by a Phd.. any opinions?

http://samizdat.mines.edu/howto/

hi MCN, I like your code & youve spurred & fueled a fantastic
collaborative thread here on the permutation puzzle, quite a rare feat,
I assure you.

& your java code is great stuff.   (& plz forgive me for not following
every nanosecond gyration directly.)

but permit me a quibble.
think of the mailing list like a stage. you wouldnt want to
get dressed on a stage, right? similar to "thinking out loud in
cyberspace".

part of programming is knowing why a particular algorithm
works. and being able to prove its correctness-- maybe not
strictly formally, but at least informally, intuitively.

I would argue if the programmer writes out code without having a good
picture of the correctness in his mind **before** he writes
it, thats a deviation from the software engineers code of
honor.

if you ask others why your code seems to work on a lot of cases..
someone might find that interesting to look at, but
that's a bit tricky, because you're the originator of it.

unless you have evidence otherwise, I think others will
assume that if your code doesnt work on all cases, then its
incorrect, and cannot be corrected except such that it will
come out looking like VPs in the end.

since VP has a nice implementation and has basically
proven its correctness as far as I can tell, how about we
close it up here & move future dialogue on the permutation puzzle
over to KLVEs list, he's interested in it.

ps MCN, do you have a home page anywhere? others may be interested
in your precocious background.


MCN writes
>PS:  It would be a great help if anyone would like to post other examples w=
>here the algorithm fails.
>Duh!  That interleaving business won't work.  Looking more like gcd is esse=
>ntial.

grants for portrayals of scientists in movies. lets see what
happens.

http://www.wired.com/news/digiwood/0,1412,57417,00.html



psychological implications of sony's aibo & robotics

http://www.usatoday.com/tech/news/techinnovations/2003-01-28-
dog_x.htm



kasparov wins 1st match & draws 2nd

http://www.msnbc.com/news/863920.asp?0si=-


how the internet is misdesigned based on root server
queries. also the underlying messaging system has some
serious problems with e.g. denial of service attacks,
because it was not designed to withstand them.

http://news.bbc.co.uk/2/hi/technology/2699071.stm

--- In theory-edge@yahoogroups.com, "Lasse Rempe <lrempe@c...>"
<lrempe@c...> wrote:

> on reading Problem 1.4, it might be interesting to ask whether the
> answer is still true for comonoids on uncountable sets. I currently
> see no reason why this should be the case, but can't say that I
> think I've got a really good feel for comonoids.

I've been thinking about this as well.  I believe my second
lemma has the following generalization:

Let D be a comonoid where the word length is the infinite
cardinal c (not the continuum c, just any infinite cardinal
c).  Assume D has the property that given any subset I of
word indices of cardinality strictly less than c, and any
0-1 valued function f on that subset, there is a word in D
that has bit i set to f(i) whenever i in I.  Then D is
discrete.

Proof sketch: Construct a symmetric crossword with an
arbitrary word as the diagonal using the same prefix
approach I used for the countably infinite case, but
with a well ordering of c having the property that
any smaller ordinal has smaller cardinality as well.

However, I can't see how this helps with the general
theorem.

Mark