On the Uncomputability of Partition Functions In Energy-Based Sequence Models
Year: 2021

Abstract:
In this paper, we argue that energy-based sequence models backed by expressive parametric families can result in uncomputable and inapproximable partition functions. Among other things, this makes model selection—and therefore learning model parameters—not only difficult, but generally undecidable. The reason is that there are no good deterministic or randomized estimates of partition functions. Specifically, we exhibit a pathological example where under common assumptions, no useful importance sampling estimates of the partition function can guarantee to have variance bounded below a rational number. As alternatives, we consider sequence model families whose partition functions are computable (if they exist), but at the cost of reduced expressiveness. Our theoretical results suggest that statistical procedures with asymptotic guarantees and sheer (but finite) amounts of compute are not the only things that make sequence modeling work; computability concerns must not be neglected as we consider more expressive model parametrizations.

heading: 1 Introduction
text: Modeling discrete sequences is central to natural language processing and bioinformatics. Many common parametric sequence models ?̃ are (or can be cast as) energy-based (LeCun et al., 2006): they yield a weight ?̃(x) for any given string x. Although energy-based models (EBMs) of sequences need not represent probability distributions, they have been proposed as such to counter the inexpressivity of autoregressive sequence models (Bakhtin et al., 2021; Lin et al., 2021, §4.1). EBMs with finite partition functions / ?̃ , ∑ x ?̃(x) ∈ R>0 define distributions ?(x) , ?̃ (x)//?̃ over strings, which are often queried under the principle of probabilistic inference (Ghahramani, 2015).1
Energy-based sequence models are often parametrized as neural models. Each parameter vector ) in some parametric neural network family ⊆ R3 identifies a parametric model ?̃) , which then defines a parametric distribution over strings ?) , assuming / ?̃) exists (Chen et al., 2018). Contemporary neural networks have been shown to be very powerful. In particular, some popular parametric neural sequence model families, such as RNNs (Siegelmann & Sontag, 1995) and Transformers (Bhattamishra et al., 2020; Pérez et al., 2021), have been formally shown to recognize recursively enumerable languages: given any Turing machine " , there is a parameter vector ) ∈ such that the parametrized sequence model #) recognizes the same language as " does. In other words, these sequence model families are Turing-complete.
It is therefore intuitive that energy-based sequence models, backed by such powerful neural networks, form expressive families of string distributions (§3.1): for any decision algorithm " , there is a parameter vector )" in a Turing-complete parametric family , such that ?)" exists, and ?)" (x) is high if and only if " accepts x. It would seem assuring to work with such expressive family of sequence distributions, : assuming the true string probabilities indeed can be computed in polytime, is well-specified. Moreover, one may assume that given we can sample from ?)" , we would be able to use consistent estimators to find ) ′ ∈ , where ) ′ ≈ )" . Unfortunately, we find that with such an expressive distribution family , whether the identifiability assumption holds— required for most consistent estimators— itself is undecidable (Turing, 1937).
1Many popular energy-based sequence models compute normalized probabilities directly (i.e., ?̃(x) = ?(x)) (Jelinek, 1980; Katz, 1987; Bengio et al., 2003; Brown et al., 2020, inter alia). This makes both training and querying with string prefixes much easier, at the cost of expressiveness (Lin et al., 2021).
Moreover, model selection on any held-out data is also undecidable. Even worse, as long as a parametric family ′ contains one specific vector ) ′ ∈ , model selection will not be possible for ′ either— even when ′ itself is not necessarily expressive (e.g., ′ can be fixed-size Transformer EBMs, which cannot parametrize all EBMs that require more parameters). We construct one such ‘pathological’ distribution ?)′ as a Transformer EBM.
These negative results stem from the uncomputability and inapproximability of / . A main technical contribution of this paper is that there is no algorithm (either deterministic or randomized) that can approximate / well. Since statistical procedures are also algorithms, common randomized estimates are not useful in this scenario, either—however, we will see that for less expressive model families, such uncomputability issues do not arise. Our negative results are summarized in Table 1. To ensure that model selection is still possible (such that we can compare different parameter vectors with confidence),2 we have no choice but to resort to less expressive string distributions.
The paper is structured as follows. In §2 we review definitions and known results of weighted languages, sequence model families, and formalize weighted Turing machines, EC-complete parametric families, and computable estimates. In §§3–5 we describe our main technical results: there exist pathological EBM sequence models that have uncomputable partition functions, which cannot be approximated well under stochastic estimates, and do not have asymptotic estimates that have any good guarantees. In §6 we that argue our negative results make model selection impossible for expressive model families, and discuss why common estimation methods fail. Finally, we discuss three ‘palliative’ parametrization choices in §7, which all guarantee computable partition functions, at the cost of expressiveness.

heading: 2 Background

heading: 2.1 Energy-based sequence models
text: Energy-based models (EBMs) of sequences (LeCun et al., 2006; Rosenfeld et al., 2001; Sandbank, 2008; Huang et al., 2018; Bakhtin et al., 2021) are a family of discrete sequence models. Given a string x ∈ +∗ over a finite vocabulary + , an EBM ?̃ computes string weight ?̃(x), but not the (normalized) string probability ?(x) = ?̃ (x)/∑x ?̃ (x). In this work, we focus on EBMs whose weight is efficiently computable, i.e., polytime in the length of x. Following Bakhtin et al. (2021) and Lin et al. (2021), we wish to use our EBMs as probability distributions; this requires normalization. While EBMs are often intractable to normalize (e.g., the Ising model), the infinite domain of finite strings opens the door to uncomputable probabilities, which invite the impossibility of model selection and comparison.

heading: 2.2 Weighted languages
text: EBMs give weights to strings. Here we formally characterize these weighted strings as a weighted language. An unweighted language ! ⊆ +∗ is a set of finite strings x over a finite vocabulary + . A weighted language ?̃ is a function ?̃ : +∗ → R≥0.3 In this work, we discuss Boolean languages, such that + = B , {0, 1}. We also focus on weighted languages where distributions over strings exist. We say a weighted language ?̃ is normalizable when / ?̃ , ∑ x∈B∗ ?̃(x) ∈ R>0: the sum over all possible
2Of course, model selection (and computing / ?̃) are not always needed— for example, simply deciding whether ?̃(x1) > ?̃(x2) for two given strings x {1,2} . In such case the uncomputability issues we discuss are not a concern.
3With a slight abuse of notation, we define support( ?̃) , {x : ?̃(x) > 0}.
strings is finite and positive. / ?̃ is also called the partition function of ?̃.4 We can then normalize ?̃ into a distribution ? over B∗ such that ?(x) = ?̃(x)// ?̃ , and thereby ∑ x∈B∗ ?(x) = 1.
The efficiently computable (weighted) languages (EC; Lin et al., 2021) are those weighted languages ?̃, where a string’s weight (which must be non-negative) is a polytime function of the string. Weighted languages defined by most EBM sequence models fall into this class, since they score every string in finite time (and usually in polytime); and the scores ultimately are computed by some algorithm.
By definition, string weights of an EC language can be obtained as a side product from a Turing machine that recognizes x (in polytime). However, Lin et al. (2021) did not precisely describe how a Turing machine maps input string x to its (rational) weight ?̃(x) in finite time. In this work, such a construction (out of many possible ones) is necessary, as we need to show that this string weighting can be done by parametric sequence model families (see Appendix A).

heading: 2.3 Locally normalized distributions
text: A popular subclass of weighted languages is locally normalized weighted languages (LN), where conditional local distributions given prefix x̂: ?(· | x̂) can be computed in finite time. Since they automatically define a distribution over strings, we use the term locally normalized distributions interchangeably. If ?(· | x̂) can be computed in polynomial time, we call such distributions efficiently locally normalized distributions (ELN)— this is the weighted language class of most autoregressive models, just as its superset EC is the weighted language class of most energy-based sequence models.
Locally normalized distributions over sequences have ?̃(x) = ?(x), and / = ∑x∈B∗ ?̃(x) = 1. They are consistent: the probability that a string is infinitely long under such distributions is zero. Equivalently, given any n > 0, we can approximate / with a finite sum of string weights: Proposition 1 (Consistency of LN distributions (Booth & Thompson, 1973; Chen et al., 2018)). Let ? ∈ LN be a locally normalized distribution over strings. All strings of a given length or longer have their probabilities bounded. That is, for all positive real numbers n , there is a length = at which all strings x of length at least = have ?(x) < n .
The consistency property of locally normalized distributions implies that they have an exact sampling procedure that almost surely terminates in finite time. Therefore, they (and in particular ELN distributions) are an attractive choice as proposal distributions in parameter estimation procedures that alternate between expectation and maximization steps (Dempster et al., 1977).

heading: 2.4 EC-complete parametric families
text: We have introduced energy-based sequence models (§2.1) and their characterization as weighted languages (§2.2). However, we usually do not work with Turing machines directly in machine learning. Here the most common models of computation are (neural) sequence model families, such as RNNs and Transformers. While those computational models can appear quite dissimilar to state-machine-based models of computation (e.g., Turing machines), they have been shown to possess the same computation power (Siegelmann & Sontag, 1995; Pérez et al., 2021). That is, they are Turing-complete.
Just as we extend the definition of Turing machines to weighted Turing machines, we likewise formalize weighted sequence model families. We thus introduce EC-complete parametric families as a sequence model counterpart of the weighted language class EC. At a high level, a parametric family is EC-complete if given any ?̃ ∈ EC (as a description of a weighted Turing machine), we can construct a parameter vector ) ∈ ⊆ Q∗ which defines ?̃’s corresponding sequence model. The model produces an output embedding which we then decide in polytime to be either a ‘halting embedding’ or not. If it is, we can then extract the weight ?̃(x). (A rigorous exposition is in Appendix H.) We show that with a slight modification to positional embeddings, the family of arbitrary precision, hard attention Transformers defined in Pérez et al. (2021) is EC-complete:5 Theorem 1. The class of one-encoder-layer four-decoder-layer Transformer networks with positional encodings (=, 1/=, 1/=2, 2=) is EC-complete.
4We use the convention that / ?̃ is the partition function of ?̃, and /@̃ of @̃, etc. The subscript is omitted in unambiguous cases.
5All proofs omitted from the main text are included in the appendices. Proof sketches for major theorems are in the main text.
Proof sketch. We extend the construction from Pérez et al. (2021), adding an additional layer to accumulate the string weight over time steps.

heading: 2.5 Estimates
text: A main result of this work is that partition functions in an EC-complete family are uncomputable. Moreover, randomness does not help estimation; and correct asymptotic estimates are not useful. We define these estimates here in order to discuss the power of different estimates concretely.
Let be a parametric family. We say function 5 : → Q is an exact estimate if there exists a weighted deterministic Turing machine that takes ) as input, then upon halting outputs 5 ()) ∈ Q in finite time. Many estimation procedures are anytime algorithms: they do not have a predetermined runtime, and they can be stopped at any time before completion to produce a valid output. Output quality of an anytime algorithm may improve with increased runtime. Moreover, many of these algorithms have asymptotic guarantees, in that their outputs are optimal in some sense (e.g., consistency) in the limit. We capture these algorithms with asymptotic estimates: a function 5 ()) is an asymptotic estimate if there exists a weighted Turing machine that takes both ) and an index 8 as input, then outputs a value 5 ?̃,8 ∈ Q in finite time, such that the outputs converge toward 5 ()) as 8 increases toward infinity. (An example is /̂asym introduced at §5.)
We now extend both exact and asymptotic estimates to the stochastic case, where we compute the estimates using randomized algorithms instead of deterministic ones. As is conventional for randomized algorithms, we assume the use of probabilistic Turing machines. Probabilistic Turing machines have access to an infinitely long random tape. The tape describes an infinite binary sequence from tossing a fair two-sided coin infinitely many times.6 We define a randomized exact estimate f as a weighted Turing machine with two input tapes— the random tape g ∈ BN distributed according to ?g , and an input tape that has )—and outputs 5 () , g) in finite time. Likewise, we say f),8 is a randomized asymptotic estimate if there exists a function 5 ()) ∈ R and a weighted Turing machine that takes () , 8), g on two input tapes, so that for all random Boolean tapes g ∈ BN, we converge with lim8→∞ 5),8,g = 5 ()). Many Monte Carlo estimates can be seen as randomized asymptotic estimates, including rejection sampling and importance sampling estimates.

heading: 3 Expressiveness and uncomputability: pathological EBMs

heading: 3.1 Expressive sequence distributions
text: To illustrate the uncomputability issues of energy-basedmodels, we construct families of string distributions that are expressive: they require the full power of an EC-complete sequence model family.
We define ?̃",: ∈ G: to be a weighted language, parametrized by (", :), where a) " is a deterministic Turing machine that takes an empty string as input (‘input-free’); and b) : ∈ Q>0. Let !TM ⊆ B∗ be a prefix-free Boolean language of computation sequences of a Turing machine— that is, encodings of the trace of the Turing machine’s operations. We define
?̃",: (x) =  1/3 |x |+1 + : if x ∈ !TM, and x encodes a valid accepting trace of " . 1/3 |x |+1 otherwise. (1)
The weighted language ?̃",: can weight any string x of length = in time $ ( poly(=) ) by verifying whether x is an accepting execution trace of " , from the initial state to an halting state. That is, ?̃ ∈ EC (§2.2). We also know that for any (deterministic) machine " , the language’s partition function / ?̃",: exists, and it must equal either 1 or 1 + : , since there is either one halting trace (/ ?̃",: = 1 + :), or none (/ ?̃",: = 1). Therefore, each ?̃ ∈ G: defines a string distribution.7
6Formally speaking, we define a probability space (Ω,A, P) where Ω = BN is our sample space, A = { : ∈ P(Ω), all strings in share the same prefix ∈ B∗} is our event space, and P( ) = 2−= where = is the length of longest shared prefix of is our probability function (Stroock, 2014).
7Our construction of expressive sequence distributions is inspired by a weighted language construction in Lin et al. (2021) (see Appendix E) for further discussion.
Since for all : ∈ Q>0, G: ⊂ EC, all weighted languages ?̃",: have an equivalent parameter vector )",: in any EC-complete family . Also, since each G: is a bĳection between the set of all input-free Turing machines and a subset of , it follows that there is no exact estimate (§2.5) of the partition function of any EC-complete family (e.g., Transformer EBMs (Theorem 1)), by a reduction from Halt (Sipser, 2013): Theorem 2. Let be a parametric EC-complete sequence model family. And let : ⊂ be bĳective with G: . There is no : ∈ Q>0 for which there exists an exact estimate /̂: that takes as input ) ∈ : as input, and computes /̂: ()) = / ?̃) in finite time.
Proof sketch. : contains parametric vectors for all input-free Turing machines " . For any of these weighted languages, knowing the exact value of / ?̃",: ∈ {1, : + 1} is enough of deciding whether " halts (" halts iff / ?̃", 9 = : + 1). Since Halt is undecidable for input-free Turing machines, the algorithm /̂: cannot exist.
We note that the uncomputability of partition functions in other expressive model families, where Turing completeness also arises (Kempe et al., 2004; Chiang & Riley, 2020).

heading: 3.2 An EBM whose partition function is uncomputable
text: Theorem 2 states there is no estimate that ‘works’ for a subset of parameter vectors. While every G: is much smaller than its superset EC, G: is still (countably) infinite. Here under the assumption that ZFC is consistent, we construct one weighted language 1̃ ∈ G1 (for simplicity; it holds for arbitrary :), where /1̃ is uncomputable: Theorem 3. Assuming ZFC axioms and that assuming they is consistent, there exists an EC weighted language 1̃ ∈ G1 such that (a) /1̃ = 2 ∈ {1, 2} exists, but (b) there is no proof of /1̃ = 2.
Proof sketch. If there were a proof /1̃ = 1 then we proved ZFC is consistent, which is impossible under Gödel’s 2nd incompleteness theorem (Jech, 1994). If there were a proof /1̃ = 2, then we proved ZFC is not consistent, which violated our assumption.
The existence of 1̃ suggests that if there is an algorithm that approximates / ?̃ , and produces a witness of its approximation quality, then this algorithm will not work on any set of parameter vectors that can parametrize 1̃—even when this algorithm may work for some subsets of . This is useful in allowing us to show negative results regarding finite subsets of . Appendix B gives one such example.

heading: 4 No randomized algorithm can estimate / accurately.
text: We’ve shown by Theorem 2 that for an EC-complete family, there are no exact estimates than can get / perfectly right. In this section, we show that no randomized exact estimate for this is unbiased. Further, there isn’t even an estimate whose bias is within some multiplicative factor n , regardless of the variance’s magnitude. Lemma 1. Let be an EC-complete parametric family. There is no multiplicative factor n ∈ Q>1 for which every ) ∈ can have its partition function approximated with Ẑn ()) within a factor of n —with probability greater than 2/3. That is, we cannot have
% ( (1/n ) / ?̃) ≤ Ẑn ()) ≤ n/ ?̃) ) > 2/3. (2)
Proof sketch. Because Ẑn computes an estimate in finite time, it can only use finitely many distinct random tape segments. We therefore derandomize Ẑn by enumerating finitely many ‘random’ tapes, and can always return correct answer, given the 2/3 success probability assumption, and would be able to decide Halt, making use of distributions in Gn 2 .
Taken together, Theorem 2 and Lemma 1 state that no exact estimate /̂—whether randomized or deterministic— can approximate / with good confidence. In Theorem 4 below, we will make an even
stronger claim: regardless of the dispersion magnitude, it is impossible to bound the mean of random exact estimates of / to within any (computable) multiplicative factor. This theorem is based on the observation that the mean of Ẑn can be computed in finite time, by derandomizing Ẑn in a manner similar to our proof of Lemma 1: Theorem 4. Let be an EC-complete parametric family. There is no multiplicative bound n ∈ Q>1 such that there exists a randomized exact estimate Ẑn that guarantees 1/n ≤ E [Ẑn ()) ]//?̃) ≤ n , for every ) ∈ where ?̃) is normalizable.
Proof sketch. We derandomize the expectation of Ẑn .

heading: 5 Common asymptotic estimates do not give useful guarantees
text: Let’s now recap the progress we’ve made so far. We’ve shown that no (deterministic) exact estimate can get / exactly right in general (Theorem 2), lest it need to solve Halt. Further, no randomized exact estimate can approximate it within any given relative tolerance, with good confidence (Theorem 4).
But what about asymptotic estimates? We do know there are correct asymptotic estimates of / . For example, consider the following asymptotic estimate /̂ ()) backed by a weighted Turing machine that takes ) ∈ and 8 ∈ N as inputs, and returns 5),8 , ∑ x:x∈B∗ , |x | ≤8 ?̃) (x). We have lim8→∞ /̂),8 = / ?̃) , so /̂ is asymptotically correct. However, /̂asym does not have a convergence rate guarantee: for any 8 ∈ N, ‖ /̂),8 − / ?̃) ‖ is uncomputable. We also do not know how much can we improve our estimate when we increment 8. As Corollary 1 suggests, we likely cannot have such a guarantee.
In this section, we formalize such intuition for two popular asymptotic estimates: rejection and importance sampling methods (other asymptotic estimates are left as future work). Specifically, we show that any parametric family that is able to parametrize 1̃ from §3.2 cannot have provably useful locally normalized distributions (§2.3) as proposal distributions.

heading: 5.1 Rejection sampling estimate of / cannot be guaranteed to be possible.
text: Rejection sampling (Owen, 2013) is a common exact sampling method, applicable even when we cannot sample from an unnormalized distribution ?̃. We instead sample from an easy-to-sample distribution @, then stochastically reject samples, to ensure the probability a sample x is kept is proportional to ?̃(x). For rejection sampling to work, the candidate @’s support must contain the target ?̃’s entire support, so that all true points can be sampled. We also need some finite constant 2 so that 2@ envelops ?̃:
∃2 ∈ R>0 such that ∀x ∈ B∗, ?̃(x) @(x) ≤ 2.
We will show that for certain EBMs, one cannot formally guarantee the existence of an eligible @. Theorem 5. Using ZFC as our axiom set and assuming they are consistent, then there exists a normalizable EC weighted language ?̃, where there does not exist a consistent locally normalized proposal distribution @ ∈ LN, and 2@ ∈ Q>0, such that it can be proven ∀x ∈ B∗, ?̃ (x)/@ (x) < 2@ ≠ ∞.
Proof sketch. Let ?̃ = 1̃. If there were such @ and 2@ , we could in finite time prove / ?̃ = 1 or / ?̃ = 2, which contradicts Theorem 3.
Theorem 5 implies that there is no way of ensuring rejection sampling works, not only for any EC-complete families, but also for any parametric family that can parametrize 1̃.

heading: 5.2 Importance sampling estimate of / cannot be guaranteed to be effective.
text: Similar to the case of rejection sampling, one cannot guarantee an importance-sampling estimate of / to be ‘good’— in this case, we mean that there cannot be a proof that the importance sampling variance is finite, regardless of the sample size.
We first formalize importance sampling estimates of / in the manner of randomized asymptotic estimates (§2.5). We define
Ẑ@),# = 1 # #∑ ==1 ?̃) (x (=) ) @(x (=) )
to be an #-sample importance sampling estimate of / ?̃) under @, so all x (=) are samples from @ ∈ LN. We generally want to minimize the variance of Ẑ@),# under @: Var@ ( Ẑ@),# ) (Owen & Zhou, 2000). And
we certainly do not want Var@ ( Ẑ@),# ) = ∞. Unfortunately, for certain EBMs, we cannot guarantee there is a good locally normalized proposal distribution that has finite variance: Theorem 6. Let be an EC-complete parametric family. Assuming ZFC axioms and assuming they are consistent, there exists ) ∈ where there does not exist a consistent locally normalized “proposal” distribution @ ∈ LN such that it can be proven Var@ ( Ẑ@),# ) < 2 ≠ ∞, where 2 ∈ Q>0.
Proof sketch. Proven in a manner similar to the proof of Theorem 5.

heading: 6 Uncomputable / causes parameter estimation problems
text: Theorems 2 and 3 state that it is generally impossible to estimate partition functions in an expressive parametric family, such as certain subsets of an EC-complete family. Here we show how parameter estimation is made difficult as well: parameter identifiability is formally undecidable for an EC-complete family. Model selection is not possible, either, despite attempts to circumvent this (Table D.1).
6.1 Parameter identifiability under EC-complete families is undecidable
Consistency of many estimators relies upon the condition of parameter identifiability (Lehmann & Casella, 2006)— two different parameter vectors should define different string distributions. But we in general cannot ascertain whether this condition holds, even for finite subsets of an EC-complete family: Theorem 7. Let be an EC-complete family. There is no algorithm that takes )1 ∈ , )2 ∈ as input, and decides whether ?̃)1 and ?̃)2 are the same weighted language.
6.2 Model selection is generally impossible for EC-complete sequence model families
Theorem 7 suggests that consistency guarantees of common estimators do not hold, when used to estimate parameter vectors from . Nonetheless, such ‘off-label’ use of consistent estimators in an expressive parametric family is quite common—one usually just selects the best model )∗ among finitely many candidates (say {)1 . . . )# }) that achieves highest held-out likelihood: )∗ = arg max)=:1≤=≤# ∏ x∈D ?)= (x), where D is a set of strings.
However, Theorem 8 implies that model selection is generally impossible for EC-complete sequence model families: Theorem 8. For any ?̃ ∈ EC and for any EC-complete family , there is no algorithm Better ?̃ that takes two parameter vectors )1 ∈ , )2 ∈ , and returns YES if KL(? | |?)1 ) ≥ KL(? | |?)2 ), and NO otherwise, where ?, ?)1 , ?)2 are string distributions defined by ?̃, ?̃)1 , ?̃)2 respectively.

heading: 7 Palliative alternatives
text: What is a practitioner to do, given that this class of models is unlearnable in general? Note that a model family does not have to be EC-complete to suffer from model selection problems (§6.2)— for example, model selection is impossible for fixed-size Transformer networks with large enough 3’s either, by an extension to Theorem 8 (Theorem 11 in Appendix F).8 9 In other words, to ensure the problem of
8In addition to model selection issues, it may also be difficult to acquire unbiased gradients of log /: ∇ (log /) , 1//∇/ , which are needed for MLE-based training.
9Limiting ourselves to small 3’s to avoid uncomputability issues may not be practical; we leave finding the largest 3 that provably does not involve uncomputability problems— if it is even possible—as future work.
uncomputability does not haunt us, the best we can do is to cripple ?̃ so severely that uncomputability is impossible.
We identify three palliative choices that restrict the family of EBMs. Each cripples the model ?̃ in its own way, affording computability at the cost of expressiveness. The choice of triage infuses the model with an inductive bias; we must tailor our models based on our prior beliefs about the problem domain.
Restricting support( ?̃) to be finite. If ?̃ only assigns non-zero weights to finitely many strings, then / ?̃ is a finite sum of rational numbers, and is also rational. Here, sampling-based inference and estimation methods return to their usefulness. One way to ensure support( ?̃) is finite is by upper-bounding the maximum string length (e.g., Bakhtin et al. (2021)).
An obvious downside of the finite-support restriction is that we cannot deal with longer strings. Moreover, while / ?̃ is computable when support( ?̃) is finite, this quantity can still be practically inapproximable, assuming that ?̃ is expressive (e.g., ?̃ is an EC weighted language that has finite support), except for very short strings: assuming NP * P/poly, no randomized estimate of / ?̃ that is a good approximation can have a guaranteed $ (poly( |x |)) time complexity (Chandrasekaran et al., 2008). However, if ?̃ has limited expressiveness (e.g., when ?̃ is an Ising model where a string weight is the sum of pairwise weights), then FPRAS algorithms for approximating / ?̃ may exist when ?̃ describe a low-degree (≤ 2) graph (Jerrum & Sinclair, 1993; Luby & Vigoda, 1999). However, for high-degree graphs (≥ 3) it can be shown no FPRAS algorithm for approximating / ?̃ exists, assuming RP ≠ NP (Galanis et al., 2016).
Autoregressive parametrization of ?̃. An alternative choice is to confine ourselves to autoregressive models, i.e., locally normalized string distributions (§2.3). Under an autoregressive model ?, /? = 1 by definition. We also note that any (unnormalized) distribution ?̃ obtained by removing probability mass from ? will have a computable partition function, as long as ?̃ ∈ EC: Theorem 9. Let ? be any LN weighted language. Any ?̃ ∈ EC where ∀x ∈ +∗, ?̃(x) ≤ ?(x) has a computable / ?̃ .
Proof sketch. We construct an algorithm that approximates / ?̃ to any arbitrary error level in finite time, exploiting the consistency property of ? (Proposition 1).
Theorem 9 implies that conditionalization operations on ?, which remove strings from the support of ? to get weighted language ?̃, result in a computable / ?̃ (as long as we can decide which strings are removed); and such a ?̃ is therefore not subjected to the limitations of Theorem 4.
Unlike the ‘finite support’ fix, an autoregressively parametrized (or subsequently conditionalized) ?̃ can have an infinite support. A conditionalized ?̃ can have an intractable (although computable) partition function, however; and they are still subject to the expressive limitations imposed on LN languages: namely there is an EC language whose string weight rankings cannot be honored by any of such conditionalized ?̃ (Lin et al., 2021).
?̃ as low-treewidth factor graph grammars. Finally, we may limit ourselves to weighted languages defined by low-treewidth factor graph grammars (Chiang & Riley, 2020). Factor graph grammars is a generalization of factor graphs, which cover many classes of graphical sequence models, such as =-gram, HMM, and whole-sentence language models (Jelinek, 1980; Kuhn et al., 1994; Rosenfeld et al., 2001), linear CRF models (Lafferty et al., 2001), and weighted FSAs in general (Dreyer & Eisner, 2009): a factor graph grammar describes a (possibly infinite) set of factor graphs, generated from a hyperedge replacement graph grammar.
Assuming that an FGG contains at most one =-observed-node factor graph for all = ∈ N, it then defines a weighted language ?̃ (x) = ∏ k∈Ψ|x | k, where factor k is a positive function of nodes. The treewidth of an FGG, ( ) is the maximum number of nodes any k can be a function of, and Ψ |x | is the set of all factors of string length |x |. If / ?̃ ∈ R exists, it can be computed exactly in$ ( poly( | | exp(, ( ) + 1)) ) following Chiang & Riley (2020). Exact computation of / ?̃ may be manageable as long as, ( ) is small, which would allow us to exactly compute held-out data likelihood, and also train with a (marginalized) MLE objective function. However, a small, ( ) implies ?̃ cannot be expressive: such a grammar cannot capture phenomena like logical coherence (Cook, 1971).

heading: 8 Related work
text: Turing completeness of formal languages and associated uncomputability issues emerge repeatedly in computer science. For example, Turing completeness may emerge as an unwanted side effect in programming languages, since it implies undecidability. One of the best known examples is the Turing completeness of the C++ grammar (Veldhuizen, 2003; Josh, 2013), which makes both parsing and compiling C++ programs undecidable. Similar problems exist for Java (Grigore, 2016) and Haskell with (unrestricted) instance declarations (Wansbrough, 1998). Another example is the (possibly inadvertently introduced) Turing completeness of the page fault handling mechanism on modern computer systems, which raises security concerns in the context of trusted computing (Bangert et al., 2013).
Our work is not the first to discuss the consequences of computability in machine learning: assuming we can acquire training data from an oracle, under a supervised learning setting, recognition of an undecidable language is PAC-learnable (Lathrop, 1996). Ben-David et al. (2019) described a scenario where identifying a high-probability finite subset from a distribution is equivalent to proving the continuum hypothesis. Agarwal et al. (2020) extended the definition of PAC learnability (Valiant, 1984) to computable learners. By contrast, we are focused on the computability of EBMs for sequences, such as a language model as a component of a larger system for automatic speech recognition. Designing an appropriate, efficient loss functional is a challenge that several prior works have compared (see Appendix D).
Lin et al. (2021) noted autoregressive factors of EC languages can be uncomputable (see also Theorem 10). They also noted that a weighted language can have an uncomputable partition function (presumably resulting from the sum over infinitely many string weights). But they did not dwell on the question whether such a weighted language could lie within the EC class, much less providing a constructive proof (see also Appendix E). Instead, they emphasized that under the assumption that oracular access to trained parameter strings is possible, arbitrarily good approximations of the (possibly uncomputable) partition function can be memorized in the (autoregressive) model parameters. There is an interesting constrast between the stances of Lin et al. (2021) and our work: Lin et al. (2021) saw the uncomputability of / as a trivial issue from the model capacity viewpoint, since good approximations take few bits in the parameters to store. On the other hand, we see that the uncomputability problem can be a parameter estimation disaster— there will be no guarantee of good approximations can be found in finite time at all.

heading: 9 Conclusion and future work
text: Energy-based models are posed as an efficient tool for decision problems, circumventing probabilities and expensive normalization (LeCun et al., 2006). Extending this vision to generic sequence models, though, can involve complexity/computability problems that are difficult, or even impossible. We’ve shown that as energy-based sequence models become more powerful, the partition function becomes uncomputable— even when we are restricted to polytime-computable weighted languages. Exact estimates, even if randomized, cannot have accuracy guarantees. Popular asymptotic estimates on the other hand are not useful either. Furthermore, model selection is generally impossible, even if we limit ourselves to fixed-size sequence model families.
This paper continues a discussion started by Lin et al. (2021), who posture energy-based models as a more powerful alternative to autoregressive sequence models. Autoregressive sequence models, after all, have wide adoption and empirical successes (Radford et al., 2019; Brown et al., 2020). By contrast, more general neural energy-based sequence models have not caught on. Why not? We give unlearnability— due to uncomputability—as a possible explanation: unless we give up the ability to learn parameters from data, we likely cannot use the full expressiveness afforded by powerful neural networks. Just like the model capacity problems brought up by Lin et al. (2021), this result is independent of the amount of training data.
We emphasize that our results do not invalidate the findings of Lin et al. (2021): regardless of the actual neural parametrization, autoregressive models can never capture certain distributions that energy-based models can. Instead, one of our main messages is that we may not be able to find those EBM parameters in finite time, if we do not know what the parameters are. Of course, if we know the task perfectly well and can in fact manually assign the model parameters, we will not need to learn from data at all. The middle ground—when we have some prior knowledge about the task, but cannot really design the parameter vectors— is an interesting direction for future work: the three palliative alternatives outlined in §7 do not take task-specific information into account at all. Can we do better than that, without suffering uncomputability problems?

heading: A Weighted Turing machines
text: We extend the definition of Turing machines into weighted Turing machines as follows. A weighted Turing machine " is described as a 7-tuple (&,Σ, X, @init, , update_num, update_denom), where the first 5 components (&,Σ, X, @init, ) have definitions following that of standard Turing machines. The last two additions are weight-update functions: both update_num and update_denom have signature & → A, where A , {same, carry}. At the end of time step 8, assuming the current state is @, we define
num8 = { num8−1 if update_num(@) = same 28 + num8−1 if update_num(@) = carry
and similarly,
denom8 = { denom8−1 if update_denom(@) = same 28 + denom8−1 if update_denom(@) = carry.
To keep our proof of model family capacity brief, we (arbitrarily) define that ∀@ ∈ ∪ {@init}, update_num(@) = update_denom(@) = same. Finally, upon arriving at a halting state ∈ in A time steps, we say numA/denomA is the weight of an input x ∈ B∗ under " , if numA/denomA is a rational number.10

heading: B Negative results possible on finite parameter subspaces
text: In subsection 3.2, we mention that the pathological EBM 1̃ can show negative results regarding finite subsets of . Here, we provide a concrete example. Corollary 1. Assuming ZFC axioms and assuming they are consistent, there exists ) ∈ such that / ?̃) ∈ Q>0 exists, but there is no algorithm /̂proof that takes ) ∈ as input, and outputs a set of strings {x= : = < #}, # ∈ N where
• there is a proof that ∑# ==1 ?̃) (x) ≥ 1/2/ ?̃) ; or
• there is a proof that ∑# ==1 ?̃) (x) < 1/2/ ?̃) .
Corollary 1 states that there exists a ‘problematic EBM’—namely 1̃—where we cannot guarantee to well approximate its partition function, by accumulating finitely many string weights, regardless of the manner of accumulation (i.e., how we choose strings) or the number of strings we enumerate over. We discuss this in further details in §2.5.

heading: C Proofs of theorems from main text
text: Theorem 1. The class of one-encoder-layer four-decoder-layer Transformer networks with positional encodings (=, 1/=, 1/=2, 2=) is EC-complete.
Proof. To model all weighted Turing machines defined in §2.2, we extend the Turing-complete oneencoder-layer three-decoder-layer Transformer network construction introduced by Pérez et al. (2021) with one additional layer. We also modify the original positional embedding function pos : N→ Q3 to include a new component. In this proof, we let
pos(8) = [0, . . . , 0, 1, 8, 1/8, 1/82, 28]
instead of pos(8) = [0, . . . , 0, 1, 8, 1/8, 1/82] as in Pérez et al. (2021). For the sake of clarity, our construction is a ‘stack-on’ construction: the encoder layer and the first 3 decoder layers are largely identical to the design of Pérez et al. (2021), with the only difference being
10When numA/denomA is not a rational number (because denomA = 0), we say the weight of input string x is undefined. However, we do not encounter that in this work: all strings in an EC language have rational weights. In any case, we only require that our family contain weighted Turing machines that return rational numbers, not that they be the only members.
necessary changes to accommodate our one additional positional embeddings component.11 It may be possible to strengthen our results by showing that one-encoder-layer three-decoder-layer Transformer networks with the original positional embeddings— the parametrization family Pérez et al. (2021) showed to be Turing-complete— are EC-complete as well, with a more involved construction. We leave such an improvement as future work.
We claim our fourth layer of the decoder has output yA = y′A + wA , where • y′A is a zero-padded version of the original Transformer output embeddings from Pérez et al. (2021). y′A is of the form
[J@A K, JBA K, < (A−1) , 0, . . . , 0] where J@A K denotes an one-hot vector of size |& | where the @A -th component is 1 (again following the notation of Pérez et al. (2021)).
• And wA is of the form
[0@ , 0B , 0,numA , denomA , 0, . . . , 0] (3)
where numA ∈ N ∪ {0} and denomA ∈ N ∪ {0} are defined in §2.2. Now we describe how wA can be computed from [y′0 . . . y ′ A ] using the attention mechanism, with the help of our new positional embeddings. Specifically, we want to show that we can construct feedforward networks &4, 4, and +4 such that
y8 = Att ( &4 (y′′8 ), 4 (Y′′8 ), +4 (Y′′8 ) ) where y′′
8 = y′ 8 + pos(8), Y′ = [y′1 . . . y ′ 8 ], and Y′′8 = Y′ + [pos(1), . . . , pos(8)]. We let
&4 (y′′) = [0, . . . , 0, 1, 0, 0, 0, 0] be a constant vector, and 4 (Y′′8 ) = Y′′8 . Finally, we let +4 (Y′′8 ) = [0@ , 0B , 0, I(update_num(@8) = carry)28 , I(update_denom(@8) = carry)28 , 0, . . . , 0]. &4 is a constant function (such that it always attends to the unity component of Y′′8 ), so it can be implemented as a single-layer feedforward network. 4 is the identity function, which can also be implemented as a single-layer feedforward network. +4 on the hand can be implemented as a fixed-size feedforward network, with the piecewise-linear sigmoidal function f: in the case of denom8 , the network would first project @8 to a = [I(update_denom(@8) = carry), I(update_denom(@8) = same)] (using the one-hot J@8K segment from y′
8 ), multiply it by b = [28 , 0] (with the help of nonlinearity from f), and
put a ⊗ b at the position of denom8 in equation (3). The component at num8 in equation (3) can be computed likewise.
Given any position A ∈ N, we have
yA = Att(&4 (y′′A ), 4 (Y′′A ), +4 (Y′′A )) = [0@ , 0B , 0,
1 A A∑ 8=1 I(update_num(@8) = carry)28 ,
1 A A∑ 8=1 I(update_denom(@8) = carry)28 ,
0, . . . ,
0] .
Let extract_avg_num(yA ) be an affine transformation that extracts the ( |& | + |Σ| + 2 )nd component from yA , and extract_avg_denom(yA ) be an affine transformation that extracts the ( |& | + |Σ| + 3
) rd 11Since we increase the output embeddings’ dimension by 1, we also need to pad all matrices in the original construction by additional zero columns/rows, such that our new positional embeddings’ new component has no effect on any computation in the encoder layer, and the first 3 decoder layers.
component from yA , we have
extract_avg_num(yA ) extract_avg_denom(yA ) = ∑A 8=1 I(update_num(@8) = carry)28∑A 8=1 I(update_denom(@8) = carry)28
= numA
denomA
which is the weight of input x = [G1 . . . G) ] as we defined in §2.2.
Theorem 2. Let be a parametric EC-complete sequence model family. And let : ⊂ be bĳective with G: . There is no : ∈ Q>0 for which there exists an exact estimate /̂: that takes as input ) ∈ : as input, and computes /̂: ()) = / ?̃) in finite time.
Proof. We can reduce Halt to computing our partition function. For the sake of contradiction, let us assume that for some : ∈ Q>0, the exact estimate /̂ exists. Our reduction from Halt of input-free Turing machines is as follows: Given any deterministic input-free Turing machine " , we build a weighted deterministic Turing machine: " ′ (Appendix A). " ′ takes as input x ∈ B∗, and outputs weight 1/3 |x |+1 + : when x is an accepting trace of " ′. Otherwise, " ′ outputs weight 1/3 |x |+1. " ′ always returns a weight for x in polytime. By the assumptions of EC-complete families (§2.4), we can build a parameter vector ) ∈ such that ?̃" ′ = ?̃) . Since from the definitions of G: we know ?̃" ′ = ?̃",: , we have ) ∈ : .
We have thus completed our reduction: if /̂: existed, we could decide whether any given input-less deterministic Turing machine " halts, by first constructing the weighted Turing machine " ′, then the corresponding ) . By our assumption, /̂: ( ?̃)) = : + 1 if and only if ∃x ∈ B∗ that is an accepting path of " ′, which is true if and only if " halts for some finite steps. Since whether " halts is undecidable, we have arrived at a contradiction (Turing, 1937; Sipser, 2013). Therefore for all : ∈ Q, the algorithm /̂: does not exist.
Theorem 3. Assuming ZFC axioms and that assuming they is consistent, there exists an EC weighted language 1̃ ∈ G1 such that (a) /1̃ = 2 ∈ {1, 2} exists, but (b) there is no proof of /1̃ = 2.
Proof. Our proof hinges on Gödel’s second incompleteness theorem: no consistent axiomatic system which includes Peano arithmetic (e.g., ZFC) can prove its own consistency. We construct a Turing machine "1 that enumerates all provable propositions under ZF, and halts if only if "1 proves the proposition 1 = 0. One such "1 with 7, 918 states has been built by Yedidia & Aaronson (2016).12
"1 is an input-free deterministic Turing machine. We construct a weighted Turing machine " ′ from "1 , in the manner of the proof of Theorem 2. We let " ′ return weight 1 + 1/3 |x |+1, in the case "1 halts with trace x. " ′ returns a weight in polytime, and therefore defines a weighted language 1̃ ∈ G1 ⊂ EC. We know from the definitions of G1 that /1̃ is either 1 or 2. Assume to the contrary that there exists a proof that /1̃ = 1. Then we know "1 did not halt. And therefore the proof would also imply that ZFC is consistent, which violates Gödel’s second incompleteness theorem. On the other hand, if there were a proof that /1̃ = 2, it would imply "1 halted and ZFC is not consistent. We therefore arrive at a contradiction.
Corollary 1. Assuming ZFC axioms and assuming they are consistent, there exists ) ∈ such that / ?̃) ∈ Q>0 exists, but there is no algorithm /̂proof that takes ) ∈ as input, and outputs a set of strings {x= : = < #}, # ∈ N where
• there is a proof that ∑# ==1 ?̃) (x) ≥ 1/2/ ?̃) ; or
• there is a proof that ∑# ==1 ?̃) (x) < 1/2/ ?̃) .
Proof. Assuming to the contrary that /̂proof existed. We construct ) ∈ such that∀x ∈ B∗, ?̃) (x) = 1̃(x). Either proof resulting from /̂proof ()): {x= : = < #} can be used to prove or disprove the consistency of ZFC.
12Subsequent efforts have led to a construction of "1 with 748 states: https://turingmachinesimulator. com/shared/vgimygpuwi.
Lemma 1. Let be an EC-complete parametric family. There is no multiplicative factor n ∈ Q>1 for which every ) ∈ can have its partition function approximated with Ẑn ()) within a factor of n —with probability greater than 2/3. That is, we cannot have
% ( (1/n ) / ?̃) ≤ Ẑn ()) ≤ n/ ?̃) ) > 2/3. (2)
Proof. In this proof, we make use of the distribution family Gn 2 (§3.1). We assume to the contrary that a multiplicative bound n satisfying equation 2 exists. Recall that our assumptions state that % ( 1/n ≤ Ẑn ())//?̃) ≤ n ) > 2/3.13 Let " be an input-free Turing machine. And let ?̃) = ?̃",n 2 ∈ Gn 2 where ) ∈ . if a Turing machine " halts, / ?̃",n 2 = 1 + n 2; therefore,
% ( (1 + n2)1/n ≤ Ẑn ()) ≤ (1 + n2)n ) > 2/3. Similarly, if " does not halt, we have / ?̃
",n 2 = 1; therefore, % ( 1/n ≤ Ẑn ()) ≤ n ) > 2/3. By combining the two conditions, we know that I(" halts) =
I(Ẑn ()) ≥ n + 1/n ∧ Ẑn ()) > n) = I(Ẑn ()) ≥ n + 1/n ). Therefore, given (1/n ) / ?̃) ≤ Ẑn ()) ≤ n/ ?̃) , we can decide if " halts by checking if Ẑn ()) ≥ n + 1/n . Since the condition (1/n ) / ?̃) ≤ Ẑn ()) ≤ n/ ?̃) only holds 2/3 of all time, we then derandomize the randomized Ẑn to get a deterministic estimate: recall that a randomized exact estimate finishes computation in finite time, regardless of the content of the random tape g. There, there are only finitely many finitely long possible ‘random’ sequences that /̂n will read, which we can enumerate. More concretely:
% ( Ẑn ()) ≥ n + 1/n ) = E g [ I(/̂n () , g) ≥ n + 1/n ) ] =
∑ g∈B<), n 1/2<), n I(/̂n () , g) ≥ n + 1/n ) (4)
where <), n ∈ N is the maximum prefix length of the random tape that /̂n () , g) will use on any g ∈ BN. Again <), n is guaranteed to exist because of our assumption /̂n () , g) ends in finite time. Since equation (4) is a finite sum of computable functions, it is also computable.
From the computability of equation (4), it follows that we can derive a deterministic algorithm from Ẑn that decides whether an arbitrary input-free Turing machine halts, which is not possible. Therefore, there is no n ∈ Q>1, such that the randomized exact estimate Ẑn satisfies the multiplicative bound %(1/n ≤ Ẑn ( )// ≤ n) > 2/3 for all ) ∈ .
Theorem 4. Let be an EC-complete parametric family. There is no multiplicative bound n ∈ Q>1 such that there exists a randomized exact estimate Ẑn that guarantees 1/n ≤ E [Ẑn ()) ]//?̃) ≤ n , for every ) ∈ where ?̃) is normalizable.
Proof. We define g to be distributed according ?g . Therefore the mean E [Ẑn ())] can be expanded as Eg∼?g [Ẑn ())] = ∑ g∈BN ?g (g) /̂n () , g). Following the same derandomization technique in the proof of
Lemma 1, we can find some < ∈ N such that ∑g∈BN ?g (g) /̂n () , g) = ∑g∈B< 1/2< /̂n () , g) in finite time. And subsequently, we can compute E [Ẑn ())] exactly in finite time. Let the exact estimate be / n . We then have / n ()) = E [Ẑn ())].
Assuming to the contrary that we could guarantee 1/n ≤ / n ()) ≤ n . Since / n is a deterministic estimate, we have can write %(1/n ≤ / n ()) ≤ n) = 1, which contradicts Lemma 1. Therefore such an estimate / n ()) does not exist.
(Below is our old proof that is only kept during the author response period, for reference purposes only. We are grateful to reviewer NAcm for simplifying it.)
To show this contradiction, we invoke the Berry–Esseen theorem (Berry, 1941, inter alia), a tighter version of the central limit theorem. It specifies not simply the fact of the sample mean’s convergence to a normal distribution, but also the rate of this convergence. As the rate is measured in terms of the third
13As is common, e.g., in defining the complexity class BPP (see Arora & Barak 2006), the fraction 2/3 is arbitrary. Any proportion bounded away from 1/2 will work.
absolute moment, let us first show a lemma that key estimands of the distribution are computable in finite time. Every randomized exact estimate f is guaranteed to have a finite and computable variance, and it will also have a finite and computable third absolute moment. More formally, the lemma is: Lemma 2. Let f ()) be a randomized exact estimate (§2.5). These three quantities are finite and computable:
• The mean ` = Eg [f ())], • The variance f2 = Eg [(f ()) − Eg [f ())])2], and • The third absolute moment V3 = Eg [|f ()) − Eg [f ())] |3].
Proof. Similar to the proof of Lemma 1, the key idea of this proof is that while the set of all random tapes BN is uncountably infinite (as can be seen from Cantor’s diagonalization argument), the randomized Turing machine behind f: 5 () , g) can only make use of some finite-length prefix of g, which implies that both the variance and third absolute moment can be computed as a finite sum of rational numbers. We show our result for the mean; we omit the similar proofs for the variance and third absolute moment.
Observe that the mean adds up finitely many rational terms:
E g∼?g [f ())] = E g∼?g [ 5 () , g)] = ∑ g∈B< 1/2< 5 () , g) ∈ Q,
where < is the (finite) greatest length of random tape used by 5 . The finite-time assumption requires that this greatest length must exist.
We can therefore compute the mean Eg [f] by the following algorithm: 1. First, determine < by trying all possible maximum lengths. For each 8 ∈ N beginning from 8 = 1, we attempt to simulate 5 () , g) on every finite ‘random tape’ g ∈ B8 . If the probabilistic Turing machine computing 5 () , g) moves beyond position 8 on g, then we know that < > 8. We terminate this simulation, then increment our counter 8 ← 8 + 1 and attempt simulation again. Otherwise, we terminate with the conclusion that < = 8.
2. Having computed the maximum length < in the previous step, we can compute the finite summation ∑ g∈B< 1/2< 5 () , g) in finite time.
This algorithm constructively completes the proof: the mean is computable in finite time.
Proof. We will show by contradiction that if the bound n were to exist, then we could solve the halting problem by a derandomization procedure similar to that in Lemma 1. For the sake of contradiction, assume that some multiplicative factor n ∈ Q>1 admits a randomized exact estimate Ẑn , where for every normalizable ) ∈ , we can bound the relative error of Ẑn :
1 n ≤ E [Ẑn ())] / ?̃) ≤ n .
We again make use of the distribution family Gn 2 (§3.1). Let n 2 be the bĳection from Gn 2 onto . If such a factor n exists, then from our multiplicative bound assumption, we know for any ?̃",n 2 ∈ Gn and its corresponding parametric model ?̃) , the behavior of the expected value depending on whether " halts: if yes, then (1 + n2)1/n ≤ E [ Ẑn ()) ] ≤ (1 + n2)n ; meanwhile if no, then 1/n ≤ E [ Ẑn ()) ] ≤ n . In either case, for any / ′ ∈ (E [Ẑn ())] − 1/n ,E [Ẑn ())] + 1/n ), deciding whether / ′ > 1/n is equivalent to deciding whether " halts:
I(/ ′ > 1/n ) = I(" halts). (5)
We can now construct an estimate of the partition function from finite samples. Let Ẑ′ n ,# ()) ,∑#
8=1 Ẑ (8) n ())/# be the sample mean of /̂n () , g) over # i.i.d. random tapes g8 . Because /̂n () , g) can be computed in finite time, the mean can be computed by simulating the # independent runs of /̂n () , g8) on a single random tape g.
A well-known result is that the sample mean Ẑ′ n ,# ()) is an unbiased estimator of the population mean: E [Ẑ′n ,# ())] = Ẑn ()), regardless of the number of samples # . We will use this as the mean in the next paragraph.
From Lemma 2, we know that both the variance f2 and the third absolute moment V3 of Ẑn ,# ()) are positive and rational. We can now invoke the Berry–Esseen theorem to provide bounds on our randomized exact estimate. Taking as the cumulative distribution function of the zero-centered variable Ẑ′ n ,# ()) √ #−E [Ẑ′n ,# ()) ] f , we have:
sup I∈R | (I) −Φ(I) | ≤ V3 f3 √ # , (6)
where is a constant whose value is known to be less than 0.8 and Φ is the standard normal CDF. Intuitively, equation (6) claims that as # approaches infinity, the distribution of the sample mean Ẑ′
n ,# ())
approaches a Gaussian centered at the true value E [Ẑ′n ,# ())] = E [Ẑn ())] with variance f 2/# . The error in this approximation to the CDF is bounded below $ (1/√# ). This result can help us reason about the counterexample distributions in Gn 2 . For every counterexample distribution ?̃ ∈ Gn 2 , and its corresponding parameter vector ) ∈ n 2 , there are a minimum number of samples # ?̃ and a positive factor _ ?̃ such that for samples with at least # ?̃ elements, the interval ` ± a is containedwithin the intervalE[Ẑn ())]±1/2n ,where ` , Ẑ′n ,#?̃ ()), and a , _ ?̃ ·f/ √ # . This in turnmeans that%(E [Ẑn ())]−1/2n ≤ Ẑ′n ,#?̃ ()) ≤ E [Ẑn ())]+1/2n ) > 2/3. Since I(Ẑ ′ n ,#?̃ ()) > 1/n ) = I(" halts) by equation (5), We therefore have a randomized exact estimate I(Ẑ′ n ,#?̃ ()) > 1/n ) that is correct with probability > 2/3. But this is impossible: by a derandomization method similar to that in the proof of Lemma 1, we would have a deterministic algorithm that takes as input an arbitrary input-free Turing machine " , builds both ?̃",n 2 ∈ Gn 2 and then ) ∈ n 2 , and finally uses ) to decide whether " halts. Therefore, our assumption must be wrong: no value of n ∈ Q>1 can bound the error of Ẑn .
Theorem 5. Using ZFC as our axiom set and assuming they are consistent, then there exists a normalizable EC weighted language ?̃, where there does not exist a consistent locally normalized proposal distribution @ ∈ LN, and 2@ ∈ Q>0, such that it can be proven ∀x ∈ B∗, ?̃ (x)/@ (x) < 2@ ≠ ∞.
Proof. By contradiction; let ?̃ = 1̃, where 1̃ is first introduced in §3.2. Assume that there exists @ ∈ LN where it is proven that ∀x ∈ B∗, ?̃ (x)/@ (x) < 2 < ∞, where 2 ∈ Q>0. We can either prove ZFC is consistent, or is inconsistent, as follows:
1. By our assumptions, @ ∈ LN scores every string x as @) (x) 5 ()) ∈ Q>0. Also, because @ is consistent and locally normalized, there exists = ∈ N such that we can prove ∀x ∈ X>={x : x ∈ B∗, |x | > =}, @(x) < 1/2 (Proposition 1). We will just prove the existence of = constructively by enumerating the strings in B∗ in increasing length. Let the complement set X≤= = B∗ − X>=. 2. The proof then examines the finitely many strings in X≤=. (a) If any of these strings x′ has 1̃(x′) > 1, then we know x′ encodes an accepting trace of
"1 (§3.2). Therefore, "1 halts, which implies there is a proof of the inconsistency of ZFC. (b) If none of these strings ∈ X≤= has 1̃(x) > 1, then we know there is also no string
x′′ ∈ X>=, such that 1̃(x′′) > 1. This is because of our assumption 2 ≥ 1̃ (x)/@ (x), which in turn means that 1̃(x) is less than 1 on these long strings X>=. Therefore, "1 does not halt, which implies there is a proof of the consistency of ZFC.
Assuming ZFC is consistent, neither a proof of ZFC, or a disproof of ZFC, is possible. We have therefore therefore arrived at a contradiction. Therefore, @ does not exist.
Theorem 6. Let be an EC-complete parametric family. Assuming ZFC axioms and assuming they are consistent, there exists ) ∈ where there does not exist a consistent locally normalized “proposal” distribution @ ∈ LN such that it can be proven Var@ ( Ẑ@),# ) < 2 ≠ ∞, where 2 ∈ Q>0.
Proof. let ?̃ = 1̃, where 1̃ is first introduced in §3.2. Assume that there exists @ ∈ LN where it is proven that Var@ (Ẑ@),# ) = : < 2 ∈ Q<0 ≠ ∞.
We have
Var@ (Ẑ@),# )
, 1 # { ∑ x∈B∗ [( ?̃) (x) @(x) )2 @(x) ] − / ?̃) } = / 2?̃)/# ( ∑ x∈B∗ ?2) (x) @(x) − 1
) = :,
where ?) (x) , ?̃) (x)/?̃) . After some manipulation, we have∑ x∈B∗ ?2) (x) @(x) = #: + / ?̃) 2
/ ?̃) 2︸ ︷︷ ︸
=B≤# :+1
.
Since ∀x ∈ B∗, ? 2 ) (x) @ (x) ≥ 0, we have
∀x ∈ B∗, ?2) (x) @(x) ≤ B; (7)
in particular, if x′ encodes a halting trace of "1 , from §3.1 we know
?) (x) = ?̃) (x) / ?̃)
= 1 + ( 13 ) |x |+1 2 > 1/2. (8)
Combining equations (7) and (8), we have for any halting trace x′ of "1 ,
1 4@(x′) < ?2) (x) @(x) ≤ B.
After some more arrangement,
@(x′) ≥ 1/4B ≥ 1 4(#: + 1) ≥ 1 4(#2 + 1) > 0.
As in the proof of Theorem 5, the existence of such a @ allows us to either prove or disprove the consistency of ZFC. For the sake of completeness, we include a proof sketch below:
1. By our assumptions, @ ∈ LN scores every string x as @) (x) 5 ()) ∈ Q>0. Also, because @ is consistent and locally normalized, there exists = ∈ N such that we can prove ∀x ∈ X>={x : x ∈ B∗, |x | > =}, @(x) < 14(#2+1) (Proposition 1). We will just prove the existence of = constructively by enumerating the strings in B∗ in increasing length. Let the complement set X≤= = B∗ − X>=. 2. The proof then examines the finitely many strings in X≤=. (a) If any of these strings x′ has ?̃) (x′) > 1, then we know x′ encodes an accepting trace of
"1 (§3.2). Therefore, "1 halts, which implies there is a proof of the inconsistency of ZFC. (b) If none of these strings ∈ X≤= has ?̃) (x) > 1, then we know there is also no string
x′′ ∈ X>=, such that ?̃) (x′′) > 1, since ?̃) (x′) > 1 ⇐⇒ 1̃(x′) > 1 ⇐⇒ "1 halts; and we have already shown that for any accepting trace x′ of "1 , @(x′) ≥ 1/4(#2+1). Therefore, "1 does not halt, which implies there is a proof of the consistency of ZFC.
Assuming ZFC is consistent, neither a proof of ZFC, or a disproof of ZFC, is possible. We have therefore therefore arrived at a contradiction. Therefore, such a @ does not exist.
Theorem 7. Let be an EC-complete family. There is no algorithm that takes )1 ∈ , )2 ∈ as input, and decides whether ?̃)1 and ?̃)2 are the same weighted language.
Proof. Assuming to the contrary that such an algorithm Distinct exists. We would be able to reduce Halt of input-free Turing machines to Distinct: we first construct )1 ∈ such that ?̃)1 (x) = 1/3 |x |+1. We then construct )2 ∈ such that ?̃)2 = ?̃",1 ∈ G1 (§3.1). Distinct()1, )2) is YES if and only if " halts.
Theorem 8. For any ?̃ ∈ EC and for any EC-complete family , there is no algorithm Better ?̃ that takes two parameter vectors )1 ∈ , )2 ∈ , and returns YES if KL(? | |?)1 ) ≥ KL(? | |?)2 ), and NO otherwise, where ?, ?)1 , ?)2 are string distributions defined by ?̃, ?̃)1 , ?̃)2 respectively.
Proof. By contradiction; assume that for some ?̃ ∈ EC, better ?̃ exists. We know there exists a weighted Turing machine (also denoted as ?̃) that on any string x, terminates in $ (poly( |x |)) and outputs ?̃(x) (Appendix A).
We show how we can reduce from Halt to better ?̃ . Given any arbitrary input-less Turing machine " , we can define a new weighted Turing machine ?̃′
" that on input string x, ?̃′ first simulates ?̃ on it and
keeps a record of ?̃(x) somewhere on the tape. ?̃′ then verifies whether x is an encoded accepting trace of " . If x is indeed an encoded accepted trace of " , ?̃′ outputs ?̃(x) + 1. Otherwise ?̃′ outputs ?̃(x). Let )1 ∈ parametrize ?̃′, and let )2 ∈ parametrize ?̃, such that ?̃)1 (x) = ?̃′(x), ?̃)2 (x) = ?̃(x),∀x ∈ B∗. We know that KL(? | |?) = 0 for any distribution ?. better ?̃ ()1, )2) returns YES if and only if KL(? | |?)1 ) = 0 ≥ KL(? | |?)2 ), which implies that ?̃)2 and ?̃)1 define the same distribution, which in turn implies that ∀x ∈ B∗, ?̃(x) = ?̃′(x), and that " never halts. Similarly, better ?̃ ()1, )2) returns NO if and only if " halts. We have thus completed our reduction from Halt; and therefore algorithm better ?̃ does not exist for all ?̃ ∈ EC.
Theorem 9. Let ? be any LN weighted language. Any ?̃ ∈ EC where ∀x ∈ +∗, ?̃(x) ≤ ?(x) has a computable / ?̃ .
Proof. We prove Theorem 9 by constructing an algorithm /̂ ?̃ : Q>0 → Q>0 that approximates / ?̃ within any desired positive rational error n : namely |/̂ ?̃ (n) − / ?̃ | ≤ n .
Let /̂= = ∑= ℓ=1 ∑ x: |x |=ℓ ?(x). We first observe that lim=→∞ /= = 1 by Proposition 1. In other words, lim=→∞ 1 − /̂= = 0, or equivalently, given any n > 0, there exists = ∈ N such that for all =′ > =, =′ ∈ N, (1 − /̂=′) < n . Therefore, given any n > 0, ∃= ∈ N that divides B∗ in two sets: X≥= = {x : x ∈ B∗, |x | ≥ =}, where∑
x∈X≥= ?(x) < n , and X<= = B∗ − X≥=. We are guaranteed to find = by enumerating all candidates from N.
We can thus implement /̂ ?̃ as the following program: given n ∈ Q>0, we first find the smallest = ∈ N, and partition B∗ into two sets X<=, X≥= as we described in the previous paragraph. We then return /̂ ?̃ (n) = ∑ x∈X<= ?̃(x).
We argue that /̂ ?̃ is a computable function. We first repeat that since = ∈ N exists, we will find = in finite time, simply by enumerating. And since the set X<= ⊂ B∗ is finite, /̂ ?̃ (n) = ∑ x∈X<= ?̃(x) can computed in finite time (under our assumption ?′ ∈ EC, ∀x ∈ B∗, ?̃(x) can be computed in time $ (poly( |x |))). Since the program we described above terminates in finite time, /̂ ?̃ is a computable function.
We then argue |/̂ ?̃ (n) − / ?̃ | ≤ n . Assuming to the contrary that |/̂ ?̃ (n) − / ?̃ | > n , we have / ?̃ > n + /̂ ?̃ (n), since /̂ ?̃ (n) ≤ / ?̃ . The inequality can further be rewritten as / ?̃ = ∑ x∈X≥= ?̃(x) +∑
x∈X<= ?̃(x) > n + /̂ ?̃ (n). Since /̂ ?̃ (n) = ∑ x∈X<= ?̃(x), we arrive at ∑
x∈X≥= ?̃(x) > n . But we already know n > ∑ x∈X≥= ?(x) ≥ ∑ x∈X≥= ?(x) ≥ ∑ x∈X≥= ?̃(x), arriving at a contradiction. Therefore |/̂ ?̃ (n) − / ?̃ | ≤ n .

heading: D Common training strategies for EBMs and their deficiencies for sequence models
text: With the plethora of learning strategies for EBMs, it is untenable to point out the deficiency in each. Table D.1 gives a handful of examples; none share the four properties we desire:

heading: E Connection between expressive sequence distributions and Lin et al.
text: (2021)’s proof that EC ≠ ELN
Our construction of expressive sequence distributions is similar to Lin et al. (2021)’s construction of an EC weighted language that is not in ELN. Whereas each weighted machine ?̃",: ∈ G: corresponds to execution traces of a deterministic Turing machine " , Lin et al. (2021) defined a single weighted language ?̃ELN for all Turing machines. Fore the sake of completeness, we describe the definition of ?̃ELN from Lin et al. (2021) below. Let enc be a prefix-free encoding function that maps a deterministic Turing machine " to a Boolean string where the function inverse enc−1 exists. And let ?̃ELN be a weighted language over Boolean strings, where ?̃ELN (x) = 1/3|x |+1 if x is of the form x (1)x (2) , where x (1) encodes some Turing machine " , and x (2) encodes an accepting execution path of " on an empty input. (Such a path may be represented as a sequence of transitions of " that begins with an initial state and ends at an accepting state.) Lin et al. (2021) then showed that prefix probabilities of ?̃ELN are uncomputable under an ELN, since Halt reduces to computing / (x (1) ). Theorem 9 implies that ?̃ELN we have just described above has a computable partition function: Theorem 10. Let / be the partition function of ?̃ELN. / is computable.
Proof. Let ?(x) = 1/3|x |+1. ? ∈ ELN ⊂ LN because ?(· | x̂) = 1/3 for all valid prefixes x̂. Since ?̃ELN ∈ EC by Lin et al. (2021, Theorem 5) and ∀x ∈ B∗, ?̃ELN (x) ≤ ?(x), we have / is computable by Theorem 9.
Similarly, the ‘sparse version’ of ?̃ELN introduced in (Lin et al., 2021, Theorem 6) can be shown to have a computable partition function as well.
Since one of our goals is to clearly demonstrate that we can construct a single weighted language ∈ EC that has an uncomputable partition function assuming ZFC (e.g., 1̃ in §3.2), we define weighted languages in G: to have at most one ‘high’ weight, as opposed to ?̃ in Lin et al. (2021, Theorem 5), where each x (1) that encodes a halting machine has a ‘high weight’ suffix x (2) .
In fact, under our construction we can directly show EC ≠ ELN, using the uncomputability of 1̃ from Theorem 3:
Corollary 2 (EC ≠ ELN under ZFC; slightly weaker version of Theorem 5 in Lin et al. (2021)). Assuming the axiomatic system of ZFC, EC ≠ ELN.
Proof. We know there exists a weighted language 1̃ ∈ EC (§3.2) that has an uncomputable partition function. Since 1̃ ∈ EC, 1̃(x) ∈ Q≥0,∀x ∈ B∗. Therefore for all strings x ∈ B∗, 1(x) = 1̃ (x)//1̃ is an uncomputable number.
Assuming to the contrary that 1̃ ∈ ELN. By definition 1(x) = ∏ 1(GC | x<C ), where each 1(GC | x<C ) ∈ Q≥0 and is computable. Since the set of computable numbers is closed under multiplication, 1(x) would also be computable, which contradicts our assumption. Therefore 1̃ ≠ ELN, which implies EC ≠ ELN.
F Impossibility of model selection in fixed-size Transformer EBM families
Theorem 11 is a sibling theorem to Theorem 8. Just as we show /1̃ is uncomputable (§3.2), we can prove that model selection is not only impossible for EC-complete parametric families (where the length of a parameter vector is unbounded), but also impossible for fixed-size Transformer EBMs with a large enough embedding size (we use (3) to denote a Transformer family with embedding size 3 below): Theorem 11. Assuming ZFC as our axiomatic system, for any ?̃ ∈ EC, there exists 30 ∈ N such that for all 3 ≥ 30, ?̃ can be captured by one-encoder-layer four-decoder-layer Transformer networks (3) (Theorem 1) with embedding size 3, where there is no provably correct algorithm Better ?̃,3 that takes two parameter vectors )1 ∈ (3) , )2 ∈ (3) , and returns YES if KL(? | |?)1 ) ≥ KL(? | |?)2 ), and NO otherwise, where ?, ?)1 , ?)2 are string distributions defined by ?̃, ?̃)1 , ?̃)2 respectively.
Proof. Let "1 be the input-free unweighted Turing machine we built in our proof of Theorem 3, whose behavior is independent of ZFC. Let "0 be any weighted Turing machine that defines the EC weighted language ?̃. And let "1 be a weighted Turing machine that weights x as ?̃(x) + 1 if and only if x encodes an accepting trace of "1; and "1 weights x as ?̃(x) otherwise. Since checking whether x is a valid trace of "1 is in $ (poly( |x |)), "1 defines an EC weighted language. Let ?"1 be the string distribution defined by "1. By an argument similar to our proof of Theorem 8, no algorithm that is provably correct can decide if KL(? | |?"1 ) ≥ KL(? | |?). We note that for any weighted Turing machine " with fewer than = states, we can build another weighted Turing machine " ′ which has = states, such that " and " ′ define the same weighted language, simply by having (finitely many) additional unreachable states in " ′. Since any weighted Turing machine with = states can be implemented as a 1-encoder-layer-4-decoder-layer Transformer networks with an embedding size ∈ $ (=), it follows that there exists 30 ∈ N such that both "0 and "1 can be encoded as parameter vectors within a fixed-size model family with 3 ≥ 30.

heading: G The halting problem and undecidability: a brief review
text: The halting problem Halt, central to this work, was first rigorously studied by Turing (1937). Put simply, it is the task of recognizing (deciding) whether a given computer program will cease to execute in finite time or not. There is no general solution to the halting problem—that is, the problem is undecidable in the context of Turing machines as a model of computation. Turing’s argument is intimately linked to Cantor’s diagonalization technique and self-reference. For details, we direct the reader to Arora & Barak (2006) or any other text on computational complexity.
H Definition of sequence model families and EC-complete parametric families
Following Pérez et al. (2021), we say a sequence model family is a set of seq-to-seq models N = {#) : ) ∈ ⊆ Q∗}, where every #) ∈ N recognizes language !) if and only if the seq-to-seq model #) , paired with embedding function 5 : B → Q3 , initial states s ∈ Q3 , and polytime termination decision function 6 : Q3 → B, accepts every string x ∈ !) . And we define #) to
accept x = [G1 . . . G) ] ∈ B∗ if and only if there exists A ∈ N, such that #) upon input embeddings [ 5 (G1) . . . 5 (G) )], produces output embeddings yA at the A-th time step, where 6(yA ) = 1. A sequence family is EC-complete if given any ?̃ ∈ EC (as a description of a weighted Turing machine), we can construct a parameter vector ) ∈ such that there exist polytime functions F? : Q3 → N ∪ {0} and F@ : Q3 → N ∪ {0}, where whenever on input x = [G1 . . . G) ], if 6(yA ) = 1 for some output embeddings yA (that is, #) accepts x in A time steps), F? (yA )/F@ (yA ) = ?̃(x).

Review summaries:
The paper works in a computational model where various architectures of energy-based-models are viewed as computational models for accepting languages. EBM's assign a weight to each string. The sum of weights is called the partition function and this needs to be computed (or at best approximated) if the energy is to be thought of as a probability measure. The paper shows that expressive EBM's are turning complete, and uses that to show that the partition function may be uncomputable. And that is even in the case the energy of a sequence could be computed in poly-time. The paper then shows some corollaries and variations of this result, showing that model selection is undecidable as well. The paper concludes by suggesting scenarios where the partition function is computable but this naturally comes at the expense of the expressivity of the model.

This theoretical work highlights uncomputability issues arising with energy-based sequence models. It is shown that an EC-complete family (a certain computational model capturing neural networks and transformers that is essentially equivalent to weighted Turing machines) cannot approximate the partition function of energy-based sequence models (EBMs) even given an unlimited amount of time and space. A consequence is the impossibility of model selection for EBMs. This paper also rules out popular estimators such as rejection and important sampling. This work concludes with a discussion of restricted EBMs that avoid such uncomputability issues. 

This paper studies "efficiently computable (EC) energy-based sequence models (EBMs)" which are simply sets of strings equipped with nonnegative weights that can be computed by a poly-time Turing machine (upon normalization, the weights induce a probability distribution over the strings). In practice, it is common for these weights to be computed by neural networks. In fact, certain neural sequence model families like RNNs and Transformers are expressive enough to be Turing-complete. In this paper, the authors find that the expressivity of such sequence model families, so-called "EC-complete parametric families", comes at a significant cost in terms of *computability/decidability* of various primitives for inference. For instance, they show that if one could actually take in any vector of parameters specifying a model in such a family and output the corresponding partition function (sum of the weights of all strings) even approximately in expectation, then would be able to decide the halting problem (Theorem 2, 4). They also exhibit a single efficiently computable EBM for which proving (within ZFC) that the partition function is one of two possible values would either disprove Godel's second incompleteness theorem or disprove consistency of ZFC (Theorem 3); this can be extended to show that *asymptotic* estimates like rejection sampling and importance sampling will also fail (Theorems 5, 6). Along similar lines, they can reduce from the halting problem to other tasks like deciding whether two given parameter vectors give rise to the same EBM ("parameter identifiability", Theorem 7), or deciding which of two given parameter vectors gives rise to an EBM which is distributionally closer to some other given EBM ("model selection", Theorem 8).  In terms of techniques, the reductions from the halting problem are all based on a simple weight function that is tiny unless if the string corresponds to a valid accepting trace of an input-free Turing machine M. The point is that the weight for any string x can be computed by M simply by simulating M on x, but the partition function is large iff M halts. The ZFC results follow by taking M which enumerates all provable propositions under ZF and halts iff it proves 1 = 0.

The paper studies the trade-off between expressiveness and computability (of the partition function) for energy-based sequence models. The theoretical results show that the high expressively of unrestricted energy based models comes at the cost of un-computability and in-approximability of the partition function. These negative results further show that rejection and importance sampling are not a panacea either.