[racket] [Off Topic] Theoretical questions

> 3. ) Is it true that attaching a source of randomness to a Turing
> machine from a theoretical perspective turns it into a hypercomputer
> (i.e. gives it "super-Turing" capabilities)?
>

Assuming you are talking about incomputable, Martin-Löf randomness, since no
Turing machine can output such a (infinite) random sequence, then a Turing
machine that has access to such a source can obviously computes things a
normal TM cannot.

For example, one particular random sequence (for one particular TM) is
Chaitin's Omega "number of wisdom", of halting probability.
This number is random (non computable by any TM), and if you have it (by
using an oracle TM) you can know for each program executed on the TM if it
will eventually halt or not.

For other types of random sequences, I can't say, although I think I read
somewhere that any random sequence is the halting probability of one TM, but
maybe I'm wrong.

See Li&Vitaniy : "An introduction to Kolmogorov complexity and its
applications", although it's not really easy to read.

Hope this helps,
Laurent
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20110317/a8120af2/attachment.html>