text:
# Using isosbestic points to extract interactions from structure factors

## Abstract

Inverting scattering experiments to obtain effective interparticle interactions for particles in solution is generally a poorly conditioned problem. More accurate potentials can be obtained through the use of isosbestic points, values of $`k`$ where the scattering intensity $`I(k)`$ or the structure factor $`S(k)`$ is invariant to changes in potential well-depth. These points also suggest a new extended corresponding states principle for particles in solution based on the particle density or packing fraction, the second osmotic virial coefficient, and a new measure of potential range.

Extracting effective interparticle interactions from experiments is a central objective in chemical physics, because these interactions govern physical behaviourLiko01 . But like many such inverse problems, this task is complicated. Experimental data is not perfect: statistical fluctuations occur, and results may not be obtainable over a complete parameter range. Moreover, the inversion procedures are often ill conditioned: small differences in the initial input can result in large changes in the final output. This letter concentrates on a well-known class of such problems, namely the inference of (spherically symmetric) effective interparticle pair potentials $`v^{eff}(r)`$ from experimental scattering data for particles in solution. For that reason lower effective volume fractions $`\eta `$ are investigated than in the better studied case of simple liquids near the triple point, where the dominance of entropic hard-core forcesHans86  makes it difficult to distinguish between different attractive potentialsReat86 ; Hans86 . Even though at lower volume fractions attractive interactions can determine the structureLoui01a , this letter shows that inversions are equally problematic, albeit for different reasons.

For particles in solution, the scattering intensity $`I(k)`$, measured by light, X-rays, or neutrons, is usually interpreted by dividing $`I(k)`$ by the single particle form factor $`P(k)`$, to obtain the structure factor $`S(k)=I(k)/(\rho P(k))`$Hunt01 ; here $`\rho =N/V`$ is the density. From $`S(k)`$, inferences are then made about the form of the inter-particle interactions $`v^{eff}(r)`$. However, this inversion is ill-conditioned: Within typical experimental accuracy, a single $`S(k)`$ at a given state-point can be interpreted with a wide range of different $`v^{eff}(r)`$’s. But, as this letter demonstrates, these problems can be circumvented by introducing a new concept, isosbestic points – values of the wave-vector $`k`$ for which $`S(k)`$ is invariant under changes of the attractive potential well depth. Isosbestic points determine the effective range of the $`v^{eff}(r)`$, and also suggest an extended corresponding states principle for particles in solution, described by three experimentally accessible variables: the range defined by these points, the particle density $`\rho `$ and the reduced second osmotic virial coefficient $`B_2^{}=B_2/B_2^{HS}`$, where $`B_2^{HS}`$ is the second virial coefficient of a hard-sphere (HS) system.

Fig. 1 helps set the stage and introduce the problem to be addressed here. Experimental dataHuan84 , taken from small-angle neutron-scattering (SANS) of a microemulsion composed of small water droplets, coated with a layer of surfactant (AOT), is compared to some theoretical structure factors $`S(k)`$. In the original letterHuan84  a best fit, using an approximate integral equation technique, yielded a hard-core diameter of $`\sigma =60\AA `$, a packing fraction $`\eta =\pi \sigma ^3/6=0.075`$, and an attractive square well (SW) potential with a range $`\mathrm{\Delta }_{SW}=0.02\sigma `$ and a well depth of $`\beta v(\sigma )=3.85`$. The quality of the integral equation fit was then confirmed by independent computer simulations. However, as strikingly demonstrated by Fig. 1, a wide range of other potentials, depicted in Fig. 1(b), also lead to fits of similar accuracy. These include HSs with attractive SWs of two different ranges $`\mathrm{\Delta }_{SW}`$, an Asakura-Oosawa (AO) depletion potentialAsak58  of range $`\mathrm{\Delta }_{AO}`$, an alternate simplified depletion potential of range $`\mathrm{\Delta }_D`$ showing the effects of solvation layersGotz98 , as well as a Lennard-Jones-n (LJ-n) potential, defined as:

$$v(r)=4ϵ\left(\left(\frac{\sigma }{r}\right)^{2n}\left(\frac{\sigma }{r}\right)^n\right),$$
(1)
with $`n=12`$. The $`S(k)`$ are calculated within the Percus Yevick (PY) integral equation closureHans86 ; PY , and are close to the analytical PY solution of Baxter’s modelBaxt68 .

Improving significantly on these pioneering experiments is hard. $`S(k)`$ is obtained by dividing $`I(k)`$ through by $`P(k)`$, which is only approximately determined, and which rapidly decays to zero for increasing $`k\sigma `$, so that achieving better accuracies for a larger $`k\sigma `$ range is very difficult. Moreover, there are few alternative methods to directly measure the interparticle interactions. In contrast, for simpler atomic or molecular systems, gas-phase experiments or ab-initio calculations can provide accurate independent estimates of the interactions, and impose important constraints on the potential forms with which to fit the experimental dataMaitland . Although increasingly accurate techniques being developed for the real-space measurement of the $`v^{eff}(r)`$ of particles in solutionIsra92 , these are often limited to certain particle types or sizes.

The upshot of Fig. 1 is that deducing an effective potential from experimental scattering data at one state point is difficult; the inversion is ill-conditioned. Clearly more information is needed to interpret the datacritique .

But first, what can be inferred from a single $`S(k)`$? One hint comes the Baxter model, which is completely determined by the packing fraction $`\eta `$ and the reduced osmotic virial coefficient $`B_2^{}`$ or equivalently, the Baxter parameter, defined as $`\tau =\frac{1}{4}/(1B_2^{})`$. The $`S(k)`$ in Fig. 1, with effective $`\tau `$ parameters ranging from $`\tau =0.093`$ to $`\tau =0.10`$ are all close to the Baxter model result with $`\tau =0.096`$. To first order therefore, measuring a single $`S(k)`$ in this regime of low packing fraction, commonly encountered for particles in solution, does not result in much more information about the effective potential than the reduced second virial coefficient $`B_2^{}`$. Just as in simple liquids inversions are hard because the $`S(k)`$ resemble those of HSsHans86 , here difficulties arise because they are close to the Baxter $`S(k)`$.

To make further progress, measurements at other state points are necessary. This is done in Figs. 2(a)-(d), which depict the $`S(k)`$ calculated for four LJ-n potentials at different temperatures. A best fit to the Baxter model $`S(k)`$ at each temperature would result in $`B_2^{}`$ as a function of temperature. But there is clearly more information in these curves: Each of the four $`v^{eff}(r)`$ results in a different set of isosbestic points, where the $`S(k)`$ is invariant for different temperatures. Fig. 2(e) shows that the first isosbestic point $`k_1\sigma `$ increases with increasing $`n`$, reflecting the decrease of the range of the LJ-n potential (1) depicted in Fig. 2(f). (Error bars in Fig 2(e) reflect the approximate nature of the isosbestic points.)

These observations can be quite easily rationalised by the following simple theory: If the total correlation function $`h(r)=g(r)1`$ is split into two parts, with $`h_0(r)=1`$ for $`r<\sigma `$, and $`h_1(r)=g(r)1`$ for $`r\sigma `$, then the structure factor $`S(k)=1+\rho \widehat{h}(k)`$ simplifies to

$$S(k)=1+\frac{4\pi \rho }{k}j_1(k)+\rho \widehat{h}_1(k),$$
(2)
where $`j_1(k)`$ is the first spherical Bessel function, and $`\widehat{h}_1(k)`$ is the Fourier Transform (FT) of $`h_1(r)`$. For potentials with a hard-core, such as most of those depicted in Fig. 1(b), this is exact, but even for the LJ-n potentials this is a good approximationsigma . Since $`\widehat{h}_0(k)=\frac{4\pi \rho }{k}j_1(k)`$ is independent of temperature (barring small effective $`\sigma `$ effects), Eq. 2 suggests that isosbestic points occur whenever $`\widehat{h}_1(k)=0`$.

It has already been pointed out that in many experimentally relevant cases with low $`\eta `$, the $`g(r)`$ are surprisingly well approximated by a simple form $`g(r)=\mathrm{exp}(\beta v(r))`$Loui00a ; Loui01a , as explicitly demonstrated in Fig. 3. This simple approximation, equivalent to taking a Mayer functionHans86  for $`h(r)`$, works best for particles with short range attractive potentials. These can become quite deep, leading to large values of $`g(r)`$ near contact, well before the system crosses a liquid-liquid or liquid-solid phase-line. Within this approximation, the dominant effect of varying the temperature is to change the amplitude of $`h_1(r)`$ (as demonstrated in Fig. 3(b)). To first order, the period of $`\widehat{h}_1(k)`$ is not affected and each $`k\sigma `$ where $`\widehat{h}_1(k)=0`$ leads to an isosbestic point. For an infinitely narrow potential, the isosbestic points would be at $`k_n\sigma =n\pi `$, but for a finite potential range there is a phase-shift, which explains why the $`k_n\sigma `$ move progressively further from $`n\pi `$ with increasing range. The excellent accuracy of this simple Mayer function theory for the first isosbestic point $`k_1\sigma `$ is demonstrated by the solid line in Fig. 2(e).

The examples depicted in Fig. 2 are at a relatively low packing fraction, but the isosbestic points are robust up to packing fractions of at least $`\eta =0.2`$, as shown in Fig. 4(a)density . These points are accurately described by the simple theory, described above.

If varying a parameter leads to isosbestic points, then this suggests that the well-depth of $`v^{eff}(r)`$ is changing while the range is not. When combined with the variation of $`B_2`$, this can help fix the form of $`v^{eff}(r)`$. However, this information may still not be sufficient, since the well-depth of $`v^{eff}(r)`$ may depend in an (unknown) non-linear fashion on the parameters like the temperature $`T`$, the pH, and salt or other additive concentration. Furthermore, as shown in Fig. 4(b), different potential shapes, picked to have the same isosbestic points, can generate similar $`S(k)`$ for each value of $`B_2^{}`$.

This similarity of the $`S(k)`$ ties in with the work of Noro and Frenkel (NF), who proposed that many properties of particles in solution could be understood from an an extended corresponding state principle based on the variables $`\eta `$, $`B_2^{}`$, and an effective well depth $`\beta ϵ`$Noro00 . However, the three potentials shown in Fig. 4(b) do not have the same well-depth, while still showing similar $`S(k)`$. This suggests an alternative corresponding states principle based on the variables $`\eta `$, $`B_2^{}`$, and an effective range $`\mathrm{\Delta }_{eff}`$ related to the isosbestic points. In fact, as NF point out, the potential range is not always uniquely defined when comparing different $`v^{eff}(r)`$’s. They suggested a non-linear mapping based on $`B_2^{}`$ to derive an effective SW range for each potential they consider. I used a simpler linear mapping to define the range $`\mathrm{\Delta }_{eff}`$ of a given potential as identical to that of a SW with the same $`k_1\sigma `$. For the LJ-n potentials this criterion reduces to the distance $`r\sigma `$ where $`\beta v(r)`$ reaches $`1/4`$ of its maximum depth, for the AO potential the effective SW range is $`\mathrm{\Delta }_{eff}0.42\mathrm{\Delta }_{AO}`$, and for the hard-core Yukawa potential, with an attractive tail of the form $`v(r)=ϵ\mathrm{exp}(r/\lambda )`$ for $`r>\sigma `$, the mapping is $`\mathrm{\Delta }_{eff}1.15\lambda `$. The results are depicted in Fig. 5, and show that these simple linear mappings successfully define an effective range for each potential type. An accurate approximation of $`k_1\sigma `$ for the (effective) SW is given by $`k_1\sigma \pi /(1+\mathrm{\Delta }_{eff}/2+\mathrm{\Delta }_{eff}^2/12)`$, which follows from an expansion of the exact solution to the simple theory of isosbestic points.

Another argument for including the $`\mathrm{\Delta }_{eff}`$ (instead of the well-depth) as one of the relevant $`3`$ variables is that the range determines the topology of the phase-diagramNoro00 . The critical range below which the fluid-fluid transition becomes metastable to the fluid-solid line is at $`\mathrm{\Delta }_{eff}0.15`$ for all four potentials (SW, AO, Yukawa and LJ-n), something consistent with what NF found. In addition, $`\mathrm{\Delta }_{eff}`$ is directly experimentally accessible through $`k_1\sigma `$. For example, taking advantage of the proximity of a metastable fluid-fluid critical point to enhance nucleation, a proposal recently made for protein solutionstenW97 , would involve tailoring solution conditions such that the measured isosbestic point is just above $`k_1\sigma =2.92`$, so that $`\mathrm{\Delta }_{eff}`$ is just below $`0.15`$.

In summary then, extracting effective potentials $`v^{eff}(r)`$ from $`S(k)`$ at the lower packing fractions typically encountered for particles in solution is a poorly conditioned problem. Whereas in simple liquids the HS model describes the dominant features of the $`S(k)`$, here the Baxter model appears to be the fundamental underlying model for $`S(k)`$ around which different attractive potentials only induce a mild perturbation. More information can be obtained by studying the isosbestic points, which help determine the range $`\mathrm{\Delta }_{eff}`$ of the potentials. Together with $`\eta `$ and $`B_2^{}`$, $`\mathrm{\Delta }_{eff}`$ can be used to define an extended corresponding states principle. Particles in solution with similar values of these three parameters should have similar properties, such as the relative stability of the fluid-fluid and fluid-solid binodals. In other words, many solution properties could be deduced without having to actually invert to an explicit form of $`v^{eff}(r)`$.

Another advantage of a description based on these variables is that they are directly experimentally accessible. In fact, numerous examples of isosbestic points can be found in the literature, ranging from colloids with short-range sticky coatsDuit91 , to colloid-polymer mixturesYe96 , to globular proteinsTard99 , to magnetic colloidsDubo99  and to colloid-micelle mixturesBart . Interestingly, these points should also appear in $`I(k)`$, although determining $`\mathrm{\Delta }_{eff}`$ still depends on an accurate $`P(k)`$. Future work will consider the role of size polydispersity (expected to mainly affect higher order $`k_n\sigma `$) and the existence of isosbestic points for non-spherical objects.

The author thanks P. Bartlett for first bringing isosbestic points to his attention, J. P. K. Doye for helpful discussions, and The Royal Society for financial support.


format: text

text:
# Separable Kernel of Nucleon-Nucleon Interaction in the Bethe-Salpeter Approach for 𝐽={0,1} The work was supported in part by the RFBR grants N 00-15-96737 and N 02-02-16542.

## 1 Formalism

We start with the partial-wave decomposed Bethe-Salpeter equation for the nucleon-nucleon $`T`$ matrix (in the rest frame of two-nucleon system):

$`t_{L^{}L}(p_0^{},p^{},p_0,p;s)`$ $`=`$ $`v_{L^{}L}(p_0^{},p^{},p_0,p;s)`$
$`+`$ $`{\displaystyle \frac{i}{4\pi ^3}}{\displaystyle \underset{L^{\prime \prime }}{}}{\displaystyle 𝑑k_0k^2𝑑k\frac{v_{L^{}L^{\prime \prime }}(p_0^{},p^{},k_0,k;s)t_{L^{\prime \prime }L}(k_0,k,p_0,p;s)}{(\sqrt{s}/2e_k+i0)^2k_0^2}}.`$
Here $`t`$ is the partial-wave decomposed $`T`$ matrix and $`v`$ is the kernel of the $`NN`$ interaction, $`e_k=\sqrt{k^2+m^2}`$. There is only one term in the sum for the singlet (uncoupled triplet) case ($`L=J`$) and there are two terms for the coupled triplet case ($`L=J1`$). We introduced square of the total momentum $`s=P^2=(p_1+p_2)^2`$ and the relative momentum $`p=(p_1p_2)/2`$ \[$`p^{}=(p_1^{}p_2^{})/2`$\] (for details, see reference ).

Assuming the separable form (rank I) for the partial-wave decomposed kernels of $`NN`$ interactions

$`v_{L^{}L}(p_0^{},p^{},p_0,p;s)=\lambda g^{[L^{}]}(p_0^{},p^{})g^{[L]}(p_0,p),`$ (2)
we can solve eq. (1) and write for the $`T`$ matrix:

$`t_{L^{}L}(p_0^{},p^{},p_0,p;s)=\tau (s)g^{[L^{}]}(p_0^{},p^{})g^{[L]}(p_0,p),`$ (3)
with the function $`\tau (s)`$ being:

$`\tau (s)=1/(\lambda ^1+h(s)).`$ (4)
Function $`h(s)`$ has the following form:

$`h(s)={\displaystyle \underset{L}{}}h_L(s)={\displaystyle \frac{i}{4\pi ^3}}{\displaystyle 𝑑k_0k^2𝑑k\underset{L}{}\frac{[g^{[L]}(k_0,k)]^2}{(\sqrt{s}/2e_k+i0)^2k_0^2}}.`$ (5)
We use following normalization condition for the on-mass-shell $`T`$ matrix for the singlet (uncoupled triplet) case:

$`t(s)t(0,\overline{p},0,\overline{p},s)={\displaystyle \frac{16\pi }{\sqrt{s}\sqrt{s4m^2}}}e^{i\delta }\mathrm{sin}\delta ,`$ (6)
and for the coupled triplet case:

$`t(s)={\displaystyle \frac{8\pi i}{\sqrt{s}\sqrt{s4m^2}}}\left(\begin{array}{cc}\mathrm{cos}2ϵe^{2i\delta _<}1& i\mathrm{sin}2ϵe^{i(\delta _<+\delta _>)}\\ i\mathrm{sin}2ϵe^{i(\delta _<+\delta _>)}& \mathrm{cos}2ϵe^{2i\delta _>}1\end{array}\right),`$ (9)
with $`\overline{p}=\sqrt{s/4m^2}=\sqrt{2mT_{lab}}`$. We introduced phase shifts $`\delta \delta _{L=J}`$, $`\delta _{}\delta _{L=J1}`$ and mixing parameter $`ϵ`$.

Bound state, if exist, is described by simple pole in the $`T`$ matrix. Using eq. (4) we can write ($`M_b=2mE_b`$, $`E_b`$ is the energy of bound state):

$`\lambda ^1=h(s=M_b^2).`$ (10)
We introduce also the low-energy parameters – scattering length $`a_L`$ and effective range $`r_L`$ – by the following equation:

$`\overline{p}^{2L+1}\mathrm{cot}\delta _L(s)=1/a_L+{\displaystyle \frac{r_L}{2}}\overline{p}^2+𝒪(\overline{p}^3)`$ (11)
At this point by using eq. (3) and calculating $`T`$ matrix on the mass-shell ($`p_0=p_0^{}=0,p=p^{}=\overline{p}`$) we can connect internal parameters of the $`NN`$ kernel and observables – phase shifts, bound state energy and low-energy parameters.

We use covariant generalization of the Yamaguchi  functions for $`g^{[L]}(k_0,k)`$:

$`g^{[S]}(k_0,k)={\displaystyle \frac{1}{k_0^2k^2\beta _0^2+i0}},`$ (12)
$`g^{[P]}(k_0,k)={\displaystyle \frac{\sqrt{|k_0^2+k^2|}}{(k_0^2k^2\beta _1^2+i0)^2}},`$ (13)
$`g^{[D]}(k_0,k)={\displaystyle \frac{C(k_0^2k^2)}{(k_0^2k^2\beta _2^2+i0)^2}}.`$ (14)
Let us consider function $`h_0(s)`$ defined in the following way (we introduce explicit dependence on $`\beta `$):

$`h_0(s,\beta )={\displaystyle \frac{i}{4\pi ^3}}_{\beta ^2}{\displaystyle 𝑑k_0k^2𝑑k\frac{1}{(\sqrt{s}/2e_k+i0)^2k_0^2}\frac{1}{k_0^2e_\beta ^2+i0}},`$ (15)
here $`e_\beta =\sqrt{k^2+\beta ^2}`$ and $`_{\beta ^2}=/\beta ^2`$.

Analyzing the analytic structure and properties of the function $`h_0(s,\beta )`$ on $`s`$ we can rewrite it in the dispersion form:

$`h_0(s,\beta )={\displaystyle \underset{4m^2}{\overset{+\mathrm{}}{}}}{\displaystyle \frac{\rho (s^{},\beta )ds^{}}{s^{}siϵ}},`$ (16)
$`\rho (s^{},\beta )=\theta (s^{}4m^2)\rho _{\mathrm{el}}(s^{},\beta )+\theta (s^{}4(m+\beta )^2)\rho _{\mathrm{in}}(s^{},\beta ),`$
with two spectral functions $`\rho _{\mathrm{el};\mathrm{in}}`$ (el stands for elastic and in for inelastic) which are connected with the imaginary parts as

$`\rho (s^{},\beta )={\displaystyle \frac{1}{\pi }}\mathrm{Im}h_0(s^{},\beta )={\displaystyle \frac{1}{2\pi i}}(h_0h_0^{}).`$ (17)
Calculating integral (16) we can obtain analytic expressions for function $`h_0(s,\beta )`$ and taking into account definitions (12-14) can connect all other functions $`h^{[L]}`$ with $`h_0`$ as:

$`h^{[S]}(s,\beta _0)=h_0(s,\beta _0),`$ (18)
$`h^{[P]}(s,\beta _1)={\displaystyle \frac{1}{2}}\left[_{\beta _1^2}+{\displaystyle \frac{1}{3}}\beta _1^2_{\beta _1^2}^2\right]h_0(s,\beta _1),`$ (19)
$`h^{[D]}(s,\beta _2)=C^2\left[1+\beta _2^2_{\beta _2^2}+{\displaystyle \frac{1}{6}}\beta _2^4_{\beta _2^2}^2\right]h_0(s,\beta _2).`$ (20)
## 2 Calculations and results

We can now calculate internal parameters of the $`NN`$ kernel by using obtained above equations to reproduce experimental values for the phase shifts (data are taken using SAID program http://gwdac.phys.gwu.edu/), deuteron energy and quadrupole moment, low-energy parameters (data are from ref. ).

1. To find parameters $`\lambda `$ and $`\beta `$ in $`{}_{}{}^{1}S_{0}^{+}`$ channel we solve system of the nonlinear equations (exp stands for experimental, $`s`$ \- for singlet):

$`a_s^{\mathrm{exp}}=a_s(\lambda ,\beta ),r_s^{\mathrm{exp}}=r_s(\lambda ,\beta ).`$ (21)
2. To find parameters $`\lambda `$, $`\beta _0`$, $`\beta _2`$ and $`C`$ in $`{}_{}{}^{3}S_{1}^{+}^3D_1^+`$ coupled channel we solve system of the nonlinear equations ($`t`$ stands for triplet):

$`a_t^{\mathrm{exp}}=a_t(\lambda ,\beta _0,\beta _2,C),E_d^{\mathrm{exp}}=r_0(\lambda ,\beta _0,\beta _2,C),`$ (22)
$`p_d=p_d(\lambda ,\beta _0,\beta _2,C),q_d^{\mathrm{exp}}=q_d(\lambda ,\beta _0,\beta _2,C).`$
Here we introduced $`D`$-wave pseudoprobability $`p_d`$.

3. To find parameters $`\lambda `$ and $`\beta `$ in uncoupled $`{}_{}{}^{3}P_{0}^{+}`$, $`{}_{}{}^{1}P_{1}^{+}`$ and $`{}_{}{}^{3}P_{1}^{+}`$ channels we use procedure to minimize function:

$`\chi ^2={\displaystyle \underset{i=1}{\overset{n}{}}}(\delta ^{\mathrm{exp}}(s_i)\delta (s_i))^2/(\mathrm{\Delta }\delta ^{\mathrm{exp}}(s_i))^2,`$ (23)
where $`n`$ is the number of the experimental points taking into account.

The results of calculations are given in tables 1 and 2 and figs. 1-4.

Table 1. Parameters for $`{}_{}{}^{1}S_{0}^{+}`$ and $`{}_{}{}^{3}S_{1}^{+}^3D_1^+`$ channels.
$`{}_{}{}^{1}S_{0}^{+}`$ $`{}_{}{}^{3}S_{1}^{+}^3D_1^+`$ $`{}_{}{}^{3}S_{1}^{+}^3D_1^+`$ $`{}_{}{}^{3}S_{1}^{+}^3D_1^+`$    ($`p_d=4\%`$) ($`p_d=5\%`$) ($`p_d=6\%`$)    $`\lambda `$ (GeV2) -0.294254 -0.499045 -0.425235 -0.359856  $`\beta _0`$ (GeV) 0.224129 0.251248 0.246713 0.242291  $`\beta _2`$ (GeV)  0.294096 0.324494 0.350217  C  1.6489 2.4109 3.2801

Table 2. Parameters for $`{}_{}{}^{3}P_{0}^{+}`$, $`{}_{}{}^{1}P_{1}^{+}`$ and $`{}_{}{}^{3}P_{1}^{+}`$ channels.
$`{}_{}{}^{3}P_{0}^{+}`$ $`{}_{}{}^{3}P_{0}^{+}`$ $`{}_{}{}^{1}P_{1}^{+}`$ $`{}_{}{}^{1}P_{1}^{+}`$ $`{}_{}{}^{3}P_{1}^{+}`$ $`{}_{}{}^{3}P_{1}^{+}`$   n=3 n=5 n=4 n=5 n=7 n=9    $`\lambda `$ (GeV2) -0.0295720 -0.0161201 0.0915850 0.195296 0.312975 0.658122  $`\beta _1`$ (GeV) 0.238515 0.2186083 0.276724 0.308907 0.338898 0.381901

Figure 1. $`{}_{}{}^{1}S_{0}^{+}`$ and $`{}_{}{}^{3}S_{1}^{+}`$ channels phase shifts.

aaa Figure 2. $`{}_{}{}^{3}P_{0}^{+}`$ channel phase shifts.

aaa Figure 3. $`{}_{}{}^{1}P_{1}^{+}`$ channel phase shifts.

aaa Figure 4. $`{}_{}{}^{3}P_{1}^{+}`$ channel phase shifts.


text:
# Muon acceleration with a very fast ramping synchrotron for a neutrino factory

## 1 Introduction

Traditionally ramping synchrotrons have provided economical particle acceleration. Here we explore a very fast ramping muon synchrotron for a neutrino factory . The accelerated muons would be stored in a racetrack to produce neutrino beams as they decay ($`\mu ^{}e^{}\overline{\nu }_e\nu _\mu `$ or $`\mu ^+e^+\nu _e\overline{\nu }_\mu `$). Neutrino oscillations  have been observed at experiments such as Homestake , Super–Kamiokande , and SNO . Further exploration using a neutrino factory could reveal effects such as CP violation in the lepton sector which could explain the matter–antimatter asymmetry of the universe.

This synchrotron must accelerate muons from 4 to 20 GeV/c with moderate decay loss. Because synchrotron radiation goes as $`m^4`$, muons radiate two billion times ( $`(105.7/.511)^4`$ ) less power than electrons for any given ring diameter and lepton energy. Magnet eddy current losses are minimized by the low duty cycle of the machine plus thin iron laminations and copper conductors. Grain oriented silicon steel is used to provide a high magnetic field with a high $`\mu `$ to minimize magnetic energy stored in the return yoke. The magnetic energy stored in the gap is minimized by reducing its size. Cool muons  with low beam emittance allow this. Stored energy goes as $`B^2/2\mu `$. The voltage required to drive a magnet is equal to $`Ldi/dt`$. Very high voltage is expensive. $`di/dt`$ must be large because of the 2 $`\mu `$sec muon lifetime, so the main option for lowering voltage is to shrink the volume of stored energy to reduce the inductance, $`L`$.

Acceleration to 4 GeV might feature fixed field dogbone arcs  to minimize muon decay loss. Fast ramping synchrotrons  might also accelerate muons to higher energies for a $`\mu ^+\mu ^{}`$ collider .

## 2 Lattices

As a first step, we form arcs with sequences of combined function cells formed within continuous long magnets, whose poles are alternately shaped to give focusing gradients of each sign. An example of such a cell has been simulated using SYNCH . The example has gradients that alternate from positive 20 T/m gradient (2.24 m long), to zero gradient (.4 m long) to negative 20 T/m gradient (2.24 m) to zero gradient (0.4 m), etc. The relatively short zero gradient section is included to approximate a real smooth change in the gradients. Details are given in Table 1.

It is proposed to use 5 such arc cells (possibly all in one magnet) to form an arc segment. These segments are alternated with straight sections containing RF. The phase advance through one arc segment is 5 x 72 = 360 degrees. This being so, dispersion suppression between straights and arcs can be omitted. With no dispersion in the straight sections, the dispersion performs one full oscillation in each arc segment, returning to zero for the next straight as shown in Fig. 1. There will be 18 such arc segments and 18 straight sections, forming the 18 superperiods in the ring.

Straight sections (22 m) without dispersion are used for superconducting RF, and, in two longer straights (44 m), the injection and extraction. To assure sufficiently low magnetic fields at the cavities, relatively long field free regions are desirable. A straight consisting of two half cells would allow a central gap of 10 m between quadrupoles, and two smaller gaps at the ends. Details are given in Table 2. Matching between the arcs and straights is not yet designed. The total circumference of the ring including combined functions magnets and straight sections adds up to 917 m ($`18\times 26.5+\mathrm{\hspace{0.17em}16}\times 22+\mathrm{\hspace{0.17em}2}\times 44`$).

## 3 Superconducting RF

The RF must be distributed around the ring to avoid large differences between the beam momentum ( which increases in steps at each RF section) and the arc magnetic field (which is increasing continuously). RF parameters are shown in Table 3.

The amount of RF used is a tradeoff between cost and muon survival. Survival is somewhat insensitive to the fraction of stored energy the beam removes from the RF cavities, because the voltage drop is balanced by time dilation. Here, only 8.2% of RF energy is used. One could, in the spirit of Oliver Twist, ask for more. Using more of the RF energy is particularly appealing with a smaller ring. Very cold muons require less focusing and allow a smaller ring. If the muons take a few extra turns at the end to accelerate, only a few extra will be lost. Also, extra acceleration time at the end will translate into less voltage needed to ramp magnets.

## 4 Combined Function Magnets

The muons accelerate from 4 to 20 GeV. If they are extracted at 95% of full field they will be injected at 19% of full field. For acceleration with a plain sine wave, injection occurs at 110 and extraction occurs at 720. So the phase must change by 610 in 37 $`\mu `$sec. Thus the sine wave goes through 3600 in 218 $`\mu `$sec, which equals a frequency of 4600 Hz.

Estimate the energy stored in each 26.5 m long combined function magnet. The gap is about .14 m wide and has an average height of .06 m. Assume an average field of 1.1 Tesla. The permeability constant, $`\mu _0`$, is $`4\pi \times 10^7`$. $`W=B^2/2\mu _0[\text{Volume}]=`$ 110 000 Joules. Next given one turn, an LC circuit capacitor, and a 4600 Hz frequency; estimate current, voltage, inductance, and capacitance.

$`B={\displaystyle \frac{\mu _0NI}{h}}I={\displaystyle \frac{Bh}{\mu _0N}}=52\text{kA;}`$ $`W=.5LI^2L=2W/I^2=80\mu \text{H}`$ (1)
$`f={\displaystyle \frac{1}{2\pi }}\sqrt{{\displaystyle \frac{1}{LC}}}C={\displaystyle \frac{1}{L(2\pi f)^2}}=15\mu \text{F;}`$ $`W=.5CV^2V=\sqrt{2W/C}=120\text{kV}`$ (2)
Separate coils might be put around each return yoke to halve the voltage as illustrated in Fig. 2. The stack of SCRs driving each coil might be center tapped to halve the voltage again. Four equally spaced coil slots could be put in each side yoke to cut the voltage by five, while leaving the pole faces continuous. 6 kV is easier to insulate than 120 kV. It may be useful to shield or chamfer  magnet ends to avoid large eddy currents where the field lines typically do not follow laminations. A DC offset power supply  could be useful. Neutrino horn power supplies look promising .

Grain oriented silicon steel is chosen for the return yoke due to its high permeability at high field at noted in Table 4. This minimizes the energy stored in the yoke which goes as $`B^2/2\mu `$. The skin depth  of a 100 micron thick lamination is given by

$$\text{Skin Depth}=\delta =\sqrt{\rho /\pi f\mu }=\sqrt{47\times 10^8/\pi \mathrm{\hspace{0.17em}4600\hspace{0.17em}1000}\mu _0}=160\mu \text{m}$$
(3)
Take $`\mu =1000\mu _0`$ as a limit on magnetic saturation and hence energy storage in the yoke. Next estimate the fraction of the inductance of the yoke that remains after eddy currents shield the laminations . The lamination thickness is $`t`$.

$$\text{L/L}_0=(\delta /t)(\mathrm{sinh}(t/\delta )+\mathrm{sin}(t/\delta ))/(\mathrm{cosh}(t/\delta )+\mathrm{cos}(t/\delta ))=0.995$$
(4)
So it appears that magnetic fields can penetrate 100 micron thick laminations at 4600 Hz. If allowable, thicker 175 micron thick laminations would be half as costly and can achieve a somewhat higher packing fraction.

Calculate the resistive energy loss in the copper coils, which over time is equal to 1/2 the loss at the maximum current of 52 000 amps. The 1/2 comes from the integral of cosine squared. Table 5 gives the resistivity of copper. Four 5 cm square copper conductors each 5300 cm long have a total power dissipation of 130 kilowatts/magnet. Eighteen magnets give a total loss of 2340 kilowatts. But the neutrino factory runs at 30 Hz. Thirty half cycles of 109 $`\mu `$sec per second gives a duty factor of 300 and a total $`I^2R`$ loss of 8000 watts. Muons are orbited in opposite directions on alternate cycles. If this proves too cumbersome, the duty cycle factor could be lowered to 150.

$$R=\frac{5300(1.8\mu \mathrm{\Omega }\text{-cm})}{(4)(5^2)}=95\mu \mathrm{\Omega };P=I^2R_0^{2\pi }\mathrm{cos}^2(\theta )𝑑\theta =\text{130\hspace{0.17em}000 w/magnet}$$
(5)
Find the skin depth of copper at 4600 Hz to see if .25 mm (30 gauge) wire is useable.

$$\text{Skin Depth}=\delta =\sqrt{\rho /\pi f\mu _0}=\sqrt{1.8\times 10^8/\pi \mathrm{\hspace{0.17em}4600}\mu _0}=0.97\text{mm}$$
(6)
Now calculate the dissipation due to eddy currents in this .25 mm wide conductor, which will consist of transposed strands to reduce this loss . To get an idea, take the maximum B-field during a cycle to be that generated by a 0.025m radius conductor carrying 26000 amps. The eddy current loss in a rectangular conductor made of transposed square wires .25 mm wide (sometimes called Litz wire ) with a perpendicular magnetic field is as follows. The width of the wire is $`w`$ and $`B=\mu _0I/2\pi r=0.2`$ Tesla.

$$P=\text{[Volume]}\frac{(2\pi fBw)^2}{24\rho }=[\mathrm{4\; .05}^253]\frac{(2\pi \mathrm{4600\; .2\; .00025})^2}{(24)\mathrm{\hspace{0.17em}1.8}\times 10^8}=2800\text{kilowatts}$$
(7)
Multiply by 18 magnets and divide by a duty factor of 300 to get an eddy current loss in the copper of 170 kilowatts. Stainless steel water cooling tubes will dissipate a similar amount of power . Alloy titanium cooling tubes would dissipate less.

Do the eddy current losses  in the 100 micron thick iron laminations. Take a quarter meter square area, a 26.5 meter length, and an average field of 1.1 Tesla.

$$\text{P}=\text{[Vol]}\frac{(2\pi fBt)^2}{24\rho }=[(26.5)(.5^2)]\frac{(2\pi \mathrm{2600\; 1.1\; .0001})^2}{(24)\mathrm{\hspace{0.17em}47}\times 10^8}=5900\text{kw}$$
(8)
Multiply by 18 magnets and divide by a duty factor of 300 to get an eddy current loss in the iron laminations of 350 kilowatts or 700 watts/m of magnet. So the iron will need some cooling. The ring only ramps 30 time per second, so the $`𝐇𝑑𝐁`$ hysteresis losses will be low, even more so because of the low coercive force, Hc, of grain oriented silicon steel.

## 5 Conclusions

The low duty cycle of the neutrino factory leads to reasonable eddy current losses in a 4600 Hz ring. Muon survival is 83%. The high permeability of grain oriented silicon steel permits high fields with little energy stored in the yoke. Gradients are switched within dipoles to minimize eddy current losses in ends. Time dilation allows extra orbits with little muon decay at the end of a cooling cycle. This allows one to use more of the stored RF energy. Much of the magnetic field in our lattice is used for focusing rather than bending the muon beam. More muon cooling would lead to less focusing, more bending, and an even smaller ring.

## Acknowledgments

This work was supported by the U. S. Dept. of Energy and National Science Foundation. Many thanks to K. Bourkland, S. Bracker, C. Jensen, S. Kahn, H. Pfeffer, G. Rees, Y. Zhao, and M. Zisman for their help and suggestions.

## References


text:
# Infinite time Turing machines

## 1 Supertasks

A supertask is a task involving infinitely many steps. Because any kind of infinitary computation will naturally involve algorithms having infinitely many computational steps—supertask algorithms—the supertask concept seems to be central to any understanding of infinitary computability. So before introducing the infinite time Turing machine model in the next section, with its explicit supertask notions of computability and decidability, let me first discuss a few supertask examples more generally.

Zeno of Elea (ca. 450 B.C.) was perhaps the first to grapple with the supertask concept in his famous paradoxical argument that it is impossible to go from here to there. Before arriving, one must first get halfway there, and before that one must get halfway to the halfway point, and so on, ad infinitum. Because one cannot accomplish these infinitely many tasks, Zeno argued, all motion is impossible. Thus, he takes the impossibility of completing a supertask as the foundation of his reductio.

In the twentieth century philosophical literature, the puzzles and paradoxes continue. Take Thomson’s lamp (Thomson 1954), for example, which is on for $`1/2`$ minute, off for $`1/4`$ minute, on for $`1/8`$ minute, and so on. After one minute (the sum of the series $`1/2+1/4+1/8+\mathrm{}`$), is it on or off? The literature is full of answers. Another toy example is the super-$`\pi `$ machine, which writes out the successive digits of $`\pi `$ on a tape, the first in $`1/2`$ minute, the next in $`1/4`$ minute, and so on, so that all the digits are written in a finite amount of time. Because there can be no last or final step in such a process, Chihara (1965) has criticized the completion of such an algorithm as unintelligible.

In a more entertaining example,22footnotemark: 2 let’s suppose that you have infinitely many one dollar bills (numbered 1, 3, 5, $`\mathrm{}`$) and upon entering a nefarious underground bar, you come upon the Devil sitting at a table piled high with money. You sit down, and the Devil explains to you that he has an attachment to your particular bills and is willing to pay you a premium to buy them from you. Specifically, he is willing to pay two dollars for each of your one-dollar bills. To carry out the exchange, he proposes an infinite series of transactions, in each of which he will hand over to you two dollars and take from you one dollar. The first transaction will take $`1/2`$ hour, the second $`1/4`$ hour, the third $`1/8`$ hour, and so on, so that after one hour the entire exchange will be complete. The Devil takes a sip of whiskey while you mull it over; should you accept his proposal? Perhaps you think you will become richer, or perhaps you think with infinitely many bills it will make no difference? At the very least, you think, it will do no harm, and so the contract is signed and the procedure begins. How could the deal harm you?

It appears initially that you have made a good bargain, because at every step of the transaction, he pays you two dollars and you give up only one. The Devil is very particular, however, about the order in which the bills are exchanged. The contract stipulates that in each sub-transaction he buys from you your lowest-numbered bill and pays you with higher-numbered bills. Thus, on the first transaction he accepts from you bill number 1, and pays you with bills numbered 2 and 4. On the next transaction he buys from you bill number 2 (which he had just paid you) and gives you bills numbered 6 and 8. Next, he buys bill number 3 from you with bills 10 and 12, and so on. When all the exchanges are completed, what do you discover? You have no money left at all! The reason is that at the $`n^{\text{th}}`$ exchange, the Devil took from you bill number $`n`$, and never subsequently returned it to you. So while it seemed as though you were becoming no poorer with each exchange, in fact the final destination of every dollar bill in the transaction is under the Devil’s ownership. The Devil is a shrewd banker, and you should have paid more attention to the details of the supertask transaction to which you agreed. And similarly, the point is that when we design supertask algorithms to solve mathematical questions, we must take care not to make inadvertent assumptions about what may be true only for finite algorithms.

Supertasks have also been studied by the physicists. In classical mechanics under the Newtonian gravity law (neglecting relativity), it is possible to arrange finitely many stars in orbiting pairs, each pair orbiting the common center of mass of all the pairs, and a single tiny moon racing faster around, squeezing just so between the dual stars so as to pick up speed with every such transaction. Assuming point masses (or collapsing stars to avoid collision), the arrangement can be made to lead by Newton’s law of gravitation to infinitely many revolutions in finite time.

Other supertasks reveal apparent violations of the conservation of energy in Newtonian physics: imagine infinitely many billiard balls of successively diminishing size, converging to a point (see Laraudogoitia 1996). The balls are initially at rest, but then the first is set rolling. It collides with the next, transferring all its energy, and that ball begins to roll. Each ball in turn collides with the next, transferring all its energy. Because of the physical arrangements of the system, the motion disappears in a sense into the singularity; after a finite amount of time all the collisions have taken place, and the balls are at rest. So we have described a physical process in which energy is conserved at each step, in every interaction, but not overall through time.

Another arrangement has the balls spaced further and further out to infinity, pushing the singularity out to the point at infinity. The first ball knocks the second, which sends the next flying, and so on out to infinity. If the balls speed up sufficiently fast, under Newtonian rules it can be arranged that all the motion is completed in a finite amount of time. The interesting thing about this example and the previous one is that time-symmetry allows them to run in reverse, with static configurations of balls suddenly coming into motion without violating conservation of energy in any interaction.

More computationally significant supertasks have been proposed by physicists in the context of relativity theory (Pitowsky 1990, Earman 1995, Earman, et. al. 1993, Hogarth 1992, Hogarth 1994). Suppose that you want to know the answer to some number theoretic conjecture, such as whether there are additional Fermat primes (primes of the form $`2^{2^n}+1`$), a conjecture that can be confirmed with a single numerical example. The way to solve the problem is to board a rocket, while setting your graduate students to work on earth looking for an example. While you fly faster and faster around the earth, your graduate students, and their graduate students and so on, continue the exhaustive search, with the agreement that if they ever find an example, they will send a radio signal up to the rocket. Meanwhile, by accelerating sufficiently fast towards the speed of light (but never exceeding it), it is possible to arrange that the relativistic time contraction on the rocket will mean that a finite amount of time on the rocket corresponds to an infinite amount of time on the earth. The point is therefore that by means of the communication between the two reference frames, what corresponds to an infinite search can be completed in a finite amount of time. And it is precisely this ability to carry out such infinite searches—to go to the horizon and back in a finite amount of time—that will make infinite time Turing machines so powerful.

With more complicated arrangements of rockets flying around rockets, one can solve more complicated number theoretic questions. Hogarth (1994) has explained how to determine in this way the truth of any arithmetic statement. More unusual relativistic Malament-Hogarth spacetimes can be (mathematically) constructed to avoid the unpleasantness of unbounded acceleration required in these rocket examples (see also Hogarth 1992, Pitowsky 1990).

These computational examples speak to a widely held strengthening of Church’s thesis, namely, the view that the classical theory of computability has correctly captured the notion of what it means to be effectively computable.33footnotemark: 3 Because the relativistic rocket examples provide algorithms for computing functions, such as the halting problem, that are not computable by Turing machines, one can view them as refuting this thesis. Supporters of this view emphasize that when thinking about what is in principle computable, we must attend to the computational power available to us as a consequence of the fact that we live in a relativistic or quantum-mechanical universe. To ignore this power is to pretend that we live in a Newtonian world. Other (perhaps less successful) arguments against the thesis appeal to the random or statistical nature of quantum mechanical phenomenon to mechanically produce non-computable bit-streams; this is possible even in Newtonian physics: a particle undergoing Brownian motion can be used to generate a random bit stream that we have no reason to think is recursive. Therefore, proponents argue, we have no reason to believe the strong form of Church’s thesis.

Apart from the question of what one can physically compute in this world, whether Newtonian or relativistic or quantum-mechanical, a mathematician can be interested in what in principle a supertask can accomplish. What are the mathematical limitations, as opposed to the physical inconveniences, of supertask computation? Which mathematical questions can and which cannot be answered via supertasks? To answer such questions, one needs a precise mathematical model of the supertask machines and the algorithms that they can carry out. One can then closely analyze the model and attempt to place the class of decidable sets, sets for which there is a computational procedure to decide whether a given object is a member of them or not, within the known complexity hierarchies of descriptive set theory (which provide a way of measuring the complexity of various sets of natural numbers or reals in terms of the complexity of their definitions). The point is that such an abstract set-theoretic analysis can place severe bounds on the class of sets that can be computable: from below, we can hope to show that all sets at or below a given level of complexity are computable; from above, we can hope to show that no sets above a certain level of complexity are computable. The proximity of these bounds to each other speaks to the quality of the analysis, and precisely locates the supertask notion of computability within the larger (and intensely studied) hierarchy of complexity.

Decades ago, Buchi (1962) and others initiated this kind of study at the lower levels of complexity, with the study of $`\omega `$-automata and Buchi machines, involving automata and Turing machine computations of length $`\omega `$ that accept or reject infinite input. The editor of this volume, Jack Copeland, has been particularly interested in the possibility of such machines completing their tasks in a finite amount of time, by accelerating the computation in time along a convergent series (e.g. the first operation takes $`1/2`$ second, the next $`1/4`$ second, and so on), and has put forth a philosophical analysis of such accelerated Turing machines in various articles (see Copeland 1998a, 1998b, 2002). Moving up in the hierarchy, Gerald Sacks and many others founded the field of higher recursion theory, including $`\alpha `$-recursion and $`E`$-recursion, a huge, deep body of work analyzing an abstract notion of computation on infinite objects (see Sacks 1990).

In this article, I describe another model of infinitary computability, infinite time Turing machines, a model which offers the strong computational power of higher recursion theory while remaining very close in spirit to the computability concept of ordinary Turing machines. Infinite time Turing machines were originally defined by Jeff Kidder in 1989, and he and I worked out the early theory together while we were graduate students at the University of California in Berkeley. Six years later, Andy Lewis and I solved some of the early questions and presented a complete introduction in a joint paper (appearing, finally, in 2000); in 1997 we solved Post’s problem for supertasks (in press). Benedikt Loewe (2001), Dan Seabold (with myself, 2001) and especially Philip Welch (1999, 2000a, 2000b) have also made important contributions. The research is at an exciting early stage.

## 2 Infinite time Turing machines

Infinite time Turing machines are obtained by extending the Turing machine concept to transfinite ordinal time. The idea is to allow a Turing machine to compute for infinitely many steps, preserving the information produced while doing so, and allowing the machine to continue with more computation afterwards. The individual computational steps will therefore be ordered like the ordinal numbers 0, 1, 2, 3, $`\mathrm{}`$ $`\omega `$, $`\omega +1`$, $`\omega +2`$, $`\mathrm{}`$ $`\omega +\omega `$, $`\omega +\omega +1`$, $`\mathrm{}`$ $`\omega +\omega +\omega `$, $`\mathrm{}`$ and so on. After each stage $`\alpha `$ of computation there is a unique next stage $`\alpha +1`$, and these culminate in the limit ordinal stages, like $`\omega `$, $`\omega +\omega `$, and so on.

So let me explain specifically how the machines work. The machine hardware is identical to a classical Turing machine, with a head moving back and forth reading and writing zeros and ones on a tape according to the rigid instructions of a finite program, with finitely many states. What is new is the transfinite behavior of the machine, behavior providing a natural theory of computation on the reals that directly generalizes the classical finite theory to the transfinite.

For convenience, the machines have three tapes-one for the input, one for scratch work and one for the output-and the computation begins with the input written out on the input tape, with the head on the left-most cell in the start state.

The successive steps of computation proceed in exactly the classical manner: the head reads the contents of the cells on which it rests, reflects on its state and follows the instructions of the finite program it is running. Accordingly, it writes on the tapes, moves the head one cell to the left or the right or not at all and switches to a new state. Thus, the classical procedure determines the configuration of the machine-the state of the machine, the position of the head and the contents of the tapes-at any stage $`\alpha +1`$, given the configuration at any stage $`\alpha `$.

We extend the computation into transfinite ordinal time by simply specifying the behavior of the machine at the limit ordinal stages, such as $`\omega `$ or $`\omega +\omega `$. When a classical Turing machine fails to halt, it is often thought of in contemporary computability theory as a sort of failure; the result is discarded even though the machine might have been writing some very interesting information on the tape, such as all the theorems of mathematics, for example, or the members of some other computably enumerable set. With infinite time Turing machines, however, we hope to preserve this information by taking some kind of limit of the earlier configurations and continuing the computation transfinitely.

Specifically, at any limit ordinal stage, the head resets to the left-most cell; the machine is placed in the special limit state, just another of the finitely many states; and the values in the cells of the tapes are updated by computing a kind of limit of the previous values that cell has displayed. Specifically, if the values in a cell have stabilized before a limit stage, then the limit value displayed by that cell at the limit stage will be this stabilized value; and otherwise, when the cell’s value has alternated from 0 to 1 and back again unboundedly often before a limit stage, then the limit value is set to 1. This limit value is equivalent, by definition, to computing for each cell what is called in mathematics the limit-supremum (the “$`lim\; sup`$”) of the previous values displayed in that cell. (The model is robust in that if we use a limit value of 0 in such cases, corresponding instead to the limit-infimum, an equivalent model of computability is obtained.) With the limit stage configuration thus completely specified, the machine simply continues computing. If after some amount of time the halt state is reached, the machine gives as output whatever is written on the output tape.

Because there seems to be no need to limit ourselves to finite input and output—the machines have plenty of time to consult the entire input tape and to write on the entire output tape before halting—the natural context for these machines is Cantor Space $`2^\omega `$, the space of infinite binary sequences. For our purposes here, let’s refer to such infinite binary sequences as real numbers.44footnotemark: 4

In this way, the machines provide a model of computation on the real numbers. Specifically, if $`p`$ is a infinite time Turing machine program, then the function that $`p`$ computes is determined by simply running an infinite time Turing machine with program $`p`$ on whatever input is given, and giving as output the output of that computation. Such functions are said to be infinite time computable, or supertask computable. (Please note that since some computations never halt, even in the infinite time context, and so the domain of such a function need not include all real numbers.) A set of reals $`A`$ is infinite time decidable, or supertask decidable, when its characteristic function, the function with value 1 for inputs in $`A`$ and 0 for inputs not in $`A`$, is supertask computable. The set $`A`$ is infinite time semi-decidable when there is a program that halts with output 1 on exactly the inputs that are in $`A`$. (Thus, the semi-decidable sets correspond in the classical theory to the computably enumerable sets, though since here we have sets of reals, one hesitates to describe them as enumerable.) Since it is an easy matter to change any output value to 1, the semi-decidable sets are exactly the sets that are the domain of a computable function, just as in the classical theory.

The first mathematical observation to make is that one need only consider countable ordinals (these are the ordinals that can be put into a one-to-one correspondence with a set of natural numbers, as opposed to the uncountable ordinals, which cannot) when analyzing the computations of infinite time Turing machines. The fact is that every supertask computation either halts or repeats in countably many steps. Let me explain in some mathematical detail why this is so. Suppose that a supertask computation has not halted in countably many steps; I will argue that it is caught in an endlessly repeating loop. By assumption, the computation proceeded through all the countable ordinals without halting, and finds itself at stage $`\omega _1`$, the first uncountable ordinal (the smallest ordinal having cardinality $`\mathrm{}_1`$), without having yet halted. Consider the complete configuration of the machine—the position of the head, the state and the contents of the tape—at this stage. I claim that this configuration must have occurred earlier, and the machine is caught in an endlessly repeating loop. Since $`\omega _1`$ is a limit ordinal, we know that the head is on the left-most cell in the limit state, as it is at any limit ordinal stage. Further, any cell with a value of 0 at stage $`\omega _1`$ must have been 0 from some countable ordinal on, and since there are only countably many cells, there must be a countable ordinal stage $`\alpha _0`$ by which all of those 0 valued cells have stabilized. Let $`\alpha _1`$ be a larger countable ordinal by which all the other cells have shown a value of 1 at least once, and $`\alpha _2`$ be a still larger value by which all the remaining cells have shown a value of 1 once again, and so on. Let $`\alpha _\omega `$ denote the first stage after all the stages an (this is still a countable ordinal). I claim that the configuration at stage $`\alpha _\omega `$ is the same as it is at stage $`\omega _1`$: since it is a limit ordinal, the head is on the first cell and in the limit state; and by construction the contents of each cell are computed in the same way that they are at stage $`\omega _1`$. Further, since beyond $`\alpha _0`$ the only cells that change are the ones that will change unboundedly often, by design, it follows that limits of this configuration are the very same configuration again, and the machine is caught in an endlessly repeating loop. (Please note that in the supertask context, a computation that merely repeats a complete machine configuration is not necessarily caught in an endlessly repeating loop, for after $`\omega `$ many repetitions, the limit configuration may allow it to escape. This is why one must consider the limits of the repeating configuration in the preceding argument. An example of this phenomenon is provided by the machine which does nothing at all except halt when it is in the limit state; this machine repeats its initial configuration many times, yet still escapes this repeating loop and halts at $`\omega `$.) The conclusion is that any computation that fails to halt in countably many steps is doomed to repeat itself endlessly as the ordinals fall through the transfinite hourglass.

## 3 How powerful are the machines?

One naturally wants to understand the power of the new machines. Since, of course, one needn’t take advantage of the new powers the machine offers, any function that is computable by a classical Turing machine is computable by an infinite time Turing machine. But further, I claim that the infinite time Turing machines are strictly more powerful than their classical counterparts. Specifically, the halting problem for classical Turing machines—the question of whether a given program $`p`$ halts on a given input n in finitely many steps, a problem well-known to be undecidable by classical Turing machines—is decidable in $`\omega `$ many steps by infinite time Turing machines. To see this, one programs an infinite time Turing machine to simulate the operation of $`p`$ on $`n`$, and if the simulated computation ever halts our algorithm gives the output that yes, indeed, the computation did halt. Otherwise, the limit state will be attained, and when this occurs the machine will know that the simulated computation failed to halt; so it outputs the answer that no, the computation did not halt. In this algorithm, it is as though the limit state exists specifically to tell the machine that the simulated computation did not yet halt.

This argument generalizes to show that the infinite time Turing machines can decide membership in any given computably enumerable set $`A`$ in $`\omega `$ many steps. On input $`n`$, one simulates the classical enumeration of $`A`$; if $`n`$ appears in the enumeration, give the output that yes, $`n`$ is in $`A`$. Otherwise, when the limit state appears, give the output that no, $`n`$ is not in $`A`$.

The power of infinite time Turing machines, though, far exceeds the classical halting problem and the computably enumerable sets. In fact, any question of first order number theory is supertask decidable. With an infinite time Turing machine, one could solve the prime pairs conjecture (which asserts that there are infinitely many prime pairs—pairs of primes, such as $`11,13`$ or $`107,109`$, which differ by two), for example, and the question of whether there are infinitely many Fermat primes (primes of the form $`2^{2^n}+1`$) and so on. With an infinite time Turing machine, one can decide the truth of any statement that is expressible in first order number theory (this includes essentially all of elementary number theory, all of finite combinatorics, all of finite graph theory, and so on). To decide a question of the form $`n\phi (n,x)`$, for example, where $`n`$ ranges over the natural numbers, one can simply try out all the possible values of $`n`$ in turn. One either finds a witness $`n`$ or else knows at the limit that there is no such witness, and in this way decides whether $`n\phi (n,x)`$ is true.

By analyzing this idea precisely, once concludes by induction on the complexity of the statement that any first order number theoretic question is decidable with only a finite number of limits, that is, before stage $`\omega ^2`$ (the limit of the sequence $`\omega `$, $`\omega 2`$, $`\omega 3`$, and so on). In fact, it is possible to prove that the class of sets that are decidable in time uniformly before $`\omega ^2`$ (meaning that for some $`n`$ the program halts on all input before stage $`\omega n`$) is exactly the class of arithmetic sets, the sets of reals that are definable by a statement using first order quantifiers over the natural numbers (see Hamkins, et. al. 2000, Theorem 2.6).

Infinite time Turing machines, however, have a power that transcends even the full first order theory. In fact, their power reaches into the projective hierarchy, in the second order theory (the projective sets are those that are definable using quantifiers not only over the natural numbers, but also over sets of natural numbers, or over the real numbers). One particular set, known as $`\text{wo}`$ (for well-order, since it consists of the real numbers that code a well-ordered relation on the natural numbers, a relation having no infinite descending sequence), serves as a familiar sentinel or gate-keeper to these higher levels of complexity. Specifically, the set $`\text{wo}`$ exists at what is called the $`\mathrm{\Pi }_1^1`$ level of complexity, a level that subsumes all of the arithmetic hierarchy of first order number theory, as well as the hyperarithmetic sets (a kind a transfinite generalization of the arithmetic sets), and it is complete for this level of complexity in the sense that every other $`\mathrm{\Pi }_1^1`$ set reduces to it. In this sense, $`\text{wo}`$ is the hardest possible $`\mathrm{\Pi }_1^1`$ set, and so to show that $`\text{wo}`$ is supertask decidable, as I will do in the next paragraph, is to show that the infinite time Turing machines have power completely transcending the classical computability theory.

With the reader’s permission, let me sketch the argument showing that $`\text{wo}`$ is decidable, using what Andy Lewis and I (2000) have called the “count-through” argument. The set $`\text{wo}`$ consists of all reals coding a well-order relation on a subset of the natural numbers. (A real $`x`$ codes a relation $``$ on $``$ in the sense that $`ij`$ if and only if the $`i,j^{\text{th}}`$ bit of $`x`$ is 1, using the Gödel pairing function $`i,j`$, which associates pairs of natural numbers with individual natural numbers in a one-to-one correspondence. This function allows a binary relation to be coded with a binary sequence.) We would like to describe a supertask algorithm which on input $`x`$ decides whether $`x`$ codes a well-ordered relation $``$ on a set of natural numbers or not, that is, whether $`x\text{wo}`$ or not. In $`\omega `$ many steps, it is easy to check whether $`x`$ codes a linear order: this amounts merely to checking that the relation $``$ coded by $`x`$ is transitive, irreflexive and connected. That is, the machine must check that whenever $`ij`$ and $`jk`$ then also $`ik`$, that $`ii`$ never holds, and that for distinct $`i`$ and $`j`$ either $`ij`$ or $`ji`$. All these requirements can be enumerated and checked in $`\omega `$ many steps. Next, the algorithm will attempt to find the least element in the field of the relation $``$. This can be done by keeping a current-best-guess on the scratch tape and systematically looking for better guesses, whenever a new smaller element is found. When such a better guess is found, it replaces the current guess on the scratch tape, and a special flag cell is flashed on and then off again. At the limit, if the flag cell is on, it means that infinitely often the guess was changed, and so the relation has an infinite descending sequence. Thus, in this case the input is definitely not a well order and the computation can halt with a negative output. Conversely, if the flag cell is off, it means that the guess was only changed finitely often, and the machine has successfully found the $``$-least element. The algorithm now proceeds to erase all mention of this element from the field of the relation $``$, by turning the bits $`i,j`$ of $`x`$ to 0 that mention it. This produces a new smaller relation, and the algorithm proceeds to find the least element of it. In this way, the relation $``$ is eventually erased from the bottom as the computation proceeds. If the relation is not a well order, eventually the algorithm will erase the largest initial segment of it that is a well order, and then discover that there is no least element remaining, and reject the input. If the relation is a well order, then the algorithm will eventually erase the entire field, and recognize that it has done so, and accept the input as a well order. So in any case the algorithm can recognize whether $`x`$ codes a well order or not, and so $`\text{wo}`$ is supertask decidable. It follows, as I explained, that every set at or below the $`\mathrm{\Pi }_1^1`$ level of complexity is also decidable. Because of this, the power of infinite time Turing machines is seen to reach into second order number theory, completely transcending the classical theory.55footnotemark: 5

Much of the classical computability theory generalizes to the supertask context of infinite time Turing machines. For example, the classical $`s`$-$`m`$-$`n`$ theorem and the Recursion Theorem, for those who are familiar with them, go through with virtually identical proofs. But some other classical results, even very elementary ones, do not generalize. One surprising result, for example, is the fact that there is a non-computable function whose graph is semi-decidable. This follows from what Any Lewis and I (in our 2000 paper) have called the “Lost Melody Theorem,” which asserts the existence of a real $`c`$ which is not writable, so that it is not the output of any computation on input 0, but such that the set $`\{c\}`$ is decidable. Imagine the real $`c`$ as the melody that you can recognize when someone sings it, but you cannot sing it on your own; so you can say yes or no whether a given object is c or not, thereby deciding the set $`\{c\}`$, but you cannot create $`c`$ from scratch. If $`c`$ is such a lost melody real, then let $`f`$ be the function defined by $`f(x)=c`$. This function is total (defined on all input) and constant (has the same value for all input). The graph of the function consists of all pairs $`(x,f(x))`$, that is, of all pairs $`(x,y)`$ for which $`y`$ is $`c`$, and this is decidable. But the function is not computable because $`c`$ is not writable. To summarize, the example shows that in the supertask context we have situation completely contrary to the classical computability theory: a non-computable function whose graph is semi-decidable; indeed, the example is all the more surprising because graph of the function $`f`$ here is actually decidable, not merely semi-decidable, and what is more, the function is total and constant! There is nothing like this in the classical computability theory.

## 4 How long are the computations?

One naturally wants to understand how long a supertask computation can be. Therefore, I define an ordinal $`\alpha `$ to be clockable if there is a computation on input 0 that takes exactly $`\alpha `$ many steps to complete (so that the $`\alpha ^{\text{th}}`$ step of computation is the act of moving to the halt state). Such a computation is a clock of sorts, a way to count exactly up to $`\alpha `$. One sets the machine running, and when it halts it is as though an alarm clock has gone off: exactly $`\alpha `$ many steps have been computed. Such clocks are especially useful when it is desired to run some other computation for a given number of steps; one simulates the clock and the other computation simultaneously, and when the clock stops, the algorithm has computed the desired number of steps.

It is very easy to see that any finite number $`n`$ is clockable; one can simply have a machine cycle through $`n`$ states and then halt. The ordinal $`\omega `$ is clockable, by the machine that halts when it encounters the limit state. Similar ideas show that if $`\alpha `$ is clockable, then so is $`\alpha +n`$ and $`\alpha +\omega `$. From this, it follows that every ordinal up to $`\omega ^2`$ is clockable. The ordinal $`\omega ^2`$ itself is clockable: one can recognize it as the first limit of limit ordinals, by flashing a cell on and then off again every time the limit state is encountered; the ordinal $`\omega ^2`$ will be first time this cell is on at a limit stage. Going beyond this, it is easy to see that if $`\alpha `$ and $`\beta `$ are clockable, then so are $`\alpha +\beta `$ and $`\alpha \beta `$. Students might enjoy finding algorithms to clock specific ordinals, such as $`\omega ^{\omega ^2}+\omega ^4`$, and I can recommend this as a way to help them understand the ordinals more deeply.

Many readers will have guessed that the analysis extends much further, to much larger ordinals. In fact, any recursive ordinal is clockable. (A recursive ordinal is one whose order relation is isomorphic to recursive relation on the natural numbers. The supremum of the recursive ordinals, of which there are only countably many, is denoted $`\omega _1^{CK}`$, named for Church and Kleene.) This can be seen by optimizing the count-through argument I gave earlier when proving that $`\text{wo}`$ is supertask decidable. Specifically, after writing on the tape in $`\omega `$ many steps a real that codes a given recursive ordinal, one proceeds to count through this ordinal by guessing the $`\omega `$ many least elements of the relation (while simultaneously erasing the previous guesses), rather than handling only one guess with each limit. In this way, each block of $`\omega `$ many steps of the algorithm will erase $`\omega `$ many elements from the field of the relation, and the length of time the count-through procedure takes is more closely connected with the ordinal being counted.

Some have been surprised that the clockable ordinals extend beyond the recursive ordinals, but in fact they extend well beyond the recursive ordinals. To see at least the beginnings of this, let me show that the ordinal $`\omega _1^{CK}+\omega `$ is clockable. By Feferman and Spector (1962), there is a recursive relation whose well-founded part has order type $`\omega _1^{CK}`$. Consider the supertask algorithm that writes this relation on the tape and then attempts to count through it. By stage $`\omega _1^{CK}`$ the non-well-founded part of the relation will have been reached, but it takes the algorithm an additional $`\omega `$ many steps to realize this. So it can halt at stage $`\omega _1^{CK}+\omega `$.

One is left to wonder, is $`\omega _1^{CK}`$ itself clockable? More generally, Are there gaps in the clockable ordinals? After all, if a child can count to twenty-seven, then one might expect the child also to be able to count to any smaller number, such as nineteen.66footnotemark: 6 The question is whether we expect the same to be true for infinite time Turing machines.

The surprising fact is that there are gaps in the clockable ordinals. Let me give a brief sketch of this argument: Consider the algorithm which simultaneously simulates all programs on input 0, recording which have halted; when a stage is found at which no programs halt, then halt. By construction, this algorithm verifies that a supertask algorithm can halt above a non-clockable ordinal, and so there are gaps in the clockable ordinals. The argument can be modified to show that the next gap above any clockable ordinal has length $`\omega `$. Other arguments establish that complicated behavior can occur at limits of gaps, because the lengths of the gaps are unbounded in the clockable ordinals.

An interesting question for future mathematical research would be to understand the structure of the clockable ordinals. For example, it is now known that no admissible ordinal can be clockable, and so the first gap occurs exactly at $`\omega _1^{CK}`$. Which is the next non-clockable ordinal? Can we find an independent characterization of the clockable ordinals? They do seem to arise very naturally in this theory.

There is another way for infinite time Turing machines to operate as clocks, and this is by carefully using the count-through argument that I mentioned earlier. To assist with this analysis, we define that a real is writable if it is the output of a supertask computation on input 0. In analogy with the recursive ordinals, we define that an ordinal is writable if it is coded by a writable real. It is easy to see that there are no gaps in the writable ordinals, because if one can write down real coding $`\alpha `$, it is an easy matter to write down from this a real coding any particular $`\beta <\alpha `$. Andy Lewis and I (2000) proved that the order-types of the set of clockable ordinals and the set of writable ordinals are the same, but the question was left open as to whether these two classes of ordinals had the same supremum, that is, whether the two sets converged upwards to the same ordinal. This was solved affirmatively by Philip Welch (2000a), allowing Andy Lewis and I to greatly simplify arguments in our paper on Post’s Problem.

## 5 The supertask halting problems and jump operators

Before discussing the supertask notions (and at the suggestion of the editor of this volume), let me spend several paragraphs giving an introduction to the elements of classical degree theory. Once having specified the operation of the classical Turing machines, one knows what it means for a function on the natural numbers to be computable and for a set of natural numbers to be decidable or computably enumerable (also known as recursively enumerable). The halting problem, the set of programs halting on a given input, then appears as a canonical example of a set that is computably enumerable but not decidable; indeed, it may be first concrete set many encounter that they know definitively to be undecidable. The natural temptation arises to ask: Suppose you had some way of answering the halting problem, what then? With this set in hand, what could you compute from it? To answer, one develops the theory of oracle computation. Specifically, for a fixed set of natural numbers $`A`$, known as the oracle, one equips the Turing machine with an extra tape, the oracle tape, on which the membership information of $`A`$ is explicitly written (the $`n^{\text{th}}`$ cell of the oracle tape is 1 when $`n`$ is in $`A`$, otherwise 0). The functions that are computable with this expanded device are the functions that are computable relative to $`A`$, and one has a notion of a set being decidable or computably enumerable relative to $`A`$.

The notion of relative computability reveals very quickly a vast mathematical structure lurking behind the scene: the Turing degrees. Specifically, one defines that $`A_TB`$ (pronounced “$`A`$ is Turing reducible to $`B`$”) when $`A`$ is decidable relative to oracle $`B`$, and this relation provides a way of measuring the relative complexity of sets; if $`A_TB`$, then $`B`$ is at least as complicated as $`A`$. The two sets are Turing equivalent, written $`A_TB`$, when each oracle is computable relative to the other, that is, when $`A_TB`$ and $`B_TA`$. If $`A`$ is any set, then the degree of $`A`$ is the equivalence class of $`A`$ in this relation, the collection of all $`B`$ such that $`A_TB`$. Any such $`B`$ has the same information content as $`A`$, because with $`B`$ we may reconstruct $`A`$ and vice versa. The strict relation $`A<_TB`$ is defined to hold when $`A_TB`$ but not $`A_TB`$. Two sets are incomparable (written $`A_TB`$) when neither is computable from the other.

The undecidability of the halting problem $`H`$ means that $`0<_TH`$, where $`0`$ refers to the simplest possible set, the empty set, whose degree is the collection of all decidable sets. It is relatively easy to see that every computably enumerable set is decidable from $`H`$, and so the question remains, known as Post’s Problem, whether there are any computably enumerable sets strictly between $`0`$ and $`H`$? That is, given the examples of the decidable sets and the various forms of the halting problem, which are all Turing equivalent, one might think that the only way to show that a given problem is undecidable is to reduce the halting problem to it. This would mean that every computably enumerable set is either decidable or equivalent to the halting problem, and there is nothing strictly between them. Post’s Problem was solved by Friedburg and Muchnik in 1956, however, with the opposite answer: with their finite injury priority argument method, one can construct a rich diversity of sets intermediate between $`0`$ and $`H`$ (see Soare 1987). We now know that there is a rich structure of computably enumerable degrees; every countable partial order, for example, finds an isomorphic copy in these degrees.

It is surprisingly easy to lift the picture that we have of the degrees between $`0`$ and $`H`$ to higher levels of the hierarchy, for the simple reason that most computability arguments relativize to the presence of a fixed oracle $`A`$. Thus, for example, the relativized halting problem $`H^A`$, the set of all programs that halt on a given input with oracle $`A`$, is computably enumerable but not decidable relative to $`A`$. This observation provides a method of jumping higher in the degree structure: the Turing jump of a set $`A`$, written $`A^{}`$ and pronounced “$`A`$-jump,” is the halting problem relative to $`A`$, and by relativizing the undecidability of the halting problem, one knows that $`A<_TA^{}`$. In this terminology, the classical halting problem $`H`$ becomes $`0^{}`$, pronounced “$`0`$-jump”. Faced with any operator, of course, one is tempted to iterate it, and doing so here produces an increasing sequence of degrees reaching upwards into the Turing hierarchy: $`0<_T0^{}<_T0^{\prime \prime }<_T0^{\prime \prime \prime }<_T\mathrm{}<_T0^{(n)}<_T\mathrm{}`$ and so on. One can ask all kinds of questions about the structure of the Turing degrees: Is every degree above $`0^{}`$ the jump of another degree? Yes. If the jumps of two sets are Turing equivalent, are the sets themselves equivalent? No. Are there undecidable degrees below $`0^{}`$ whose jump is still only $`0^{}`$? Yes. Are there minimal non-computable degrees? Yes. Are the computably enumerable degrees dense, in the sense that whenever one is strictly less than another, then there is a third strictly in between? Yes. (For a textbook account of all these answers and much more, consult Soare 1987).

Perhaps the broad philosophical view here is that each Turing degree represents a possible amount of information—this being precisely what is preserved by the Turing equivalence relation—and if we are interested in the structure of information, which I assume most readers of this volume are, it behooves us to understand the structure of the Turing degrees.

This concludes my introduction to the theory of the classical Turing degrees; let me now turn to the corresponding supertask model. Every new model of computation naturally also provides a corresponding new halting problem, the question whether a given computation halts. Thus, in the supertask context of infinite time Turing machines, we have the supertask halting problem. The full supertask halting problem $`H`$ is the question of whether a given infinite time Turing machine program $`p`$ halts on a given real input $`x`$. A special case of this problem is the weak halting problem $`h`$, which is the question of whether a given program $`p`$ halts on the trivial input $`0`$. The analogues of these two problems in the classical computability context are Turing equivalent and there is no big fuss made there distinguishing them, but here in the supertask context the situation is somewhat subtler.

The classical arguments directly generalize to show that the halting problems $`h`$ and $`H`$ are semi-decidable but not decidable. First, for semi-decidability, the point is that given a program $`p`$ and input $`x`$ (or input $`0`$), one can simply simulate $`p`$ on $`x`$ to see if it halts. If it does, output the answer that yes, it halted; otherwise, keep simulating. Second, for undecidability, let me give in the case of $`H`$ the classical diagonalization argument. Suppose that $`H`$ were decidable by an infinite time Turing machine, and consider the following algorithm: on input $`p`$, use the decision procedure for $`H`$ to determine whether $`p`$ halts on input $`p`$; if it does, then go into an infinite loop and never halt; if it does not, then halt immediately. This algorithm is infinite time computable by some program $`q`$. But observe that, by design, we have achieved the ubiquitous diagonal contradiction, namely, the program $`q`$ halts on input $`q`$ if and only if $`q`$ does not halt on input $`q`$. So $`H`$ cannot be decidable. The classical arguments also generalize to show that the weak halting problem $`h`$ is also undecidable.

Once one has introduced the halting problems, it is again natural to wonder what one could compute if one had some means to solve these problems, and one is led to the notion of oracle computation. There are, however, two natural types of oracles to use in the infinite time Turing machine context. On the one hand, one can use an individual real number as an oracle just as one does in the classical context, by simply adding an oracle tape containing this real number, and allowing the machine to access this tape during the computation. This corresponds exactly to adding an extra input tape and thinking of the oracle as a fixed additional input.

But ultimately one realizes this is not the right type of oracle to consider, since an oracle is more properly the same type of object as one that might be decidable or semi-decidable, namely, a set of real numbers, not a mere individual real number. That is, with supertasks we have made the move to a higher-type theory of computability-with functions defined on sets of real numbers, rather than on sets of natural numbers-and we naturally want to develop our theory of relative computability at this level as well. Thus, we want somehow to allow a set of real numbers, such as the halting problem $`H`$, to become an oracle for the machines. And since such a set could be uncountable, and the set $`H`$ in particular is definitely uncountable, we can’t expect to be able to write out the entire contents of the oracle on an extra tape, as in the classical theory. Instead, we provide an oracle model of relative computability by which the machine can make membership queries of the oracle. Specifically, for a fixed oracle set of reals $`A`$, we equip an infinite time Turing machine with an initially blank oracle tape on which the machine can read and write. The machine makes a membership query of $`A`$ by writing out a real number $`a`$ on the oracle tape, and then switching to a special query state; the result, however, is that the machine moves actually to the yes or no state, depending on whether $`aA`$ or not, and the algorithm has completed its query of $`A`$. In this way, the machine is able to ask, of any real $`a`$ that it is capable of producing, whether $`aA`$ or not, and use the answer as the basis for more computation. This query model of oracle computation has proven robust. In the lower-type case of oracle sets of natural numbers, it is computationally equivalent to the usual oracle tape model in both the classical theory and the supertask theory here. And in the higher-type case of sets of reals, it closely follows the well-known definition in set theory of Gödel’s constructible universe $`L[A]`$, relative to the predicate $`A`$, since when building this model, one is allowed to apply the predicate only to previously constructed objects, just as our oracle machines are only allowed to make queries of the form “is $`aA`$?” for real numbers $`a`$ that they are able to produce for the purpose. Queries, for example, of the form “is there a real $`y`$ in the oracle having such-and-such property?” do not have the required form.

From the notion of oracle computation, of course, just as in the classical theory, one obtains a notion of relative computability. Specifically, one set $`A`$ is computable relative to another set $`B`$, if having $`B`$ as an oracle allows one to decide membership in $`A`$, that is, if the characteristic of $`A`$ is computable with oracle $`B`$. When this occurs, we write $`A_{\mathrm{}}B`$, indicating that $`B`$ is at least as complicated as $`A`$, and we say that $`A`$ reduces to $`B`$. From this notion of relative computability, we can then define when two oracles are equivalent: $`A`$ is equivalent to $`B`$, written $`A_{\mathrm{}}B`$, if and only if each is computable from the other, that is, $`A_{\mathrm{}}B`$ and $`B_{\mathrm{}}A`$; the strict relation $`A<_{\mathrm{}}B`$ is defined to hold if and only if $`A_{\mathrm{}}B`$ but not $`A_{\mathrm{}}B`$. The equivalence classes of the equivalence relation $`_{\mathrm{}}`$ form the infinite time Turing degrees, namely, two sets have the same degree when they are equivalent to each other. When two sets are equivalent, they have the same information content, as far as supertask computation is concerned, because from either of them one can consruct the other. It is therefore in the structure of these degrees that nature of supertask computation is to be revealed; it is here that we will discover both the power and the limitations of supertask computation.

The two halting problems give rise, of course, to two jump operators. Specifically, for any set $`A`$ we have the halting problem $`H`$ relative to $`A`$, the question of whether a given program $`p`$ halts on a given input $`x`$ using oracle $`A`$. This problem is denoted by $`A^{\mathrm{}}`$, pronounced $`A`$-jump, in analogy with the Turing jump. We also have the weak jump $`A^{\mathrm{}}`$, obtained by adding to $`A`$ the weak halting problem $`h`$ relative to oracle $`A`$. The Jump Theorem asserts that for any set, $`A<_{\mathrm{}}A^{\mathrm{}}<_{\mathrm{}}A^{\mathrm{}}`$, and it is because of this theorem that we know that the two halting problems $`h`$ and $`H`$ are not equivalent. This is because $`h`$ is equivalent to $`0^{\mathrm{}}`$ and $`H`$ is equivalent to $`0^{\mathrm{}}`$, and so since $`0^{\mathrm{}}<_{\mathrm{}}0^{\mathrm{}}`$, it follows that $`h<_{\mathrm{}}H`$. That is, $`h`$ is computable from $`H`$ but not vice versa. The Jump Theorem is generalized by the absorption property of the jump operators, namely, the fact that the strong jump absorbs applications of the weak jump, expressed by the equivalence $`A^{\mathrm{}\mathrm{}}_{\mathrm{}}A^{\mathrm{}}`$. This theorem shows that in a sense, the strong jump $`\mathrm{}`$ jumps much higher than the weak jump $`\mathrm{}`$, as it means that $`A^{\mathrm{}}`$ is much higher in the degree structure than $`A^{\mathrm{}}`$. In particular, it follows from the absorption property that $`A^{\mathrm{}}`$ cannot be equivalent to $`A^{\mathrm{}}`$, since in that case $`A^{\mathrm{}\mathrm{}}`$ would be equivalent to $`A^{\mathrm{}\mathrm{}}`$, which by the Jump Theorem is strictly more complicated than $`A^{\mathrm{}}`$. All these results are discussed at length in my paper with Andy Lewis (2000).

## 6 Post’s Problem for Supertasks

Post’s problem, the question in classical computability theory of whether there are non-decidable semi-decidable degrees other than the halting problem, has a direct supertask analogue: Are there intermediate semi-decidable degrees between $`0`$ and the jump $`0^{\mathrm{}}`$?

The answer is delicately mixed. On the one hand, contrasting sharply with the classical theory in the context of degrees in the real numbers, we have a negative answer. The fact is that there are no real numbers $`z`$ strictly in between 0 and the jump $`0^{\mathrm{}}`$. Thus, while over the past fifty years the classical theory has supported an active, vibrant study of the computably enumerable degrees and indeed, of all the degrees between 0 and the Turing jump $`0^{}`$, my theorem with Andy Lewis shows that in the context of supertask degrees of real numbers between 0 and the jump $`0^{\mathrm{}}`$, there is simply nothing to study.

Since this result is one of the strongest departures from the classical theory that has yet arisen, let me briefly sketch the proof. Suppose that $`z`$ is a real number and $`0_{\mathrm{}}z_{\mathrm{}}0^{\mathrm{}}`$. So $`z`$ is the output of program $`p`$ using $`0^{\mathrm{}}`$ as an oracle. Consider the algorithm that computes approximations to $`0^{\mathrm{}}`$ by simultaneously simulating all programs on input 0 and keeping track of which programs have halted. As these approximations to $`0^{\mathrm{}}`$ are gradually revealed, the algorithm may use program $`p`$ with them in an attempt to produce the real number $`z`$. All of the proper approximations to $`0^{\mathrm{}}`$ are actually writable. If one of the proper approximations can successfully produce $`z`$, then $`z`$ also is writable, and consequently $`0_{\mathrm{}}z`$. Conversely, if none of the proper approximations can produce $`z`$, then on input $`z`$ we can recognize $`0^{\mathrm{}}`$ as the true approximation, the first approximation able to produce $`z`$, and consequently $`z_{\mathrm{}}0^{\mathrm{}}`$. So in no case can the real $`z`$ be strictly in the middle.

Nevertheless, despite this negative solution of Post’s problem in the context of real degrees, there is a supertask analogue of the positive answer in the classical theory when it comes to sets of reals. Specifically, there is an oracle $`A`$, a set of reals, that is strictly in between 0 and the jump $`0^{\mathrm{}}`$. Indeed, there are incomparable semi-decidable sets $`A_{\mathrm{}}B`$ (meaning that neither set is computable from an oracle for the other), and a rich structure of degrees between 0 and $`0^{\mathrm{}}`$. The argument generalizes the Friedburg-Munchnik priority argument (see Soare 1987) to the supertask context, much as Sacks did for $`\alpha `$-recursion theory (see Sacks 1990). So the vibrant classical study of degrees between 0 and the jump $`0^{\mathrm{}}`$ that I mentioned earlier finds its analogue here, in the context of the degrees of sets of reals.

Let me close this article by asking the broad questions: What is the structure of the infinite time Turing degrees? To what extent do the properties of this structure mirror or differ from the classical structure? The field is wide open.

## References

* J. R. Buchi, Logic, Methodology and Philosophy and Science (Proc. 1960 Internat. Congr.), volume 1 of 1, Stanford University Press, Stanford, CA, 1962.
* C. S. Chihara, On the possibility of completing an infinite process, Philosophical Review, 74:74-87, 1965.
* Jack Copeland, Super Turing-Machines, Complexity, vol. 4 (1998a) pp. 30-32.
* Jack Copeland, Even Turing Machines Can Compute Uncomputable Functions, In Calude, C., Casti, J., Dinneen, M. (eds) Unconventional Models of Computation, London: Springer-Verlag, 1998b, pp. 150-164.
* Jack Copeland, Accelerating Turing Machines, Minds and Machines (in press, to appear in 2002, in a Special Issue on effective procedures, edited by Carol Cleland).
* John Earman, Bangs, crunches, whimpers and shrieks: singularities and acausalities in relativistic spacetimes, The Clarendon Press, Oxford University Press, New York, 1995.
* John Earman and John D. Norton, Forever is a day: supertasks in Pitowski and Malament-Hogarth spacetimes, Philos. Sci., 60(1):22-42, 1993.
* Solomon Feferman and C. Spector, Incompleteness Along Paths in Progressions of Theories, The Journal of Symbolic Logic, 27:383-390, 1962.
* Joel David Hamkins and Andy Lewis, Infinite time Turing machines, The Journal of Symbolic Logic, 65(2):567-604, 2000.
* Joel David Hamkins and Daniel Seabold, Infinite time Turing machines with only one tape, Mathematical Logic Quarterly, 47(2):271–287, 2001.
* Joel David Hamkins and Andy Lewis, Post’s problem for supertasks has both positive and negative solutions, to appear in the Archive for Mathematical Logic.
* Hogarth, Does general relativity allow an observer to view an eternity in a finite time? Foundations of Physics Letters, 5:173-181, 1992.
* Hogarth, Non-Turing computers and non-Turing computability, volume 1 of East Lansing: Philosophy of Science Association (D. Hull, M. Forbes and R. B. Burian, eds.), 126-138, 1994.
* Benedikt Löwe, Revision sequences and computers with an infinite amount of time, Logic Comput., 11(1):25-40, 2001.
* J. P. Laraudogoitia, A beautiful supertask, Mind, 105(417):81-84, January 1996.
* Pitowsky, The physical Church thesis and physical computational complexity, Iyyun, 39:81-99, 1990.
* Gerald E. Sacks, Higher Recursion Theory, Springer-Verlag Publishing Company, Berlin, 1990.
* Robert I. Soare, Recursively Enumerable Sets and Degrees, Springer-Verlag Publishing Company, New York, 1987.
* Thomson, Tasks and super-tasks, Analysis, XV:1-13, 1954-55.
* Philip Welch, Friedman’s trick: Minimality arguments in the infinite time Turing degrees, in “Sets and Proofs”, Proceedings ASL Logic Colloquium, 258:425-436, 1999.
* Philip Welch, The lengths of infinite time Turing machine computations, Bulletin of the London Mathematical Society, 32(2):129-136, 2000a.
* Philip Welch, Eventually infinite time Turing machine degrees: Infinite time decidable reals, Journal of Symbolic Logic, 65, No.3, 2000, pp11, 2000b.

## Notes

1. My research has been supported in part by grants from the CUNY Research Foundation and the National Science Foundation.
2. I heard a version of this example in an email exchange with Peter Vallentyne in March, 2001.
3. The editor Jack Copeland has pointed out that Church and Turing put forth only the weaker thesis asserting that the functions computable by effective procedures that could in principle be carried out by a person with paper and pencil are Turing machine computable.
4. While the binary expansion of a real number reveals a close connection between ordinary real numbers in the unit interval and infinite binary sequences, they are not entirely equivalent, largely because the binary expansion of a real number may not be unique. For example, while $`0.0111\mathrm{}`$ and $`0.1000\mathrm{}`$ are equal as real numbers, the sequences $`0111\mathrm{}`$ and $`1000\mathrm{}`$ are distinct. We may regard the set of natural numbers as naturally included in the space of infinite binary sequences by identifying the number 0 with the sequence $`000\mathrm{}`$, the number 1 with $`100\mathrm{}`$, the number 2 with $`110\mathrm{}`$, and so on.
5. The exact complexity class of the decidable sets lies between $`\mathrm{\Sigma }_1^1\mathrm{\Pi }_1^1`$ and $`\mathrm{\Delta }_2^1`$, since every semi-decidable set has complexity $`\mathrm{\Delta }_2^1`$. The Arithmetic sets are exactly those that are uniformly decidable with a finite number of limits, that is, before $`\omega ^2`$, and the hyperarithmetic sets, the $`\mathrm{\Delta }_1^1`$ sets, are exactly the sets which can be decided in some bounded recursive ordinal length of time, uniformly before $`\omega _1^{CK}`$. The class $`\mathrm{\Delta }_2^1`$ is known to be closed under the supertask jump operators, so there is a very rich supertask complexity hierarchy entirely contained within $`\mathrm{\Delta }_2^1`$.
6. Friends with children have informed me that such an expectation is unwarranted; one sometimes can’t get the child to stop at the right time. This reminds me of a time when my younger brother was in kindergarten, the children all sat in a big circle taking turns saying the next letter of the alphabet: A, B, C, and so on, around the circle in the manner of the usual children’s song (evidently an American phenomenon). After the letter K, the next child contributed LMNOP, thinking that this was only one letter.