CS Paper Radar

Michael Rabin's fingerprints across the theory of computation

Avi Wigderson

cs.GL math.HO ·submitted 2026-10-19 21:36 UTC · v1
publishedunusual

Abstract

Michael O. Rabin was a major founder and leader of theoretical computer science. He died on April 14, 2026, at the age of 94. This paper aims to survey the wide scope and lasting impact of his research.

Comment
63 pages

Closest papers

Nearest neighbours by meaning across the whole index.

The Mathematical Evolution of Addressing: From Yushchenko's Address Programming Language to A Mathematics of Arrays How Addressing Evolved into a Mathematical Theory of Indexing, Array Computation, and Machine Realization

cs.GL cs.PL ·2026-09-20 ·Lenore Mullin, Gaetan Hains
similarity 0.49
Abstract

This article argues that a central development in the history of computing is the mathematical evolution of addressing. During the three decades separating Kateryna Yushchenko's Address Programming Language (1958) from Lenore Mullin's A Mathematics of Arrays (1988), addressing evolved from a machine-level mechanism for locating data into a formal theory of indexing, reduction, and machine realization, passing through Kenneth Iverson's algebra of arrays and Philip Abrams' recognition of shape as an architectural resource. Mullin's theory establishes indexing itself, via the function ψ, as the primitive from which array operations compose, reduce to a Denotational Normal Form, transform into an Operational Normal Form, and realize on hardware through dimension lifting. Historical claims are sourced against primary material, with inferences flagged as such; mathematical claims are stated as identities; performance claims are marked validated, theoretically established, or provisional. The result links programming languages, array mathematics, and computer architecture in one account.

0.23

From Maps to Metabolism: Historical Precedents and a Unified Critique of Computationalism

cs.AI q-bio.NC ·2026-10-23 ·J. Mark Bishop, Slawomir J. Nasuto
similarity 0.48
Abstract

Alexander Lerchner's recent work on the 'abstraction fallacy' argues that computational functionalism confuses physical processes with abstract descriptions, and that symbolic computation alone cannot instantiate consciousness. Yet these claims were anticipated by Korzybski's map-territory distinction, Searle's critique of strong artificial intelligence, Floridi's levels of abstraction, Spencer et al.'s observer-relativity arguments, Winograd and Flores's account of computation as socially grounded practice, and Nasuto and Bishop's biological arguments. Synthesizing these contributions, this paper advances a form of non-computational physicalism: consciousness depends upon intrinsically organized, metabolically grounded physical dynamics rather than abstract computation, whilst leaving open the possibility of artificial consciousness. An objection is that this critique targets an outdated computationalism. Mechanistic computationalism, associated with Milkowski, Piccinini, Craver, Bechtel, and Kaplan, treats computation as a property of physically realized mechanisms rather than substrate-independent formalism. Although this represents an important advance, it does not dissolve the abstraction fallacy. Computational attributions remain dependent upon choices of state individuation, system boundaries, and interpretive mapping that are not determined by physical facts alone. Kaplan and Craver's 'model-to-mechanism mapping' constrains computational descriptions without eliminating their dependence upon an external observer. Grounding computation in neural mechanisms does not confer intrinsic significance or the normativity explored by Bickhard and Nasuto and Bishop. The abstraction fallacy persists wherever computational descriptions are treated as constitutive of, rather than descriptive of, physical reality.

0.24

Discovering formally verified quantum programs with AI

cs.AI quant-phcs.PL ·2026-11-06 ·Sergey Shirobokov, Ben Jaderberg, Katerina Hristova, George Tsoukalas, Johannes Bausch +20 more
theory similarity 0.43
Abstract

The timeline by which quantum computers can solve breakthrough problems in science depends on improved quantum algorithms as much as on better hardware. Such algorithmic advances are typically achieved through many years of expert human collaboration. In mathematics and computer science, large language models have accelerated progress through automated discovery loops. However, quantum algorithms can only be evaluated by classical computers on restricted or small instances. Here we demonstrate automated discovery of quantum programs beyond these regimes including order-of-magnitude improvements on scientific applications. To achieve this, we build a quantum program library in the Lean theorem prover in which Gemini 4 agents synthesize novel programs against formal problem specifications and verify their correctness and cost. Agent teams collaborate, sharing results and knowledge through wikis and discussing ideas at organized conferences. Our results improve on prior baselines for parallel search (up to 2.55x), quantum arithmetic (290x), and simulations relevant to fusion, photochemistry and drug-metabolism by 11x, 8x and 2.5x respectively. Combining human and artificial intelligence at scale, under the rigor of mathematical proof, lets researchers design algorithms that today's classical and quantum computers cannot test, shortening the path to practical quantum computation.

0.31

Executable Archaeology: Reanimating the Logic Theorist

cs.AI cs.LOcs.PLcs.SC ·2026-11-14 ·David Moews, Jeff Shrager
similarity 0.42
Abstract · This paper builds upon a previous ArXiv paper of a similar name: https://arxiv.org/pdf/2603.13514. This paper is NOT a mere rehash of the pr…

The Logic Theorist (LT), created by Allen Newell, J. C. Shaw, and Herbert Simon in 1955--1956, is regarded by some as the first artificial intelligence program. It was originally simulated by hand and written in a pseudocode called the Logic Language (LL), which was later called Information Processing Language One (IPL-I). LT was revised many times. The first machine-executed version was written in IPL-II and ran on the JOHNNIAC, and a late version was published in 1963 by Einar Stefferud as a pedagogical document and written in IPL-V, the only version of IPL that was formally released to the public. We describe a reanimation of both the IPL-I (LL) version of LT and the 1963 IPL-V version. Comparing the two reanimations illuminates the process of the invention of early AI algorithms and computer languages.

0.25

Rabin Games Revisited

cs.FL ·2026-10-11 ·Antonio Di Stasio, Moshe Y. Vardi
published similarity 0.42
Abstract · In Proceedings GandALF 2026, arXiv:2610.08898

Rabin games have their roots in Michael Rabin's seminal work on automata over infinite trees and form a classical model for infinite-round games with ω-regular winning conditions. They play a central role in automata theory and temporal synthesis: translating an LTL specification into an equivalent deterministic Rabin automaton reduces synthesis to solving a Rabin game. In practice, however, Rabin games are typically solved indirectly, via parity games. One possible reason is that many direct algorithms have a factorial dependence on the Rabin index k, the number of Rabin pairs. In this work, we revisit Rabin's 1972 recursive algorithm. The algorithm is implicit in Rabin's proof and intertwined with finite-state determinacy. First, we "excavate" it as an explicit arena-based solver using standard reachability- and Büchi-game solving as basic building blocks, thus avoiding the exponential dependence on the alphabet in Rabin's original presentation. Second, we show that memoization removes the factorial term from the recursion-tree analysis. Finally, we introduce a variation that recurses on the Rabin index. These results provide a modern analysis of Rabin's recursive method and a basis for studying direct Rabin-game solvers for temporal synthesis.

0.37

Quo Vadis? Scientific Discovery in the Age of Artificial Intelligence

cs.CY ·2026-08-18 ·Petr O. Jedlicka
publishedsurvey similarity 0.41
Abstract · To be published in Theory of Science

This paper examines the growing role of AI in scientific discovery. It first surveys the rapid rise of AI capabilities, especially in reasoning, abstraction, planning, and long-horizon task execution, before turning to scientometric evidence of AI's diffusion across the sciences. It then proposes a typology of AI systems used in research, ranging from specialized scientific AI through scientific AI assistants and agents to hybrid experimental systems that combine computation and physical experimentation. On this basis, it offers a selective overview of recent achievements in mathematics and computer science, physics, chemistry, the life sciences, and the behavioural and social sciences. It argues that, despite these advances, current systems remain constrained by important technical, epistemic, and institutional limitations, and that their growing use introduces both near-term and longer-term risks. The conclusion further suggests that the advancement of AI in science raises broader questions concerning the division of cognitive labour between human researchers and machines.

0.26

Mixed-Precision Computing for Scientific Discovery: Formats, Co-Design, and Responsible Approximation

cs.AR math.NAcs.MS ·2026-09-29 ·Emmanuel Agullo, Hartwig Anzt, Daniel Bauer, David Bindel, Alfredo Buttari +35 more
similarity 0.41
Abstract · 41 pages

Reduced and mixed precision have moved from a niche optimization to a central design axis in scientific computing and engineering, driven by energy constraints, heterogeneous accelerators, and the convergence of simulation and machine learning. This paper organizes the landscape around seven coupled themes---number formats, floating-point emulation, emerging architectures, hardware/software co-design, relation to other approximations, software design, and precision as a multilevel resource ---and, for each theme, synthesizes the state of the art, future directions, and open questions. We emphasize \emph{energy per trusted solution} as the core objective, and we frame \say{recklessly responsible} computing as a pragmatic doctrine: exploit low precision aggressively, but with systematic detection, escalation, and certification pathways.

0.52

Counterexample-driven autonomous research with application to excess radiated energy in a Z-pinch

cs.AI physics.plasm-ph ·2026-11-01 ·Bowen Zhu, Jian Wu
code/data similarity 0.40
Abstract · 27 pages, 8 figures, 5 tables; v2 adds fine-grid Stage IV trailing-plasma timing and timestep-contraction controls, load-versus-background e…

Recent breakthroughs in artificial-intelligence-assisted mathematics show that open-ended machine search can outperform human mathematicians, yet transferring this paradigm to physics requires refactoring the research workflow. We introduce Simjecture, an open-source framework in which language-model agents pursue human-defined physical conjectures. The framework tackles two central challenges in this transfer: first, because physics is empirical and no model is final, it structures inquiry around counterexample-driven falsification and prospective hypothesis repair; second, because physical theories must interact with the real world, it uses computational physics as an executable testbed while separating the qualification of numerical instruments from scientific claim review so solvers and diagnostics can be adapted within a recorded investigation. We apply the framework in a 136.3 h investigation to tackle the long-standing problem of radiated energy exceeding the imploding-shell kinetic energy in a Z-pinch. The investigation reveals competing effects of energy conversion, retention, and release timing. Stronger coherent helical deformation increases resistive conversion while reducing radiation and increasing retained energy. In a matched fine-grid test, broadening the trailing-plasma profile delays the later radiation maximum by 1.80 ns and recovers an early 153 J bolometric deficit to within 0.08% by 44 ns, with a spectral response that shifts during the pulse. These results provide new insight into energy conversion in high-energy-density plasma physics and demonstrate a new paradigm for physics research.

0.33