Re: Using QTI to generate algorithms

From: Hal Finney <hal.domain.name.hidden>
Date: Tue, 19 Apr 2005 16:22:10 -0700 (PDT)

David Barrett-Lennard writes:
> On a computer we generate a million numbers at random, and we write a
> program that tests whether the numbers are stored in ascending order, and if
> not causes the experimenter to be killed.
> ...
> An interesting question is whether there will be a tendency to discover
> short and concise algorithms. In any case, the experiment could be repeated
> many times to allow the experimenter to seek short programs - by giving it
> less space to work in.

Yes, I think it would. If each bit of the program is set randomly,
then the measure of the branches where the experimenter survives should
be proportional to the length of the program. So he would expect to
see one of the shortest programs possible.

> Some really difficult problems could be solved with this technique - eg
> "Find a proof to ...", and the test code simply validates the line of
> reasoning.
>
> Evidently QTI gives the experimenter the equivalent computing power of a
> Quantum computer. ie exponential order problems can be solved in linear
> time.

Quantum computers can't solve exponential problems in linear time.
They can solve some problems, like factoring, in linear time, but no
one knows whether these problems are exponential or not. They can do
some exponential problems, like searching, in less time than a classical
computer but the time is still exponential.

I'm not sure how the power of this QTI based computer would compare with
a conventional quantum computer. One practical problem, even if you
accept the correctness of QTI, is in making the kill-you circuit reliable
enough that it is not the weakest link in the chain. You need to have
its failure probability be significantly less than the probability that
your program will work. But that latter probability may be exponentially
tiny, so engineering the killer circuit may be intractable.

Hal Finney
Received on Tue Apr 19 2005 - 20:20:16 PDT