Computation, Automata, Languages

10 Apr 2009 17:40

---

Computers aren't made of matter.
--- Greg Egan, Permutation City

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.

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".

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.

Complexity classes --- in space (memory), time, other resources? Analog equivalents. "Phase transitions" between complexity classes, and the analogy to physical phase transitions.

If you do insist on making a computer out of matter, what limits does that impose on the computation?

See also: AI; Biological computers; Cellular Automata; Computational Mechanics (for exploring the intrinsic computation of physical processes); Computers; Dynamics; Gödel's Theorem (a consequence of the existence of uncomputable functions); 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

Recommended:
• 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]
• Gary William Flake, The Computational Beauty of Nature: Computer Explorations of Fractals, Chaos, Complex Systems, and Adaptation [Review: A Garden of Bright Images]
• Marco Giunti, Computation, Dynamics, and Cognition [The first two-thirds has a nice treatment of abstract computers as discrete dynamical systems, including some apparently new results about non-Turing computation; the stuff about cognition and scientific explanation seems, by contrast, strained and tacked-on. Does not acknowledge that analog computation is computation!]
• J. Hartmanis and R. E. Stearns, Algebraic Structure Theory of Sequential Machines
• 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.]
• 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
• Matthias Scheutz, "Computational versus Causal Complexity", Minds and Machines 11 (2001): 543--566 [Abstract: "The main claim of this paper is that notions of implementation based on an isomorphic correspondence between physical and computational states are not tenable. Rather, `implementation' has to be based on the notion of `bisimulation' in order to be able to block unwanted implementation results and incorporate intuitions from computational practice. A formal definition of implementation is suggested, which satisfies theoretical and practical requirements and may also be used to make the functionalist notion of `physical realization' precise. The upshot of this new definition of implementation is that implementation cannot distinguish isomorphic bisimilar from non-isomporphic bisimilar systems anymore, thus driving a wedge between the notions of causal and computational complexity. While computationalism does not seem to be affected by this result, the consequences for functionalism are not clear and need further investigations." PDF]
• Claude E. 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]
• E. Vidal, F. Thollard, C. de la Higuera, F. Casacuberta and R. C. Carrasco, "Probabilistic Finte-State Machines"
  1. IEEE Transactions on Pattern Analysis and Machine Intelligence 27 (2005): 1013--1025
  2. IEEE Transactions on Pattern Analysis and Machine Intelligence 27 (2005): 1026--1039
• Richard Zippel, "On Satisfiability," e-print available from Dr. Zippel's homepage [on connections between 3-SAT and Monte Carlo methods]

To read:
• Andrew Adamatzky (ed.), Collison-Based Computing
• Jiri Adamek and Vera Trnkova, Automata and Algebras in Categories
• Arbib (ed.), Algebraic Theory of Machines, Langauges, and Semigroups
• G. Ausiello, Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties
• Falk Bartels, Ana Sokolova and Erik de Vink, "A hierarchy of probabilistic system types", Theoretical Computer Science 327 (2004): 3--22
• W. Barthel, A. K. Hartmann, M. Leone, F. Ricci-Tersenghi, M. Weigt, and R. Zecchina, "Generating hard and solvable satisfiability problems: A statistical mechanics approach," cond-mat/0111153
• Demian Battaglia, Michal Kolár and Riccardo Zecchina, "Minimizing energy below the glass thresholds", Physical Review E 70 (2004): 036107 = cond-mat/0402529 [How K-SAT is like a glass]
• Asa Ben-Hur, Alexander Roitershtein and Hava T. Siegelmann, "Probabilistic analog automata", Theoretical Computer Science 320 (2004): 449--464
• Udi Boker and Nachum Dershowitz, "Comparing Computational Power", cs.LO/0510069
• 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."]
• C. S. Calude, J. Casti, and M. J. Dinneen, eds., Unconventional Models of Computation
• 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]
• 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]
• Simona Cocco and Remi Monasson
  • "Exponentially hard problems are sometimes polynomial, a large deviation analysis of search algorithms for the random Satisfiability problem, and its application to stop-and-restart resolutions," cond-mat/0203012
  • "Trajectories in phase diagrams, growth processes and computational complexity: how search algorithms solve the 3-Satisfiability problem," cond-mat/0009410
• J. H. Conway, Regular Algebra and Finite Machines
• Jean-Charles Delvenne, Petr Kurka and Vincent Blondel, "Computational Universality in Symbolic Dynamical Systems", cs.CC/0404021
• Alan John Dix, Formal Methods for Interactive Systems
• David Doty and Jared Nichols, "Pushdown Dimension", cs.IT/0504047
• Joseph A. Goguen and Grant Malcolm, Algebraic Semantics of Imperative Programs
• Robert Goldblatt, Logics of Time and Computation
• Odd Goldreich, Computational Complexity: A Conceptual Perspective [blurb]
• Gramss, Bornholdt, Gross, Mitchell and Pellizzari (eds.), Non-Standard Computation: Molecular Computation --- Cellular Automata --- Evolutionary Algorithms --- Quantum Computers
• David Harel
  • The Science of Computing: Exploring the Nature and Power of Algorithms
  • Computers Ltd: What They Really Can't Do
• Thomas A. Henzinger, Rupak Majumdar and Jean-Francois Raskin, "A Classification of Symbolic Transition Systems," cs.LO/0101013
• Dorit Hochbaum, Approximation Algorithms for NP-Hard Problems
• 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
• Johannes Kobler and Rainer Schuler, "Average-case intractability vs. worst-case intractability", Information and Computation 190 (2004): 1--17
• O. C. Martin, R. Monasson and R. Zecchina, "Statistical mechanics methods and phase transitions in optimization problems," cond-mat/0104428
• Andrea Montanari and Riccardo Zecchina, "Boosting search by rare events," cond-mat/0112142
• Rajeev Motwani, Randomized Algorithms
• Leszek Plaskota, Noisy Information and Computational Complexity
• Proceedings of the Symposium on Mathematical Tehory of Automata, New York, April 1962 [Some wonderful-looking old papers on algebraic approaches to automata theory]
• György E. Révész, Introduction to Formal Languages
• National Research Council (USA), Probability and Algorithms [online]
• Wolfgang Reisig, Petri Nets: An Introduction
• Hartley Rogers Jr., Theory of Recursive Functions and Effective Computability
• R. Y. Rubinstein, "A Stochastic Minimum Cross-Entropy Method for Combinatorial Optimization and Rare-event Estimation", Methodology and Computing in Applied Probability 7 (2005): 5--50 [This suggests connections between information theory and stochastic approximation methods for NP-hard problems, including NP-complete problems. This would be very cool, so I need to do more than read the abstract --- at some point...]
• Arto Salomaa, Computation and Automata
• David Sankoff, "Branching Processes with Terminal Types: Application to Context-Free Grammars", Journal of Applied Probability 8 (1971): 233--240 [JSTOR]
• Yuzuru Sato, Logic and Computation in Dynamical Systems [Ph.D. thesis, University of Tokyo, 2000]
• Géraud Sénizergues, "Complete Formal Systems for Equivalence Problems," Theoretical Computer Science 231 (2000): 309--334
• Tanya Sienko, Andrew Adamatzky and Nicholas Rambidi (eds.), Molecular Computing
• Edward P. Stabler and Edward L. Keenan, "Structural similarity within and among languages," Theoretical Computer Science 293 (2003): 345--363
• Wojciech Szpankowski, Average Case Analysis of Algorithms on Sequences [Preprint version]
• J. F. Traud and H. Wozniakowski, "Persepctives on Information-Based Complexity," Bulletin of the American Mathematical Society 26 (1992): 29--52 = math.NA/9201269
• 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
• Vijay V. Vazirani, Approximation Algorithms
• R. F. Walters, Categories and Computer Science
• Herbert S. Wilf, Algorithms and Complexity [online]
• Wlodek Zadrozny, "Minimum Description Length and Compositionality," cs.CL/0001002