Computation, Automata, Languages

27 Aug 2023 16:27

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? Conversely: when do physical systems compute?

See also: AI; Algorithmic Information Theory; 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