Computation, Automata, Languages
Last update: 07 Jul 2025 09:52First version: 11 March 2001
Computers aren't made of matter.Ideal, theoretical computers are rather mathematical objects: they are, equivalently, algorithms, or effective procedures, or abstract automata, or functions which can be specified recursively, or formal languages.
--- Greg Egan, Permutation City
Things to learn more about: Classifications of machines and languages (beyond the classical, four-level Chomsky hierarchy). Hierarchies of computational power. Abstract-algebraic treatment of automata. Effects of making automata stochastic. Techniques for proving equivalence of automata; of minimizing automata. Bisimulation. Techniques for inferring automata or grammars from their languages, especially when generation is stochastic. Non-finite-state transducers. Stochastic context-free grammars and their connections with branching processes. "Logics of time and computation".
Computational complexity: not "what can be computed, at all?", but "given that something can be computed, what resources does the computation require?"
Analog computation. What forms are structurally stable? Other forms of unconventional computation. DNA computation doesn't interest me very much, because that's just another kind of hardware, and slow, big and noisy at that. But quantum computation is very interesting, because it can do something new. So, possibly, is computation in dynamical systems.
If you do insist on making a computer out of matter, what limits does that impose on the computation? Conversely: when do physical systems compute?
- See also:
- AI
- Algorithmic Information Theory
- Biological computers
- Cellular Automata
- Complexity
- Complexity Measures
- Computational Mechanics (for exploring the intrinsic computation of physical processes)
- Computers
- Dynamics
- Gödel's Theorem
- Grammatical Inference
- Math I Ought to Learn
- Machine Learning, Statistical Inference and Induction
- Parallel and Distributed Computing
- Physics of Computation and Information
- Programming
- Quantum Mechanics (for quantum computers)
- Symbolic Dynamics
- Transducers
- Visual Grammars
- Recommended, big picture:
- Gary William Flake, The Computational Beauty of Nature: Computer Explorations of Fractals, Chaos, Complex Systems, and Adaptation [Review: A Garden of Bright Images]
- Harry R. Lewis and Christos H. Papadimitriou, Elements of the Theory of Computation [Very nice textbook; the proofs, for instance, are comprehensible and correct, which is not always the case with the competition.]
- Marvin Minsky, Computation: Finite and Infinite Machines
- Cristopher Moore and Stephan Mertens, The Nature of Computation [Cris and Stephan were kind enough to let me read this in manuscript; it's magnificent. Review: Intellects Vast and Warm and Sympathetic]
- Recommended, close-ups:
- Michael Arbib, Brains, Machines and Mathematics
- George S. Boolos and Richard C. Jeffrey, Computability and Logic
- Taylor L. Booth, Sequential Machines and Automata Theory [Fascinating material on probabilistic machines which has dropped out of later texts]
- J. Richard Büchi, Finite Automata, Their Algebras and Grammars: Towards a Theory of Formal Expressions
- J. H. Conway, Regular Algebra and Finite Machines
- Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics
- Joseph Y. Halpern, "Beyond Nash Equilibrium: Solution Concepts for the 21st Century", arxiv:0806.2139
- Eric Mjolsness, "Stochastic Process Semantics for Dynamical Grammar Syntax: An Overview", cs.AI/0511073
- Cristopher Moore, "Recursion Theory on the Reals and Continuous-Time Computation," Theoretical Computer Science, 162 (1999): 23--44
- E. Vidal, F. Thollard, C. de la Higuera, F. Casacuberta and R. C. Carrasco, "Probabilistic Finte-State Machines"
- Recommended, close-ups, historical interest:
- Noam Chomsky, "Three Models for the Description of Language", IRE Transactions on Information Theory 2 (1956): 113--124
- J. Hartmanis and R. E. Stearns, Algebraic Structure Theory of Sequential Machines
- Anil Nerode, "Linear Automaton Transformations", Proceedings of the American Mathematical Society 9 (1958): 541--544
- George N. Raney, "Sequential Functions", Journal of the ACM 5 (1958): 177--180
- Claude Shannon and John McCarthy (eds.). Automata Studies [Think of this as a collection of many of the ways computer science could have gone, including some of the ways it did, e.g., Kleene's paper introducing regular expressions and finite automata]
- To read, big picture:
- James Anderson, Automata Theory with Modern Applications
- John Carroll and Darrell Long, Theory of Finite Automata: with an Introduction to Formal Languages [Good chapter on finite-state transducers; dunno about the rest yet]
- György E. Révész, Introduction to Formal Languages
- Hartley Rogers Jr., Theory of Recursive Functions and Effective Computability
- Arto Salomaa, Computation and Automata
- To read, history and philosophy:
- Jeffrey M. Binder, Language and the Rise of the Algorithm [Learned of from this review]
- Paul Bohan Broderick, "On Communication and Computation", Minds and Machines 14 (2004): 1--19 ["The most famous models of computation and communication, Turing Machines and (Shannon-style) information sources, are considered. The most significant difference lies in the types of state-transitions allowed in each sort of model. This difference does not correspond to the difference that would be expected after considering the ordinary usage of these terms."]
- Giuseppe Longo, "The difference between Clocks and Turing Machines" [PDF via Dr. Longo]
- Marcin Milkowski, Explaining The Computational Mind [For the material on what it means to explain phenomena computationally]
- Jan von Plato, The Great Formal Machinery Works: Theories of Deduction and Computation at the Origins of the Digital Age
- To read, historical interest:
- M. A. Arbib, "Automata Theory and Control Theory --- A Rapproachement", Automatica 3 (1966): 161--189
- National Research Council (USA), Probability and Algorithms [1992, so now of merely historical interest, but I've been meaning to read it since the mid-1990s...]
- To read, connections of automata and languages to abstract algebra and category theory:
- Jiri Adamek and Vera Trnkova, Automata and Algebras in Categories
- M. A. Arbib, Algebraic Theory of Machines, Langauges, and Semigroups
- Joseph A. Goguen and Grant Malcolm, Algebraic Semantics of Imperative Programs
- R. F. Walters, Categories and Computer Science
- To read, probabilistic automata and algorithms (which one could handle as just another input, but that's not illuminating):
- Falk Bartels, Ana Sokolova and Erik de Vink, "A hierarchy of probabilistic system types", Theoretical Computer Science 327 (2004): 3--22
- Asa Ben-Hur, Alexander Roitershtein and Hava T. Siegelmann, "Probabilistic analog automata", Theoretical Computer Science 320 (2004): 449--464
- E.-E. Doberkat, Stochastic Automata: Stability, Nondeterminism and Prediction
- A. A. Lorents, Stochastic automata: constructive theory
- Rajeev Motwani, Randomized Algorithms
- To read, particle- or collision- based computing:
- Andrew Adamatzky (ed.), Collison-Based Computing
- Tanya Sienko, Andrew Adamatzky and Nicholas Rambidi (eds.), Molecular Computing
- To read, analog computing and computing in dynamical systems (some overlap with other topics):
- Manuel Lameiras Campagnolo, Cristopher Moore, and José Félix Costa, "Iteration, Inequailities, and Differentiability in Analog Computers" [On-line]
- Manuel Lameiras Campagnolo and Cristopher Moore, "Upper and lower bounds on continuous-time computation" [On-line]
- Jean-Charles Delvenne, Petr Kurka and Vincent Blondel, "Computational Universality in Symbolic Dynamical Systems", cs.CC/0404021
- Yuzuru Sato, Logic and Computation in Dynamical Systems [Ph.D. thesis, University of Tokyo, 2000. I remember Yuzuru explaining a lot of this when we shared an office...]
- To read, synchronizing and/or re-setting words for automata, especially finite automata (related to a particular slow-moving project):
- Jorg Olschewski, Michael Ummels, "The Complexity of Finding Reset Words in Finite Automata", arxiv:1004.3246
- To read, comparisons and especially distances between languages and automata (again, related to particular projects):
- Edward P. Stabler and Edward L. Keenan, "Structural similarity within and among languages," Theoretical Computer Science 293 (2003): 345--363
- To read, not yet or not otherwise classified:
- Udi Boker and Nachum Dershowitz, "Comparing Computational Power", cs.LO/0510069
- C. S. Calude, J. Casti, and M. J. Dinneen, eds., Unconventional Models of Computation
- Alan John Dix, Formal Methods for Interactive Systems
- David Doty and Jared Nichols, "Pushdown Dimension", cs.IT/0504047
- Robert Goldblatt, Logics of Time and Computation
- Gramss, Bornholdt, Gross, Mitchell and Pellizzari (eds.), Non-Standard Computation: Molecular Computation --- Cellular Automata --- Evolutionary Algorithms --- Quantum Computers
- Thomas A. Henzinger, Rupak Majumdar and Jean-Francois Raskin, "A Classification of Symbolic Transition Systems," cs.LO/0101013
- Marcus Hutter, "The Fastest and Shortest Algorithm for All Well-Defined Problems," cs.CC/0206022
- Giorgi Japaridze, "Computatbility Logic: A Formal Theory of Interaction", cs.LO/0404024
- Marc Mezard and Andrea Montanari, Information, Physics, and Computation
- David Sankoff, "Branching Processes with Terminal Types: Application to Context-Free Grammars", Journal of Applied Probability 8 (1971): 233--240 [JSTOR]
- Géraud Sénizergues, "Complete Formal Systems for Equivalence Problems," Theoretical Computer Science 231 (2000): 309--334
- J. V. Tucker and J. I. Zucker
- "Abstract Computability, Algebraic Specification and Initiality," cs.LO/0109001
- "Abstract versus Concrete Computation on Metric Partial Algebras," cs.LO/0108007
- Antii Valmari, "Fast brief practical DFA minimization", Information Processing Letters 112 (2012): 213--217
- Wlodek Zadrozny, "Minimum Description Length and Compositionality," cs.CL/0001002
