pith. sign in

arxiv: 2102.13531 · v2 · pith:NBBQCEGCnew · submitted 2021-02-26 · 🧮 math.LO

Lower bounds on β(α) and other properties of α-ITRMs

Merlin Carl This is my paper

Pith reviewed 2026-05-24 13:47 UTC · model grok-4.3

classification 🧮 math.LO
keywords alpha-ITRMsinfinite time register machinescomputational strengthlower boundsbeta functionhalting problemuniversal machinescardinal recognition
0
0 comments X

The pith

α-ITRMs exceed the computational strength conjectured for them at certain ordinals α.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves lower bounds on β(α), the measure of what α-ITRMs can compute, for selected values of α. These bounds are high enough to contradict an earlier conjecture about the machines' limits. It also establishes that three properties stand or fall together for α-ITRMs: whether the bounded halting problem is solvable, whether a universal machine exists, and whether allowing the machines to recognize cardinals increases their power. The results apply across all relevant ordinals α. A reader cares because these equivalences and bounds tighten the map of what transfinite register machines can and cannot do.

Core claim

For certain α the function β(α) satisfies stricter lower bounds than previously conjectured, so that α-ITRMs reach higher computational strength than expected. In addition, for all relevant α the following are equivalent: the bounded halting problem is unsolvable by α-ITRMs, a universal α-ITRM exists, and cardinal-recognizing α-ITRMs are strictly stronger than ordinary ones. The computational strength of cardinal-recognizing ITRMs equals that of ordinary ITRMs.

What carries the argument

The function β(α), which tracks the supremum of ordinals computable by α-ITRMs and thereby quantifies their strength.

If this is right

  • For the α values in question, α-ITRMs can compute ordinals that the refuted conjecture placed beyond their reach.
  • The three listed properties (unsolvability of bounded halting, existence of a universal machine, and strict gain from cardinal recognition) are inseparable for every relevant α.
  • Cardinal recognition adds no extra power to ordinary ITRMs.
  • The computational map for α-ITRMs is now fixed by these equivalences rather than by independent open questions.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same lower-bound technique might be tried on other transfinite register or tape models whose strength functions remain open.
  • If the equivalences extend to still larger classes of machines, the distinction between halting solvability and universality would collapse in a broader setting.
  • Concrete programs witnessing the new lower bounds on β(α) could be extracted to test the bounds on small explicit α.

Load-bearing premise

The basic definitions and properties of α-ITRMs and of β(α) supplied by the cited earlier papers remain valid.

What would settle it

An explicit α-ITRM program, for one of the α values treated in the paper, that halts at an ordinal strictly below the claimed lower bound on β(α).

read the original abstract

This paper extends our paper \cite{C2} for the conference ``Computability in Europe'' 2022. After Infinite Time Turing Machines (ITTM) were introduced in Hamkins and Lewis \cite{HL}, a number of machine models of computability have been generalized to the transfinite, along with various variants thereof. While for some of these models the computational strength has been successfully determined, there are still several white spots on the map of transfinite computability. In this paper, we contribute to the understanding of the computational strength of transfinite machine models by (i) proving lower bounds on the computational strength of $\alpha$-Infinite Time Register Machines ($\alpha$-ITRMs) for certain values of $\alpha$, refuting a conjecture about their strength made in \cite{alpha itrms}, (ii) showing that the computational strength of cardinal-recognizing ITRMs is equal to that of ITRMs and (iii) showing that non-solvability of the bounded halting problem, existence of a universal machine and an increase of computational power by allowing machines to recognize cardinals are equivalent for $\alpha$-ITRMs for all relevant values of $\alpha$ .

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript extends the authors' prior conference paper on α-Infinite Time Register Machines (α-ITRMs). It proves lower bounds on the function β(α) for selected values of α, refuting a conjecture on their computational strength from the cited work [alpha itrms]. It further shows that cardinal-recognizing ITRMs have the same strength as standard ITRMs and establishes equivalences, for all relevant α, among non-solvability of the bounded halting problem, existence of a universal machine, and gain in power from cardinal recognition.

Significance. If the lower bounds and equivalences hold, the results map additional territory in the computational strength of transfinite register machines, directly refuting a prior conjecture with explicit constructions and clarifying that three natural properties are equivalent for α-ITRMs. The work builds on the standard definitions from the cited literature without introducing new free parameters or ad-hoc axioms.

minor comments (2)
  1. [Introduction] The abstract and introduction cite the conjecture from [alpha itrms] and the extension of [C2], but a short paragraph explicitly contrasting the new lower-bound constructions with the earlier results would help readers track the incremental contribution.
  2. [Preliminaries] Notation for β(α) and the relevant ordinals is introduced via the prior works; a one-sentence reminder of the definition of β(α) in the preliminaries section would improve self-contained readability without lengthening the paper.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary, significance assessment, and recommendation of minor revision. No major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity; new lower bounds and equivalences are independent of cited priors

full rationale

The paper's central results consist of explicit lower bounds on β(α) that refute a conjecture from the cited prior work, plus equivalence theorems for cardinal-recognizing variants and solvability properties. These are presented as extensions relying on the standard definitions of α-ITRMs and β(α) taken from the literature, without any reduction of the new claims to fitted parameters, self-definitional loops, or load-bearing self-citations that would make the derivation equivalent to its inputs by construction. The argument chain remains self-contained against external benchmarks once the basic machine model is granted.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

No free parameters, axioms, or invented entities are mentioned in the abstract; all technical content is deferred to prior citations.

pith-pipeline@v0.9.0 · 5736 in / 1027 out tokens · 16903 ms · 2026-05-24T13:47:40.238541+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

25 extracted references · 25 canonical work pages · 1 internal anchor

  1. [1]

    Abramson, G

    F. Abramson, G. Sacks. Uncountable Gandy Ordinals. Journal of the London Mathematical Society, vol. s2-14(3) (1976)

    work page 1976

  2. [2]

    Buchholz, S

    W. Buchholz, S. Feferman, W. Pohlers, W. Sieg (eds.). Iterated inductive definitions and subsystems of analysis: recent proof-theoretical studies. Lecture Notes in Mathematics 897, Springer (1981)

    work page 1981

  3. [3]

    M. Carl. Ordinal Computability. An Introduction to Infinitary Machines. De Gruyter (2019) (forthcoming)

    work page 2019

  4. [4]

    M. Carl, T. Fischbach, P, Koepke, R. Miller, M. Nasfi, G. Weckbecker. The basic theory of Infinite Time Register Machines. Archive for Mathematical Logic 49 (2010) 2, 249-273

    work page 2010

  5. [5]

    M. Carl. Taming Koepke's Zoo II: Register Machines. Preprint, arxiv 1907.09513 (2019)

    work page internal anchor Pith review Pith/arXiv arXiv 1907

  6. [6]

    M. Carl, L. Galeotti. Resetting Infinite Time Blum-Shub-Smale-Machines. Preprint. arXiv:2001.07133v2 (2020)

    work page arXiv 2001

  7. [7]

    M. Carl. Optimal results on recognizability for infinite time register machines. Journal of Symbolic Logic 80 (4):1116-1130 (2015)

    work page 2015

  8. [8]

    N. Cutland. Computability. An introduction to recursive function theory. Cambridge University Press (1980)

    work page 1980

  9. [9]

    Friedman, P

    S. Friedman, P. Welch. Hypermachines. J. Symb. Log., vol. 76(2), pp. 620-636 (2011)

    work page 2011

  10. [10]

    Gitman, T

    V. Gitman, T. Johnstone, J. Hamkins. What is the theory ZFC without power set? Mathematical Logic Quarterly, vol. 62(4) (2011)

    work page 2011

  11. [11]

    Gostanian

    R. Gostanian. The next admissible ordinal. Annals of Mathematical Logic, vol 17(1-2) (1979)

    work page 1979

  12. [12]

    Hamkins, A

    J. Hamkins, A. Lewis. Infinite Time Turing Machines. Journal of Symbolic Logic 65(2), 567--604 (2000)

    work page 2000

  13. [13]

    J. Hamkins. MathOverflow Post, https://mathoverflow.net/questions/345007/relation-between-eta-and-omegal-1/345037#345037, accessed: 11.11.2019

    work page 2019

  14. [14]

    Koepke, B

    P. Koepke, B. Seyfferth. Ordinal machines and admissible recursion theory. Annals of Pure and Applied Logic, vol. 160, pp. 310--318 (2009)

    work page 2009

  15. [15]

    Koepke, B

    P. Koepke, B. Seyfferth. Towards a theory of infinite time Blum-Shub-Smale machines

    work page

  16. [16]

    Koepke, A

    P. Koepke, A. Morozov. On the computational strength of Infinite Time Blum-Shub-Smale Machines. Algebra and Logic, vol. 56, no. 1, (2017)

    work page 2017

  17. [17]

    P. Koepke. Infinite time register machines. In Logical Approaches to Computational Barriers, Arnold Beckmann et al., eds., Lecture Notes in Computer Science 3988 (2006), 257-266

    work page 2006

  18. [18]

    G. J\"ager. Iterating Admissibility in Proof Theory. In: J. Stern (ed.): Proceedings of the Herbrand Symposium, Logic Colloquium 1981. North Holland Publishing Company (1982)

    work page 1981

  19. [19]

    P. Koepke. Ordinal Computability. In Mathematical Theory and Computational Practice. K. Ambos-Spies et al. (eds.), Lecture Notes in Computer Science 5635, pp. 280--289 (2009)

    work page 2009

  20. [20]

    Koepke, R

    P. Koepke, R. Miller. An enhanced theory of infinite time register machines. In Logic and Theory of Algorithms. A. Beckmann et al, eds., Lecture Notes in Computer Science 5028 (2008), 306-315

    work page 2008

  21. [21]

    D. Madore. A Zoo of ordinals. Available online. http://www.madore.org/ david/math/ordinal-zoo.pdf

    work page

  22. [22]

    P. Koepke. Turing Computations on Ordinals. Bull. of Symbolic Logic, Volume 11(3) (2005)

    work page 2005

  23. [23]

    Koepke, R

    P. Koepke, R. Siders. Register computations on ordinals. Archive for Mathematical Logic vol. 47, pp. 529--548 (2008)

    work page 2008

  24. [24]

    P. Welch. Characteristics of discrete transfinite Turing machine models: halting times, stabilization times, and Normal Form Theorems. Theoretical Computer Science, vol. 410, (2009), 426-442

    work page 2009

  25. [25]

    P. Welch. Transfinite Machine Models. In: R. Downey (ed.), Turing's Legacy, Lecture Notes in Logic, Association for Symbolic Logic, (2013)

    work page 2013