nLab hypercomputation

Contents

Contents

Idea

A concept of computation assuming computable operations more powerful than in traditional computability (more powerful than partial recursive functions and computable functions in computable analysis).

For instance a Turing machine that could not just run forever, but actually process an infinite number of steps “in finite time” would be a hypercomputer. Bauer provides a realizability topos for infinite time computation; see also Hamkins.

It has been argued that there are spacetimes – see at Malament–Hogarth spacetime – which are such that they allow trajectories on which a computer could travel indefinitely together with spacetime points at which an observer could observe the whole infinite history of the computer in finite time. If this indeed were physically realizable it would to some extent contradict the physical Church-Turing thesis, which asserts that no physical process can realize a computer more powerful than a Turing machine.

References

Last revised on September 15, 2019 at 05:15:37. See the history of this page for a list of all contributions to it.