« Are You Sure that Ketel One is in the Protocol? | Main | Sounds Like the Set-up for a Commercial »
October 21, 2006
What it is Possible to Compute
Here's the abstract for a paper in preparation. I saw a talk on the subject on Friday, and I'm really curious about the proofs. I really can't figure out how stochasticity would increase the computational power of a system.
In other words, other algorithms are known where stochasticity dramatically increases efficiency, but here stochasticity increases what it is possible to compute, regardless of efficiency. Without stochasticity, computations are limited to primitive recursive functions, but with stochasticity, the full generality of Turing machine computation is attained.
Posted by todd at October 21, 2006 10:36 PM
Comments
you, sir, are a geek.
Posted by: jon at October 23, 2006 7:25 PM
Post a comment
Thanks for signing in, . Now you can comment. (sign out)
(If you haven't left a comment here before, you may need to be approved by the site owner before your comment will appear. Until then, it won't appear on the entry. Thanks for waiting.)