Editing Computability (section)

== Stronger models of computation ==
The [[Church–Turing thesis]] conjectures that there is no effective model of computing that can compute more mathematical functions than a Turing machine. Computer scientists have imagined many varieties of '''[[hypercomputer]]s''', models of computation that go beyond Turing computability.

=== Infinite execution ===
{{Main|Zeno machine}}
Imagine a machine where each step of the computation requires half the time of the previous step (and hopefully half the energy of the previous step...). If we normalize to 1/2 time unit the amount of time required for the first step (and to 1/2 energy unit the amount of energy required for the first step...), the execution would require

:<math>1 = \sum_{n=1}^{\infty} \frac{1}{2^n} = \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \frac{1}{16} + \cdots</math>

time unit (and 1 energy unit...) to run. This infinite series converges to 1, which means that this Zeno machine can execute a countably infinite number of steps in 1 time unit (using 1 energy unit...). This machine is capable of deciding the halting problem by directly simulating the execution of the machine in question. By extension, any convergent infinite [must be provably infinite] series would work. Assuming that the infinite series converges to a value ''n'', the Zeno machine would complete a countably infinite execution in ''n'' time units.

=== Oracle machines ===
{{Main|Oracle machine}}
So-called Oracle machines have access to various "oracles" which provide the solution to specific undecidable problems. For example, the Turing machine may have a "halting oracle" which answers immediately whether a given Turing machine will ever halt on a given input. These machines are a central topic of study in [[recursion theory]].

=== Limits of hyper-computation ===
Even these machines, which seemingly represent the limit of automata that we could imagine, run into their own limitations.  While each of them can solve the halting problem for a Turing machine, they cannot solve their own version of the halting problem. For example, an Oracle machine cannot answer the question of whether a given Oracle machine will ever halt.