pith. sign in

arxiv: 2605.18342 · v1 · pith:QERZJDRInew · submitted 2026-05-18 · 💻 cs.LO

Mathematical Informatics: Algorithms

Thomas Seiller (CNRS , JFLI) This is my paper

Pith reviewed 2026-05-19 23:35 UTC · model grok-4.3

classification 💻 cs.LO
keywords algorithmimplementationcomputabilitydirected graphpartial mapsdata structuremonoid actiondynamical system
0
0 comments X

The pith

Algorithms are defined as finite directed graphs whose edges are labelled by partial maps over an abstract data structure.

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

The paper continues an intensional approach to computability that takes programs and computations, rather than functions, as the primary objects. It defines an algorithm as a finite directed graph with edges labelled by partial maps on an abstract data structure. This separates control, shown as the graph structure, from data, shown as an algebra of operations. A program in a given model implements the algorithm when computational steps correspond to the labelled transitions while preserving the transformations induced on data representations. The result places algorithms as abstract partial specifications of computational behaviour that can be realized in multiple models.

Core claim

We introduce a formal notion of algorithm as a finite directed graph whose edges are labelled by partial maps over an abstract data structure. This definition separates control from data, representing the former as a graph and the latter as an algebra of operations. We then define what it means for a program, in a given model of computation, to implement such an algorithm, by requiring a correspondence between computational steps and labelled transitions that preserves the induced transformations on representations of data. This yields a precise notion of implementation and situates algorithms as abstract partial specifications of computational behaviour.

What carries the argument

The labelled directed graph for an algorithm, which encodes control flow separately from data operations given as partial maps on an abstract data structure and supports a correspondence relation for implementation.

If this is right

  • Algorithms function as abstract partial specifications that multiple programs in different models can implement.
  • Implementation becomes a precise relation based on preservation of induced data transformations.
  • Control and data are cleanly separated, with control as finite graph structure and data as an algebra of partial maps.
  • Uniform comparison of implementations becomes possible across models cast as monoid actions on configuration spaces.

Where Pith is reading between the lines

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

  • The graph-based definition may allow proofs that distinct programs realize the same algorithm without reference to any single machine model.
  • The same structures could later support comparisons of resource use or efficiency among implementations of one algorithm graph.
  • Such graphs might serve as a neutral specification format usable across programming paradigms.

Load-bearing premise

Models of computation can be described uniformly as monoid actions on a configuration space so that programs become dynamical systems whose steps correspond to graph transitions while preserving data transformations.

What would settle it

A concrete example of a program and algorithm pair where the intuitive sense of implementation holds yet the required step-to-transition correspondence fails to preserve data transformations, or where the correspondence holds yet no implementation relation is accepted.

Figures

Figures reproduced from arXiv: 2605.18342 by JFLI), Thomas Seiller (CNRS.

Figure 1
Figure 1. Figure 1: Two presentations of Euclid’s algorithm. [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Example of glueing the implicit assumption is that several copies of these data structures are si￾multaneously interpreted within the implementing model of computation. For￾mally, this is equivalent to considering products of data structures: if D = (D, S) and D ′ = (D′ , S′ ) are data structures, then their product D × D ′ is defined as (D × D′ , SׯS ′ ) where: SׯS ′ = {s × IdD′ | s ∈ S} ∪ {IdD × s ′ | … view at source ↗
Figure 3
Figure 3. Figure 3: Two specified algorithms [PITH_FULL_IMAGE:figures/full_fig_p014_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: The mergesort algorithm. Finally, let us note that in the proposed algorithm, no order is enforced on the two subroutines sort(a) and sort(b): the label simply imposes that both operation are performed in this part of the algorithm. As a consequence, an implementation may choose to sort a before b, or b before a, or even sort both in parallel. Variants of this algorithm in which an order is imposed can be … view at source ↗
read the original abstract

This work continues the development of an intensional approach to computability initiated in previous work, in which programs and computations, rather than functions, constitute the primary objects of study. In this setting, models of computation are described as monoid actions on a configuration space, and programs as dynamical systems constrained by this action. Within this framework, we introduce a formal notion of algorithm as a finite directed graph whose edges are labelled by partial maps over an abstract data structure. This definition separates control from data, representing the former as a graph and the latter as an algebra of operations. We then define what it means for a program, in a given model of computation, to implement such an algorithm, by requiring a correspondence between computational steps and labelled transitions that preserves the induced transformations on representations of data. This yields a precise notion of implementation and situates algorithms as abstract partial specifications of computational behaviour.

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 paper continues prior work on an intensional approach to computability in which programs and computations are primary objects. Models of computation are formalized as monoid actions on configuration spaces and programs as dynamical systems constrained by these actions. The central contribution defines an algorithm as a finite directed graph with edges labelled by partial maps over an abstract data structure, separating control (the graph) from data (an algebra of operations). It then defines implementation of such an algorithm by a program in a given model via a correspondence between computational steps and labelled graph transitions that preserves the induced transformations on data representations, yielding a precise notion of implementation and situating algorithms as abstract partial specifications of computational behaviour.

Significance. If the definitions prove useful, the framework supplies a model-independent way to specify algorithms abstractly while relating them to concrete implementations across different computational models. It builds directly on standard objects (directed graphs, partial maps, monoid actions) and emphasizes the separation of control and data, which is a clear strength for intensional studies. No machine-checked proofs, reproducible code, or falsifiable predictions are provided; significance therefore rests on the utility and adoption of the new definitions rather than on derived theorems.

minor comments (2)
  1. [Abstract] Abstract, final sentence: the preservation condition on induced transformations is stated at a high level; an explicit formal statement (e.g., a commuting diagram or equation relating the partial maps to the monoid action) would make the implementation definition easier to verify and apply.
  2. The manuscript refers to 'previous work' on intensional computability without specific citations; adding references to the relevant prior papers would help readers situate the new definitions.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their accurate summary of the manuscript and for recommending minor revision. The referee's description correctly identifies the central definitions: algorithms as finite directed graphs with edges labelled by partial maps on abstract data structures, and implementation via step correspondences that preserve data transformations in monoid-action models. No specific major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper's central contribution is the introduction of definitional constructs: algorithms formalized as finite directed graphs whose edges are labelled by partial maps over an abstract data structure, together with a correspondence-based notion of implementation inside a monoid-action model of computation. These build directly on standard mathematical objects (directed graphs, partial functions, monoid actions, dynamical systems) without any equations, predictions, or theorems that reduce by construction to fitted parameters or prior self-referential inputs. The mention of continuing prior intensional computability work is contextual background rather than a load-bearing justification for any derived result; no invariance, uniqueness theorem, or computational property is asserted whose validity depends on an unverified self-citation chain. The framework is therefore self-contained as an organizing definition rather than a deductive derivation.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 1 invented entities

The framework rests on the prior intensional approach to computability and on standard mathematical structures; no numerical parameters are fitted and no new physical entities are postulated.

axioms (2)
  • domain assumption Models of computation are described as monoid actions on a configuration space
    Invoked in the abstract as the setting in which programs are dynamical systems.
  • domain assumption A correspondence between computational steps and labelled transitions preserves induced transformations on representations of data
    Central requirement for the implementation relation stated in the abstract.
invented entities (1)
  • Algorithm formalised as finite directed graph with edges labelled by partial maps no independent evidence
    purpose: To separate control flow from data operations and serve as an abstract partial specification
    New definition introduced in the paper; no independent evidence outside the definitional framework is provided.

pith-pipeline@v0.9.0 · 5670 in / 1438 out tokens · 38218 ms · 2026-05-19T23:35:58.289370+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. [1]

    Polity Press (2022), https://books.google.fr/books?id=sIVdzgEACAAJ

    Airoldi, M.: Machine Habitus: Toward a Sociology of Algor ithms. Polity Press (2022), https://books.google.fr/books?id=sIVdzgEACAAJ

    work page 2022

  2. [2]

    Anh-Ton Le, H.L., Valarcher, P.: Completeness of Seiller ’s Abstract Machine (2025), https://hal.u-pec.fr/hal-05137612 , preprint

    work page 2025

  3. [3]

    Computational Complexity 2 (1992), https://doi.org/10.1007/BF01201998

    Bellantoni, S., Cook, S.: A new recursion-theoretic char acteriza- tion of the polytime functions. Computational Complexity 2 (1992), https://doi.org/10.1007/BF01201998

    work page doi:10.1007/bf01201998 1992

  4. [4]

    Bulletin of the European Association for Theoretical Computer Science (2003)

    Blass, A., Gurevich, Y.: Algorithms: A quest for absolute definitions. Bulletin of the European Association for Theoretical Computer Science (2003)

    work page 2003

  5. [5]

    Blass, A., Dershowitz, N., Gurevich, Y.: When are two algo rithms the same? CoRR abs/0811.0811 (2008), http://arxiv.org/abs/0811.0811

    work page arXiv 2008

  6. [6]

    American Journal of Mathematics 58(2), 345–363 (1936), http://www.jstor.org/stable/2371045

    Church, A.: An unsolvable problem of elementary number th e- ory. American Journal of Mathematics 58(2), 345–363 (1936), http://www.jstor.org/stable/2371045

    work page arXiv 1936

  7. [7]

    Oxford Univer- sity Press (2018).https://doi.org/10.1093/oso/9780198814788.001.0001

    Dean, W.: Algorithms and the mathematical foundations of computer sci- ence. In: Horsten, L., Welch, P. (eds.) Gödel’s Disjunction : The scope and limits of mathematical knowledge. Oxford University Pr ess (08 2016). https://doi.org/10.1093/acprof:oso/9780198759591.003.0002

    work page doi:10.1093/acprof:oso/9780198759591.003.0002 2016

  8. [8]

    Gastaldi, J.L., Jarvis, S., Seiller, T., Terilla, J.: Lin ear realisability structures in enriched adjunctions (2026), submitted

    work page 2026

  9. [9]

    Gastaldi, J.L., Jarvis, S., Seiller, T., Terilla, J.: Pro jective metric geometry of tropical nuclei: gap matrices, event loci, and order chambe rs (2026), submitted

    work page 2026

  10. [10]

    ACM Transactions on Computational Logic 1, 77–111 (2000)

    Gurevich, Y.: Sequential abstract state machines captu re sequential algorithms. ACM Transactions on Computational Logic 1, 77–111 (2000)

    work page 2000

  11. [11]

    Gurevich, Y.: What Is an Algorithm?, pp. 31–42. Springer Berlin Heidelberg (2012). https://doi.org/10.1007/978-3-642-27660-6_3

    work page doi:10.1007/978-3-642-27660-6_3 2012

  12. [12]

    Heath, T.: The Thirteen Books of Euclid’s Elements. No. v ol. 1, Cambridge Uni- versity Press (1956)

    work page 1956

  13. [13]

    Heath, T.: The Thirteen Books of Euclid’s Elements. No. v ol. 2, Cambridge Uni- versity Press (1956) 20 T. Seiller

    work page 1956

  14. [14]

    Heath, T.: The Thirteen Books of Euclid’s Elements. No. v ol. 3, Cambridge Uni- versity Press (1956)

    work page 1956

  15. [15]

    Kagaku tetsugaku 53(2), 65–93 (2021)

    Joinet, J.B., Seiller, T.: From abstraction and indisce rnibility to classification and types: revisiting hermann weyl’s theory of ideal elements. Kagaku tetsugaku 53(2), 65–93 (2021). https://doi.org/10.4216/jpssj.53.2_65

    work page doi:10.4216/jpssj.53.2_65 2021

  16. [16]

    Transactions of the American Mathematical Society 91(1), 1–52 (1959), http://www.jstor.org/stable/1993145

    Kleene, S.C.: Recursive functionals and quantifiers of fi nite types i. Transactions of the American Mathematical Society 91(1), 1–52 (1959), http://www.jstor.org/stable/1993145

    work page arXiv 1959

  17. [17]

    Uspekhi Mat

    Kolmogorov, A.N., Uspenskii, V.A.: On the definition of a n algorithm. Uspekhi Mat. Nauk 13, 3–28 (1958)

    work page 1958

  18. [18]

    practical a rithmetics

    Lamassé, S.: Relationships between french “practical a rithmetics” and teaching? In: Scientific Sources and Teaching Contexts Throughout His tory: Problems and Perspectives, pp. 125–153. Springer (2013)

    work page 2013

  19. [19]

    Markov, A.A.: The theory of algorithms, Trudy Mat. Inst. Steklov., vol. 42. Acad. Sci. USSR (1954)

    work page 1954

  20. [20]

    Moschovakis, Y.: What is an algorithm? In: Mathematics U nlimited — 2001 and beyond (2001)

    work page 2001

  21. [21]

    In: Dales, H.G., Oliveri, G

    Moschovakis, Y.N.: On founding the theory of algorithms . In: Dales, H.G., Oliveri, G. (eds.) Truth in Mathematics, pp. 71–104. Oxford Universi ty Press, Usa (1998)

    work page 1998

  22. [22]

    The Reasoner 17(4) (Jul 2023), https://riviste.unimi.it/index.php/thereasoner/article/view/24136

    Naibo, A., Petrolo, M., Seiller, T.: Goa: The geom- etry of algorithms. The Reasoner 17(4) (Jul 2023), https://riviste.unimi.it/index.php/thereasoner/article/view/24136

    work page 2023

  23. [23]

    Seiller, T.: Mathematical informatics (2024), https://theses.hal.science/tel-04616661, habilitation thesis

    work page 2024

  24. [24]

    Seiller, T.: Mathematical informatics: Models of compu tation (2026), https://hal.archives-ouvertes.fr/hal-05587108 , submitted

    work page 2026

  25. [25]

    Jou rnal of Logic and Com- putation 21(2), 253–286 (2011)

    Yanofsky, N.S.: Towards a definition of an algorithm. Jou rnal of Logic and Com- putation 21(2), 253–286 (2011). https://doi.org/10.1093/logcom/exq016

    work page doi:10.1093/logcom/exq016 2011