Question

Certain idealizations of a Turing machine yield an increase in computational power, such as an inductive Turing machine, which can (trivially) solve the halting problem if it has an infinite amount of time to run.

A related variation is the "type-2 Turing machine" defined by Weihrauch, which (if I understand correctly) is basically a Turing machine with an infinite-length input, and a write-only output tape for which previous outputs cannot be changed. Such models are useful for describing real computation.

Does this model of computation have more computational power than a standard Turing machine, similar to the inductive one?

I would naively guess yes, since the theory of "type-2 computability" and "type-2 recursion" seems to be distinct from the ordinary theory of computability, and it seems intuitive that anything which is "type-1 computable" should also be "type-2 computable" (but not the other way around). However, I am unsure of all this.

Burgin (2004) seems to suggest this as a model of hypercomputation in his book on "super-recursive algorithms," but as he does not offer a proof of such, I may be misinterpreting.

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top