4
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

Type-2 Turing machines are not more powerful than ordinary Turing machines in the sense that any map $\mathbb{N} \to \mathbb{N}$ that can be computed by a type-2 machine can also be computed by an ordinary machine. To see this, suppose a type-2 Turing machine $T$ computes a function $f : \mathbb{N} \to \mathbb{N}$. We can convert $T$ to an ordinary machine by modifying it so that it stops as soon as it writes $f(n)$ on the output (and we can tell when this happens because the output is a single finite number, so it cannot take forever for the machine to produce it).

It is far more interesting to go up one level and compare computability of functionals, which are maps $$F : \mathbb{N}^\mathbb{N} \to \mathbb{N}$$ that take an infinite sequence of numbers as an input and output a number. Now there is a difference between type 1 and type 2.

Say that a functional $F$ is type-2 computable if there exists a type-2 Turing machine $T$ such that, for any sequence $\alpha \in \mathbb{N}^\mathbb{N}$, when $\alpha$ is written on the input tape and machine $T$ is run, it writes $F(\alpha)$ on the output tape (and terminates).

Say that a functional $F$ is type-1 computable if there exists a type-1 Turing machine $T$ (i.e., an ordinary one), such that, for any computable sequence $\alpha \in \mathbb{N}^\mathbb{N}$, if we write onto the input tape the encoding $n$ of a machine that computes $\alpha$, then $T(n)$ writes $F(\alpha)$ on the output tape (and terminates).

Notice that a type-1 computable functional only accepts computable inputs, whereas a type-2 computable functional accepts all inputs. If we write $\mathcal{R}$ for the set of all computable sequences of numbers (i.e., the total computable functions), then a type-1 computable functional is a map $F : \mathcal{R} \to \mathbb{N}$ computed by some type-1 machine, whereas a type-2 computable functional is a map $F : \mathbb{N}^\mathbb{N} \to \mathbb{N}$ computed by some type-2 machine.

Because $\mathcal{R} \subseteq \mathbb{N}^\mathbb{N}$, we can convert any type-2 functional to a type-1 functional by simply feeding it only computable inputs. We have:

Theorem: When a type-2 computable functional is restricted to computable inputs, it becomes a type-1 computable functional.

Proof. The theorem is not a complete triviality. The input is presented to a type-2 functional as a sequence, whereas to a type-1 functional it is presented as a description of a Turing machine computing the sequence. So, suppose $F$ is a type-2 functional computed by a type-2 machine~$T$. We convert $T$ to a type-1 machine as follows: when given an input $n$ which described a machine $M$ that computes some $\alpha \in \mathcal{R}$, we simulate an input type for $T$ so that whenever $T$ wants the $k$-th cell of the input, we run $M(k)$ to compute $\alpha(k)$ and give $T$ the answer. $\Box$

Can we go in the other direction? Suppose $F : \mathcal{R} \to \mathbb{N}$ is computed by a type-1 machine $T$. Perhaps we can extend $F$ to all of $\mathbb{N}^\mathbb{N}$ to get a computable $\overline{F} : \mathbb{N}^\mathbb{N} \to \mathbb{N}$ which agrees with $F$ on $\mathcal{R}$? The anwser is negative! (See Exercise 15-40 in H. Rogers Jr. "Theory of Recursive Functions and Effective Computability".)

The moral of the story is this (as I have often repeated on these forums): all known notions of computability of functions from numbers to numbers agree, but notions of computability of functionals do not, and they are incomparable in general.

$\endgroup$
  • $\begingroup$ Thanks, so to clarify: you say "Type-2 Turing machines are not more powerful than ordinary Turing machines in the sense that any map N→N that can be computed by a type-2 machine can also be computed by an ordinary machine. To see this, suppose a type-2 Turing machine T computes a function f:N→N. We can convert T to an ordinary machine by modifying it so that it stops as soon as it writes f(n) on the output (and we can tell when this happens because the output is a single finite number, so it cannot take forever for the machine to produce it)." $\endgroup$ – Mike Battaglia May 22 '18 at 15:05
  • $\begingroup$ Are you talking only about total recursive functions here? Because otherwise we have the same situation as usual - we either do not know at which step the output f(n) really has been obtained (similarly to an inductive Turing machine), or we do not know if the machine will ever finish outputting or is stuck in a loop. $\endgroup$ – Mike Battaglia May 22 '18 at 15:10
  • $\begingroup$ Yes, I am talking about total functions. Type 2 machines are defined so that they convert total sequences to total sequences. If you want to allow partial functions, you can do that too, in which case you get a more reasonable theory and a better match. $\endgroup$ – Andrej Bauer May 22 '18 at 15:40
  • 1
    $\begingroup$ Nope, a type 2 machine which accepts or rejects an infinite sequence simply outputs a single bit (if you insist on infinite computation, it can output dummy bits after that). One consequence of this is that in order to reach its decision, it must have only inspected a finite amount of input, an observation that leads to the important theorem that computable maps are continuous. $\endgroup$ – Andrej Bauer May 22 '18 at 19:58
  • 1
    $\begingroup$ Yes. Do you have a question? $\endgroup$ – Andrej Bauer May 25 '18 at 17:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.