Geometry of Program Synthesis
Authors: James Clift
Daniel Murfet
James Wallbridge
Venue:  (2021)
Keywords: Program Synthesis
Singular Learning Theory
Bayesian Inference
MCMC

Abstract: We present a new perspective on program synthesis in which programs may be identified with singularities of analytic functions. As an example, Turing machines are synthesised from input-output examples by propagating uncertainty through a smooth relaxation of a universal Turing machine.  The posterior distribution over weights is approximated using Markov chain Monte Carlo and bounds on the generalisation error of these models is estimated using the real log canonical threshold, a geometric invariant from singular learning theory.  


Under review as a conference paper at ICLR 2021
GEOMETRY OF PROGRAM SYNTHESIS
Anonymous authors
Paper under double-blind review
ABSTRACT
We present new perspective on program synthesis in which programs may be identified with singularities of analytic functions. As example, Turing ma- chines are synthesised from input-output examples by propagating uncertainty through smooth relaxation of a universal Turing machine. The posterior distri- bution over weights is approximated using Markov chain Monte Carlo and bounds on the generalisation error of these models is estimated using the real log canoni- cal threshold, a geometric invariant from singular learning theory.
INTRODUCTION
The idea of program synthesis dates back to the birth of modern computation itself (Turing 1948) and is recognised as one of the most important open problems in computer science (Gulwani al. 2017). However, there appear to be serious obstacles to synthesising programs by gradient descent scale (Neelakantan et al.) 2016 Kaiser Sutskever 2016 Bunel al. 2016 Gaunt al. 2016 Evans & Grefenstette/ 2018 Chen et al. 2018) and these problems suggest that it would be appro- priate to make a fundamental study of the geometry of loss surfaces program synthesis, since this geometry determines the learning process. To that end, in this paper we explain new point of view on program synthesis using the singular learning theory of Watanabe (2009) and the smooth relaxation of Turing machines from Clift & Murfet (2018).
In broad strokes this new geometric point of view on program synthesis says:
Programs to be synthesised are singularities of analytic functions. U C Rd is open and K U + R is analytic, then z U is critical point of K if VK (x) and singularity of the function K it is a critical point where K (x) =
The Kolmogorov complexity of a program is related to geometric invariant of the associated singularity called the Real Log Canonical Threshold (RLCT). This invariant controls both the generalisation eтror and the learning process, and is therefore an appro- priate measure of "complexity" continuous program synthesis. See Section
The geometry has concrete practical implications. For example, a MCMC-based ap- proach to program synthesis will find, with high probability, solution that is of low com- plexity (if it finds solution at all). We sketch a novel point of view on the problem of "bad local minima" (Gaunt et 2016 based on these ideas. See Section 4
We demonstrate all of these principles in experiments with toy examples of synthesis problems.
Program synthesis as inference. We use Turing machines, but mutatis mutandis everything applies other programming languages. Let T be Turing machine with tape alphabet Σ and set of states Q and assume that on any input z E Σ* the machine eventually halts with output T(x) E Σ*. Then to the machine we may associate the set ((x, ((x)))=EX> C E' x Σ.. Program synthesis the study of the inverse problem: given subset of E' x D would like to determine (if possible) Turing machine which computes the given outputs on the given inputs.
If we presume given probability distribution q(x) on Σ* then can formulate this as problem of statistical inference: given a probability distribution g(z, y) on Σ' x Σ" determine the most likely machine producing the observed distribution q(2, y) (z))))((z) If we fix universal Turing machine 24 then Turing machines can be parametrised by codes w E Wroode with U(z, w) = T(x) for all x E Σ". We let p(y|e, w) denote the probability of l/ w) (which is either zero one)

---

Under review as a conference paper at ICLR 2021
so that solutions to the synthesis problem in bijection with the zeros of the Kullback- divergence between the true distribution and the model
[] (())))(())) log g(ylz)
K(w)=
dady.
(I)
plylæ, a, w)
So far this is just a trivial rephrasing of the combinatorial optimisation problem of finding a Turing machine T with (xx) = for all (z, y) with q(z,, v) > 0.
Smooth relaxation. One approach is to seek a smooth relaxation of the synthesis problem consisting of an analytic manifold W 2 Weode and an extension of K' to an analytic function K WW - R so that we can search for the zeros of K using gradient descent. Perhaps the most natural way to construct such smooth relaxation is to take W to be space of probability distributions over Weode and prescribe a model p(y ar, w) for propagating uncertainty about codes to uncertainty about outputs (Gaunt al. 2016: Evans & Grefenstette 2018). The particular model we choose is based on the semantics of linear logic (Clift & Murfet 2018). Supposing that such a smooth relaxation has been chosen together with a prior ((w) over W, smooth program synthesis becomes the study of the statistical learning theory of the triple (p, 9, 9.)
There are perhaps two primary reasons consider the smooth relaxation. Firstly, one might hope that stochastic gradient descent or techniques like Markov chain Monte Carlo will be effective means of solving the original combinatorial optimisation problem. This not a new idea (Gulwani al., 2017 (6) but so far its effectiveness for large programs has not been proven. Independently, one might hope to find powerful new mathematical ideas that apply to the relaxed problem and shed light on the nature of program synthesis. This is the purpose of the present paper.
Singular learning theory. We denote by Wa = {w E W| ((w) 0} so that
Wo n code C Wo W
(2)
where Woode is the discrete set of solutions to the original synthesis problem. We refer to these the classical solutions. As the vanishing locus of an analytic function, Wo is analytic space over T.. (Hironaka] 1964] 10.1), (Griffith & Harris 1978) and it is interesting to study the geometry of this space near the classical solutions. Since K is Kullback-Leibler divergence it is non-negative and so it not only vanishes on Wo but VK also vanishes, hence every point of Wo is singular point.
Beyond this the geometry of Wo depends on the particular model p(y|ær, w)) that has been chosen, but some aspects are universal: the nature of program synthesis means that typically Wo is an extended object (i.e. it contains points other than the classical solutions) and the Hessian matrix of second order partial derivatives of K at a classical solution is not invertible that is, the classical solutions are degenerate critical points of K. This means that singularity theory is the appropriate branch of mathematics for studying the geometry of Wo near a classical solution. It also means that the Fisher information matrix
I(w)s = //
i Sw;
[og p(u|,, w)] ow,y [log plyle
is degenerate at a classical solution, so that the appropriate branch of statistical learning theory is singular learning theory (Watanabel [007] 2009). For an introduction to singular learning theory in the context of deep learning see (Murfet et al. (2020).
Broadly speaking the contribution of this paper is realise program synthesis within the frame- work of singular learning theory, at both a theoretical and an experimental level. In more detail the contents of the paper are:
We define staged pseudo- UTM (Appendix B which is well-suited to experiments with the ideas discussed above. Propagating uncertainty about the code through this UTM using the ideas of (Clift & Murfet 2018) defines triple (p. g. :p) associated to synthesis problem. This formally embeds program synthesis within singular learning theory.
We realise this embedding in code by providing an implementation in Py Torch of this prop- agation of uncertainty through UTM. Using the No-U-Turn variant of MCMC (Hoffman) & Gelman 2014) we can approximate the Bayesian posterior of any program synthesis problem (of course in practice are limited by computational constraints in doing so).
2

---

Under review as a conference paper at ICLR 2021
We explain how the real log canonical threshold (a geometric invariant) is related to Kol- mogorov complexity (Section 3
We give a simple example (Appendix ( in which Wo contains the set of classical solutions as a proper subset and every point of Wo is a degenerate critical point of K.
For two simple synthesis problems detectA and parity tyCheck we demonstrate all of the above, using MCMC to approximate the Bayesian posterior and theorems from Watan- abe| (2013) to estimate the RLCT (Section We discuss how Wo is an extended object and how the RLCT relates to the local dimension of Wo near a classical solution.
RELATED WORK
The idea of synthesising Turing machines can be traced back to the work of Solomonoff on inductive inference (Solomonoff. 1964). A more explicit form of the problem was given in [Biermann] (1972) who proposed an algorithmic method. Machine learning based approaches appear in Schmidhuber (1997) and Hutter (2004), which pay particular attention model complexity, and Gaunt et al. 2016) and Freer et al. (2014), the latter using the notion of "universal probabilistic Turing machine" (De Leeuw al.] 1956). A different probabilistic extension of a universal Turing machine was introduced in Clift & Murfet (2018) via linear logic. Studies of the singular geometry of learning models go back to Amari et al. (2003) and notably, the extensive work of Watanabe 2009). 2009).
2 TURING MACHINE SYNTHESIS AS SINGULAR LEARNING
All known approaches to program synthesis can be formulated in terms of a singular learning prob- lem. Singular learning theory the extension of statistical learning theory to account for the fact that the set of learned parameters Wo has the structure of an analytic space opposed to an analytic manifold (Watanabe) 2007 2009p. is organised around triples (p, q, (p) consisting of a class of models {ply|æ, w)
W a true distribution (tylzr) and prior oo W.
In our approach we fix a Universal Turing Machine (UTM), denoted U, with a description tape (which specifies the code of the Turing machine to be executed), a work tape (simulating the tape of that Turing machine during its operation) and a state tape (simulating the state of that Turing machine). The general statistical learning problem that given some initial string x on the work tape, predict the state of the simulated machine and the contents of the work tape after some specified number of steps (Clift & Murfet 2018 $7.1). For simplicity, in this paper we consider models that only predict the final state; the necessary modifica- tions in the general case are routine. We also assume that W parametrises Turing machines whose tape alphabet Σ and set of states Q have been encoded by individual symbols in the tape alphabet of U. Hence 2/ is actually what we call a pseudo- Prr (see Appendix F Again, treating the general case is routine and for the present purposes only introduces uninteresting complexity.
be formulated using 2/ is the following:
Let E denote the tape alphabet of the simulated machine, Q the set of states and let L,, S, R stand for left, stay and right, the possible motions of the Turing machine head. We assume that [Q] > 1 since otherwise the synthesis problem trivial. The set ordinary codes Woode for a Turing machine sits inside compact space of probability distributions W over codes
Wrode II x (L. S.R) C
II AΣ AQ XOXAAUL SR =:
where AX denotes the set of probability distributions over a set X, see (8. and the product is over pairs (a, q) Σ x Q For example the point ((o',4',d) when it reads a under the head in state writes o', transitions into state o' and moves in direction d. Given E Weode let step' (x, w) E Q denote the contents of the state tape of l/ after & timesteps (of the simulated machine) when the work tape is initialised with & and the description tape with w.
Weode encodes the machine which
TTe space W of parameters is clearly semi-analytic, that is, it is cut out of Rd for some d by the vanishing fi(x) = = fr(x) = 0 of finitely many analytic functions on open subsets of Rd together with finitely many inequalities ø1 (x) > 0................ o.....g.(2 2 where the g, (x) are analytic. In fact W is almi-algebraic, since the f. and gj may all be chosen to he polynomial functions.
3

---

Under review as a conference paper at ICLR 2021
There is principled extension of this operation of U to smooth function
A step': 3n W AQ
which propagates uncertainty about the symbols on the description tape to uncertainty about the final state and we refer to this extension the smooth relaxation of U. The details are given in Appendix
[ but at an informal level the idea behind the relaxation is easy to understand: to sample from A step" (z, w) run L/ to simulate timesteps in such way that whenever the UTM needs to "look at" an entry on the description tape we sample from the corresponding distribution specified The significance of the particular smooth relaxation that we use is that its derivatives have logical interpretation (Clift& & Murfet 2018 $7.1).
by w [
The class of models that consider is
plyla, w) A step (ar, w)
(5)
where is fixed for simplicity in this paper. More generally we could also view z as consisting of a sequence and timeout, as is done in (Clift & Murfet 2018 $7.1). The construction of this model
is summarised in Figure]
state
state
state
init
work
A step
wook
A step
A
step
work
code
codl
code
Figure I: The state of is represented by the state of the work tape, state tape and description (code) tape. The work tape is initialised with a sequence & E Σ", the code tape with w E W and the state tape with some standard initial state, the smooth relaxation A step of the pseudo-UTM run for steps and the final probability distribution over states is
Definition 2.1 (Synthesis problem). A synthesis problem for U consists of a probability distribution (xx,)) over Σ- x Q. We say that the synthesis problem is deterministic if there is Σ -> Q such that q(y = [(=)[z) = 1 for all x E Σ"
Definition 2.2. The triple (p, 4, sp) associated to a synthesis problem is the model of (5 together with the true distribution and uniform prior yp on the parameter space W. The Kullback-Leible function K (w) of the synthesis problem is defined by [ and solution to the synthesis problem is a point Wo. A classical solution is a point of Wo W code
As A step' polynomial function, K is analytic and Wo is semi-analytic space (it is cut out of the semi-analytic space W by the vanishing of K). If the synthesis problem is deterministic and q(x) is uniform on some finite subset of Σ* then Wi is seme-algebraic (it is cut out of W by polynomial equations) and all solutions lie at the boundary of the parameter space W (Appendix D) However in general Wo only semi-analytic and intersects the interior of W (Example C.2 We assume that (v)(x)) is realisable that is, there exists wo W with q(y(z) p(y|2, wo).
A triple (p. q, sp) is regular if the model is identifiable, ie. for all inputs æ E R", the map sending w to the conditional probability distribution p(y|æ, w) is one-to-one, and the Fisher information matrix is non-degenerate. Otherwise, the learning machine is strictly singular (Watanabe) 2009 $1.2. 1). Triples arising from synthesis problems explicit example where multiple parameters w determine the same model, and in Example C22 we
typically singular: in Example 2.5 below show an
give an example where the Hessian of K is degenerate everywhere on Wo (Watanabe 2009
1.1.3).
Noting that this sampling procedure is repeated every time the UTM looks given entry.
4

---

Under review as a conference paper at ICLR 2021
Remark 2.3. Non- -onermteriiiittic synthesis problems arise naturally in various contexts, for example in the fitting of algorithms to the behaviour of deep reinforcement learning agents. Suppose an agent acting in an environment with starting states encoded by Σ" and possible episode end states by E Q. Even if the optimal policy is known to determine a computable function E - Q the statistics of the observed behaviour after finite training time will only provide function E. - AQ and if we wish to fit algorithms to behaviour it makes sense to deal with this uncertainty directly.
Definition 2.4. Let (p: 9: (p) be the triple associated to synthesis problem. The Real Log Canon- ical Threshold (RLCT) X of the synthesis problem is defined so that - À is the largest pole of the meromorphic extension (Atiyah 1970) of the zeta function ((z) J ())))((((dd
The more singular the analytic space Wo of solutions is, the smaller the RLCT. One way to think of the RLCT is as count of the effective number of parameters near Wo (Murfet al. 2020 $4). In Section we relate the RLCT to Kolmogorov complexity and in Section we estimate the RLCT of the synthesis problem detectA given below, using the method explained in Appendix
Example 2.5 (detectA). The deterministic synthesis problem detectà has Σ {O, A. B). Q = {reject, ] and g(y(x)) determined by the function taking in string æ: A's and B's and returning the state accept if the string contains A and state reject otherwise. The conditional true distribution g (z) is realisable because this function is computed by Turing machine.
Two solutions are shown in Figure On the left is a parameter wy E Wo \ Weode and on the right W, E Wo n Wrode, Varying the distributions in wy that have nonzero entropy we obtain a submanifold V S Wi containing wy of dimension 14. This leads by (Watanabe) [2009 Remark 7.3) to bound on the RLCT of X < (300- - 14) which is consistent with the experimental results in Table This highlights that solutions need lie vertices of the probability simplex, and Wo may contain a figh-dimensional submanifold around a given classical solution.
+
tuple
tuple?
tuple
3
tuple_3
uulle
tuple_4
5
tiple_5
tuple.6
blank
rejiet
acropt
Blank
myjcc
accept
right
say
reject
accept
Black
a
myject
sccept
right
sty
Figure 2: Visualisation of two solutions for the synthesis problem detectA.
2.1 THE SYNTHESIS PROCESS
Synthesis a problem because we do not assume that the true distribution is known: for example, <(y[=)) is deterministic and the associated function is Σ' Q, we assume that some example pairs (x, f (z)) are known but no general algorithm for computing of known (if it were, synthesis would have already been performed). In practice synthesis starts with sample D,, [(x,, y:) Y= from q(., y) with associated empirical Kullback-Leibhe distance
1
log ((v.(27) 2r4)
(w,(w)
Σ n2
M3 w)
i=1
If the synthesis problem is deterministic and u. E Weode then (u) = 0 if and only if u explains S S n. We now review two natural ways of
the data in the sense that step' (It, u) yi finding such solutions in the context of machine learning.
Synthesis by stochastic gradient descent (SGD). The first approach is to view the process of program synthesis as stochastic gradient descent for the function K W - R. We view D, large training set and further sample subsets Dm with m & n and compute VK,, to take gradient descent steps W w; v/ Kn, (wx) for some learning rate 77. Stochastic gradient descent has the advantage (in principle) of scaling to high-dimensione parameter spaces W, but in practice is challenging gradient descent to find points of Wo (Gaunt et al. (016))

---

Under review as a conference paper at ICLR 2021
Synthesis by sampling. The second approach is to consider the Bayesian posterior associated to the synthesis problem, which can be viewed as an update on the prior distribution after seeing Dn
p(w)DD)) pl p(Dn|w)p(u) p(Dn)
Zn ((w) II Heule, w)
1 z
exp(-nKn(w)) + log (p(w))
where Z f exp(-nK, (w))).. If is large the posterior distribution concentrates around solutions w E Wn and so sampling from the posterior will tend to produce machines that are (nearly) solutions. The gold standard sampling is Markov Chain Monte Carlo (MCMC). Scaling MCMC to where W high-dimensional is a challenging task with many attempts to bridge the gap with SGD (Welling & Tch 201T Chen al., 2014 Ding et al. 2014 Zhang al. 2020). Nonetheless in simple cases we demonstrate experimentally in Section that machines may be synthesised by using MCMC to sample from the posterior.
COMPLEXITY OF PROGRAMS
Every Turing machine is the solution of deterministic symthesis problem, so Section associates to any Turing machine singularity of semi-analytic space Wo- To indicate that this connection is not vacuous, we sketch how the complexity of a program is related to the real log canonical threshold of singularity. A more detailed discussion will appear elsewhere.
Let q(x, y) be a deterministic synthesis problem for UI which only involves input sequences in some restricted alphabet Eipput that is, (()) = 0 if & (Einpur)- Let D, be sampled from q(z, y) and let u,u Weode n Wo be explanations for the sample in the sense that (u) k,(()) O. Which explanation for the data should we prefer? The classical answer based on Occam's 's razor (Solomonoff] 1964) is that we should prefer the shorter program, that is, the one using the fewest states and symbols.
Set N |عز and M = IQ]. Any Turing machine T using N' S N symbols and M' M states has a code for U of length eM'N'' where is a constant. We assume that Einput is included in the tape alphabet of T so that N' 2 [Eepuel and define the Kolmogorov complexity of q with respect to Ui to be the infimum c(q) of M N' over Turing machines T that give classical solutions for
Let be the RLCT of the triple (p, q, associated the synthesis problem (Definition 2.4 Theorem 3.1. A < (M + N)((g).
Proof. Let u E Woode n Wo be the code of Turing machine realising the infimum in the definition of the Kolmogorov complexity and suppose that this machine only uses symbols in E' and states in Q' with N' = | and M = 'Q'). The time evolution of the staged pseudo-UTT UTM V/ simulating on E Ex Emput is independent of the entries on the description tape that belong to tuples of the form (a, q, ?, ?,?,) ?) with (a,
Σn x Q'. Let V C W be the submanifold of points which agree with on all tuples with (a.q) E E' x Q' and are otherwise free. Then u V C Wo and codim
(M + N) and by (Watanabe 2009 Theorem 7.3) we have X < 2 codim(V).
Remark 3.2. The Kolmogorov complexity depends only on the number of symbols and states used. The RLCT is more refined invariant since it also depends how each symbol and state is used CCiff& Murfet 2018 Remark 7.8) as this affects the polynomials defining Wo (see Appendix[D)
4 PRACTICAL IMPLICATIONS
Using singular learning theory have explained how programs to be synthesised are singularities of analytic functions, and how the Kolmogorov complexity of a program bounds the RLCT of the associated singularity. We sketch some practical insights that follow from this point of view.
Synthesis minimises the free energy: the sampling- sampling-based approach to synthesis (Section 2.1 aims to approximate, via MCMC, sampling from the Bayesian posterior for the triple (p, q. :p) associated to a synthesis problem. To understand the behaviour of these Markov chains we follow the asymp- totic analysis of (Watanahe) 2009 Section 7.6). If we cover W by small closed balls V, around

---

significant Under review as a conference paper at ICLR 2021
points wa then compute the probability that sample comes from Va by
1
/ c c-nka(w))((u p(w))d
Pa Zo
and if is sufficiently large this is proportional to e where the quantity
fa Knn + A, log(n)
called the free energy. Here K₂ is the smallest value of the Kullback-Leibler divergence on Va and X is the RLCT of the WK, nv, where W - {w E W K(w) c} is level set of K. The Markov chains used to generate approximate samples from the posterior are attempting to minimise the free energy, which involves a tradeoff between the energy Kan and the entropy Xa log(n).
Why synthesis gets stuck: the kind of local minimum of the free energy that we want the synthesis process to find are solutions Wa E Wo where Aa is minimal. By Section DettionJont one may think of these points as the "lowest complexity" solutions. However it is possible that there are other local minima of the free energy. Indeed, there may be local minima where the free energy is lower than the free energy at any solution since at finite it is possible to tradeoff an increase in Ka against a decrease the RLCT Xa In practice, the existence of such "siren minima" the free energy may manifest itself as regions where the synthesis process gets stuck and fails to converge to solution. In such a region K + Aa log(n) < À llg(n)) where À the RLCT of the synthesis problem. In practice it has been observed that program synthesis by gradient descent often fails for complex problems in the sense that it fails to converge to solution (Gaunt et al.] 2016). While synthesis by SGD and sampling are different, it is a reasonable hypothesis that these siren minima contributing factor in both cases.
Can avoid siren minima? If we let Ae denote the RLCT of the level set W. then siren minima of the free energy will be impossible at a given value of n and cas long as A 2 - A-c Tog(n] the more singular W. is the lower the RLCT, so this lower bound says that the level sets should not become too singular too quickly as increases. At any given value of there a "siren free" region in the range e 2 log(a) since the RLCT is non-negative (Figure 3 Thus the learning process will be more reliable the smaller Alog(n) is. This can arranged either by increasing n (providing more examples) or decreasing A. x
Recall that
While the RI.T is determined by the synthesis problem, is possible to change its value by chang- ing the structure of the UTM As we have defined it M is "simulation type" UTM, but one could for example add special states such that steps is executed by the UTM (i.e. a subroutine). This amounts to specifyingg codes in higher level programming language. Hence one of the practical insights that can be derived from the geometric point of view program synthesis is that varying this language is natural way to engineer the sin- gularities of the level sets K, which according to singular learning theory has direct implications for the learning process.
code specifies a transition into that state a series of
slope
Tugin]
siven froe
Alog(n)
Figure 3: Level sets above the cutoff cannot contain siren local minima of the free energy.
7

---

Under review as a conference paper at ICLR 2021
5 EXPERIMENTS
We estimate the RLCT for the triples (p. q: (p) associated to the synthesis problems detectt, (Ex- ample 2.5) and pari ParityCheck. Hyperparameters of the various machines contained in Table of Appendix B The true distribution q(x)) is defined as follows: we fix a minimum and maximum sequence length I b and sample x ((x) we first sample length uniformly from [a, and then uniformly sample æ from {A, BJ
We perform MCMC the weight vector for the model class {p(ylæ, w) represented in our PyTorch implementation by three tensors of shape {[L n. m.lhiiis where L is the number of tuples in the description tape of the TM being simulated and {n:} are the number of sym- bols, states and directions respectively. A direct simulation of the UTM is used for all experiments improve computational efficiency (Appendix G We generate, for each inverse temperature / and dataset D,, Markov chain via the No-U-turn sampler from Hoffman & Gelman (2014). We use standard uniform distribution as our prior yp
W) where w is
Max-length
Temperature
RLCT
Std
R squared
log(500)
8,089205
3.524719
0.965384
log(1000)
6,533362
2.094278
0,966856
log(500)
4.601800
1.156325
0.974569
8
log(1000)
4.431683
1,069020
0.967847
9
log(500)
5.302598
2.415647
0.973016
(1000)
4.027324
1.866802
0.958805
log(500)
3,224910
1.169699
0.963358
10
(1000)
3,433624
0,999967
0,949972
Table 1: RLCT estimates for detectA.
For the problem detectà given in Example 2.5 the dimension of parameter space is dim W 30. We use generalized least squares to fit the RLCT (with goodness-of-fi measured by S2²), the algorithm of which is given Appendix A Our results are displayed in Table T and Figure ] Our purpose in these experiments is not to provide high accuracy estimates of the RLCT, as these would require much longer Markov chains. Instead we demonstrate how rough estimates consistent with the theory can be obtained at low computational cost. If this model were regular the RLCT would be dim W/2- 15.
RLCT of detectA varying true distribution
10
temperature
log(500)
log(1000)
max-length
Figure 4: Plot of RLCT estimates for detectA, Shaded region shows one standard deviation.
The deterministic synthesis problem parityCheck has
= (D,
Q (reject, accept, get.eeeett...eeeeeerr.eeeeeeeeoe
8

---

Under review as a conference paper at ICLR 2021
The distribution q(x) is discussed in Section 5 and (()(2) is determined by the function taking in a string of A's and B's, and terminating in state accept if the string contains the same number of A's as B's, and terminating in state reject otherwise. The string is assumed to contain symbols. The true distribution is realisable because there a Turing machine using E and Q which computes this function: the machine works by repeatedly overwriting pairs consisting of a single A and B with ss; if there are any A's without a matching B left over (or vice versa), we reject, otherwise we accept.
blank
In more detail, the starting state Ne moves right on the tape until the first A or B is found, and overwrites it with an X. it's an (resp. B) we enter state getNextB (resp. getNext..). If no A or B is found, we enter the state accept. The state getNextA (resp. getNextB) moves right until an (resp. B) is found, overwrites with an X and enters state gotoStart which moves left until blank symbol is found (resetting the machine to the left end of the tape). If no A's (resp. B's) were left on the tape, we enter state reject. The dimension of the parameter space is dim W 240. this model were regular, the RLCT would be dim W/2 120. Our RLCT estimates are contained Table 2
Max-length
Temperature
RLCT
Std
R squared
5
lo0(300)
4.411732
0.252458
0,969500
6
log (300)
4.005667
0.365855
0.971619
log (300)
3.887679
0.276337
0.973716
Table 2: RLCT estimates for parityCheck.
DISCUSSION
We have developed theoretical framework in which all programs in principle be learnt from input-output examples via an existing optimisation procedure. This is done by associating to each program smooth relaxation which, based on Clift & Murfet (2018). can be argued to be more canonical than existing approaches. This realization has important implications for the building of intelligent systems.
In approaches to program synthesis based on gradient descent there is a tendency to think of solutions to the synthesis problem as isolated critical points of the loss function K, but this a false intuition based on regular models. Since neural networks, Bayesian networks, smooth relaxations of UTMs and all other extant approaches to smooth program synthesis are strictly singular models (the map from parameters to functions is not injective) the set Wo of parameters w with K(w) = 0 is complex extended object, whose geometry is shown by Watanabe's s singular learning theory to be deeply related to the learning process. We have examined this geometry in several specific examples and shown how to think about complexity of programs from a geometric perspective. is our hope that algebraic geometry can assist in developing the next generation of synthesis machines.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Shun-ichi Amari, Tomoko Ozeki, and Hyeyoung Park. Learning and inference in hierarchical mod- els with singularities. Systems and Computers in Japan, 34(7):34-42, 2003.
Michael F Atiyah. Resolution of singularities and division of distributions. Communications on Pure and Applied Mathematics, 23(2):145-150, 1970.
Alan W Biermann. On the inference of Turing machines from sample computations. Artificial Intelligence. 3:181-198, 1972.
Rudy R Bunel, Alban Desmaison, Pawan K Mudigonda, Pushmeet Kohli, and Philip Torr. Adaptive neural compilation. In Advances in Neural Information Processing Systems, pp. 1444 1452, 2016.
Tianqi Chen, Emily Fox, and Carlos Guestrin. Stochastic gradient Hamiltonian Monte Carlo. In International Conference Machine Learning, pp. 1683-1691, 2014.
Xinyun Chen, Chang Liu, and Dawn Song. Execution- Execution-guided guided neural program synthesis. In Interna- tional Conference on Learning Representations, 2018.
James Clift and Daniel Murfet. Derivatives of Turing machines in linear logic. arXiv preprint arXiv:180S. 11000,118110 2018.
Karel De Leeuw Edward F Moore, Claude E Shannon, and Norman Shapiro. Computability by probabilisticc machines. Automata studies, 34:183-198, 1956.
Nan Ding, Youhan Fang, Ryan Babbush, Changyou Chen, Robert D Skeel, and Hartmut Neven. Bayesian sampling using stochastic gradient thermostats. In Advances in Neural Information Processing Systems, pp. 3203-3211, 2014.
Richard Evans and Edward Grefenstette. Learning explanatory rules from noisy data, Journal of Artificial Intelligence Research, 61:1-64, 2018.
Cameron E Freer, Daniel M Roy, and Joshua B Tenenbaum. Towards common-sense reasoning via conditional simulation: legacies of Turing artificial intelligence. Turing 's Legacy, 42:195-252, 2014.
Alexander L Gaunt, Mare Brockschmidt, Rishabh Singh, Nate Kushman, Pushmeet Kohli, Jonathan Taylor, and Daniel Tarlow. Terpret: A probabilistic programming language for program induction. arXiv preprint arXiv: (o::::60844440 2016.
Phillip Griffith and Joseph Harris. Principles of Algebraic Geometry. Wiley-Interscience, 1978.
Sumit Gulwani, Oleksandr Polozov, and Rishabh Singh. Program synthesis. Foundations and Trends in Programming Languages, 4(1-2):1-119, 2017.
Heisuke Hironaka. Resolution of singularities of an algebraic variety over field of characteristic zero: I. Annals of Mathematics, 79(1):1092203, 1964.
Matthew D Hoffman and Andrew Gelman. The No-U-Tum sampler: adaptively setting path lengths in Hamiltonian Monte Carlo. J. Mach. Learn. Res,, 15(1):1993-163, 2014.
Mareus Hutter. Universal artificial intelligence: Sequential decisions based on algorithmic proba- bility. Springer Science & Business Media, 2004.
Eukasz Kaiser and Ilya Sutskever. Neural GPUs learn algorithms. In International Conference on Learning Representations, 2016.
Daniel Murfet, Susan Wei, Mingming Gong, Hui Li, Jesse Gell-Redman, and Thomas Quella. Deep learning is singular, and that's good. arXiv preprint arXiv:2010.11560, 2020.
Arvind Neelakantan, Quoc V. Le, and Ilya Sutskever. Neural programmer: Inducing latent programs with gradient descent. International Conference on Learning Representations, ICLR 2016, 2016.
10

---

Under review as a conference paper at ICLR 2021
Jürgen Schmidhuber.
Discovering neural nets with low Kolmogorov complexity and high general- ization capability. Neural Networks, 10(5):857-83) 8735,, 1997.
Ray J Solomonoff. A formal theory of inductive inference. Part 1. Information and control, 7(1): 1-22, 1964.
Alan Turing. Intelligent machinery. NPL Mathematics Division, 1948.
Sumio Watanabe. Almost all learning machines are singular. In 2007 IEEE Symposium on Founda- fions of Computational Intelligence, pp. 383-388 IEEE, 2007.
Sumio Watanabe. Algebraic Geometry and Statistical Learning Theory, volume 25. University Press, 2009.
Cambridge
Sumio Watanabe. A widely applicable Bayesian information criterion. Journal of Machine Learning Research, 14:867-897, 2013.
Max Welling and Yee W Teh. Bayesian learning via stochastic gradient Langevin dynamics. In Proceedings of the 28th International Conference on Machine Learning, pp. 681-688, 2011.
Ruqi Zhang, Chunyuan Li, Jianyi Zhang, Changyou Chen, and Andrew Gordon Wilson Cyclical stochastic gradient MCMC for Bayesian deep learning. In International Conference Learning Representations, 2020.
APPENDIX
A ALGORITHM FOR ESTIMATING RLCTS
Given a sample Dr, = (( y:) from g( y) let Ln(w) = -1 Σm log bogp(Bslas, w) be the negative log likelihood. We would like estimate
1 2 / (w]](w)((w))
/
Il plustrr, &
where 2 = ( plui,z, w dw for some inverse temperature B. If 3 constant 3o. then by Theorem 4 of Watanabe (013).
Sn for some
log
A Alog T
Alog n + Op(1)
R$ E (nLn (..o(w))
+
Un
Bo
2/3
where } is sequence of random variables satisfying E(U,) 0 and is the RLCT. In practice, the last two terms often vary negligibly with 1/33 and so E (w)) approximates a linear function of 1/3 with slope (Watanabe 20133 Corollary 3). This is the foundation of the RLCT estimation procedure found in Algorithm] which is used in our experiments.
Algorithm RLCT estimation
Input: range of f'',, set of training sets T each of size n, approximate samples (wi...., WR] from p (x)) for each training set D, and each 3 for training set D, E T do for 3 in range of B's do
Approximate 1E (w)) with R ER nen (w,)) where wi...., we are approximate sam- ples from (w) end for
Perform generalised least squares to fit À in Equation ( call result \(D,,)
end for
Output: + Ep.er
11

---

Under review as a conference paper at ICLR 2021
Each RLCT estimate (DD)) in Algorithm 1 was performed by linear regression the pairs {(1/3,, En [nLn (w)])) where the five inverse temperatures B, are centered on the inverse tem- perature 1/T where T is the temperature reported for each experiment in Table and Table 2
From a Bayesian perspective, predictions about outputs y should be made using the predictive dis-
tribution
p' (u(lor D..) - p(u)k,, w) ())(w( Dr.dw......
The Bayesian generalisation error associated to the Bayesian predictor is defined as the Kullback- Leibler distance to the true conditional distribution
Bn(n) == Dxl(allp") /
(()]zz) p"(y)x)
((vl)))(()) log
dydr.
If some fundamental conditions are satisfied (Definition 6.1 and Definition 6.3 of Watanabe (2009) then by Theorem 6.8 of loc.cit., there exists random variable B", such that as - oc, E B, (n)) converges to B[Bğ]- In particular, by Theorem 6.10 of Watanabe (2009) B[B3] A.
B HYPERPARAMETERS
The hyperparameters for the various synthesis tasks are contained in Table The number of samples is R in Algorithm and the number of datasets is (T]. Samples are taken according to the Dirichlet distribution, a probability distribution over the simplex, which is controlled by the concentration. When the concentration is a constant across all dimensions, is assumed here, this corresponds to a density which is symmetric about the uniform probability mass function occurring in the centre of the simplex. The value a 1.0 corresponds to the uniform distribution over the simplex. Finally, the chain temperature controls the default / value, ie. all inverse temperature values are centered around T/T where T the chain temperature.
Hyperparameter
detectA
parityCheck
Dataset size (1t)
200
100
Minimum sequence length (a)
4
1
Maximum sequence length (b)
7/8/9/10
5/6/7
Number of samples (R)
20,000
2,000
Number of burn-in steps
1,000
500
Number of datasets (TT)
4
3
Target accept probability
0.8
0.8
Concentration (ex)
1.0
1.0
Chain temperature (1')
log((00)/log(100)
log(300)
Number of timesteps (t)
10
42
Table 3: Hyperparameters for Datasets and MCMC.
C THE SHIFT MACHINE
The pseudo-UTM U is a complicated Turing machine, and the models p(ylar, w) of Section are therefore not easy to analyse by hand. To illustrate the kind of geometry that appears, we study the simple Turing machine shiftMe MaMaaaiiinnn of Clift & Murfet (2018) and formulate and the input to the machine will be string of the form Enaaazagl where is called the counter and a; E {A, B). The transition function, given in loc.cit., will move the string of A's and B's leftwards by n steps and fill the right hand end of the string with A's, keeping the string length invariant. For example, ABU is the input to M, the output will be AAB.
associated
statistical learning problem. The tape alphabet is A,
Set W 20, A(A, B} and view (h, E W representing a probability distribution (1 - h) 0 h- for the counter and (1 -1-18 k) B + A A for 01 The model is
3
ply|== = (az, as), w) = (1 - k A+ +1 h) k) B Σ
11-1 11 - -)3-1 a;-
i-1 2=2
12

---

Under review as a conference paper at ICLR 2021
This model is derived by propagating uncertainty through shiftMachine in the same way that ply|æ, w) is derived from A step' in Section by propagating uncertainty through U. We assume that some distribution q(z) over {A, B)² is given.
Example C.I. Suppose q(y(z)) = p(y|z, wo) where wh = (1, 1). It is easy to see that
1 Σ
1 logp(y = azfa (az, 0z), w) log (h, k)]
K(w)= - 4 02.03
where gl,, ((1 - ((1-1)2k k + h²) ((1 h1 k) h² is polynomial in w. Hence
Wo {(h, k-) E W (h, 1} = V(g 1) [0, 1]
a semi-algebraic variety, that is, is defined by polynomial equations and inequalities. Here V(h) denotes the vanishing locus of function h.
Example C.2. Suppose (AB) and q(ul> = AB) 1 _ B. Then the Kullback-Leibler divergence is K(h, k)
log(4f(1 - f)) where (1 h) 2h(1 h). Hence VK
(f } Fー-ク f.. Note that has no critical points, and so AK 0 at (h, k) (0, 1)2 and only
if [(h, k)) 2. Since K is non-negative, any Wo satisfies (k(w) 0 and so
Wo [0, wwa//1/411110000 (0,1) V( )
semi-algebraic. Note that the curve f 2 is regular while the curve 4f - f] = 1 is singular and it is the geometry of the singular curve that is related to the behaviour of K. This curve is shown
in Figure 5 straightforward to check that the determinant of the Hessian of K is identically
zero Wo, u. so that every point on Wo is degenerate critical point of K.
Figure 5: Values of K khh, k) on [0, 1]2 are shown by colour, ranging from blue (zero) to red (0.01).
The singular analytic space K (white) and the regular analytic level set K 0.001 (black).
D GENERAL SOLUTION FOR DETERMINISTIC SYNTHESIS PROBLEMS
In this section consider the of deterministic synthesis problem g(z, which is finitely supported in the sense that there exists a finite set X' C Σx such that g(x) e for all x E X' and q(x) 0 for all i & X. We first need discuss the coordinates
the parameter space W of (3). To specify point on W is to specify for each pair (a, q) E Σ x Q (that is, for each tuple on the description tape) triple of probability distributions
Σ 1 EAΣ,
e'EQ
Σ
Uy 3.
of E AQ,
q'EQ
Σ
2 de ALL,
dE(L,S,R)
13

---

Under review as a conference paper at ICLR 2021
The space W of distributions is therefore contained in the affine space with coordinate ring x
Rw = == o, (Vg (.9
Jo {=d") 2--) J.g.al
The function F Å step' (z. -) W - AQ is polynomial (Clift Murfet 2018 Proposition 4.2) and we denote for Q F E Rw the polynomial computing the associated component of the function F Let OW denote the boundary of the manifold with comners W, that is, the set of all points on W where least one of the coordinate functions given above vanishes
ow v(
II d'EQ
II D'EQ
3. Uq
II
0.
3d
dE(L.S.R)
where Vhh denotes the vanishing locus of h. Lemma D.1. Wo # W.
Proof. Choose E X' with ((x) > and let y be such that ((ylx) Let Weode be the code for the Turing machine which ignores the symbol under the head and current state, transitions some fixed state s + y and stays. Then w & Wo.
Lemma D.2. The set Wo is semi-algebrate and Wo a.W
Proof. Given E E" with ((x) > O we write = y(x) for the unique state with g(z, v) * 0. In this notation the Kullback- divergence is
K(w)= Σ (cDkL(Vll = =
log F Ff (w) -c log II
(w).
TE
NE
xEX
Hence
Wo Wn N #EX
v(1 - (w)
semi-algebraic.
Recall that the function A step' is associated to an encoding of the UTM in linear logic by the Sweedler semantics CClit & Murfet, 2018) and the particular polynomials involved have a form that is determined by the details of that encoding (Clift & Murfet 2018 Proposition 4.3). From the design of our UTM we obtain positive integers m, Re for a E E. E Q, {L, R} and a
function π θ Q where
θ =
-= E x Qm x (L
0.8
We represent elements of θ by tuples (n, (.E) E θ where u/a. E E for a E E. g E Q and < S 4, and similarly Ç(0, q. E Q and Ela, k) (L,
S, R). The polynomial FØ is
ma II
ndd
F
Σ (1, (,E))
II
I
o. p(a.3))
0.9 Velaaa)
II 1=1
ag (()
(a.C.E)E
0.9
j=1
where 8 is Kronecker delta. With this in hand may compute
Wo = wn n V(1 (w))
#EX
= Wn n (w)).
#EX sty
But F is polynomial with non-negative integer coefficients, which takes values in [0, 1] for w W. Hence it vanishes on w if and only if for each triple p. ç. with s ((, ç. E) one or more of the coordinate functions 2.
.5.9 ..4 pp)og.))* ((())g))>* (((....)) vanishes on w.
The desired conclusion follows unless for every x E X and (u. C.E) E θ we have (u, (.E.C))))))))) =
that F 0 for all * But in this case case Wo W which contradicts Lemma D.I n
14

---

Under review as a conference paper at ICLR 2021
E STAGED PSEUDO-UTM
Simulating a Turing machine M with tape alphabet E and set of states Q on a standard UTM requires the specification of an encoding of 2 and Q in the tape alphabet of the UTM. From the point of view of exploring the geometry of program synthesis, this additional complexity is uninteresting and so here we consider staged Preudo-UTM whose alphabet is
ΣUTM = EUQUI U (L. R, S) U (X,0)
where the union is disjoint where D is the blank symbol (which is distinct from the blank symbol of M). Such a machine is capable of simulating any machine with tape alphabet E and set of states Q but cannot simulate arbitrary machines and is not UTM in the standard sense. The adjective staged refers to the design of the UTM, which we now explain. The set of states is
QUT = { compSymbol, compState, copySy copyState, copyDir, compStttee ScopySymbol, StatyState, -copyDir, updateSymbol, updateState, updateDir, resetDescr }.
The UTM has four tapes numbered from 0 to 3, which we refer to the description tape, the staging tape, the state tape and the working tape respectively. Initially the description tape contains a string of the form
X 5o di $1 ...ggid.... N
corresponding to the tuples which define M, with the tape head initially on so- The staging tape is initially a string XXX with the tape head over the second X. The state tape has single square containing some distribution in AQ, corresponding to the initial state of the simulated machine M, with the tape head over that square. Each square on the the working tape is some distribution in AE with only finitely many distributions different from D. The UTM is initialized in state compSymbol.
The operation of the UTM outlined in 6 consists of two phases; the scan phase (middle and right path), and the update phase (left path). During the scan phase, the description tape is scanned from left to right, and the first two squares of cach tuple are compared to the contents of the working tape and state tape respectively. If both agree, then the last three symbols of the tuple are written to the staging tape (middle path), otherwise the tuple is ignored (right path). Once the X the end of the description tape is reached, the UTM begins the update phase, wherein the three symbols on the staging tape are then used to print the new symbol on the working tape, to update the simulated state on the state tape, and to move the working tape head in the appropriate direction. The tape head on the description tape is then reset to the initial X.
Remark E. One could imagine variant of the UTM which did not include staging tape, instead performing the actions on the work and state tape directly upon reading the appropriate tuple on the description tape. However, this is problematic when the contents of the state or working tape are distributions, as the exact time-step of the simulated machine can become unsynchronised, increas- ing entropy. As a simple example, suppose that the contents of the state tape were 0.5q + 0.5p, and the symbol under the working tape head was Upon encountering the tuple sqs'ql q' R. the machine would enter superposition of states corresponding to the tape head having both moved right and not moved, complicating the future behaviour.
We define the period of the UTM to be the smallest nonzero time interval taken for the tape head on the description tape to return to the initial X, and the machine to reenter the state compSymbol. If the number of tuples on the description tape N. then the period of the UTM is T 10. + 5. Moreover, other than the working tape, the position of the tape heads are T -pperiodic..
F SMOOTH TURING MACHINES
Let 1/ be the staged pseudo-UTM of Appendix E In defining the model p(ylæ, w) associated to a synthesis problem in Section 2 we use a smooth relaxation A step' of the step function of 44 In this appendix we define the smooth relaxation of any Turing machine following CClift & Murfet (2018).
Let M = (E, 2) be a Turing machine with finite set of symbols E, a finite set of states Q and transition function 8: Σ x Q + Σx Q x 0,, 1}. We write 8; = proj, o 8 for the ith component of 5 for E (1,2,3). 3). For D E Σ, let
دズ { Z (i) 0 except for finitely many i}.
15

---

Under review as a conference paper at ICLR 2021
CompSymbol
b.
else
LLSS
RLSS
RLSS
updateSymbol
compState
compState
a, X,
8, b, C,
a, a,
else
b. C.
write a, X, b, SRSS
RSSS
RSSS
updateState
copySymbol
coppySymbl
D. c.
8, b.b, b.
write a, x, d SASS
write a, c, RRSS
SASS
RRSS
updateDir
copyState
copyState
b.
b.
write X, SLSb
write
SASS
RASS
LSSS
resetDescr
copyDir
Copyyir
b.
ASSS
RLSS
go to compSymbol
Figure 6: The UTM. Each of the rectangles are states, and an arrow + q' has the following interpretation: if the UTM is in state q and sees the tape symbols (on the four tapes) as indicated by the source of the arrow, then the UTM transitions to state q', writes the indicated symbols (or if there is no write instruction, simply rewrites the same symbols back onto the tapes), and performs the indicated movements of each of the tape heads. The symbols b, c, d stand for generic symbols which are not X.
We can associate M discrete dynamical system M =<Z.7 step) where
step -2 + 220 Q
is the step function defined by
step(a, g) (a=50(r00))
(ofoo.),,0 (-. 02..... 02....)),,((..0...))) s)).
.2....).
with shift map a (s((os))) (o) = O0t0s(00.4)
Let X be finite set. The standard X X-simplex is defined
AX =
Σ X E RX ZEX
Σ X 1 and X 2 f all E X}
(8)
2
where R.X is the free vector space on X. We often identify X with the vertices of AX under the canonical inclusion X + AX given by i(x) = Ex'ex Swmp''. For example {0, 1} c (( 1)) ~ [0, 1].
A tape square is said to be relative position E Z if it is labelled after enumerating all squares in increasing order from left to right such that the square currently under the head is assigned zero. Consider the following random variables at times > 0:
16

---

Under review as a conference paper at ICLR 2021
Yu, Σ: the content of the tape square at relative position time t.
St E Q: the internal state at time t.
Wr. E E: the symbol to be written, in the transition from time to + 1.
Mv E (,,S, R): the direction to move, in the transition from time t t + 1.
We call a smooth dynamical system a pair (A, consisting of smooth manifold A with corners together with a smooth transformation Φ A - A. Definition F.1. Let M = (2,
Q, be a Turing machine. The smooth relaxation of M is the smooth
dynamical system ((AΣ) 7,7 x AQ, Astep) where
Astep (A x AQ (AE) x AQ
2,0
a smooth transformation sending a state determined by the equations
to ((P(KuH))) P(S(+1))
P(Mr, d|c)= = Eong
g|C),
[Wr:=000
- q(O),
P(S41 = c] Eag 022 - d'C)),
P(Y,,41 = o|C)= P(Mur LIC)
o|C) + 6 Pu=r - o(0) + P(Mut S(C) P o 8,=0 P P(Wr, P(W,
+ P(Mu = RIC)(
= o|C) + + 6 =o()))
where C (AE)² AQ is an initial state.
We will call the smooth relaxation of Turing machine a smooth Turing machine. A smooth Turing machine encodes uncertainty the initial configuration a Turing machine together with update rule for how to propagate this uncertainty over time. We interpret the smooth step function as updating the state of belief of "naive" Bayesian observer. This nomenclature comes from the assumption of conditional independence between random variables in our probability functions.
Remark F.2. Propagating uncertainty using standard probability leads to a smooth dynamical sys- tem which encodes the state evolution of "ordinary" Bayesian observer of the Turing machine. This requires the calculation of various joint distributions which makes such an extension computa- tionally difficult to work with. Computation aside, the naive probabilistic extension is justified from the point of view of derivatives of algorithms according to the denotational semantics of differential linear logic. See Clift & Murfet (2018) for further details.
We call the smooth extension of universal Turing machine smooth universal Turing machine. Recall that the staged pseudo-U'TM UTM Z/ has four tapes: the description tape, the staging tape, the state tape and working tape. The smooth relaxation of 2/ is smooth dynamical system
Astepu [(AFUTM)) 2 x AQUTM >> (A x AQUTM
If use the staged pseudo-UT UTM to simulate Turing machine with tape alphabet E S EUTM and states Q C ΣUTM then with some determined initial state the function Astep restricts to
Astepy 2 x W x AQ x X - (AE)2 x W AQ x X
where the first factor is the configuration of the work tape, W is as in and
X = [(AEuT)) 2.0 x AQUTM
where the first factor is the configuration of the staging tape. Since U is periodic period T 10N + 5 (Appendix E the iterated function (A stepy)" takes an input with staging tape in its
17

---

Under review as a conference paper at ICLR 2021
default state XXX and UTM state compSymbol and returns configuration with the same staging tape and state, but with the configuration of the work tape, description tape and state tape updated by one complete simulation step. That is,
(Astepu)) (I, w, X.X compSymbol) = (F(x, w, XXXX, commyyyy))
for some smooth function
F: ( W AQ (AΣ)&.) 2D W AQ.
Finally we can define the function A step' of (4). We assume all Turing machines are initialised in some common state init E Q-
Definition F.3. Given 2 0 we define A steep' Σ" x W + AQ by
A Astep' (2,, (.) 11g F (zz, w. init)
where He the projection onto AQ.
G DIRECT SIMULATION
For computational efficiency in our PyTorch implementation of the staged pseudo-UTM we imple- ment F of (9) rather than Å stepu. We refer to this as direction simulation since it means that we update in step the state and working tape of the UTM for full cycle where cycle consists of T 10N + 5 steps of the UTM.
Let St) and (t) be random variables describing the contents of state tape and working tape in relative positions O, u respectively after 2 0 time steps of the UTM. We define 5() == S(4 + Tt) and (1)= = (4 + Ti) where / 2 0 and u E Z. The task then is to define functions f, g such that
5(t + =) ((5(t)
(((+1)=g((xuc
The functional relationship is given as follows: for S i < N indexing tuples the description
tape, while processing that tuple, the UTM is in a state distribution X; - + (1 - X²) -q where
q (copySymbol, copyState, Diry Given the initial state of the description tape, we assume uncertainty about s',q', d only. This determines map
0: (1.....,N) N) +EXQ Q
where the description tape at tuple number is given by P()))0()22P())P))))P)P) We define the conditionally independent joint distribution between
by
A Σ 6000) P(Yo..- = ((0))=g((S_11 =
oEΣ
9EQ
P(Y. 0()))) P(._1
0(1)2).
We then calculate a recursive set of equations for S j S N describing distributions P(S;),
and P(d,) on the staging tape after processing all tuples up to and including tuple j. These are given
by P(šo) P( = P(d.) = 1. X and
P(s.) Σ (>. P(s σ) (1 Aa) P(s,- - o)) + Xx) 1 x
P(() Σ
(hi P(g. =) +1 (1- P(g-1 =)] 9)} . (1 - Aa) p(p--1 X
qEQ
P(d.) Σ
P a) (1 A1) p(d. a)) (1 Aa) p(d: XX X.
(E(L.,R,S)
Let Ag = P(SN = X): P P( = =o) + P( = σ). In terms of the above distributions
P(S.) Σ
PPâN = X): P(.._ 9) + P(yN = =Q)) -9
qEQ
18

---

Under review as a conference paper at ICLR 2021
and
P(Y 0) P(dN L) P + Au=1
P(dxx R) ( =a) + 01m-119
P(dN S) (6uz0 (Y =0) )u=0AA
+ P(dN = x) (60460 P(Ptt- 5u=
Using these equations, we can state efficient update rules for the staging tape. We have
N
P(šN = X) = II
X1),
P(šN = = = N3.
Σ
P(s =0) II (1-
/=1
==1
1=j+1
N
N
N
P(âN = =X II (1 N2),
P(âN = 9) = Σ
P(d) =4) II
(1
X1)
jml
j=l
(=j+1
N
N
N
P(dy X)
(1 11),
P(dv = a) X, -)=
P(dj = a) II
(1 - (1)
==1
j=1
1=j+1
To enable efficient computation, (A E RN, We view
express these equations using tensor calculus. Let
0: R: + RE IQQ
tensor and so 8 Ei (00((1) 0()2 RV & RE
RQQ Then
0. (P
@ P(S--1)= = Σ P(Y 0()))) - =
If we view
ERN & R as tensor, then
N P(AN) = P(s' =
N
N
N
A [I (1- (1- x)) 1=/+1
A.
II
X), II Ad), .1......1111.... AN),
J=1
1=2
1=3
can be expressed in terms the vector À only. Similarly, P(d. =) ERR &
R with
N P(ÂN) Σ P(ds =)) A II (1 (1-M0 21) =
II 1=2
X1) I AD ....,, AN);
j=1
1=++1
1=3
and P(d. = o) E R.N.
R with
N A II
N |I
P(dx)= Σ P(dy =))
(1 x))
=
A1)
II Ao..... --Nw.1))
j=1
1=++1
19


Reviews:
[{"review_id": "lIOxjjOZii_", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors apply algebraic geometry to program synthesis, by identifying programs with points of analytic varieties. They construct a smooth relaxation to the synthesis problem by considering the space of probability distributions over codes for universal turning machines (which is a smooth/continuous manifold), and then translate this probability into corresponding probabilities of generating a correct program. This allows them to extend the KL divergence on the discrete distribution of codes to a smooth function, whose zeros correspond to the desired programs. They use MCMC to find (approximate) these zeros.\n\nOverall, the approach seems interesting, but seems to be a bit complex for a real application (both examples considered in the experiments seem pretty small/toy problems). While the ideas are interesting, it seems like more work needs to be done before they could be of interest to practical program synthesis (admittedly, the authors do not claim that it is practical, but I am unable to judge the paper by quality of the theoretical work)\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "MwRJAoxb86o", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "- quality : good\n- clarity : very good. I was worried about reading this due to all the math symbols, but it turns out the big pictures are clearly explained.\n- originality : okay\n- significance : not sure\n\nI could not follow the more technical aspects as I'm not a theory person (although I did fail algebraic geometry at one point). The main claim of the paper is that when doing relaxations and attempt to view satisfying programs as the variety W0 of some mathematical function, W0 is typically larger than W0 \\intersect Wcode. This is important because one may easily find a point of solution in the variety W0, yet it cannot be realized as a working program in Wcode. I can confirm that this is indeed the case in some limited capacity when I tried to approximate deterministic functions via neural networks, and attempted to synthesize these functions by \"pulling back\" from the output to the space of programs, which resulted in a relaxed representation of program that has very low loss, yet do not correspond to actual programs. It is nice to see why this happened in a formal setting.\n\nAs I am confident that my expertise in this area is not high, I will not be providing an explicit pro/con list. I would instead ask a few questions to the authors and hope I can get a good response:\n\n- A natural thing to make program synthesis more amendable is by changing the set Wcode. For instance, if I were to represent the function that adds 3, I can either do that with x + 3, or with x+1+1+1. Now, which one of these representation would lead to a Wcode that has a better chance of intersecting better with W0? As DSL designers, we have fairly big freedom in designing what Wcode is, that is often the only thing we can control. Is there a rule of thumb that we can follow to ensure that gradient-based or sampling-based relaxation works well? i.e. W0 isn't such a horrible extended object?\n\n- Another \"knob\" that we can control easily in synthesis is the number of input output examples, and which examples to give. If I want to specify a polynomial of degree 2, I can choose either 3 points, or 30 points. Which is easier? Specifically, given a specific Wcode, given two dataset of input-output examples, D1 and D2. Let Sol(D,Wcode) denote the set of programs in Wcode that satisfies D completely, in a classical sense. The question is, if Sol(D1, Wcode) = Sol(D2, Wcode), how do we quantify if synthesis is easier over D1 or over D2 ? i.e. which set, Variety(D1) or Variety(D2) is the more horrible extended object of Wcode?\n\nfinal recommendation:\nI maintain my score. I think this is an interesting piece of work that can easily be used as citations whenever the discussion of \"why don't you just relax your program to be differentiable\" comes up, and I can cite this paper and say \"no that does not work theoretically\".", "extra_scores": {}, "extra_text": {}}, {"review_id": "-JEuvp6AckQ", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper is very densely written with a lot of heavy mathematical formalism and not enough schematics to explain how it works. Most of the foundations are coming from theoretical computer science that is beyond my area of expertise. I spent many hours and still don't understand the point that the authors are trying to make. It seems to me that they are trying to use some extensions of the manifold variety in order to do program synthesis. They support their thesis with some theorems and assumptions around the geometry of program synthesis. The whole paper revolves around the zeros of the KL divergence between q(x,y) and p(y|x,w). They give a detailed analysis of these functions and justify why the Singular Learning Theory is appropriate for this study.\nFollowing the references wasn't easy. The paper is based on this work https://arxiv.org/pdf/1805.11813.pdf which is outside of my research area.\n\nI would suggest a revision and a lighter submission of the paper, I am not sure it is appropriate for this venue", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper is a bad fit for ICLR and the authors may consider submitting to more theoretical venues. This paper studies algebraic geometry (an area unfamiliar to most ICLR readers) of program synthesis, with the "hope that algebraic geometry can assist in developing the next generation of synthesis machines." Unfortunately, this paper does not get far enough down that path, and its implications cannot realistically be appreciated by an ICLR audience. The reviewers indicate that their low confidence is due to their lack of understanding of algebraic geometry and not due to their lack of understanding of program synthesis. The featured implication of the paper is that synthesized programs are singularities of analytic functions, which is not very meaningful to the ICLR audience. Even if external reviewers verified the correctness of the math, the ICLR audience would still not understand the implications. 
Decision: Reject