Authors
Toby Ord
Oxford University
Abstract
While it is well known that a Turing machine equipped with the ability to flip a fair coin cannot compute more than a standard Turing machine, we show that this is not true for a biased coin. Indeed, any oracle set X may be coded as a probability pX such that if a Turing machine is given a coin which lands heads with probability pX it can compute any function recursive in X with arbitrarily high probability. We also show how the assumption of a non-recursive bias can be weakened by using a..
Keywords No keywords specified (fix it)
Categories (categorize this paper)
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Translate to english
Revision history

Download options

PhilArchive copy


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 72,564
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

On Computable Numbers, with an Application to the Entscheidungsproblem.Alan Turing - 1936 - Proceedings of the London Mathematical Society 42 (1):230-265.
Systems of Logic Based on Ordinals.Alan Mathison Turing - 1939 - London: Printed by C.F. Hodgson & Son.

Add more references

Citations of this work BETA

The Many Forms of Hypercomputation.Toby Ord - unknown - Journal of Applied Mathematics and Computation 178:142-153.

Add more citations

Similar books and articles

Analytics

Added to PP index
2009-05-21

Total views
29 ( #398,866 of 2,533,484 )

Recent downloads (6 months)
1 ( #391,480 of 2,533,484 )

How can I increase my downloads?

Downloads

My notes