JID:APAL AID:2399 /FLA [m3L; v 1.133; Prn:14/05/2014; 9:56] P.1 (1-11)

Annals of Pure and Applied Logic ••• (••••) •••–•••

Contents lists available at ScienceDirect

T m

B

U a

A

A

M 03 03 68 03

K

In

O

Su

T 1. m h et or ti

T st cl ht 01Annals of Pure and Applied Logic www.elsevier.com/locate/apal he computational strengths of α-tape infinite time Turing achines enjamin Rin niversity of California, Irvine, Logic and Philosophy of Science, Irvine, CA, USA r t i c l e i n f o a b s t r a c t rticle history: vailable online xxxx

SC:

D10

D60

Q05

D78 eywords: finite time Turing machine rdinal computability pertask ransfinite computation

In [7], open questions are raised regarding the computational strengths of so-called ∞-α-Turing machines, a family of models of computation resembling the infinitetime Turing machine (ITTM) model of [2], except with α-length tape (for α ≥ ω).

Let Tα denote the machine model of tape length α (so Tω is just the ITTM model).

Define that Tα is computationally stronger than Tβ (abbreviated Tα Tβ) precisely when Tα can compute all Tβ-computable functions f : min(α,β)2 → min(α,β)2, plus more. The following results are found: (1) Tω1 Tω. (2) There are countable ordinals α such that Tα Tω, the smallest of which is precisely γ, the supremum of ordinals clockable by Tω. In fact, there is a hierarchy of countable Tαs of increasing strength corresponding to the transfinite (weak) Turing-jump operator ∇. (3) There is a countable ordinal μ such that neither Tμ Tω1 nor Tμ Tω1—that is, the models

Tμ and Tω1 are computation-strength incommensurable (and the same holds if countable μ′ > μ replaces μ). A similar fact holds for any larger uncountable device replacing Tω1 . (4) Further observations are made about countable Tα. © 2014 Elsevier B.V. All rights reserved.

Background

Over the past few years, interest has grown in the study of models of transfinite computation—theoretical achines that extend classical computibility theory into an infinitary context. A number of distinct models ave been devised, typically resembling one of the classical machines (Turing machines, register machines, c.) but with some modification that takes the operations into the transfinite. For a detailed survey, see [14] [15]. Of the machines so defined during this recent wave, particular attention has been given to the infinite me Turing machines of [2], which were the first to see print.

Infinite time Turing machines, or ITTMs, are a set of theoretical computing machines similar to classical uring machines, with the exception that halting computations are not assumed to run for only finitely many eps. Instead, computations are permitted to run for transfinitely many steps before halting. Whereas a assical finitary Turing machine is considered to “fail” in some sense if it does not successfully halt within

E-mail address: brin@uci.edu. tp://dx.doi.org/10.1016/j.apal.2014.04.016 68-0072/© 2014 Elsevier B.V. All rights reserved.

JID:APAL AID:2399 /FLA [m3L; v 1.133; Prn:14/05/2014; 9:56] P.2 (1-11) 2 B. Rin / Annals of Pure and Applied Logic ••• (••••) •••–••• a an in

C in w m ta “c ta m an th fu ca va lim

W fr is m si be pa

H pl pr to us a ar du of 1 sa co 2 st ch (a 3 he 4 thfinite number of steps, an ITTM may compute through steps 1, 2, . . . , ω, (ω + 1), (ω + 2), . . . , (ω + ω), . . . d halt after, say, ω4 + ω + 17 steps. It can even halt after a non-recursive ordinal number of steps.

In [2], the machines are conceived as having three tapes: an input tape, an output tape, and a scratch tape tended for calculations. Each machine has a read–write head that at any given time occupies the nth cell n of each of these tapes simultaneously (the leftmost cell is C0, and the tapes have ω-many cells extending finitely to the right). In the present work, we instead imagine just a single tape for input and output, ith a parallel tape for scratch work. This type of machine is computationally equivalent to the three-tape achines.1

It will be convenient to use the fact from [3, Corollary 2.4] that it is possible to use the single scratch pe of a machine to simulate having a machine with multiple parallel tapes. As described in [6], there are anonical but tedious” translations of programs on machines with n tapes to programs on machines with one pe. We also recall from [6] that one can use finite binary strings as codes for ‘symbols’, and thus at times ay treat the tape as containing a sequence of arbitrary symbols from an alphabet rather than binary bits.

Since an ITTM may run for transfinitely many steps, it has time to read and process infinite-length input, d to write infinite-length output. Hence ITTMs can be understood as computing (partial) functions on e reals ω2. (We can still represent a natural number k by a string consisting of all 0s except Ck.) The nctions computable by an ITTM form a strict superset of the Turing-computable functions.

To define the machine’s behavior fully, [2] stipulates that on successor ordinal steps, cell values are lculated identically to the way they are determined in a Turing machine, but at limit ordinal steps, cell lues take on the lim sup of their values at previous stages.2 In the present paper, as in [6] and elsewhere, the inf is used instead. The difference is immaterial as the resulting models of computation are equivalent. e also set the machine’s head position and program state at the limit stage to their respective lim inf s om prior stages.3

For ITTMs there are both computable and noncomputable functions f : ω2 → ω2. Any recursive function computable, as is the classical halting problem. An ITTM can solve the latter by running any Turing achine computation in parallel with some program known to halt after ω steps, checking whether the mulated Turing computation has halted or not by that stage. The model’s computational power goes far yond this, however. It is capable of deciding membership in any set of reals up to complexity Π11—in rticular, it is able to determine whether a give real a ∈ ω2 codes4 a well-ordered relation on N (see [2]). owever, all ITTM-decidable sets of reals (indeed, all ITTM semi-decidable sets of reals) fall below comexity Δ12. For an example of non-computable functions, there are ITTM analogs of the classical halting oblem, defined below.