1. The diagonal method and hypercomputation.Toby Ord & Tien D. Kieu - 2005 - British Journal for the Philosophy of Science 56 (1):147-156.
    The diagonal method is often used to show that Turing machines cannot solve their own halting problem. There have been several recent attempts to show that this method also exposes either contradiction or arbitrariness in other theoretical models of computation which claim to be able to solve the halting problem for Turing machines. We show that such arguments are flawed—a contradiction only occurs if a type of machine can compute its own diagonal function. We then demonstrate why such a situation (...)
    Direct download (11 more)  
    Export citation  
    Bookmark   9 citations  
  2. Quantum hypercomputation.Tien D. Kieu - 2002 - Minds and Machines 12 (4):541-561.
    We explore the possibility of using quantum mechanical principles for hypercomputation through the consideration of a quantum algorithm for computing the Turing halting problem. The mathematical noncomputability is compensated by the measurability of the values of quantum observables and of the probability distributions for these values. Some previous no-go claims against quantum hypercomputation are then reviewed in the light of this new positive proposal.
    Direct download (11 more)  
    Export citation  
    Bookmark   8 citations  
  3.  35
    Using biased coins as oracles.Toby Ord & Tien D. Kieu - 2009 - International Journal of Unconventional Computing 5:253-265.
    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 (...)
    Direct download  
    Export citation  
    Bookmark   1 citation