@misc{gorard2022functorialperspectivemulticomputationalirreducibility, title={A Functorial Perspective on (Multi)computational Irreducibility}, author={Jonathan Gorard}, year={2022}, eprint={2301.04690}, archivePrefix={arXiv}, primaryClass={cs.CC}, url={https://arxiv.org/abs/2301.04690}, } @article{Rice1953Classes, author = {Rice, H. G.}, title = {Classes of recursively enumerable sets and their decision problems}, journal = {Transactions of the American Mathematical Society}, volume = {74}, number = {2}, pages = {358--366}, year = {1953}, month = {Mar}, doi = {10.1090/s0002-9947-1953-0053041-6}, url = {https://www.jstor.org/stable/1990888}, publisher = {American Mathematical Society} } @article{Landin1966Next700, author = {Landin, Peter J.}, title = {The Next 700 Programming Languages}, journal = {Communications of the ACM}, volume = {9}, number = {3}, pages = {157--166}, year = {1966}, doi = {10.1145/365230.365257} } @article{Felleisen1991ExpressivePower, author = {Felleisen, Matthias}, title = {On the Expressive Power of Programming Languages}, journal = {Science of Computer Programming}, volume = {17}, number = {1--3}, pages = {35--75}, year = {1991}, doi = {10.1016/0167-6423(91)90036-W} } @article{Dybvig2007MonadicDelimited, author = {Dybvig, R. Kent and Peyton Jones, Simon and Sabry, Amr}, title = {A Monadic Framework for Delimited Continuations}, journal = {Journal of Functional Programming}, volume = {17}, number = {6}, pages = {687--730}, year = {2007}, doi = {10.1017/S0956796807006259} } @article{Abramsky2000FullAbstractionPCF, author = {Abramsky, Samson and Jagadeesan, Radha and Malacaria, Pasquale}, title = {Full Abstraction for PCF}, journal = {Information and Computation}, volume = {163}, number = {2}, pages = {409--470}, year = {2000}, doi = {10.1006/inco.2000.2930} } @article{Milner1978Polymorphism, author = {Milner, Robin}, title = {A Theory of Type Polymorphism in Programming}, journal = {Journal of Computer and System Sciences}, volume = {17}, number = {3}, pages = {348--375}, year = {1978}, doi = {10.1016/0022-0000(78)90014-4} } @article{CoquandHuet1988CoC, author = {Coquand, Thierry and Huet, G{\'e}rard}, title = {The Calculus of Constructions}, journal = {Information and Computation}, volume = {76}, number = {2--3}, pages = {95--120}, year = {1988}, doi = {10.1016/0890-5401(88)90005-3} } @book{Pierce2002TAPL, author = {Pierce, Benjamin C.}, title = {Types and Programming Languages}, publisher = {The MIT Press}, address = {Cambridge, MA}, year = {2002}, isbn = {9780262162098} } @article{floridi2025conjecture, author = {Floridi, Luciano}, title = {A Conjecture on a Fundamental Trade-Off Between Certainty and Scope in Symbolic and Generative AI}, journal = {Philosophy \& Technology}, volume = {38}, pages = {93}, year = {2025}, doi = {10.1007/s13347-025-00927-z}, url = {https://doi.org/10.1007/s13347-025-00927-z} } @article{GilbertLynch2002CAP, author = {Gilbert, Seth and Lynch, Nancy}, title = {Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services}, journal = {SIGACT News}, volume = {33}, number = {2}, pages = {51--59}, year = {2002}, doi = {10.1145/564585.564601} } @article{SabryFelleisen1993CPS, author = {Sabry, Amr and Felleisen, Matthias}, title = {Reasoning about Programs in Continuation-Passing Style}, journal = {LISP and Symbolic Computation}, volume = {6}, number = {3--4}, pages = {289--360}, year = {1993}, doi = {10.1007/BF01019462} } @inproceedings{HoffmannHofmann2010PolyPotential, author = {Hoffmann, Jan and Hofmann, Martin}, title = {Amortized Resource Analysis with Polynomial Potential: A Static Inference of Polynomial Bounds for Functional Programs}, booktitle = {Programming Languages and Systems (ESOP 2010)}, series = {Lecture Notes in Computer Science}, volume = {6012}, pages = {287--306}, publisher = {Springer}, year = {2010}, doi = {10.1007/978-3-642-11957-6_16} } @inproceedings{HoffmannAehligHofmann2012RAML, author = {Hoffmann, Jan and Aehlig, Klaus and Hofmann, Martin}, title = {Resource Aware {ML}}, booktitle = {Computer Aided Verification (CAV 2012)}, series = {Lecture Notes in Computer Science}, volume = {7358}, pages = {781--786}, publisher = {Springer}, year = {2012}, doi = {10.1007/978-3-642-31424-7_64} } @article{DalLago2022ICCsurvey, author = {Dal Lago, Ugo}, title = {Implicit computation complexity in higher-order programming languages: A Survey in Memory of Martin Hofmann}, journal = {Mathematical Structures in Computer Science}, volume = {32}, number = {6}, pages = {760--776}, year = {2022}, doi = {10.1017/S0960129521000505} } @inproceedings{DannerLicataRamyaa2015CostSemantics, author = {Danner, Norman and Licata, Daniel R. and Ramyaa, Ramyaa}, title = {Denotational cost semantics for functional languages with inductive types}, booktitle = {Proceedings of the 20th {ACM} {SIGPLAN} International Conference on Functional Programming (ICFP 2015)}, pages = {140--151}, year = {2015}, doi = {10.1145/2784731.2784749} } @article{Thorup1998TreewidthCFG, author = {Thorup, Mikkel}, title = {All structured programs have small tree width and good register allocation}, journal = {Information and Computation}, year = {1998}, doi = {10.1006/inco.1997.2697} } @article{ConradoGoharshadyLam2023PathwidthCFG, author = {Conrado, Giovanna Kobus and Goharshady, Amir Kafshdar and Lam, Chun Kit}, title = {The Bounded Pathwidth of Control-Flow Graphs}, journal = {Proceedings of the {ACM} on Programming Languages}, volume = {7}, number = {OOPSLA2}, pages = {292--317}, year = {2023}, doi = {10.1145/3622807} } @article{GreenPetre1996CogDims, author = {Green, Thomas R. G. and Petre, Marian}, title = {Usability Analysis of Visual Programming Environments: A 'Cognitive Dimensions' Framework}, journal = {Journal of Visual Languages and Computing}, volume = {7}, number = {2}, pages = {131--174}, year = {1996}, doi = {10.1006/jvlc.1996.0009} } @inproceedings{CraryWeirich2000RBC, author = {Crary, Karl and Weirich, Stephanie}, title = {Resource Bound Certification}, booktitle = {Proceedings of the 27th {ACM} {SIGPLAN}-{SIGACT} Symposium on Principles of Programming Languages (POPL 2000)}, pages = {184--198}, year = {2000}, doi = {10.1145/325694.325716} } @article{Lawvere1969Diagonal, author = {Lawvere, F. William}, title = {Diagonal arguments and Cartesian closed categories}, journal = {Lecture Notes in Mathematics}, volume = {92}, pages = {134--145}, year = {1969}, publisher = {Springer}, doi = {10.1007/BFb0084323}, } @article{Kaminsky2025Geocomp, author = {Kaminsky, M. Benjamin}, title = {Geometric Computation: Twin Helices and the Algebra of Flow}, year = {2025}, month = {Sept}, doi = {10.5281/zenodo.17149853}, note = {Preprint DOI, pending acceptance} } @incollection{Howard1980FormulaeAsTypes, author = {Howard, William A.}, title = {The Formulae-as-Types Notion of Construction}, booktitle = {To H. B. Curry: Essays on Combinatory Logic, Lambda Calculus, and Formalism}, editor = {Seldin, J. P. and Hindley, J. R.}, publisher = {Academic Press}, address = {New York}, pages = {479--490}, year = {1980} } @article{Curry1942Inconsistency, author = {Curry, Haskell B.}, title = {The Inconsistency of Certain Formal Logics}, journal = {The Journal of Symbolic Logic}, volume = {7}, number = {3}, pages = {115--117}, year = {1942}, doi = {10.2307/2269292} } @misc{Shapiro2017CurryParadoxSEP, author = {Shapiro, Lionel}, title = {Curry's Paradox}, howpublished = {Stanford Encyclopedia of Philosophy}, year = {2017}, note = {Accessed 2026-03-03} } @article{Brady2013Idris, author = {Brady, Edwin}, title = {Idris, a general-purpose dependently typed programming language: Design and implementation}, journal = {Journal of Functional Programming}, volume = {23}, number = {5}, pages = {552--593}, year = {2013}, doi = {10.1017/S095679681300018X} } @inproceedings{Gimenez1995GuardedDefs, author = {Gim{\'e}nez, Eduardo}, title = {Codifying Guarded Definitions with Recursive Schemes}, booktitle = {Types for Proofs and Programs (TYPES 1994)}, series = {Lecture Notes in Computer Science}, volume = {996}, pages = {39--59}, publisher = {Springer}, year = {1995}, doi = {10.1007/3-540-60579-7_3} } @misc{Barras2006GuardCondition, author = {Barras, Bruno}, title = {The Guard Condition of Coq}, year = {2006}, note = {Slides/technical note} } @inproceedings{Coquand1986GirardParadox, author = {Coquand, Thierry}, title = {An Analysis of Girard's Paradox}, booktitle = {Proceedings of the Symposium on Logic in Computer Science (LICS)}, pages = {227--236}, publisher = {IEEE Computer Society Press}, year = {1986} } @inproceedings{Hurkens1995GirardSimplification, author = {Hurkens, Antonius J. C.}, title = {A Simplification of Girard's Paradox}, booktitle = {Typed Lambda Calculi and Applications (TLCA 1995)}, series = {Lecture Notes in Computer Science}, volume = {902}, pages = {266--278}, publisher = {Springer}, year = {1995}, doi = {10.1007/BFb0014058} } @inproceedings{Wells1994LICSUndecidable, author = {Wells, J. B.}, title = {Typability and Type-Checking in the Second-Order Lambda-Calculus are Equivalent and Undecidable}, booktitle = {Proceedings of the Ninth Annual Symposium on Logic in Computer Science (LICS '94)}, pages = {176--185}, publisher = {IEEE Computer Society}, year = {1994}, doi = {10.1109/LICS.1994.316068} } @article{Wells1999SystemFUndecidable, author = {Wells, J. B.}, title = {Typability and Type Checking in System F are Equivalent and Undecidable}, journal = {Annals of Pure and Applied Logic}, volume = {98}, number = {1--3}, pages = {111--156}, year = {1999}, doi = {10.1016/S0168-0072(98)00047-5} } @techreport{Bawden1977LispMachineProgress, author = {Bawden, Alan and Moon, David and Weinreb, Daniel}, title = {LISP Machine Progress Report}, institution = {MIT Artificial Intelligence Laboratory}, number = {AIM-444}, year = {1977}, note = {AI Memo 444} } @article{Greenblatt1980LispMachine, author = {Greenblatt, Richard D.}, title = {A {LISP} Machine}, journal = {SIGARCH Computer Architecture News}, volume = {8}, number = {3}, year = {1980}, doi = {10.1145/800083.802703} } @article{Moon1984GCLargeLispSystem, author = {Moon, David A.}, title = {Garbage Collection in a Large {Lisp} System}, journal = {Proceedings of the 1984 ACM Symposium on {LISP} and Functional Programming}, year = {1984}, note = {Describes GC techniques in the Symbolics 3600 environment} } @book{Weinreb1981LispMachineManual, author = {Weinreb, Daniel and Moon, David}, title = {The {Lisp} Machine Manual}, publisher = {MIT Artificial Intelligence Laboratory}, year = {1981} } @incollection{Steele2002EvolutionOfLisp, author = {Steele, Guy L.}, title = {The Evolution of {Lisp}}, booktitle = {History of Programming Languages, Volume II}, editor = {Bergin, Thomas J. and Gibson, Richard G.}, publisher = {Addison-Wesley}, year = {2002} } @article{PattersonDitzel1980RISC, author = {Patterson, David A. and Ditzel, David R.}, title = {The Case for the Reduced Instruction Set Computer}, journal = {ACM SIGARCH Computer Architecture News}, volume = {8}, number = {6}, pages = {25--33}, year = {1980} } @article{Futamura1999PartialEvalCompilerCompiler, author = {Futamura, Yoshihiko}, title = {Partial Evaluation of Computation Process---An Approach to a Compiler-Compiler}, journal = {Higher-Order and Symbolic Computation}, volume = {12}, number = {4}, pages = {381--391}, year = {1999}, doi = {10.1023/A:1010095604496} } @book{JonesGomardSestoft1993PEBook, author = {Jones, Neil D. and Gomard, Carsten K. and Sestoft, Peter}, title = {Partial Evaluation and Automatic Program Generation}, publisher = {Prentice Hall}, year = {1993}, isbn = {0130202495} } @article{Lawvere2006DiagonalArguments, author = {Lawvere, F. William}, title = {Diagonal Arguments and Cartesian Closed Categories}, journal = {Reprints in Theory and Applications of Categories}, number = {15}, pages = {1--13}, year = {2006}, note = {Reprint with author commentary} } @article{Landauer1961Irreversibility, author = {Landauer, Rolf}, title = {Irreversibility and Heat Generation in the Computing Process}, journal = {IBM Journal of Research and Development}, volume = {5}, number = {3}, pages = {183--191}, year = {1961}, doi = {10.1147/rd.53.0183} } @book{Tarski1936Truth, author = {Tarski, Alfred}, title = {The Concept of Truth in Formalized Languages}, publisher = {Oxford University Press}, year = {1936}, note = {Translated in \emph{Logic, Semantics, Metamathematics} (1956)} } @article{Huet1975Unification, author = {Huet, G{\'e}rard}, title = {A Unification Algorithm for Typed $\lambda$-Calculus}, journal = {Theoretical Computer Science}, volume = {1}, number = {1}, pages = {27--57}, year = {1975}, doi = {10.1016/0304-3975(75)90010-4} } @inproceedings{Huet1976Unification, author = {Huet, G{\'e}rard}, title = {Resolution d'\'equations dans les langages d'ordre $1,2,\dots,\omega$}, booktitle = {Proceedings of the 2nd International Conference on Automata, Languages and Programming (ICALP)}, year = {1976}, note = {Higher-order unification; semi-decidability and search behavior} } @article{WrightFelleisen1994TypeSoundness, author = {Wright, Andrew K. and Felleisen, Matthias}, title = {A Syntactic Approach to Type Soundness}, journal = {Information and Computation}, volume = {115}, number = {1}, pages = {38--94}, year = {1994} } @article{WeirichEtAl2017DependentHaskell, author = {Weirich, Stephanie and Voizard, Antoine and Azevedo de Amorim, Pedro Henrique and Eisenberg, Richard A.}, title = {A Specification for Dependent Types in Haskell}, journal = {Proceedings of the ACM on Programming Languages}, volume = {1}, number = {ICFP}, pages = {31:1--31:29}, year = {2017}, doi = {10.1145/3110275} } @article{Church1936, author = {Church, Alonzo}, title = {An Unsolvable Problem of Elementary Number Theory}, journal = {American Journal of Mathematics}, volume = {58}, number = {2}, pages = {345--363}, year = {1936}, doi = {10.2307/2371045} } @article{Turing1937, author = {Turing, Alan M.}, title = {On Computable Numbers, with an Application to the Entscheidungsproblem}, journal = {Proceedings of the London Mathematical Society}, volume = {s2-42}, number = {1}, pages = {230--265}, year = {1937}, doi = {10.1112/plms/s2-42.1.230} } @book{Barendregt1984Lambda, author = {Barendregt, Henk P.}, title = {The Lambda Calculus: Its Syntax and Semantics}, publisher = {North-Holland}, year = {1984}, edition = {Revised}, isbn = {9780444875082} } @incollection{Tait1967SN, author = {Tait, William W.}, title = {Intensional Interpretations of Functionals of Finite Type I}, booktitle = {The Journal of Symbolic Logic}, year = {1967}, note = {Classic normalization proof technique (Tait's method)} } @book{Girard1972SN, author = {Girard, Jean-Yves}, title = {Interpr\'etation Fonctionnelle et \'Elimination des Coupures de l'Arithm\'etique d'Ordre Sup\'erieur}, publisher = {PhD thesis, Universit\'e Paris VII}, year = {1972}, note = {Foundational work on strong normalization for typed lambda calculi} } @book{Perlis1982Epigrams, author = {Perlis, Alan J.}, title = {Epigrams on Programming}, publisher = {ACM Press}, year = {1982}, note = {Often circulated as ``Epigrams in Programming''; includes the ``Turing tarpit'' epigram} } @article{Blum1967ComplexityAxioms, author = {Blum, Manuel}, title = {A Machine-Independent Theory of the Complexity of Recursive Functions}, journal = {Journal of the ACM}, volume = {14}, number = {2}, pages = {322--336}, year = {1967}, doi = {10.1145/321386.321395} } @article{TroyerWiese2005SignProblem, author = {Troyer, Matthias and Wiese, Uwe-Jens}, title = {Computational Complexity and Fundamental Limitations to Fermionic Quantum Monte Carlo Simulations}, journal = {Physical Review Letters}, volume = {94}, number = {17}, pages = {170201}, year = {2005}, doi = {10.1103/PhysRevLett.94.170201} } @article{SchaeferSommerVirotta2011CriticalSlowingDown, author = {Schaefer, Stefan and Sommer, Rainer and Virotta, Francesco}, title = {Critical slowing down and error analysis in lattice {QCD} simulations}, journal = {Nuclear Physics B}, volume = {845}, number = {1}, pages = {93--119}, year = {2011}, doi = {10.1016/j.nuclphysb.2010.11.020} } @article{ArkaniHamedTrnka2014Amplituhedron, author = {Arkani-Hamed, Nima and Trnka, Jaroslav}, title = {The Amplituhedron}, journal = {Journal of High Energy Physics}, volume = {2014}, number = {10}, pages = {030}, year = {2014}, doi = {10.1007/JHEP10(2014)030}, note = {arXiv:1312.2007} } @article{CourantFriedrichsLewy1928, author = {Courant, Richard and Friedrichs, Kurt and Lewy, Hans}, title = {\"Uber die partiellen Differenzengleichungen der mathematischen Physik}, journal = {Mathematische Annalen}, volume = {100}, pages = {32--74}, year = {1928}, doi = {10.1007/BF01448839} } @book{HairerLubichWanner2006GNI, author = {Hairer, Ernst and Lubich, Christian and Wanner, Gerhard}, title = {Geometric Numerical Integration: Structure-Preserving Algorithms for Ordinary Differential Equations}, edition = {2}, publisher = {Springer}, year = {2006}, doi = {10.1007/3-540-30666-8} } @book{Baxter1982ExactlySolved, author = {Baxter, Rodney J.}, title = {Exactly Solved Models in Statistical Mechanics}, publisher = {Academic Press}, year = {1982} } @book{KorepinBogoliubovIzergin1993QISM, author = {Korepin, V. E. and Bogoliubov, N. M. and Izergin, A. G.}, title = {Quantum Inverse Scattering Method and Correlation Functions}, publisher = {Cambridge University Press}, year = {1993} } @article{CubittPerezGarciaWolf2015SpectralGap, author = {Cubitt, Toby S. and P{\'e}rez-Garc{\'\i}a, David and Wolf, Michael M.}, title = {Undecidability of the spectral gap}, journal = {Nature}, volume = {528}, pages = {207--211}, year = {2015}, doi = {10.1038/nature16059} } @book{Rogers1967, author = {Rogers, Hartley}, title = {Theory of Recursive Functions and Effective Computability}, publisher = {McGraw--Hill}, year = {1967} } @book{Soare1987, author = {Soare, Robert I.}, title = {Recursively Enumerable Sets and Degrees}, publisher = {Springer}, year = {1987}, doi = {10.1007/978-3-642-61644-0} } @book{Kleene1952, author = {Kleene, Stephen C.}, title = {Introduction to Metamathematics}, publisher = {North-Holland}, year = {1952} } @article{CoeckeFritzSpekkens2016ResourceTheory, author = {Coecke, Bob and Fritz, Tobias and Spekkens, Robert W.}, title = {A Mathematical Theory of Resources}, journal = {Information and Computation}, volume = {250}, pages = {59--86}, year = {2016}, doi = {10.1016/j.ic.2016.02.008} } @incollection{AbramskyCoecke2004CategoricalQM, author = {Abramsky, Samson and Coecke, Bob}, title = {A Categorical Semantics of Quantum Protocols}, booktitle = {Proceedings of the 19th Annual IEEE Symposium on Logic in Computer Science}, publisher = {IEEE}, year = {2004}, pages = {415--425}, doi = {10.1109/LICS.2004.1319636} } @book{Kogge1991SymbolicComputers, author = {Kogge, Peter M.}, title = {The Architecture of Symbolic Computers}, publisher = {McGraw-Hill}, address = {New York}, year = {1991}, isbn = {0070355967}, note = {Also listed in some catalogs as a 1990 publication/printing.} } @book{NielsenChuang2010, author = {Nielsen, Michael A. and Chuang, Isaac L.}, title = {Quantum Computation and Quantum Information}, edition = {10th Anniversary}, publisher = {Cambridge University Press}, year = {2010} } @article{KochenSpecker1967, author = {Kochen, Simon and Specker, Ernst P.}, title = {The Problem of Hidden Variables in Quantum Mechanics}, journal = {Journal of Mathematics and Mechanics}, volume = {17}, number = {1}, pages = {59--87}, year = {1967} } @article{AbramskyBrandenburger2011Contextuality, author = {Abramsky, Samson and Brandenburger, Adam}, title = {The Sheaf-Theoretic Structure of Non-Locality and Contextuality}, journal = {New Journal of Physics}, volume = {13}, pages = {113036}, year = {2011}, doi = {10.1088/1367-2630/13/11/113036} } @inproceedings{Gottesman1998HeisenbergRepresentation, author = {Gottesman, Daniel}, title = {The Heisenberg Representation of Quantum Computers}, booktitle = {Group22: Proceedings of the XXII International Colloquium on Group Theoretical Methods in Physics}, year = {1998}, note = {arXiv:quant-ph/9807006} }