Many Worlds and Oracles

From: Tim May <>
Date: Mon, 30 Dec 2002 12:58:29 -0800

On Monday, December 30, 2002, at 11:57 AM, Jesse Mazer wrote:
> As I understood it, the basic idea here was to use the fact that
> history must work out consistently to get a machine that could solve
> problems much faster than a Turing machine. For example, for any
> problem that requires exponential time to reach a solution but for
> which possible solutions can be checked in polynomial time, you could
> have the machine pick a possible solution at random, then check to see
> if the solution actually works, then if it *doesn't* work it sends
> back a sort of override command that changes the original guess, which
> would create an inconsistency.

Or just kills you and/or your world.

This idea predates Max Tegmark by quite a while...I give Moravec the

My own version of an oracle was done for an article I sent out in 1994.
Included below.

RSA Broken By The Russians?

Kolmogorov Cryptography System Possibly Cracked
1 Apr 1994

    MOSCOW (AP) -- At a press conference held minutes ago in a crowded
    Russian mathematicians announced that a breakthrough had been made
    nearly a decade ago in the arcane branch of mathematics known as
    "cryptography," the science of making messages that are unreadable to

    Leonid Vladwylski, Director of the prestigious Moscow Academy of
    Sciences, called the press conference yesterday, after rumors began
    circulating that noted Russian-American reporter John Markoff was in
    Russia to interview academicians at the previously secret city of
    Soviet cryptographers, Kryptogorodok. The existence of
    sister city to Akademogorodok, Magnetogorsk, and to the rocket cities
    of Kazhakstan, had been shrouded in secrecy since its establishment
    1954 by Chief of Secret Police L. Beria. Its first scientific
    director, A. Kolmogorov, developed in 1960 what is called in the West
    "public key cryptography." The existence of Kryptogorodok was
    to the West until 1991, when Stephen Wolfram disclosed its existence.

    American cryptographers initially scoffed at the rumors that the
    Russians had developed public-key cryptography as early as 1960, some
    15 years prior to the first American discovery. After interviews
    year at Kryptogorodok, noted American cryptographers Professor D.
    Denning and D. Bowdark admitted that it did seem to be confirmed.

    Professor Denning was quoted at the time saying that she did not
    this meant the Russians could actually break the Kolmogorov system,
    known in the West as RSA, because she had spent more than a full
    trying to do this and had not succeeded. "Believe me, RSA is still
    unbreakable," she said in her evaluation report.

    Russia's top mathematicians set out to break Kolmogorov's new coding
    system. This required them to determine that "P = NP" (see
    article). Details are to be published next month in the journal
    "Doklady.Krypto," but a few details are emerging.

    The Kolmogorov system is broken by computing the prime numbers which
    form what is called the modulus. This is done by randomly guessing
    constituent primes and then detonating all of the stockpiled nuclear
    weapons in the former Soviet Union for each "wrong guess." In the
    Worlds Interpretation of quantum mechanics, invented in 1949 by Lev
    Landau (and later, independently by Everett and Wheeler in the U.S.),
    all possible outcomes of a quantum experiment are realized.

    As Academician Leonid Vladwylski explained, "In all the universes in
    which we guessed the wrong factors, we were destroyed completely.
    since we are obviously here, talking to you at this press
conference, in
    this universe we have an unbroken record of successfully factoring
    the largest of imaginable numbers. Since we are so optimistic about
    this method, we say the computation runs in 'Nondeterministic
    Time.' Allow me to demonstrate..."

    [Press Conference will be continued if the experiment is a success.]

    MOSCOW (AP), ITAR-Tass, 1 April 1994

First, it was Stephen Wolfram's actual suggestion, a couple of years ago
after the USSR imploded, that we try to recruit mathematicians and
programmers from what he surmised must exist: a secret city of Soviet
cryptographers. It probably exists. We did it at Los Alamos, they did
with their rocket scientists and others (Akademogorodok exists), so why
put their version of NSA a bit off the beaten track? Note that our own
is within a stone's throw of the Baltimore-Washington Parkway. I
be surprised to learn that their experts were ensconced somewhere in the

I tried to acknowledge Steve with my comments. By the way, so far as I
know, no word has come out on whether he was right in this speculation.
(Maybe some of the Russians he does in fact have working at Wolfram are
these folks? Naw...)

Second, Kolmogorov did basic work on information theory, probability,
statistics. One has to assume he had ties to the Soviet cryptography
effort (about which little has been written about, so far). If anyone
Russia could have seen public key methods coming, he is a candidate. No
evidence that he or any other Russian did, though.

Third, my references to Denning and Sternlight were perhaps not
funny (though I didn't aim for a riotously funny tone). Especially in
light of David Sternlight's excellent follow-up here... never let it be
said that David lacks a sense of humor. The Denning reference was to
own comments about spending a weekend or so trying (and failing, not
surprisingly) to crack the Skipjack algorithm. (Real ciphers often take
years to break, as with the knapsack algorithm, recent crunching of DES,

Fourth, the "Many Worlds" interpretation of quantum mechanics does
and leads to approaches such as I described. It's also a hypothetical
to ensure one's wealth: simply bet everything you own at 1000-to-1 odds
then commit suicide in all universes in which you lose. Not very
convincing, I agree. Hans Moravec writes about this in his "Mind
Children," 1987.

Finally, I used the headers and format of a real article in the ClariNet
system, then made modifications. Given that the Supreme Court has
ruled in favor of "fair use" for satire, I hope my version of "2 Live
meets RSA" does not get my sued. (I could just kill myself in all
realities in which Brad sues me.)
Received on Mon Dec 30 2002 - 16:08:10 PST

This archive was generated by hypermail 2.3.0 : Fri Feb 16 2018 - 13:20:07 PST