Geometry of Program Synthesis
arXiv:2103.16080
Abstract
We re-evaluate universal computation based on the synthesis of Turing machines. This leads to a view of programs as singularities of analytic varieties or, equivalently, as phases of the Bayesian posterior of a synthesis problem. This new point of view reveals unexplored directions of research in program synthesis, of which neural networks are a subset, for example in relation to phase transitions, complexity and generalisation. We also lay the empirical foundations for these new directions by reporting on our implementation in code of some simple experiments.
16 pages, 7 figures
References in corpus (7)
- A Widely Applicable Bayesian Information Criterion
- Stochastic Gradient Hamiltonian Monte Carlo
- TerpreT: A Probabilistic Programming Language for Program Induction
- An RNA-Based Theory of Natural Universal Computation
- Towards common-sense reasoning via conditional simulation: legacies of Turing in Artificial Intelligence
- Deep Learning is Singular, and That's Good
- Derivatives of Turing machines in Linear Logic