The Lost Melody Theorem for Infinite Time Blum-Shub-Smale Machines

Merlin Carl

arxiv: 2009.10582 · v2 · pith:AY4EZGPVnew · submitted 2020-09-22 · 🧮 math.LO

The Lost Melody Theorem for Infinite Time Blum-Shub-Smale Machines

Merlin Carl This is my paper

Pith reviewed 2026-05-24 14:11 UTC · model grok-4.3

classification 🧮 math.LO

keywords lost melody theoreminfinite time Blum-Shub-Smale machinesrecognizabilityhyperarithmetic realsconstructible hierarchyreal numbersinfinitary computability

0 comments

The pith

The lost melody theorem holds for infinite time Blum-Shub-Smale machines, so non-computable reals exist that these machines can recognize.

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

The paper establishes that infinite time Blum-Shub-Smale machines admit non-computable yet recognizable real numbers. It further shows that every ITBM-recognizable real is hyperarithmetic. Both recognizable and unrecognizable reals occur at every level of the constructible hierarchy below L_ω₁^CK where new reals first appear.

Core claim

The paper shows that the lost melody theorem holds for ITBMs, i.e. the existence of non-computable, but recognizable real numbers; ITBM-recognizable real numbers are hyperarithmetic; and both ITBM-recognizable and ITBM-unrecognizable real numbers appear at every level of the constructible hierarchy below L_ω₁^CK at which new real numbers appear at all.

What carries the argument

ITBM-recognizability of real numbers, which transfers the existence proof for non-computable recognizable reals from the ITTM setting using the model definitions of Koepke and Seyfferth.

If this is right

Non-computable but ITBM-recognizable real numbers exist.
Every real recognizable by an ITBM is hyperarithmetic.
At each level of the constructible hierarchy below L_ω₁^CK where new reals appear, both recognizable and unrecognizable reals occur.

Where Pith is reading between the lines

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

The result extends the lost melody phenomenon from Turing-style infinitary machines to real-number machines without extra assumptions on arithmetic operations.
The uniform appearance of both kinds of reals suggests that recognizability and non-recognizability are interleaved in the same constructible stages for this model.

Load-bearing premise

The definitions and basic properties of ITBMs allow the recognizability analysis and proof techniques developed for ITTMs to transfer directly without requiring further model-specific assumptions.

What would settle it

An explicit ITBM-recognizable real number that is not hyperarithmetic would falsify the claim.

read the original abstract

We consider recognizability for Infinite Time Blum-Shub-Smale machines, a model of infinitary computability introduced in Koepke and Seyfferth [KS]. In particular, we show that the lost melody theorem (originally proved for ITTMs in Hamkins and Lewis [HL]), i.e. the existence of non-computable, but recognizable real numbers, holds for ITBMs, that ITBM-recognizable real numbers are hyperarithmetic and that both ITBM-recognizable and ITBM-unrecognizable real numbers appear at every level of the constructible hierarchy below $L_{\omega_{1}^{\text{CK}}}$ at which new real numbers appear at all.

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.

Desk Editor's Note private letter to a colleague

Carl shows the lost melody theorem transfers to ITBMs along with hyperarithmetic and L-hierarchy placement, but the abstract leaves the model-transfer details unshown.

read the letter

The core result is that non-computable but recognizable reals exist for infinite time Blum-Shub-Smale machines, that those recognizable reals are hyperarithmetic, and that both recognizable and unrecognizable reals appear at every level of L below ω₁^CK where new reals appear. This is new work for the ITBM model; the original lost melody theorem was for ITTMs, and the hierarchy statements add structure that was not already recorded for this machine type. The paper takes the Koepke-Seyfferth definition and applies recognizability ideas from Hamkins-Lewis, which is a reasonable move in this narrow subfield. Credit is due for stating three clean claims and for tying the recognizability class to both hyperarithmetic sets and the constructible hierarchy. The abstract is short on proof steps, so the actual derivations are not visible here. The main open question is whether the real-arithmetic operations and continuous state transitions in ITBMs require new arguments or whether the ITTM techniques carry over unchanged. If the paper only cites the prior definitions without an explicit simulation or adjustment for halting on reals, the hyperarithmetic bound and the density claim could need extra justification. That said, nothing in the abstract suggests circularity or invented entities, and the claims are stated as existence and classification results rather than parameter fits. This paper is aimed at people already working on infinitary machine models and their descriptive-set-theoretic properties. A reader who follows ITTM and ITBM literature would find the extension and the L-level statements useful as a data point. It is narrow enough that it will not change broader computability theory, but the claims are precise enough to merit referee time. I would send it to referees familiar with both machine models rather than desk-reject it.

Referee Report

2 major / 1 minor

Summary. The paper proves three claims for Infinite Time Blum-Shub-Smale machines (ITBMs): the lost melody theorem holds, i.e., there exist non-computable but ITBM-recognizable real numbers; all ITBM-recognizable reals are hyperarithmetic; and both ITBM-recognizable and ITBM-unrecognizable reals appear at every level of the constructible hierarchy L_α (α < ω₁^CK) at which new reals appear.

Significance. If the results hold, the work shows that the lost melody phenomenon and the hyperarithmetic characterization of recognizable reals are robust under the shift from discrete-tape ITTMs to real-arithmetic ITBMs, and it gives a precise density statement inside the constructible hierarchy. This strengthens the comparative theory of infinitary computability models.

major comments (2)

[Proof of the lost melody theorem and hyperarithmetic bound (main body)] The three central claims rest on the assumption that recognizability notions and halting behavior transfer directly from the ITTM results of Hamkins-Lewis to the ITBM model of Koepke-Seyfferth. No explicit simulation lemma or reduction establishing that exact real arithmetic and continuous state transitions preserve the relevant computability classes is indicated, which is load-bearing for all three theorems.
[Section establishing density in the constructible hierarchy] The density claim at every level of L_α below ω₁^CK requires that the ITBM-recognizability predicate does not collapse or expand the hyperarithmetic sets in a way that would skip levels; the manuscript must verify that the real-number operations do not create new recognizable reals outside the hyperarithmetic hierarchy.

minor comments (1)

[Introduction] The abstract states the three claims clearly but the manuscript should include a short comparison table or diagram contrasting ITTM and ITBM halting and recognizability definitions.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and the positive evaluation of the significance of our results on the robustness of the lost melody theorem and related properties under the ITBM model. We address each major comment below and will revise the manuscript to strengthen the justifications as requested.

read point-by-point responses

Referee: [Proof of the lost melody theorem and hyperarithmetic bound (main body)] The three central claims rest on the assumption that recognizability notions and halting behavior transfer directly from the ITTM results of Hamkins-Lewis to the ITBM model of Koepke-Seyfferth. No explicit simulation lemma or reduction establishing that exact real arithmetic and continuous state transitions preserve the relevant computability classes is indicated, which is load-bearing for all three theorems.

Authors: We agree that an explicit simulation or reduction argument is needed to rigorously connect the ITTM results to the ITBM setting, particularly given the differences in real arithmetic and continuous state transitions. Although the proofs in the manuscript are developed directly for ITBMs, the absence of a dedicated lemma justifying the preservation of recognizability and halting behavior means the transfer is not fully explicit. In the revised version we will add a new lemma (or subsection) providing the required simulation, establishing that the relevant computability classes are preserved under the shift to the ITBM model. This will support all three main theorems. revision: yes
Referee: [Section establishing density in the constructible hierarchy] The density claim at every level of L_α below ω₁^CK requires that the ITBM-recognizability predicate does not collapse or expand the hyperarithmetic sets in a way that would skip levels; the manuscript must verify that the real-number operations do not create new recognizable reals outside the hyperarithmetic hierarchy.

Authors: The manuscript already proves that all ITBM-recognizable reals are hyperarithmetic, which ensures that no recognizable reals are created outside the hyperarithmetic hierarchy. However, to directly address the concern about potential level-skipping in the constructible hierarchy due to real-number operations, we will add an explicit verification (in the form of a clarifying paragraph or short lemma) in the density section. This will confirm that the ITBM operations preserve the alignment with hyperarithmetic degrees and do not cause the recognizability predicate to skip levels in L_α for α < ω₁^CK. revision: yes

Circularity Check

0 steps flagged

No circularity; proof transfers prior ITTM results via external machine definitions

full rationale

The paper presents an existence proof that the lost melody theorem and hyperarithmetic characterization hold for ITBMs by direct transfer of techniques from Hamkins-Lewis on ITTMs, resting on the external definitions in Koepke-Seyfferth. No equations, fitted parameters, or self-citations by the present author appear in the provided text that would reduce any claimed result to a definition or input by construction. The derivation chain is self-contained against the cited external benchmarks and does not rename or smuggle in results via the author's own prior work.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper is a pure existence proof inside existing models of computation and set theory; it introduces no free parameters, no ad-hoc axioms, and no new postulated entities.

axioms (2)

standard math Standard ZFC set theory and the definition of the constructible hierarchy L
Invoked to state the placement of reals below L_ω₁^CK
domain assumption The model of ITBMs as introduced in Koepke and Seyfferth
The paper relies on this prior definition for all machine behavior

pith-pipeline@v0.9.0 · 5630 in / 1484 out tokens · 43368 ms · 2026-05-24T14:11:11.464046+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

17 extracted references · 17 canonical work pages

[1]

Bowler, A

N. Bowler, A. Mathias. Rudimentary recursion, gentle functions and provident sets. Notre Dame Journal of Formal Logic 56(1) (2015)

work page 2015
[2]

Boolos, H

G. Boolos, H. Putnam. Degrees of Unsolvabllity of constructible sets of integers, J. Symbolic Logic 33 (1968)

work page 1968
[3]

M. Carl. Ordinal Computability. An introduction to infinitary machines. De Gruyter Berlin/Boston (2019)

work page 2019
[4]

The distribution of ITRM-recognizable reals. Ann. Pure Appl. Log. 165(9): 1403-1417 (2014)

work page 2014
[5]

Optimal Results on ITRM-recognizability. J. Symb. Log. 80(4): 1116-1130 (2015)

work page 2015
[6]

The lost melody phenomenon. In: S. Geschke et al. (eds.): Infinity, Computability, and Metamathematics : Festschrift celebrating the 60th birthdays of Peter Koepke and Philip Welch. London : College Publ.(Tributes ; 23) (2014)

work page 2014
[7]

M. Carl, T. Fischbach, P. Koepke, R. Miller, M. Nasfi, G. Weckbecker. An enhanced theory of infinite time register machines. In: A. Beckmann et al. (eds.): Logic and Theory of Algorithms. Lecture Notes in Computer Science 5028 (2008),

work page 2008
[8]

M. Carl, P. Schlicht, P. Welch. Recognizable sets and Woodin cardinals. Ann. Pure Appl. Log. 169(4): 312-332 (2018)

work page 2018
[9]

Hamkins, A

J. Hamkins, A. Lewis. Infinite Time Turing Machines. J. Symbolic Logic. 65(2) (2000)

work page 2000
[10]

R. Jensen. The fine structure of the constructible hierarchy. Ann. of Math. Logic 4(3) (1972)

work page 1972
[11]

P. Koepke. Infinite Time Register Machines. In: A. Beckmann et al. (eds.): Logical Approaches to Computational Barriers. A. Beckmann et al. (eds.) Lecture Notes in Computer Science 3988 (2006),

work page 2006
[12]

Koepke, R

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

work page 2008
[13]

Koepke, B, Seyfferth

P. Koepke, B, Seyfferth. Towards a theory of Infinite Time Blum-Shub-Smale Machines. In: S. Cooper et al. (eds.): How the World Computes. CiE 2012. Lecture Notes in Computer Science, vol 7318. Springer Berlin (2012)

work page 2012
[14]

Koepke, A

P. Koepke, A. Morozov. The computational strength of infinite time blum-shub-smale machines. Algebra and Logic 56(1) (2017)

work page 2017
[15]

A. Mathias. Provident sets and rudimentary set forcing. Fundamenta Mathematicae 230 (2015)

work page 2015
[16]

G. Sacks. Higher Recursion Theory. Perspectives in Mathematical Logic, Volume 2. Springer Berlin (1990)

work page 1990
[17]

P. Welch. Discrete Transfinite Computations. In: G. Sommaruga, T. Strahm (eds.): Turing's Revolution. The Impact of His Ideas about Computability. Birkh\"auser Basel (2015)

work page 2015

[1] [1]

Bowler, A

N. Bowler, A. Mathias. Rudimentary recursion, gentle functions and provident sets. Notre Dame Journal of Formal Logic 56(1) (2015)

work page 2015

[2] [2]

Boolos, H

G. Boolos, H. Putnam. Degrees of Unsolvabllity of constructible sets of integers, J. Symbolic Logic 33 (1968)

work page 1968

[3] [3]

M. Carl. Ordinal Computability. An introduction to infinitary machines. De Gruyter Berlin/Boston (2019)

work page 2019

[4] [4]

The distribution of ITRM-recognizable reals. Ann. Pure Appl. Log. 165(9): 1403-1417 (2014)

work page 2014

[5] [5]

Optimal Results on ITRM-recognizability. J. Symb. Log. 80(4): 1116-1130 (2015)

work page 2015

[6] [6]

The lost melody phenomenon. In: S. Geschke et al. (eds.): Infinity, Computability, and Metamathematics : Festschrift celebrating the 60th birthdays of Peter Koepke and Philip Welch. London : College Publ.(Tributes ; 23) (2014)

work page 2014

[7] [7]

M. Carl, T. Fischbach, P. Koepke, R. Miller, M. Nasfi, G. Weckbecker. An enhanced theory of infinite time register machines. In: A. Beckmann et al. (eds.): Logic and Theory of Algorithms. Lecture Notes in Computer Science 5028 (2008),

work page 2008

[8] [8]

M. Carl, P. Schlicht, P. Welch. Recognizable sets and Woodin cardinals. Ann. Pure Appl. Log. 169(4): 312-332 (2018)

work page 2018

[9] [9]

Hamkins, A

J. Hamkins, A. Lewis. Infinite Time Turing Machines. J. Symbolic Logic. 65(2) (2000)

work page 2000

[10] [10]

R. Jensen. The fine structure of the constructible hierarchy. Ann. of Math. Logic 4(3) (1972)

work page 1972

[11] [11]

P. Koepke. Infinite Time Register Machines. In: A. Beckmann et al. (eds.): Logical Approaches to Computational Barriers. A. Beckmann et al. (eds.) Lecture Notes in Computer Science 3988 (2006),

work page 2006

[12] [12]

Koepke, R

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

work page 2008

[13] [13]

Koepke, B, Seyfferth

P. Koepke, B, Seyfferth. Towards a theory of Infinite Time Blum-Shub-Smale Machines. In: S. Cooper et al. (eds.): How the World Computes. CiE 2012. Lecture Notes in Computer Science, vol 7318. Springer Berlin (2012)

work page 2012

[14] [14]

Koepke, A

P. Koepke, A. Morozov. The computational strength of infinite time blum-shub-smale machines. Algebra and Logic 56(1) (2017)

work page 2017

[15] [15]

A. Mathias. Provident sets and rudimentary set forcing. Fundamenta Mathematicae 230 (2015)

work page 2015

[16] [16]

G. Sacks. Higher Recursion Theory. Perspectives in Mathematical Logic, Volume 2. Springer Berlin (1990)

work page 1990

[17] [17]

P. Welch. Discrete Transfinite Computations. In: G. Sommaruga, T. Strahm (eds.): Turing's Revolution. The Impact of His Ideas about Computability. Birkh\"auser Basel (2015)

work page 2015