The 2D Ray Tracing Problem using ABCD Lenses and Mirrors is Turing Complete

Andreas Jakoby; Christian Schindelhauer; Rosemary U. Adejoh; Sneha Mohanty

arxiv: 2606.24218 · v1 · pith:5WJCNHZGnew · submitted 2026-06-23 · 💻 cs.CC

The 2D Ray Tracing Problem using ABCD Lenses and Mirrors is Turing Complete

Rosemary U. Adejoh , Andreas Jakoby , Sneha Mohanty , Christian Schindelhauer This is my paper

Pith reviewed 2026-06-25 22:14 UTC · model grok-4.3

classification 💻 cs.CC

keywords Turing completenessray tracingABCD matrixparaxial opticsreversible computationoptical simulationcomputational universalityflowchart simulation

0 comments

The pith

Two-dimensional ray tracing with ABCD lenses and plane mirrors is Turing-complete.

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

The paper establishes that ray paths in a 2D optical system using thin lenses and mirrors can simulate arbitrary computation. It first shows that any 2x2 matrix with determinant 1 arises from three lenses, then combines lenses with mirrors to realize linear updates on two variables. These updates form a reversible flowchart that is proven Turing-complete for rational values. The geometric embedding of this flowchart into the plane therefore makes the ray-tracing problem itself Turing-complete, showing that three-dimensional space is not required for optical universality.

Core claim

The two-dimensional ray tracing problem with thin lenses and plane mirrors, under the ABCD paraxial model, is Turing-complete. This follows from proving that any SL(2,R) matrix is realizable by three lenses, that mirrors permit reversible two-variable linear flowcharts, and that the restricted two-variable reversible flowchart problem is Turing-complete; the flowchart is then embedded geometrically in the plane.

What carries the argument

A two-variable reversible flowchart whose linear updates are realized by ABCD lens matrices and plane-mirror reflections.

If this is right

Any reversible Turing machine has a corresponding finite 2D arrangement of lenses and mirrors.
Deciding the eventual path of a ray in such a system is undecidable in general.
Optical computation is possible without requiring three spatial dimensions.
The ray-tracing decision problem in this model is at least as hard as the halting problem.

Where Pith is reading between the lines

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

Planar optical devices could in principle perform universal computation if fabrication precision meets the paraxial ideal.
Similar linear-update plus reflection mechanisms in other 2D physical systems may also be Turing-complete.
Dimensionality constraints alone do not limit computational power in this class of optical models.

Load-bearing premise

Lenses and mirrors can be placed so that every intended ray path occurs without collisions, angle violations, or departures from the paraxial model.

What would settle it

Exhibit one two-variable reversible flowchart for which no planar arrangement of lenses and mirrors realizes the required linear updates without ray intersections or paraxial violations.

Figures

Figures reproduced from arXiv: 2606.24218 by Andreas Jakoby, Christian Schindelhauer, Rosemary U. Adejoh, Sneha Mohanty.

**Figure 4.** Figure 4: Reversible flowchart for the computation transition (p, x, z, q) for x = β and z = 0. We assume that within a computation the RTM always alternates from step to step between computing and head moving transition. In the following construction, we ensure that the two flowchart variables are always bounded, i.e., θ, y ∈ Q ∩ (−2, 2). This is motivated by the limited size of the lenses used later on. Furthermo… view at source ↗

**Figure 5.** Figure 5: Left head movement [p, □, −1, q] y< 1 p y> 1 y< 1 y> 1 y> 1 y< 1 y> 1 y< 1 q y → y/2 ω → 2ω y → y +1 y → y/2 ω → 2ω y → y +1 y → 2y ω → ω/2 y → 2y ω → ω/2 y → y ↑ 1 y → y ↑ 1 y → 2y ω → ω/2 y → y/2 ω → 2ω test test assert assert s0 = ω s0 =1 s0 =0 ! y ω " → ! ↑ω y " ! y ω " → ! ω ↑y " ! y ω " → ! ω ↑y " ! y ω " → ! ω ↑y " [PITH_FULL_IMAGE:figures/full_fig_p008_5.png] view at source ↗

**Figure 7.** Figure 7: The geometry of a thin lens. Note that we assume d → 0. Lens with focal radius Halt Start Finish ω0 ω d1 d2 d3 f1 f2 ! y ω " → ! 1 d1 01 " · ! y ω " ! y ω " → ! 1 d2 01 " · ! y ω " ! y ω " → ! 1 d3 01 " · ! y ω " ! y ω " → ! 10 ↑1/f1 1 " · ! y ω " y0 y Lens with focal radius ! y ω " → ! y0 ω0 " Start ray ray ray ! y ω " → ! 10 ↑1/f2 1 " · ! y ω " [PITH_FULL_IMAGE:figures/full_fig_p008_7.png] view at source ↗

**Figure 9.** Figure 9: Geometry of the grid-based layout for the [PITH_FULL_IMAGE:figures/full_fig_p010_9.png] view at source ↗

**Figure 11.** Figure 11: Note that the matrix multiplication operations remain unchanged, since the transformation corresponds to a [PITH_FULL_IMAGE:figures/full_fig_p010_11.png] view at source ↗

**Figure 11.** Figure 11: Crossing/connection, redirection, Test, and Assertion at the nodes of the ray-tracing grid. [PITH_FULL_IMAGE:figures/full_fig_p011_11.png] view at source ↗

read the original abstract

We establish that the two-dimensional ray tracing problem with thin lenses and plane mirrors is Turing-complete, thereby resolving an open question posed by Reif et al. in 1994 as to whether three-dimensional space is necessary for computational universality in optical systems. To this end, we consider the standard approximation of reflection and refraction, namely the ABCD model for paraxial optics, which describes ray propagation through lenses (refraction) via a 2 x 2 matrix, combined with the geometric reflection model for plane mirrors. In the absence of mirrors, two-dimensional ray tracing using any combination of lenses in this ABCD matrix model can be described by a single 2 x 2 matrix-vector product, where the matrix has real entries and determinant 1. Conversely, we show that any such matrix with determinant 1 can be represented as a composition of exactly three appropriately spaced thin lenses. When mirrors are combined with lenses, the ray tracing problem can be described by a flowchart using only two variables, which establishes Turing computability for rational-valued inputs, spaces and matrix entries. Building on this observation, we present a construction of ray tracing that simulates a reversible Turing machine. We begin with a restricted version of the reversible flowchart problem, in which only two variables and certain linear functions are permitted. We prove that this restricted variant is Turing-complete. We then show that such a flowchart admits a geometric realization using lenses and mirrors in our model, thereby establishing the main result: Turing-completeness of the two-dimensional ray tracing problem with ABCD-model lenses and mirrors.

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

Closes the 2D optical Turing-completeness question with an ABCD-lens plus mirror construction, but the planar embedding step is the one that still needs verification.

read the letter

The paper shows that 2D ray tracing under the ABCD paraxial model with thin lenses and plane mirrors is Turing complete, which would settle the open question from Reif et al. in 1994 about whether three dimensions are required.

They do two things cleanly. Any 2x2 matrix with determinant 1 can be built from exactly three thin lenses; that fact is stated directly and looks usable on its own. They then reduce the optics problem to a restricted reversible flowchart that uses only two variables and linear updates, prove that this restricted model is already Turing complete over the rationals, and sketch how the flowchart maps to a layout of lenses and mirrors.

The soft spot is the geometric embedding itself. Fitting multiple independent optical paths into the plane without ray crossings, angle violations, or departures from the paraxial regime is not automatic, and the abstract gives no quantitative bounds or non-intersection argument. The stress-test note flags exactly this point. If the full construction supplies a concrete, collision-free layout that stays inside the model assumptions, the result holds; if the details are thin or rely on extra dimensions in disguise, the claim weakens.

The work is aimed at researchers who track computational models of physical systems and the Reif line of questions. A reader who wants to see how the 2D case is handled will get value from the reduction steps. It deserves a serious referee because it directly addresses a long-open problem with an explicit construction rather than a hand-wavy existence argument.

Referee Report

2 major / 1 minor

Summary. The manuscript claims that the two-dimensional ray tracing problem with thin lenses and plane mirrors under the ABCD paraxial model is Turing complete. It proceeds in three steps: (i) any 2x2 matrix with determinant 1 can be realized exactly as a composition of three appropriately spaced thin lenses; (ii) a restricted reversible flowchart using only two variables and linear updates is Turing complete; (iii) any such flowchart admits a faithful geometric embedding into the plane using ABCD lenses and plane mirrors that preserves the linear semantics.

Significance. If the embedding construction is correct and free of unintended intersections or paraxial violations, the result resolves the 1994 open question of Reif et al. by showing that three-dimensional space is not required for optical computational universality. The explicit matrix factorization into three lenses and the reduction to known properties of reversible Turing machines constitute concrete, falsifiable contributions that link paraxial optics directly to reversible computation.

major comments (2)

[Abstract / geometric realization] Abstract (final paragraph) and geometric-realization section: the claim that 'such a flowchart admits a geometric realization using lenses and mirrors in our model' is load-bearing for the main theorem, yet the manuscript provides no explicit non-intersection argument, angle bounds, or layout procedure guaranteeing that multiple independent optical paths can be placed in 2D without ray crossings that would couple the two variables or violate the paraxial assumption.
[Section proving restricted flowchart is TC] The reduction from the restricted 2-variable reversible flowchart to a reversible Turing machine is asserted to be Turing complete, but the manuscript must verify that the allowed linear functions and two-variable restriction suffice to simulate arbitrary reversible computation without requiring additional state variables that cannot be realized optically.

minor comments (1)

Notation for the ABCD matrices and the two flowchart variables should be introduced with explicit definitions before the embedding construction to improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their thoughtful review and for identifying points where the presentation of our constructions can be strengthened. We address each major comment below and indicate the revisions we will make.

read point-by-point responses

Referee: [Abstract / geometric realization] Abstract (final paragraph) and geometric-realization section: the claim that 'such a flowchart admits a geometric realization using lenses and mirrors in our model' is load-bearing for the main theorem, yet the manuscript provides no explicit non-intersection argument, angle bounds, or layout procedure guaranteeing that multiple independent optical paths can be placed in 2D without ray crossings that would couple the two variables or violate the paraxial assumption.

Authors: We agree that an explicit non-intersection argument and layout procedure would improve rigor. The geometric-realization section constructs independent optical paths for the two variables by routing them through spatially separated regions using mirrors, with element placements chosen to avoid crossings. However, the current text does not include a dedicated proof of non-intersection or explicit angle bounds. We will add a new subsection that formalizes the layout procedure, proves that rays remain in disjoint regions (thus preserving variable independence), and verifies that all angles satisfy the paraxial assumption. This constitutes a partial revision: the core embedding construction is unchanged, but the supporting argument will be expanded with the requested details. revision: partial
Referee: [Section proving restricted flowchart is TC] The reduction from the restricted 2-variable reversible flowchart to a reversible Turing machine is asserted to be Turing complete, but the manuscript must verify that the allowed linear functions and two-variable restriction suffice to simulate arbitrary reversible computation without requiring additional state variables that cannot be realized optically.

Authors: The section establishes Turing completeness by exhibiting an explicit reduction from reversible Turing machines to the 2-variable linear flowchart. The allowed linear updates (multiplication by SL(2,R) matrices and additions) are shown to be sufficient to encode and simulate the tape contents and head movements of a reversible TM using only the two variables; the proof encodes the configuration such that no auxiliary variables are required. We will revise the section to include an additional paragraph that explicitly verifies why the two-variable restriction and permitted linear functions suffice for arbitrary reversible computation and why no optically unrealizable extra states arise. revision: yes

Circularity Check

0 steps flagged

Derivation is self-contained via explicit proofs and constructions

full rationale

The paper first proves Turing-completeness for a restricted two-variable reversible flowchart with linear updates, then constructs an explicit geometric realization using ABCD-matrix lenses and mirrors. No step reduces by definition to its own output, no fitted parameters are relabeled as predictions, and no load-bearing claim rests on self-citation chains. The central embedding argument is presented as a direct construction rather than an imported uniqueness result or ansatz.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The proof relies on standard facts from linear algebra and computability theory plus the assumption that the ABCD model plus geometric reflection can embed the required linear updates without physical interference.

axioms (2)

domain assumption Any 2x2 matrix with determinant 1 can be factored into a product of three lens matrices
Invoked to realize arbitrary SL(2,R) transformations with lenses alone.
standard math Reversible Turing machines are Turing complete
Used to reduce the optical problem to a known universal model.

pith-pipeline@v0.9.1-grok · 5829 in / 1245 out tokens · 23147 ms · 2026-06-25T22:14:53.895193+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

16 extracted references · 12 canonical work pages

[1]

Adejoh, Andreas Jakoby, Sneha Mohanty, and Christian Schindelhauer

Rosemary U. Adejoh, Andreas Jakoby, Sneha Mohanty, and Christian Schindelhauer. How Pinball Wizards Simulate a Turing Machine. In C. Aiswarya, Ruta Mehta, and Subhajit Roy, editors,45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025), volume 360 ofLeibniz International Proceedings in Informatics...

work page doi:10.4230/lipics.fsttcs.2025.4 2025
[2]

What do reversible programs compute? In Martin Hofmann, editor, Foundations of Software Science and Computational Structures, pages 42–56, Berlin, Heidelberg, 2011

Holger Bock Axelsen and Robert Glück. What do reversible programs compute? In Martin Hofmann, editor, Foundations of Software Science and Computational Structures, pages 42–56, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg.doi:10.1007/978-3-642-19805-2_4

work page doi:10.1007/978-3-642-19805-2_4 2011
[3]

Bastiaans and Tatiana Alieva

Martin J. Bastiaans and Tatiana Alieva. Classification of lossless first-order optical systems and the linear canonical transformation.Journal of the Optical Society of America. A, Optics, image science, and vision, 24 4:1053–62,
[4]

URL:https://api.semanticscholar.org/CorpusID:23969043
[5]

Semantics for a Turing-Complete Reversible Pro- gramming Language with Inductive Types

Kostia Chardonnet, Louis Lemonnier, and Benoît Valiron. Semantics for a Turing-Complete Reversible Pro- gramming Language with Inductive Types. In Jakob Rehof, editor,9th International Conference on Formal Structures for Computation and Deduction (FSCD 2024), volume 299 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 19:1–19:19, Dagstuh...

work page doi:10.4230/lipics.fscd.2024.19 2024
[6]

Corcovilos

Theodore A. Corcovilos. Beyond the abcds: A better matrix method for geometric optics by using homogeneous coordinates.American Journal of Physics, 91(6):449–457, 06 2023.doi:10.1119/5.0083069

work page doi:10.1119/5.0083069 2023
[7]

Universality in computable dynamical systems: old and new.Journal of Physics: Complexity, 6(3):035014, sep 2025.doi:10.1088/2632-072X/ae00b5

Ángel González-Prieto, Eva Miranda, and Daniel Peralta-Salas. Universality in computable dynamical systems: old and new.Journal of Physics: Complexity, 6(3):035014, sep 2025.doi:10.1088/2632-072X/ae00b5

work page doi:10.1088/2632-072x/ae00b5 2025
[8]

Computer solutions of the traveling salesman problem,

Herwig Kogelnik. Imaging of optical modes—resonators with internal lenses.Bell System Technical Journal, 44(3):455–494, 1965. URL:https://doi.org/10.1002/j.1538-7305.1965.tb01672.x

work page doi:10.1002/j.1538-7305.1965.tb01672.x 1965
[9]

Classical billiards can compute, 2025

Eva Miranda and Isaac Ramos. Classical billiards can compute, 2025. URL: https://arxiv.org/abs/2512. 19156,arXiv:2512.19156

Pith/arXiv arXiv 2025
[10]

Unpredictability and undecidability in dynamical systems.Physical Review Letters, 64(20):2354, 1990

Cristopher Moore. Unpredictability and undecidability in dynamical systems.Physical Review Letters, 64(20):2354, 1990. URL:https://doi.org/10.1103/PhysRevLett.64.2354

work page doi:10.1103/physrevlett.64.2354 1990
[11]

Reversible turing machines

Kenichi Morita. Reversible turing machines. InTheory of Reversible Computing, pages 103–156. Springer, 2017. URL:https://doi.org/10.1007/978-4-431-56606-9_5

work page doi:10.1007/978-4-431-56606-9_5 2017
[12]

Brigham Young University, Department of Physics Provo, UT 84602, 2015

Justin Peatross and Michael Ware.Physics of light and optics. Brigham Young University, Department of Physics Provo, UT 84602, 2015

2015
[13]

John H. Reif, J. Doug Tygar, and A. Yoshida. Computability and complexity of ray tracing.Discrete & Computational Geometry, 11:265–288, 1994. URL:https://doi.org/10.1007/BF02574009

work page doi:10.1007/bf02574009 1994
[14]

Reversible computing

Tommaso Toffoli. Reversible computing. In Jaco de Bakker and Jan van Leeuwen, editors,Automata, Languages and Programming, pages 632–644, Berlin, Heidelberg, 1980. Springer Berlin Heidelberg. URL: https://doi. org/10.1007/3-540-10003-2_104

work page doi:10.1007/3-540-10003-2_104 1980
[15]

Fundamentals of reversible flowchart languages

Tetsuo Yokoyama, Holger Bock Axelsen, and Robert Glück. Fundamentals of reversible flowchart languages. Theoretical Computer Science, 611:87–115, 2016.doi:10.1016/j.tcs.2015.07.046

work page doi:10.1016/j.tcs.2015.07.046 2016
[16]

H. T. Yura and S. G. Hanson. Optical beam wave propagation through complex optical systems.J. Opt. Soc. Am. A, 4(10):1931–1948, Oct 1987. URL: https://opg.optica.org/josaa/abstract.cfm?URI= josaa-4-10-1931,doi:10.1364/JOSAA.4.001931. 12 The 2D Ray Tracing Problem using ABCD Lenses and MirrorsTECHNICALREPORT A Appendix: Combination of Thin Lenses for Gener...

work page doi:10.1364/josaa.4.001931 1931

[1] [1]

Adejoh, Andreas Jakoby, Sneha Mohanty, and Christian Schindelhauer

Rosemary U. Adejoh, Andreas Jakoby, Sneha Mohanty, and Christian Schindelhauer. How Pinball Wizards Simulate a Turing Machine. In C. Aiswarya, Ruta Mehta, and Subhajit Roy, editors,45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025), volume 360 ofLeibniz International Proceedings in Informatics...

work page doi:10.4230/lipics.fsttcs.2025.4 2025

[2] [2]

What do reversible programs compute? In Martin Hofmann, editor, Foundations of Software Science and Computational Structures, pages 42–56, Berlin, Heidelberg, 2011

Holger Bock Axelsen and Robert Glück. What do reversible programs compute? In Martin Hofmann, editor, Foundations of Software Science and Computational Structures, pages 42–56, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg.doi:10.1007/978-3-642-19805-2_4

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

[3] [3]

Bastiaans and Tatiana Alieva

Martin J. Bastiaans and Tatiana Alieva. Classification of lossless first-order optical systems and the linear canonical transformation.Journal of the Optical Society of America. A, Optics, image science, and vision, 24 4:1053–62,

[4] [4]

URL:https://api.semanticscholar.org/CorpusID:23969043

[5] [5]

Semantics for a Turing-Complete Reversible Pro- gramming Language with Inductive Types

Kostia Chardonnet, Louis Lemonnier, and Benoît Valiron. Semantics for a Turing-Complete Reversible Pro- gramming Language with Inductive Types. In Jakob Rehof, editor,9th International Conference on Formal Structures for Computation and Deduction (FSCD 2024), volume 299 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 19:1–19:19, Dagstuh...

work page doi:10.4230/lipics.fscd.2024.19 2024

[6] [6]

Corcovilos

Theodore A. Corcovilos. Beyond the abcds: A better matrix method for geometric optics by using homogeneous coordinates.American Journal of Physics, 91(6):449–457, 06 2023.doi:10.1119/5.0083069

work page doi:10.1119/5.0083069 2023

[7] [7]

Universality in computable dynamical systems: old and new.Journal of Physics: Complexity, 6(3):035014, sep 2025.doi:10.1088/2632-072X/ae00b5

Ángel González-Prieto, Eva Miranda, and Daniel Peralta-Salas. Universality in computable dynamical systems: old and new.Journal of Physics: Complexity, 6(3):035014, sep 2025.doi:10.1088/2632-072X/ae00b5

work page doi:10.1088/2632-072x/ae00b5 2025

[8] [8]

Computer solutions of the traveling salesman problem,

Herwig Kogelnik. Imaging of optical modes—resonators with internal lenses.Bell System Technical Journal, 44(3):455–494, 1965. URL:https://doi.org/10.1002/j.1538-7305.1965.tb01672.x

work page doi:10.1002/j.1538-7305.1965.tb01672.x 1965

[9] [9]

Classical billiards can compute, 2025

Eva Miranda and Isaac Ramos. Classical billiards can compute, 2025. URL: https://arxiv.org/abs/2512. 19156,arXiv:2512.19156

Pith/arXiv arXiv 2025

[10] [10]

Unpredictability and undecidability in dynamical systems.Physical Review Letters, 64(20):2354, 1990

Cristopher Moore. Unpredictability and undecidability in dynamical systems.Physical Review Letters, 64(20):2354, 1990. URL:https://doi.org/10.1103/PhysRevLett.64.2354

work page doi:10.1103/physrevlett.64.2354 1990

[11] [11]

Reversible turing machines

Kenichi Morita. Reversible turing machines. InTheory of Reversible Computing, pages 103–156. Springer, 2017. URL:https://doi.org/10.1007/978-4-431-56606-9_5

work page doi:10.1007/978-4-431-56606-9_5 2017

[12] [12]

Brigham Young University, Department of Physics Provo, UT 84602, 2015

Justin Peatross and Michael Ware.Physics of light and optics. Brigham Young University, Department of Physics Provo, UT 84602, 2015

2015

[13] [13]

John H. Reif, J. Doug Tygar, and A. Yoshida. Computability and complexity of ray tracing.Discrete & Computational Geometry, 11:265–288, 1994. URL:https://doi.org/10.1007/BF02574009

work page doi:10.1007/bf02574009 1994

[14] [14]

Reversible computing

Tommaso Toffoli. Reversible computing. In Jaco de Bakker and Jan van Leeuwen, editors,Automata, Languages and Programming, pages 632–644, Berlin, Heidelberg, 1980. Springer Berlin Heidelberg. URL: https://doi. org/10.1007/3-540-10003-2_104

work page doi:10.1007/3-540-10003-2_104 1980

[15] [15]

Fundamentals of reversible flowchart languages

Tetsuo Yokoyama, Holger Bock Axelsen, and Robert Glück. Fundamentals of reversible flowchart languages. Theoretical Computer Science, 611:87–115, 2016.doi:10.1016/j.tcs.2015.07.046

work page doi:10.1016/j.tcs.2015.07.046 2016

[16] [16]

H. T. Yura and S. G. Hanson. Optical beam wave propagation through complex optical systems.J. Opt. Soc. Am. A, 4(10):1931–1948, Oct 1987. URL: https://opg.optica.org/josaa/abstract.cfm?URI= josaa-4-10-1931,doi:10.1364/JOSAA.4.001931. 12 The 2D Ray Tracing Problem using ABCD Lenses and MirrorsTECHNICALREPORT A Appendix: Combination of Thin Lenses for Gener...

work page doi:10.1364/josaa.4.001931 1931