Hypercomputation: computing more than the Turing machine

• Published in 2002
• Added on 2011-02-09

Due to common misconceptions about the Church-Turing thesis, it has been widely assumed that the Turing machine provides an upper bound on what is computable. This is not so. The new field of hypercomputation studies models of computation that can compute more than the Turing machine and addresses their implications. In this report, I survey much of the work that has been done on hypercomputation, explaining how such non-classical models fit into the classical theory of computation and comparing their relative powers. I also examine the physical requirements for such machines to be constructible and the kinds of hypercomputation that may be possible within the universe. Finally, I show how the possibility of hypercomputation weakens the impact of Godel's Incompleteness Theorem and Chaitin's discovery of 'randomness' within arithmetic.

Comment

A probably overblown argument for a model of computation that does more than Turing machines.

Links

• http://arxiv.org/abs/math/0209332
• http://arxiv.org/pdf/math/0209332v1

Other information

BibTeX entry

@article{Ord2002,
	key = {Ord2002},
	type = {article},
	title = {Hypercomputation: computing more than the Turing machine},
	author = {Ord, Toby},
	abstract = {Due to common misconceptions about the Church-Turing thesis, it has been
widely assumed that the Turing machine provides an upper bound on what is
computable. This is not so. The new field of hypercomputation studies models of
computation that can compute more than the Turing machine and addresses their
implications. In this report, I survey much of the work that has been done on
hypercomputation, explaining how such non-classical models fit into the
classical theory of computation and comparing their relative powers. I also
examine the physical requirements for such machines to be constructible and the
kinds of hypercomputation that may be possible within the universe. Finally, I
show how the possibility of hypercomputation weakens the impact of Godel's
Incompleteness Theorem and Chaitin's discovery of 'randomness' within
arithmetic.},
	comment = {A probably overblown argument for a model of computation that does more than Turing machines.},
	date_added = {2011-02-09},
	date_published = {2002-04-10},
	urls = {http://arxiv.org/abs/math/0209332,http://arxiv.org/pdf/math/0209332v1},
	collections = {Basically computer science,Unusual computers},
	journal = {Arxiv preprint math/0209332},
	url = {http://arxiv.org/abs/math/0209332 http://arxiv.org/pdf/math/0209332v1},
	year = 2002,
	archivePrefix = {arXiv},
	eprint = {math/0209332},
	primaryClass = {math.LO},
	urldate = {2011-02-09}
}