Pith. sign in

REVIEW 3 major objections 4 minor 23 references

Basic interactive algorithms: Preview

T0 review · 3 major / 4 minor · reviewed 2026-08-05 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This preview argues that nondeterministic, probabilistic, and quantum algorithms can be recast as basic algorithms with appropriate oracles, pointing toward a unified axiomatization of basic interactive algorithms.

desk verdict A clearly-written preview with no new results; the oracle-based unification claim is the load-bearing promise, but unverified and unspecified here. read the letter →

arxiv 2508.05798 v1 pith:EB2EZVXP submitted 2025-08-07 cs.LO cs.CLmath.LOquant-ph

Yuri Gurevich This is my paper · ORCID
classification cs.LOcs.CLmath.LOquant-ph
keywords basicalgorithmsabstractstatemachinesoraclesnondeterministicprobabilisticquantuminteractiveChurch–Turingthesis
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

Classical algorithms were axiomatized decades ago as basic algorithms, with every basic algorithm shown behaviorally equivalent to an abstract state machine. This dialog preview argues that the expanded algorithmic landscape—nondeterministic, probabilistic, quantum circuit, and other interactive algorithms—can be brought under the same roof: each can be viewed as a basic algorithm equipped with appropriate oracles. If the promised axiomatization of basic interactive algorithms succeeds, one set of principles would cover many algorithm families and sharpen the distinction between the logician's Church–Turing thesis and the broader physical thesis. The preview itself is a foretaste; the axiomatization and proofs are deferred to the upcoming work.

What carries the argument

The central machinery is the paired notions of a basic algorithm and an oracle. A basic algorithm is the sequential, step-by-step computation already captured by the classical axiomatization; an oracle is an external agent that answers queries between steps, supplying nondeterministic choices, random bits, or quantum measurement outcomes. The classical result that every basic algorithm is behaviorally equivalent to an abstract state machine provides the yardstick for the reduction. In this preview, the oracle does the work of absorbing everything non-sequential or non-deterministic about an algorithm, leaving a shared discrete-step computational core that the upcoming axiomatization of basic

What would settle it

Find a concrete quantum circuit algorithm whose observable input–output behavior provably cannot be matched by any basic algorithm with an oracle that answers only discrete queries between finitely many steps—for example, a circuit whose output must reflect the full amplitude vector of a superposition rather than any finite transcript of oracle answers. Such a circuit would refute the preview's central claim.

Watch

Extended reading notes

Core claim

The paper's central claim is that the quarter-century-old axiomatization of sequential algorithms is not left behind by newer algorithm paradigms. Nondeterministic and probabilistic algorithms are illustrated as basic algorithms whose oracles supply the missing choices or random bits, and the author asserts that quantum circuit algorithms and many other classes fit the same pattern. The underlying mechanism is the oracle: a way to import the non-classical or non-deterministic part of a computation into the environment while the algorithm itself remains a basic, step-by-step, sequential-time process. The paper also draws a sharp line between the Church–Turing thesis as logicians use it—a thes

Load-bearing premise

The load-bearing premise is that an oracle can absorb the genuinely non-sequential features of quantum and interactive computation—superposition, measurement, and continuous interaction—while the algorithm itself still advances in discrete sequential steps.

Editorial extensions

If this is right

  • If the oracle reduction is right, nondeterministic and probabilistic algorithms inherit the behavioral equivalence result: each has an abstract state machine with an oracle that matches its behavior.
  • Quantum circuit algorithms would fall inside the interactive basic-algorithm framework, so the axiomatization of basic interactive algorithms would supply a common semantic foundation for quantum and classical computation.
  • The distinction between the Church–Turing thesis and the physical thesis becomes a formal boundary: the first is about basic algorithms, while the second is a much stronger claim about physical systems that no axiomatization of algorithms alone can settle.
  • The upcoming axiomatization would give a precise sense in which 'algorithm' has expanded since the 1960s without changing the underlying sequential computational core.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • An implication left implicit is that this framing relocates the novelty of probabilistic and quantum computation from the algorithm to the environment: the computational engine stays classical and sequential, and the oracle is where randomness or quantumness enters. That would make 'quantum advantage' a property of the environment plus interaction protocol, not of a new kind of step.
  • A testable extension: apply the same oracle construction to other proposed algorithm families—analog, adiabatic, or continuous-time models—and check whether their input–output behavior can be reproduced by a basic algorithm with a suitable oracle. The preview's claim predicts yes as long as the computation can be organized into discrete steps.
  • The paper's sharp separation of the two theses suggests that an experiment showing a physical process that cannot be simulated by a Turing machine would refute the physical thesis while leaving the logician's Church–Turing thesis untouched; this distinction is often blurred in popular debate.
  • The likely pressure point is time: if a genuinely continuous-time oracle is needed, the discrete-step postulate of basic algorithms may have to be relaxed, which would change the shape of the axiomatization rather than merely adding an oracle.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. This short preview/dialog note recalls the 1990s ASM axiomatization of sequential algorithms, which the author now calls 'basic algorithms,' and distinguishes the original Church-Turing thesis from the stronger 'physical thesis.' It claims that nondeterministic and probabilistic algorithms can be viewed as basic algorithms with appropriate oracles, and that the same view applies to quantum circuit algorithms and other classes. No formal definitions or proofs appear in the abstract, and the full text as submitted is almost entirely unreadable due to encoding corruption, so the concrete technical content cannot be verified.

Significance. If the advertised program were carried out, a unified behavioral axiomatization covering nondeterministic, probabilistic, and quantum circuit algorithms would be a substantial contribution to the theory of algorithms and would sharpen the physical Church-Turing thesis. The paper's historical framing and its reliance on the independently established ASM axiomatization are genuine strengths. However, as it stands the central claim is only asserted. The oracle mechanism is unspecified, so the quantum claim is vulnerable to vacuous or unfaithful formalization; no proof or even precise statement is recoverable from the submitted text.

major comments (3)
  1. [Abstract, last sentence] The claim that 'the same view applies to quantum circuit algorithms' is load-bearing but unsupported: there is no formal definition of 'oracle' or 'basic interactive algorithm' in the recoverable text. The oracle notion must be constrained so that the reduction is neither vacuous (an arbitrary oracle implementing the whole circuit in one step) nor ineffective (a classical oracle too weak to represent superposition and measurement). The author needs to state the oracle axioms and give at least a precise version of the quantum reduction before this claim can be assessed.
  2. [Full text (as submitted)] The body of the paper is mojibake; no definition, theorem, equation, or proof is recoverable. Thus the abstract's assertion that the paper 'illustrates' the oracle view for nondeterministic and probabilistic algorithms cannot be checked. A readable source file is a precondition for any further evaluation and should be supplied in a revision.
  3. [Abstract, first paragraph] The paper self-describes as a 'preview' offering a 'foretaste of an upcoming work.' This explicitly defers the axiomatization to a future paper, yet the abstract makes concrete present-tense claims about nondeterministic, probabilistic, and quantum algorithms. The scope needs to be clarified: either restrict the paper to historical/terminological exposition, or include the promised technical core. Currently the assertions outrun the demonstrated content.
minor comments (4)
  1. [Terminology] The new name 'basic algorithms' for 'sequential algorithms' or 'classical algorithms' should be tied to the prior literature (e.g., Gurevich's ASM axiomatization) to avoid terminological confusion.
  2. [References] The 'physical thesis' is invoked without citations; references to Gandy, Deutsch, or related papers on the physical Church-Turing thesis would be helpful.
  3. [Metadata] The submission contains an extraneous arXiv identifier and math.AP header line, apparently an artifact of text extraction; the source should be cleaned.
  4. [Structure] If the paper is intended as a preview, it would benefit from an explicit statement of which results are established here and which are deferred to the full paper, possibly as a bulleted list.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the preview makes promises rather than deriving conclusions from fitted inputs or self-referential definitions.

full rationale

This is a preview/foretaste paper: it explicitly refers to 'an upcoming work on the axiomatization of basic interactive algorithms' and does not present a formal derivation, theorem, or construction. The claim that nondeterministic and probabilistic algorithms 'can be viewed as basic algorithms with appropriate oracles' is an assertion of a future research program, not a result derived from premises that include the conclusion. The paper invokes the quarter-century-old ASM-style axiomatization of sequential/basic algorithms, but that axiomatization is an independent, externally established body of work; its use as background is not a self-citation chain. The quantum-algorithm claim is admittedly not demonstrated in this text, and the oracle mechanism is unspecified, but under-specification and unverifiability are not circularity. The skeptical worry that an unconstrained oracle could make the unification vacuous is a substantive correctness risk for the announced work, not a circular step in this paper. No equation or definition in the visible text reduces to its own input, and no fitted parameter is relabeled as a prediction. Therefore the honest finding is no significant circularity.

Assumptions & free parameters 0 free parameters · 1 assumptions · 0 invented entities

Only one background axiom is identified: the ASM thesis as prior established work. No free parameters or invented entities. The preview itself makes no fitted or empirical claims.

assumptions (1)
  • domain assumption The ASM axiomatization of sequential algorithms is correct and applicable as a foundation for the oracle-based extension.
    The abstract relies on this earlier axiomatization, which proved every basic algorithm is behaviorally equivalent to an abstract state machine, to frame the planned extension.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Basic interactive algorithms: Preview." pith.science (2026). https://pith.science/paper/EB2EZVXP

@misc{pith2026250805798,
  author       = {Pith},
  title        = {Pith review of: Basic interactive algorithms: Preview},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/EB2EZVXP}},
  note         = {Machine review of arXiv:2508.05798}
}
read the original abstract

This dialog paper offers a preview and provides a foretaste of an upcoming work on the axiomatization of basic interactive algorithms. The modern notion of algorithm was elucidated in the 1930s--1950s. It was axiomatized a quarter of a century ago as the notion of ``sequential algorithm'' or ``classical algorithm''; we prefer to call it ``basic algorithm" now. The axiomatization was used to show that for every basic algorithm there is a behaviorally equivalent abstract state machine. It was also used to prove the Church-Turing thesis as it has been understood by the logicians. Starting from the 1960s, the notion of algorithm has expanded -- probabilistic algorithms, quantum algorithms, etc. -- prompting introduction of a much more ambitious version of the Church-Turing thesis commonly known as the ``physical thesis.'' We emphasize the difference between the two versions of the Church-Turing thesis and illustrate how nondeterministic and probabilistic algorithms can be viewed as basic algorithms with appropriate oracles. The same view applies to quantum circuit algorithms and many other classes of algorithms.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

23 extracted references · 23 canonical work pages

  1. [1]

    Andreas Blass and Yuri Gurevich, ``Abstract state machines capture parallel algorithms,'' ACM Transactions on Computational Logic 4:4 (Oct.\ 2003) 578--651 with ``Correction and Extensions'' in 9:3 (June 2008) article 19

    work page 2003

  2. [2]

    Andreas Blass and Yuri Gurevich, ``Ordinary interactive small-step algorithms'', ACM Transactions on Computational Logic, part I in 7:2 (April 2006), pages 363--419, parts II and III in 8:3 (July 2007) articles 15 and 16

    work page 2006

  3. [3]

    Andreas Blass, Yuri Gurevich, Dean Rosenzweig and Benjamin Rossman ``Interactive small-step algorithms,'' parts I and II, Logical Methods in Computer Science 3:4 (2007) articles 3 and 4

    work page 2007

  4. [4]

    Alonzo Church, ``An unsolvable problem of elementary number theory'', American Journal of Mathematics 58 (1936), 345--363

    work page 1936

  5. [5]

    Stephen Cook, ``The complexity of theorem-proving procedures,'' Proceedings of the Third Annual ACM Symposium on Theory of Computing (STOC) 1971 151–-158

    work page 1971

  6. [6]

    Gandy, ``Church's thesis and principles for mechanisms'', In ``The Kleene Symposium'' (eds

    Robin O. Gandy, ``Church's thesis and principles for mechanisms'', In ``The Kleene Symposium'' (eds. J. Barwise et al.), North-Holland 1980 123--148

    work page 1980

  7. [7]

    Nachum Dershowitz and Yuri Gurevich, ``A natural axiomatization of computability and proof of Church's thesis,'' Bulletin of Symbolic Logic 14:3 (2008) 299--350

    work page 2008

  8. [8]

    Andreas Glausch and Wolfgang Reisig, ``An ASM-characterization of a class of distributed algorithms,'' Lecture Notes in Computer Science 5115, Springer, https://doi.org/10.1007/978-3-642-11447-2_4

    work page doi:10.1007/978-3-642-11447-2_4

Show all 23 references
  1. [9]

    Also (slightly revised) in ``Current Trends in Theoretical Computer Science: Essays and Tutorials" (eds

    Yuri Gurevich, ``Evolving algebras: An introductory tutorial,'' Bulletin of EATCS 43 (1991) 264--284. Also (slightly revised) in ``Current Trends in Theoretical Computer Science: Essays and Tutorials" (eds. G. Rozenberg and A. Salomaa), World Scientific 1993 266--292

    1991

  2. [10]

    Yuri Gurevich, ``Evolving algebra 1993: Lipari guide,'' in ``Specification and Validation Methods'' (ed. E. B\"orger), Oxford University Press 1995 9--36, https://arxiv.org/pdf/1808.06255

    1993 arXiv

  3. [11]

    Yuri Gurevich, ``Sequential abstract state machines capture sequential algorithms,'' ACM Transactions on Computational Logic 1:1 (2000), 77--111

    2000

  4. [12]

    Yuri Gurevich, ``Unconstrained Church-Turing thesis cannot possibly be true,'' Bulletin of EATCS 127 (2019), https://arxiv.org/pdf/2002.03145

    2019 arXiv

  5. [13]

    Yuri Gurevich and Andreas Blass, ``Software science view on quantum circuit algorithms,'' Information and Computation 292 (2023) article 105024, https://arxiv.org/pdf/2209.13731

    2023 arXiv

  6. [14]

    Yuri Gurevich and Jim Huggins, ``The semantics of the C programming language,'' Springer Lecture Notes in Computer Science 702 (1993) 274--308

    1993

  7. [15]

    Kleene, ``Introduction to metamathematics,'' Wolters-Noordhoff Publishing and North-Holland Publishing Company, 1971 (First published by D

    Stephen C. Kleene, ``Introduction to metamathematics,'' Wolters-Noordhoff Publishing and North-Holland Publishing Company, 1971 (First published by D. Van Nostrand Company in 1952.)

    1971

  8. [16]

    Kolmogorov, ``On the notion of algorithm,'' Uspekhi Matematicheskikh Nauk (in Russian) vol

    Andrey N. Kolmogorov, ``On the notion of algorithm,'' Uspekhi Matematicheskikh Nauk (in Russian) vol. 8 issue 4(56) (1953) p. 175, https://www.mathnet.ru/rus/rm/v8/i4/p173

    1953

  9. [17]

    9:3 (1973) 115--116

    Leonid Levin, ``Universal search problems,'' Problems of Information Transmission (in Russian). 9:3 (1973) 115--116

    1973

  10. [18]

    Michael Rabin and Dana Scott, ``Finite automata and their decision problems,'' in IBM Journal of Research and Development 3:2 (1959) 114--125

    1959

  11. [19]

    ``Theory of recursive functions and effective computability,'' McGraw-Hill 1967

    Hartley Rogers, Jr. ``Theory of recursive functions and effective computability,'' McGraw-Hill 1967

    1967

  12. [20]

    Shoenfield, ``Recursion theory,'' Springer Verlag 1993

    Joseph R. Shoenfield, ``Recursion theory,'' Springer Verlag 1993

    1993

  13. [21]

    StackExchange contributors, ``What would it mean to disprove Church-Turing thesis?'' Theoretical Computer Science StackExchange, Asked August 17, 2010, https://cstheory.stackexchange.com/questions/88/

    2010

  14. [22]

    Turing, ``On computable numbers, with an application to the Entscheidungsproblem,'' Proceedings of the London Mathematical Society , ser

    Alan M. Turing, ``On computable numbers, with an application to the Entscheidungsproblem,'' Proceedings of the London Mathematical Society , ser. 2 vol. 42 parts 3 and 4, 1936, 230--265. Corrigenda in vol. 43 (1937) 544--546

    1936

  15. [23]

    Wikipedia, ``Straightedge and compass construction,'' \ CC BY-SA 4.0, seen on May 15, 2025

    2025

Pith tools

Reviewed August 5, 2026 · model on record in the stance chip above.