On the Representational Capacity of Recurrent Neural Language Models
Authors: Franz Nowak
Anej Svete
Li Du
Ryan Cotterell
Venue: EMNLP 2023 Main (2023)
Keywords: RNN
LM
Turing machine
formal languages
probabilistic
language model

Abstract: This work investigates the computational expressivity of language models (LMs) based on recurrent neural networks (RNNs). 
Siegelmann and Sontag (1992) famously showed that RNNs with rational weights and hidden states and unbounded computation time are Turing complete. 
However, LMs define weightings over strings in addition to just (unweighted) language membership and the analysis of the computational power of RNN LMs (RLMs) should reflect this. 
We extend the Turing completeness result to the probabilistic case, showing how a rationally weighted RLM with unbounded computation time can simulate any deterministic probabilistic Turing machine (PTM) with rationally weighted transitions. 
Since, in practice, RLMs work in real-time, processing a symbol at every time step, we treat the above result as an upper bound on the expressivity of RLMs. 
We also provide a lower bound by showing that under the restriction to real-time computation, such models can simulate deterministic real-time rational PTMs.

On the Representational Capacity of Recurrent Neural Language Models
Franz Nowak' Anej Svete' Du Ryan Cotterell
'ETH Zürich 2 Johns Hopkins University
{fnowak, asvete, rcotterellJ@ethz.com leoduêcs. j.u. edu
Abstract
PTM
QPTM
2PDA IU
Prop
Peep
This work investigates the computational expressivity of language models (LMs) based on recurrent neural networks (RNNs). Siegel- mann and Sontag (1992) famously showed that RNNs with rational weights and hidden states and unbounded computation time are Turing complete. However, LMs define weightings over strings addition to just (unweighted) language membership and the analysis of the computational power of RNN LMS (RLMs) should reflect this. We extend the Turing completeness result to the probabilistic case, showing how a rationally weighted RLM with unbounded computation time simulate any deterministic probabilistic Turing machine (PTM) with rationally weighted transitions. Since, in practice, RLMs work in real-time, processing a symbol at every time step, we treat the above result as an upper bound on the expressivity of RLMss. We also provide lower bound by showing that under the restriction to real-time computation, such models can sim- ulate deterministic real-time rational PTMss.
12
E-2PDA S CeRMM
unbounded
Prop.4.1
RLM
real-time, deterministic
RD OPPM
RD 2PDA
Cor
Figure 1: Roadmap through the paper showing relations between different models of computation. A PTM is reformulation of the classic probabilistic Turing ma- chine. A QPTM is PTM with multiple rationally weighted transition functions. A 2PDA probabilis- tie two-tape pushdown automaton. E-2PDA is 2PDA that is deterministic in its output alphabet. An RLM is simple RNN L.M. sRLM is an RLM aug- mented with empty output symbol (s). The prefix "RD-" denotes deterministic real-time machines.
of semimeasures over strings can RLMs represent, i.e., what their computational expressivity?
The empirical capabilities of trained language models have spurred a large field of work testing their reasoning and linguistic abilities. However, theoretical understanding of what these models are inherently capable of still lacking (Delctang et al., 2023). Connecting an LM architecture well-understood models computation can help us determine whether the architecture is able to perform the sequences of computations required to carry out an algorithmic task (Pérez et al., 2019). Furthermore. connecting it linguistic models can tell us whether the architecture is capable of correctly modeling the linguistic structure of sentence symbolically (Linzen et al., 2016). Finally, characterizing the types of semimeasures the architecture can represent allows us to make more concrete claims about the abilities and limitations of the architecture itself.
//gi com/rycolab/ wwntturiinncompleteeeeee
1 Introduction
A language model (LM) is definitionally semimeasure' over strings (Icard, 2020). Re- cent advances in their capabilities, leading to the widespread adoption of LMs, have sparked interest in their theoretical properties and guarantees. Pre- vious work has characterized modern architectures such recurrent neural networks (RNNs; Elman, 1990; Hochreiter and Schmidhuber, 1997) in terms of the formal languages they and cannot recog- nize (Kleene, 1956; Minsky, 1967; Siegelmann and Sontag, 1992; Merrill et al., 2020, inter alia). How- ever, characterizing LMs as formal languages is, in some sense, a category error because LMs encode semimeasures over strings instead of deciding lan- guage membership (Chen et al., 2018). 8). In this work, we thus offer another perspective on understand- ing RNN LMs (RLMs) by asking: What classes
RLMs have set many important milestones in language modeling and still hold the state of the in some important settings of natural language processing (Qiu et al., 2020; Orvieto et al., 2023). Moreover, despite the recent trend towards the recurrence-free and, thus, parallelizable,
RRouhly, a semimeasure is a generalization of a probabil- ity measure over strings such that the total measure may he less than one.

---

transformer-basee LMs (Vaswani al., 2017), elements of recurrence have found their way into recent language models and RNNs themselves have recently even been proposed as alternatives or extensions to some high-performing models (Peng et al., 2023; Orvicto et al., 2023; Zhou et al., 2023). At high level, RNNs work by maintaining a hidden state encoding the processed string, much like how formal models of computation such as Turing machines process and store information. This sequential nature has motivated the com- parison of the computational power of RNNs to that of various formal models of computation, from simple models such as finite-state automata (Kleene, 1956; Merrill et al., 2020) and counter machines, all the way up to Turing machines and related models (Minsky, 1967; Siegelmann and Sontag, 1992; Weiss et al., 2018).
on the other hand, the assumption of unbounded computation time does represent large departure from realistic models. In practice, RLMs perform a constant number of computational steps per symbol, operating in a real-time setting (Weiss et al., 2018). Therefore, we treat the above result as an upper bound on the computational power of recurrent RLMs. As a lower bound, study second type of RLMs, restricting the models to operate in real-time, which results in more fine-grained hierarchy of specific Turing machine-like models equivalent to an RLM. We hence characterize the expressivity of RLMs in terms of classical computational models.
Our work offers a first step towards a com- prehensive characterization of the expressivity of RLMs in terms of the classes of probability measures they can represent. In addition to providing insights into the computational capacity of RLMs, the work also follows the recent exploration of the measure-theoretic foundations of LMs (Welleck et al., 2020; Meister et al., 2023; Du et al., 2023), while focusing on a particular architecture. We conclude the paper by posing several open questions on the exact position of RLMs the hicrarchy of relevant computational models. Fig. shows a roadmap of the puper, with the two types of RLMs of interest and their relation to different formal computational models.
Precisely where RNNs end up on the hicrarchy of formal models of computation depends on the specific formalization. In this work, we charac- terize the computational power of RNNs in their most permissive formalization, i.e., one that allows RNNs to process and produce aational-valued vectors and perform an unbounded number of com- putational steps per input symbol by allowing them to emit empty tokens, E, in between words. Siegel- mann and Sontag (1992) show that such RNNs can simulate any deterministic Turing machine and are, hence, Turing complete. 2 While this sheds light on the processing power of RNNs, their result is not directly applicable to language modeling, it does not take into account the probability assigned the strings. By extending Siegelmann and Sontag's (1992) construction to the probabilistic case, we provide first steps towards understanding the expressive power of RLMs with rational arithmetic. We show that RLMs with rational weights and unbounded computation time can compute exactly the same semimeasures over strings as probabilistic Turing machines.
2 Preliminiaries
In this section, we build up the necessary defini- tions and vocabulary for the rest of the paper.
2.1 Recurrent Neural Language Models
A formal language L is a subset of the Kleene clo- sure Σ' of some finite non-empty set of symbols, i.c. an alphabet, Σ. An element of E is called a string, y. Furthermore, E denotes the empty string. We assume throughout that & & Σ and denote Σ, der [e).). A (discrete) semimeasure over Σ" is a function μ:: Σ* + [0,1] such that Eyer> μ (y) S (Bauwens, 2013; Ieard, 2020). If the semimeasure of all strings sums to one, i.e., ΣyEr' / (gy =1 1, then is called a probability measure." A language model (LM) is defined as semimeasure over Σ* If p is a probability measure, we call a tight language model.
On one hand, rational arithmetic offers a reason- ably faithful formalization of real-world models in that computer scientists often analyze numerical algorithms using such an idealization. 3 However,
"Note that the restriction on the Turing machine heing deterministic does not change the generated language since any non-deterministic Turing machine has an equivalent deter- ministic Turing machine, albeit with a potentially much longer running time a given string (Gill, 1974).
'In many cases even real arithmetic is assumed, c.g., when theoretically analyzing optimization algorithms (Forst and Hoffmann, 2010, Ch. 1).
"Note that our definition differs from Li and Vitányi's (2008) who instead define semimeasures over prefix strings.

---

Most modern LMs are autoregressive, meaning they define p ( through conditional semimea- sures of the next symbol given the string produced so far and the measure of ending the string, i.e.,
measures are defined by projecting Eh, to the prob-
ability simplex A [ using projection function
E
π
P(Ue VEt) (Eh:)g
(4)
N II p (yn yen)
(z)= (EOS y)
(1)
When generating from an RLM, we assume the next symbol is sampled according to the probabilities defined by π (Eh;) and is then passed as the next input symbol back into the RNN until EOS is generated.
where EOS denotes the special end-of-string symbol, which specifies that the generation of a string has halted. The inclusion of EOS allows (but does not guarantee) a p defined autoregressively define a probability measure over Σ' (Du al., 2023). We will denote Σ _ EU [FOS}-
2.2 Turing Machines
We use reformulation of the classic defini- tion of probabilistic Turing machine similar Weihrauch's (2000) Type-2 Turing machine."
We will use the following definition of an RNN.
Definition 2.1. A simple RNN R is an RNN with the following hidden state update rule:
Definition 2.2. A probabilistic Turing machine (PTM) is two-tape machine specified by the 6- tuple M (Q, E, ,,, 82, qs 9p), where
h, (Uh, + Vr(yi) + b)
(2)
where bn is a vector in Q, D is the dinensional- ity of the hidden state, Σ + Q is the symbol representation function, R is the embedding dimen- sion, b QP, U E QDDD, and V QxR, The function f the saturated sigmoid, defined as:
Q is finite set of states;
and I' are the input and tape alphabets, and T includes the blank symbol Li;
4.99 Q are initial and final states;
6(1.2) Q r + Q x r Eg {L, R. N} are two transition functions, one of which is chosen at random at each computation step.
0 x <0
(xx
I e [0
(3)
The Turing machine defined above has two tapes. The first a working tape on which symbols from the tape alphabet can be read and written. The second is an append-only output tape on which M writes symbols of the output alphabet Σ. In the beginning, both tapes are empty, i.e., the working tape has only blank symbols LJ, and the output tape has only empty symbols e. Starting in the initial state q. any time step t. the machine samples one of the two transition functions at random, each with probability I and applies it. given transition can 2.
1
ifr>1
Due to their sequential nature, RNNs have been linked to formal models of computation such as finite-state automata, pushdown automata (PDA), and Turing machines under various formalizations with different implications on computational power (e.g., Siegelmann and Sontag, 1992; Hao et al., 2018; Korsky and Berwick, 2019; Merrill, 2019; Merrill et al., 2020; Hewitt et al., 2020, inter alia). For example, if, instcad of using the saturated sigmoid, we assumed that f is function that maps to finite set, this would result in RNNs that are at most expressive finite-state automata (Min- sky, 1967; Svete and Cotterell, 2023). Merrill et al. (2020) study the computational power of saturated RNNs by investigating the effect of asymptotically large weights. Finally, Siegelmann and Sontag (1992) assumes rational-valued arithmetic, which is the convention we follow in this work.
be written as (q.7) 9/d (d' 7)), where q, E Q,7.7 E T, Eg, and d E (L, N). The semantics of such a transition is as follows: When in state and reading 7 on the working tape, go to state g'. write y to the working tape, write y e Σg to the output tape, and move the head on the working tape by one symbol along the tape in the direction d, that is, left (L), right (R), or stay in place (N). 6 When y E, the machine simply does
An RNN specifies an LM by defining condi- tional probability measure over Ve given d-t- Let E (DEED be an output matrix and R an RNN. An RLM is an LM whose conditional probability
'Note our adding an additional tape does not increase the power the Turing machine (Sipser. 2013, Ch. 3). "The stay-in-place operation is often added to make proof's simpler but does not add expressivity (Sipser, 2013, Ch. 3).

---

not write anything on the output tape. The machine halts once it reaches the final state 9.- We call the sequence of symbols y E E" on the output tape at that point the output of the machine.
71 72, 73, 74, Eg. Such a transition denotes that the 2PDA in the state q with the symbol 7 on top of the first stack pops 7/1 and "2 from the first and second stack, pushes "/3 and Y onto the stacks and moves to state q'_ At the same time, the 2PDA consumes or emits (depending on the use-casc) a symbol from Σg.
Note that, once a transition function has been chosen, since it is a function, the next transition is uniquely determined by the current state q and the current tape symbol y under the read-write head. In the following, call pair of (g:7)) E Q a configuration of M.
Again assume the rational weighting function 8 of 2PDA is locally normalized over configu- rations (g: 7) E Q x T, where y is the symbol currently on the top of the first stack:
Remark 2.1. Given a probabilistic Turing machine M as defined above, we can get the probability of M halting and outputting a specific string by summing the probabilities of all halting paths? through the machine that result in y being written on the output tape (the probability of each path is 2-", where n is the number of computation steps).
8 8 917-21-933 g.)
Σ MEEL 7I.T./3..4E..
(5)
72-474
A 2PDA starts at the initial state q. with both stacks empty (only containing the symbol 1) and then sequentially applies transitions according to their probability given by d. The automaton halts when reaching the final state, 9p- The sequence of the symbols output by the automaton concatenated in the order of transitions taken constitutes the output string.
Remark 2.1 induces a semimeasure over the pos- sible sequences y E Σ" that a PTM M can output, which we will call M- That is, PM is the probability that M will halt with y as its output.
Remark 2.2. The notion of halting probability as defined in Remark 2.1 has a counterpart in RLMs, namely, the probability mass placed on all finite strings generated (Icard, 2020). For details, see Appendix A.
A note on variants of computational models. Our definition of a probabilistic Turing machine differs from the traditional definition of mere lan- guage acceptors in that they start from a starting state Q. and then iteratively apply probabilistic tran- sitions to generate outputs y E Σ", where each specific y has a corresponding probability of being produced. This is to simplify the comparison to 2PDA and to be able to interpret them as language models in their own right.
2.3 Pushdown Automata
We now move to another probabilistic computa- tional model: The two-stack pushdown automaton.
Definition 2.3. A probabilistic two-stack push- down automaton (2PDA) is a two-stack-maching defined by the tuple P = (Q, E,
T, 5, q. 92), where
Next, we define what it means for two proba- bilistic models of computation to be equivalent.
Q is a finite set of states;
Σ and I are the input and stack alphabets, and I includes the bottom-of-stee symbol L;
Definition 2.4. We say that two probabilistic computational models Mi and M2 are weakly equivalent if. for any string y E Σ., we have FMI = Fz If. furthermore, there exists a weight-preservingg yield-preserving' bijection between halting paths in the two models, they are called strongly equivalent. 10
4. 4g E Q are the initial and final states;
8: Qxxxxxxx E. x + Q is a transition weighting function.
To make the connection to Turing machines more straightforward, our definition of 2PDA its cur-
assumes that its transitions depend rent state q and the top stack symbol of only the first of the two s We write transitions as 3:7.71 11, d' for q, g' C Q E Ex, y E
3 An Upper Bound
In this section, we establish an upper bound on the expressive power of RLMs by extending
q 72
"The yield path is string produces. i.e. the sequence symbols emitted by the actions on the path. also lift this definition to classes of models (C, C2). which are called strongly equivalent if M. E Ci-M2 E Co such that Mi and M2 are strongly equivalent, and vice versa.
'A path a finite sequence of actions performed by a computational model starting from an initial configuration. path halting if ends a final state. "This is without loss of generality; see Appendix B.

---

Siegelmann and Sontag's (1992) result to the proba- bilistic case of language models. Because want to upper bound the power of RLMs used in prac- tice, we will start with a more unrealistic recurrent LM which can output empty symbols (e), which we denote as =RLM. We first introduce variant of probabilistic Turing machines that can have arbi- trary (finite) number of rationally valued transition functions and show that they are strongly equiva- lent to 2PDA (Section 3.1). We then review Siegel- mann and Sontag's (1992) construction for the unweighted case (Section 3.2). Finally, we extend this construction to the probabilistic case by show- ing how to simulate 2PDA with an eRLM. We conclude with the observation that this results in the equivalence of PTMs and eRLMs (Section 3.3).
O, U. T
TM
2PDA
B
C
E
A
Figure 2: Simplified view of 2PDA simulating a TM.
See Appendix C for the proof. Theorem 3.1. QPTMs and 2PDA are strongly equivalent.
3.1 Rationally Weighted PTMs
This paper considers the expressive power of RNNs with rational weights. To make the connection to PTMS easier, is helpful to define a more general type of a PTM which, instead of sampling between two equally probable transition functions, can have any number of possible transitions at a given computation step, each of which has rational probability of being applied.
Proof. The proof that any PTM has strongly equivalent 2PDA closely follows the proof that any (unweighted) deterministic TM can be simulated by two-stack PDA (Thm. 8.13; Hopcroft al., 2001).
The idea to use the two stacks in tandem to simu- late the TM's infinite tape. The first stack contains the symbols to the right of the TM's head and the top symbol on the first stack is the tape symbol un- der the TM's head. The second stack contains the symbols to the left of the head. See Fig. 2 for vi- sualization. The extension to the probabilistic case, using the introduced definitions of QPTMs and 2PDA, is straightforward; see Appendix D.
Definition 3.1. rational-valued probabilistic Turing machine (QPTM) is a PTM whose transi- tion weighting
frctiinngfunttion function is of the form:
(6) In other words, for any current configuration, it assigns aational-valued probability in the inter- val [0, 1] to each available transition. We require that the probabilities rations, that is, for all q I.
8: Q XQXXXXXXX (L,
3.2 Simulating Unweighted TMs
normalized over configu-
Before we introduce the equivalence the models in the probabilistic case, we review the classical un- weighed construction of an RNN simulating TM first introduced by Siegelmann and Sontag (1992)
8/d 2i4) (11)))24
Σ
=1 (7)
and simplified by Chung and Siegelmann (2021). Specifically, Siegelmann and Sontag (1992) show that a simple RNN can encode a TM by simulating deterministic unweighted 2PDA. This 2PDA takes an input string and maps to the output M (y) given by the simulated Turing machine:
yCE,, CQ E', d.,..
The original construction by Siegelmann and Son- tag (1992) uses unweighted 2PDA which are equiv- alent to Turing machines (Hopcroft et al., 2001). We now want to show that we can simulate a PTM with an eRLM in the same way, that is via prob- abilistic 2PDA as defined above. Therefore, we first show that PTMs and probabilistic 2PDA are also equivalent, in the following two propositions.
true
if M accepts y
M def
false
if M rejects y
(8)
undef
if M does not halt y
Proposition 3.1. PTMs and QPTMs are weakly equivalent.
Naturally, Thm. 3.1 suggests, unweighted two-stack PDAs are equivalent to unweighted TMs (Sipser, 2013).

---

Given deterministic unweighted 2PDA, the con- struction defines an RNN that halts and stores the acceptance of y by the 2PDA in a specific neuron the RNN, or never halts if M (y) - undef.
With this, an RNN simulating 2PDA can be constructed by keeping hidden state vector di- vided into multiple sets of values, three of which will be relevant for our extension: (1) Two stack neurons, each representing a stack; (2) Two read- out neurons, each encoding the symbols on top of one of the stacks; (3) [Q] state neurons encoding the current state of the 2PDA. The readout neurons can be computed from the stack encodings 1) (711 and 17 (72) similarly how the stack encodings are updated. See top of Fig. 3 for an illustration of how these components can be used to determine the quantities relevant to determining the next action of the 2PDA. More details of the construction can be found in Chung and Siegelmann (2021, Thm. 1).
The crux of the construction lies in encoding the content of stack in a neuron." Importantly, the encoding must be such that (i) the tops of the stacks can easily be read and (ii) the encoding of the stack can easily be updated upon popping off or pushing onto the stack. This can, for example, be achieved by mapping a (binary) string Y = ?1 71..77 into r (7) def O.n (YN)... ....) (71), where:
1 y O
7 (7) del
otherwise
77 (m))
Notice the opposite orientation of the two en- codings: The top of the stack in Y is written on the right-hand side while it is the left-most digit in the numerical encoding which enables easy updates to the encoding; with this, popping YN = 0 can, for example, be performed by computing f (10 1.00n(2) (7) 1), popping PN = -1 by computing / (10-n (r) - -3). pushing 7 = 0 by (7) + 1.). and pushing =
[top (7))
[top (7)).
77 (72)
[top (72) [ql
h
ha
hn
computing f (10
by computing f (10 17 (>))+ +
E- [[tp (7)), PerpA (: top (7)).
Similarly, the current state of a 2PDA is stored a set of neurons keeping the one-hot encoding of the state, which is updated by simulating the transition function of the 2PDA. This can be done by intersecting the states reachable from the current configuration of the 2PDA and the states reachable by the currently read symbol, the same way as in the classical Minsky construction of simple RNN simulating a finite-state automaton (Minsky, 1954). Because of the determinism of the transition function, this results a single possible next state. The intersection can be implemented using conjunction, which is possible using the saturated sigmoid function.
Figure 3: A schematic illustration of how the model from Chung and Siegelmann (2021) stores the informa- tion about the configuration of the 2PDA and how it can be used to access the information needed for defin- ing string probabilities. We denote with [-] the one-hot encoding function of the input arguments. ha hh refer to the rest of the hidden state not directly relevant for determining the configuration of the 2PDA.
Importantly, note that in this case, the RNN (and the 2PDA) can be fully deterministic due to the equivalence of deterministic and non non-deterministic unweighted TMs. They also do not have to consider any e-transitions steps generating e's since there is no generation in the sense of Section 2.3. These two aspects will, however, require more attention in the probabilistic case, which we discuss next.
A neuron is term of art for component of the hidden state vector.
"Note that the stack encoding defined by Siegelmann and Sontag (1992) is somewhat different since it does use the base-ten but rather base-four encoding. To keep the presentation simpler, choose the base-ten one; the intuition remains the same.
3.3 Simulating PTMs
A TM can perform an unbounded number of computational steps per output symbol. To account for this with RLMs in the language modeling setting, we extend their definition to one that allows generating e's, effectively allowing RNNs to perform computations without affecting the output string (sRLM).
'"Since we are using a simple RNN, the coefficient cannot be chosen based on the current input. This is why all such actions are performed in parallel (into individual processing neurons). The result of the correct operation (based on the input symbol and the current stack configuration) can then he copied back into the stack neuron. This is why multiple RNN update sub-steps are required.

---

Definition 3.2. An RLM with s-transitions (sRLM) is an RLM that can output e-sybbols.
matrix E. Note that due the E-determinism of P, single pair of the stack symbol and the current state (top (71) q) determines the conditional probability measure over the next symbol. 16 More precisely, we define E Q which maps the one-hot encoding of the pair (7, () to Eg [egl-dimensional vector of probabilities over the next symbol." 17 To achieve that, simply let (x,())))
More precisely, an eRLM defines symbol rep- resentation function r: Eg - Q and the output matrix E Q Ee|xD, where D and R are param- eters depending on the 2PDA (Chung and Siegel- mann, 2021), and Σ = Σ U {E}. The E-symbols represent empty substrings, so the final output of the =RLM is the output string with E's removed. Effectively, this gives eRLM the possibility to perform arbitrary number of computations per symbol of the string. With this additional gadget, we are able state our main result establishing a close connection between PTMs and cRLMs.
correspond to 8 9.20 a=p )). where we index
the output matrix directly with the elements for cleaner notation." 18 Denoting with [7. 4l the one-hot encoding of the tuple (7: q). the vectors E E[7, q] represent semimeasures over Σg, and π can be set to the identity function." 19 Considering that R directly simulates all possible paths of P, it is easy see that R generates string y with sequence of actions if and only if P generates well. Moreover, the encoding of the probabilities in E means that the probabilities of the action sequences are always the same.
On determinism. The construction we describe in the following theorem requires that the next tran- sition of the 2PDA is fully specified given the cur- rent state (g. and the (sampled) output symbol from Σg. That is, the non-determinism of the simulated 2PDA is constrained to the sampling step of the RIM, meaning there can only be one possible transition in the 2PDA per output sym- bol. We call a 2PDA or QPTM that has this property E-deterministic. Note that this is still a non-deterministic automaton; see Def. 4.1.
A formal statement of the theorem is given in Ap- pendix E. We provide a proof where we show that the correspondence between the paths produced by Chung and Siegelmann's 's (2021) construction and the definition of E described above results in a trivial weight- and hieldpreseevvng mapping be- tween the paths of the 2PDA P and the sRLM R that simulates it. Together, this shows that the two machines are strongly equivalent. 20 This construction is implemented in https: / //gi thub. com hwtoollarrnnnuuuinggggee turrtttrrnngaae -on-tturrnn--ccmleeeeesssss completeness..
Theorem 3.2 (Informal). For every Σ- deterministic probabilistic 2PDA, there is strongly equivalent eRLM.
Rough idea. Given a E-deterministic 2PDA P, we design an sRLM R that simulates P by executing its transitions and hence defining the same semimeasure over strings. We use the LM controller from Chung and Siegelmann (2021) (with the same definitions of the parameters U, V. and b), as it conveniently models the transitions of P and exposes the parts of its configuration required to define the transition (and with it the string) probabilities. Note the additional e's do not change the construction. This leaves us with the task of appropriately defining the output matrix E. Exposing the symbols the top of the stacks, top (71) and top (72), and the current state q of P in by (cf. Fig. 3) allow us easily access the appropriate probabilities encoded in the output
Finally, we can show that the expressivity of eRLMs is bounded from above by that of a 2PDA.
Recall that the target configuration of depends only on the top symbol of the first stack, y der top (71)-
17 Oone-hot encodings of the state-stack symbol pairs can be obtained by applying the RNN update (sub- (ste) in which the nonlinearity is used to implement conjunction. This adds an- other sub-step to the simulation of the full 2PDA update step.
18 AAgain. due to the assumed determinism, the elements with are irrelevant for the weights.
'' identity function is generally not projection function onto the probability simplex. However, since its inputs this case already lie the probability simplex, its use is possible. More generally, we could use the sparsemax function (Martins and Astudillo, 2016), which acts like the identity function on the probubility simplex. Alternatively, we could use the more popular sofumax function and set the entries of E to log-
"Note that this does not make the resulting 2PDA unambiguous in the sense that any given string can only be produced one way. There is still the potential for ambiguity because, in a given configuration, the 2PDA could either produce certain symbol y, or it could move to different configuration via an e- e-transtion and then produce the same symbol via a diffcrent transition.
arithms the original probabilities (defining log 0 def -oc). NNot that the bijection between paths is trivial in the case of real-time Y-determinissiec 2PDA because there is no ambiguity over output symbols for any given configuration.

---

Proposition 3.2. Every sRLM has weakly equiv- alent 2PDA.
but also deterministic. We define such 2PDA analogously the single stack case:?? Definition 4.1. A 2PDA deterministic if:
Proof. For the proof, see Appendix G.
For any current state q E Q, current top stack symbol Y E Т, and a given oulput symbol y E Σg, there is at most one transition with non-zero probability.
4 A Lower Bound
While Thm. 3.2 establishes a concrete result on the expressive power of cRLMs, the result follows from somewhat unrealistic assumptions, namely rationally weighted networks and unbounded computation time. We contend the first assumption is reasonable approximation, since even for small neural networks the number of expressible states be large; assuming double precision loating point numbers, an RNN can yield as many 264-D different states, where D is the number of neurons.2! However, RLMs used in practice operate in real-time, outputting a symbol at every computation step. To make our analysis closer to this use case, in this section, we develop a lower bound the expressivity of an RLM under the real-time restriction while still allowing rational arithmetic operations.
If. in a given computation step, the weight of an e-transition is non-zero, then weight is and the weight of all other transitions
If 8(g, e, e) = for all q E Q,7 E I then we say is a real-time deterministic probabilistic 2PDA (RD 2PDA).
Corollary 4.1. RLMs can simulate RD-2PDA.
Proef. This follows directly from Thm. 3.2 since an RD-2PDA is just a special case of the 2PDA without e-transitions which is exactly the restric- tion imposed on the RLM.
4.3 Real-time Deterministic QPTM
As before, we want to connect the RLM with the better-understood PTM. To do so, introduce new class of rationally weighted PTMs that are deterministic and operate in real-time.
4.1 Real-time RLMs
Now, switch back studying the more common RLM with an RNN controller based on Def. 2.1. Firstly, note that the class of RLMs is subset of the class of eRLMs:
Definition 4.2. A QPTM is deterministic if. for any configuration 4,7 E Q x T, and any symbol C Σg, there is at most one transition starting at that configuration and emitting y with non-zero probability. Furthermore, if there is transition with non-zero
Proposition 4.1. For every RLM there exists strongly equivalent eRLM.
starting (q,7) outputting probability, it must be the only possible transition in that configuration. If there are no e-transitions with non-zero probability at all, then called real-time IRD-QPTM).
Proof. This result follows trivially from Def. 3.2: An RLM is simply an eRLM that always assigns probability 0 to outputting
4.2 Real-time Deterministic 2PDA
Corollary 4.2. RD QPTMs are strongly equiva- (ent RD-2PDA:
The lack of e-transitions requires the properties of the simulated model to change: As in Thm. 3.2, the RNN construction requires that there is only one transition for every output symbol and configuration. Previously, this was done by imposing E-determinism, where non-determinism over symbols at a given time step can be reintro- duced by delaying transitions through the use of additional e-transitions, which is not possible here. In fact, the lack of e's and binarization means the resulting PDA has to be not just real-time,
Proof. This directly follows from Thm. 3.1 because RD DPQMPMMs are a special case of general QPTMs.
The resulting Turing machine that our RLM can simulate is now strictly less expressive than the original PTM. See Appendix for the proof. Hence, our lower bound is strictly less powerful than the upper bound.
"eeal-time deterministic PDA have previously been inves- tigated (Harrison and Havel, 1972; Pittl and Ychudai, 1983, inter alia), but to the authors' knowledge, this has not been extended to the two-stack case.
"To use the state space with limited precision more effectively, one could add more stack-encoding neurons or choose more efficient encodings of the stack contents.

---

5 Open Questions
allowing directly characterize the classes of (probabilistic) languages LMs can represent.
This work establishes upper and lower bounds the expressive power of RLMs. While this shows how powerful RLMs can be, the bounds do not completely and precisely characterize the models interest. A natural question for follow-up work is, therefore, the following.
Coneretely, we place two different formaliza- tions of RLMs into the framework of probabilistic Turing machines, thus characterizing their com- putational power. To connect our results with the bigger picture of understanding RLMs, consider again Fig. The upper part of Fig. 1 (left right) expresses the equivalence of PTMs, their rationally valued equivalent and probabilistic two-stack PDAs. These provide an upper bound for E-deterministic 2PDA, which are 2PDA that are deterministic in their output alphabet. These in turn can be simulated by RLMs that output E, allowing the model to perform unbounded num- ber of computations in between outputting output tokens. In Appendix G, we show that any cRLM is weakly equivalent to some 2PDA, meaning the expressivity of &RLM is of 2PDA. The lower half of the Fig. 1 shows the results on the more realistic real-time RLMs with rational weight. We show that such models match the expressive power of real-time probabilistic Turing machines with rational weights (lower left) through their correspondence to real-time deterministic probabilistic 2-stack PDAs (lower right). These results provide set of first insights into the modeling power of modern language models and hopefully provide starting point for the investigation of other modern architectures, such as transformers (Vaswani et al., 2017).
Open Question 5.1. What is the exact computa- tional power of a rationally weighted RLM?
While we do not answer this question defini- tively, we hope that the steps and framework outlined here help follow-up work to establish more precise descriptions of LMs in general, be it in the form of RNNs or other architectures. Furthermore, in this work, we have introduced novel models of probabilistic computation (RD-2PDA, RD-QU (P-Q)MM) that prove useful for describing RLMs in a formal setting due to the close connection between their dynamics and those RNNs. We also provide preliminary analysis of the concrete computational power of the novel models. For example, in Appendix F, we provide an example of a language that can be generated by a QPTM but not by its real-time deterministic counterpart, thereby showing that the former is more powerful than the latter. However, leave a more precise characterization of their expressive power to future work, specifically.
by that
Open Question 5.2. What is the relation- ship between deterministic QPTMs and non- deterministic devices lower on the hierarchy of computational models, e.g., deterttnrcicistic prob- abilistic sinite-state automata which cannot be represented by deterministic finite-state automata (Mohri, 1997; Buchsbaum et al., 2000)?
Limitations
Here, we list several points of our analysis that we consider limiting. Similarly to Siegelmann and Sontag (1992), all our results assume the RLMs to have rationally valued weights and hidden states, which is not the case for RLMs implemented in practice. It remains to be shown if the bounded pre- cision in practical implementations proves to be too restrictive for the LMs to learn solve algorithmic problems. The upper bound result additionally as- sumes that computation time unbounded, which a departure from how RNNs function in practice. It is not clear how an RNN could be trained in a non-real-time manner. or if that would actually lead to better results on any of the standard NLP tasks. Importantly, note that the lower bound result is likely not tight, as, we only show the ability of RLMs to simulate a specific computational model (namely, RD-QPTMs). There might be more
Open Question 5.3. Are the ERLM introduced in Def. 3.2 weakly equivalent to non-deteriiiistic QPTMs without the need to introduce two different types of s symbol to store the direction of the head in the outputs?
6 Discussion and Conclusion
The widespread deployment of LMs in more and more far-reaching applications motivates pre- cise theoretical understanding of their abilities and shortcomings. In this paper, we show that tools from formal language theory, namely, probabilis- tie Turing machines and their extensions, offer a fruitful means of investigating those abilities by

---

expressive models that can also be simulated by RLMs. In general, the results presented are the- oretical in nature and not necessarily a practically efficient way of simulating Turing machines. More- over, we do not suggest that trained RNNs in prac- tice actually implement such mechanisms, but only that they are theoretically capable of doing it; The construction thus serves the specific purpose of the- oretically simulating PTMs and does not naturally extend training and inference outside of prob- lems specifically designed for Turing machines.
Chomsky hierarchy. In The Eleventh International Conference on Learning Representations.
Li Du, Lucas Torroba Hennigen, Tiago Pimentel, Clara Meister, Jason Eisner, and Ryan Cotterell. 2023. A measure- thesorrtt characterization of tight language models. In Proceedings of the 61 st Anmual Meet- ing of the Association for Computational Linguistics (Volume 1: Lony Pupers), pages 9774-9770, Toronto, Canada. Association for Computational Linguisties.
Jeffrey L. Elman. 1990. Finding structure in time. Cog- nitive Science, 14(2):179-211
Wilhelm Forst and Dieter Hoffmann. 2010. Optimiza- zion- Theory and Practice. Springer New York, NY.
Ethics Statement
Our work sheds light on the theoretical capabilities of language models. To the best of the authors'
John T. Gill. 1974. Computational complexity of proba- bilistic turing machines. In Proceedings of the Sixth Annual ACM Symposium on Theory of Computing. STOC '74, page 91-95, New York, NY, USA. Asso- ciation for Computing Machinery.
knowledge, it does not pose any ethical issues.
Acknowledgements
Yiding Hao, William Merrill, Dana Angluin, Robert Frank, Noah Amsel. Andrew Benz, and Simon Mendelsohn. 2018. Context-free transductions with neural stacks. Proceedings of the 2018 EMNLP Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NI.., pages 306-315, Brussels, Belgium, Association for Computational Linguistics.
We would like to thank the anonymous reviewers for their helpful comments. We would also like to thank Abra Ganz and Clément Jambon for their thoughtful feedback and suggestions.
References
Michael A. Harrison and Ivan M. Havel. 1972. Real- time strict deterministic languages. SIAM Journal Computing, 1(4):333-44.
Bruno Bauwens. 2013. Upper semicomputable sumtests for lower semicomputable semimeasures. arXiv preprint 111.:11312.1718
John Hewitt, Michael Hahn, Surya Ganguli, Percy Liang, and Christopher D. Manning, 2020. RNNs can generate bounded hierarchical languages with optimal memory. In Proceedings of the 2020 Con- ference on Empirical Methods in Natural Language Processing (EMNLP), pages 997822010. Online. As- sociation for Computational Linguistics.
Adam L. Buchsbaum, Raffaele Giancarlo, and Jef- fery R. Westbrook. 2000. On the determinization of weighted finite automata. SIAM Journal on Com- puting, 3055:
W.A. Burkhard and P.P. Varaiya. 1971. Complexity problems in real time languages. Information Sci- ences, 310:87-100.
Sepp Hochreiter and Jürgen Schmidhuber. 1997. Long short-term memory. Neural Computation. 9(8): 1885:1735-788
Yining Chen, Sorcha Gilroy, Andreas Maletti, Jonathan May, and Kevin Knight. 2018. Recurrent neural net- works weighted language recognizers. In Proceed- ings of the 2018 Conference of the North American Chapter of the Association for Computational Lin- guistics: Human Language Technologies, Volume I (Long Papers), pages 2261-2271 New Orleans, Louisiana. Association for Computational Linguis- tics.
John E. Hoperoft, Rajeev Motwani, and Jeffrey D. Ull- man. 2001. Introduction Automata Theory, Lan- guages, and Computation, 3 edition. Pearson.
Thomas F. Ieard, 2020. Calibrating generative mod- els: The probabilistic Chomsky- Schützenberreer hierarchy. Journal of Mathematical Psychology, 95: 10230..
Stephen Chung and Hava Siegelmann. 2021. Turing completeness of bounded-precision recurrent neural networks. In Advances in Neural Information Pro- cessing Systems, volume 34, pages Curran Associates, Inc.
S. C. Kleene, 1956. Representation of Events in Nerve Nets and Finite Automata, pages 3-42. Princeton University Press, Princeton.
Donald Ervin Knuth and Andrew Chi-Chih, Yao. 1976. The complexity of nonuniform random number gen- eration. In Algorithmss and Complexity: New Di- rections and Recent Results, page 357-428, USA. Academic Press, Inc.
Gregoire Deletang, Anian Ruoss, Jordi Grau-Moya, Tim Genewein, Li Kevin Wenliang, Elliot Catt, Chris Cundy, Mareus Hutter, Shane Legg, Joel Veness, and Pedro A Ortega. 2023. Neural networks and the

---

Samuel A. Korsky and Robert C. Berwick. 2019. On the computational power of RNNs. arXiv preprint arXiv: 1900,96969999
Jan Pittl and Amiram Ychudai. 1983. Constructing a realtime deterministic pushdown automaton from a grammar. Theoretical Computer Science, 22(1):57- 69.
Ming Li and Paul M.B. Vitányi. 2008, An Introduction to Kolmogoroy Complexity and Its Applications, 3 edition. Springer Publishing Company, Incorporated.
Jorge Pérez, Javier Marinković, and Pablo Barceló. 2019. On the Turing completeness of modern neural network architectures. In International Conference on Learning Reprexentations.
Tal Linzen, Emmanuel Dupoux, and Yoav Goldberg. 2016. Assessing the ability of LSTMs to learn syntax- sensitive dependencies. Transactions of the Associa- tion for Computational Linguistics, 1:521-535.
XiPeng Qiu, TianXiang Sun, YiGe Xu, YunFan Shao. Ning Dai, and XuanJing Huang. 2020. Pre-trained models for natural language processing: A survey. Science China Technological Sciences, 631):1887 1897.
André F. T. Martins and Ramón E. Astudillo. 2016. From softmax to sparsemax: A sparse model of at- tention and multi-label classification. In Proceed- ings of the 33rd International Conference on Interna- tional Conference on Machine Learning Volume 48, ICML'16, 16, page 1624-1623.
Michael Rabin. 1963. Real time computation. Israel Journal of Mathematics, 1(4::203-211.
Arnold L. Rosenberg. 1967. Real-time definable lan- guages. Journal of the ACM, 14(4):645-62..
Clara Meister, Tiago Pimentel, Gian Wiher, and Ryan Cotterell. 2023. Locally typical sampling. Transac- tions of the Association for Computational Linguis- tics, 11:1021121.
Daniel M. Roy. 2011. Computability, Inference and Modeling in Probabilistic Programming. Ph.D. the- sis, Massachusetts Institute of Technology, USA. AA10823858.
William Merrill. 2019. Sequential neural networks as automata. In Proceddnggs of the Workshop on Deep Learning and Formal Languages: Building Bridges, pages 1-13, Florence. Association for Computational Linguistics.
Hava T. Siegelmann and Eduardo D. Sontag. 1992. On the computational power of neural nets. In Proceed- ings of the Fifth Annual Workshop on Computational Learning Theory, COLT '92, page 440-449, New York, NY, USA. Association for Computing Machin- ery.
William Merrill, Gail Weiss, Yoav Goldberg, Roy Schwartz, Noah A. Smith, and Eran Yahav. 2020. A formal hierarchy of RNN architectures. In Pro- ceedings of the 58th Annual Meeting of the Associa- tion Computational Linguistics, pages 443-459) Online. Association for Computational Linguisties.
Michael Sipser. 2013. Introduction the Theory of Computation, 3 edition. Cengage Learning.
Marvin L. Minsky, 1967. Computation: Finite and Infinite Machines. Prentice-Hall, Inc., USA.
Anej Svete and Ryan Cotterell, 2023. Recurrent neu- ral language models as probabilistic finite-state au- tomata. arXiv preprint arXiv:2310.05161.
Marvin Lee Minsky, 1954. Neural Nets and the Brain Model Problem. Ph.D. thesis, Princeton University.
Kohtaro Tadaki, Tomoyuki Yamakami, and Jack C.H. Lin. 2010. Theory of one-tape linear-time Turing machines. Theoretical Computer Science, 41 1(1):22- 43.
Mehryar Mohri. 1997. Finite-state transducers in lan- guage and speech processing. Computational Lin- guistics, 23(2):269-311
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. 2017. Attention is all you need. In Advances in Neural Information Pro- cessing Systems, volume 30. Curran Associates, Inc.
Antonio Orvicto, Samuel L Smith, Albert Gu, Anushan Fermando, Caglar Gulcehre, Razvan Pascanu, and Soham De. 2023. Resurrecting recurrent neural net- works for long sequences.
Bo Peng. Eric Alcaide, Quentin Anthony, Alon Albalak, Samuel Arcadinho, Huanqi Cao, Xin Cheng, Michael Chung, Matteo Grella, Kranthi Kiran GV, Xuzheng He, Haowen Hou, Przemyslaw Kazienko, Jan Kocon, Jiaming Kong, Bartlomiej Koptyra, Hayden Lau, Kr- ishna Sri lpsit Mantri, Ferdinand Mom, Atsushi Saito, Xiangru Tang, Bolun Wang. Johan S. Wind, Stansi- law Wozniak, Ruichong Zhang, Zhenyuan Zhang, Qihang Zhao, Peng Zhou, Jian Zhu, and Rui-Jie Zhu. 2023. RWKV: Reinventing RNNs for the trans- former era. arXiv preprint 23055 2305. 13048.
Klaus Weihrauch. 2000. Computable Analysis An Introduction. Texts Theoretical Computer Science. An EATCS Series. Springer.
Gail Weiss, Yoav Goldberg, and Eran Yahav, 2018. On the practical computational power of finite precision RNNs for language recognition. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Popers), pages 740-745 Melbourne, Australia, Association for Computational Linguistics.

---

Sean Welleck, Ilia Kulikov, Jaedeok Kim, Richard Yuanzhe Pang, and Kyunghyun Cho. 2020. Consistency of recurrent language model with respect incomplete decoding. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 5553-5568, Online. Association for Computational Linguistics.
Wangchunshu Zhou, Yuchen Eleanor Jiang, Peng Cui, Tiannan Wang, Zhenxin Xiao, Yifan Hou, Ryan Cot- terell, and Mrinmaya Sachan. 2023, RecurrentGPT: Interactive generation of (arbitrarily) long text, arXiv preprint 2305. 13304.

---

A Halting Probability and RLM
As discussed in remark 2.1, the halting probability of a PTM is defined as the sum of the probabilities of all halting paths, i.e., paths that end with dp. Note that EOS in a RLM and the final state 4p in PTM are similar constructs, and
consider similar notion for RLM.
We first see how the corresponding notion of halting probability arises in the context of RLM. While it is possible to define a probability measure over Σ" with the autoregressive parameterization as in Eq. (1), not all semimeasures defined by Eq. (1) are probability measures over "". For example, in the definition of RLM (Section 2. if we pathologically choose a projection function л such that it always places zero probability on EOS, we would end up with a semimeasure that places 0 probability on Σ 23 In fact, Eq. (1) defines a probability measure over the set of finite and infinite strings: Σ" U E Under this formulation, the halting probability of an RLM is the probability mass placed on the set of finite strings, Σ" 24 We recognize that similar situation exists in the case of PTM, where the non-halting trajectories are infinite sequences that be considered as elements of {0, 1)0002
In trying to measure the probability mass placed on the set Σ* within E' we first need to define an appropriate probability measure over E' U.P. However, defining probability measures over uncountable sets such as g or {0, 1) d raises nontrivial difficulties. As a simple illustration, consider an infinite fair coin toss. The sample space for this semimeasure is (H, T Clearly, each single infinite event (a binary string w) has probability (2) O. However, treating uncountable semimeasures carelessly would result in the following paradox:
(U
= (({H,T)0') p
U WE(H.
{w} = Σ p((w))=
0 WE(H.
Σ
(10)
WE(T.T
For reasons like this, a rigorous discussion of PTM (Roy, 2011) or RLM (Du et al., 2023) will involve modicum of mcasure theory and typically starts with defining the appropriate o-algebra. In this work, we find that introducing such technical machinery obscures our purposes and therefore intentionally omitted them. For a rigorous discussion on the corresponding definition of halting probability in RLMs and more general autoregressive models, see Du et al. (2023).
B Versions of Probabilistic Two-stack Pushdown Automata
In our work, we use an adaptation of the traditional two-stack PDA whose transition function depends only on the top symbol of one of the stacks (and the current state), whereas usually the top symbols of both stacks are taken into account. This setup follows the proof by (Hoperoft et al., 2001) but warrants additional justification when applied to the probabilistic case.
Proposition B.1. A 2PDA whose transition weighting function depends on the top symbol of both stacks can be simulated by a 2PDA whose transition function depends only on the top symbol of the first stack.
Proof. (->) ) P1 be 2PDA whose transition function has the form ò such that:
Q
Q
(1
Σ VERe.T 7i.78Ta-77EE.
N1765/ .7 +73, ( =
(11)
72-
We now show that we can construct a 2PDA P2 as defined in Def. 2.3, such that for any transition in P1, P2 has finite sequence of transitions resulting in the same state and stack configurations. Let Mo in mo of be such transition in P1, where y is the top symbol on the first stack and / is the q
For other examples where the autoregressive factorization results in Σ- receiving probability mass, see Du et al. (2023). "II case E having probability 0 we say that Eq. (1) defines a tight language model. a tight language model, the halting probability is we can treat Eq. (1) as a probability measure over E* We can view each random branching as corresponding to either 0 or 1, thus resulting in an infinite binary string.

---

top symbol on the second stack. We can simulate this transition in P2 through the following chain of transitions, where introduce consition-specifii new state q":
Eni My d" q" yo' m d' q
(12)
72-38
(=) The converse direction of proving that any such 2PDA P1 whose transitions depend on the top symbols of both stacks can simulate specific 2PDA P2 whose transitions depend only on the top symbol of the first stack is trivial: For any transition in P2, we can just create transition with the same semantics and weight in P1 for each second stack top symbol 7/.
Rationally Weighted Probabilistic Turing Machines
01.71
91-71
yx/ (pr)
y1/ds sn/dd (px)
42 (p2)
P2 y2 dal
0:7
02:72
=
9.7
qa.7
ps+ps
92:72
U/ /ds(ps))
E/N(p2 ps)
12_22__ U2 /d (1 12
13:73
93:73
Figure 4: Binarization of example computation graph described in Prop. 3.1.
Proposition 3.1. PTMs and QPTMs are weakly equivalent.
Proof. - The forward direction is trivial: Every PTM is a QPTM because is rational number.
(E) We start by noting that we can transform any QPTM M into one that has exactly two possible (rational-valucd) transitions at any current state and tape symbol. We do this by repeatedly applying the following transformations: For any 74 Q I that has only one possible transition, its probability is I, so we can split it into two new identical transitions with probability 2.2 For (4,7) E Q x r, this allows exactly 2 possible transitions, this is already as required by the PTM (save for the probabilities, which we deal with the next step). For any (q. 7) E Q x that allow possible transitions, we repeatedly apply the following steps:
1. We choose one of the transitions whose probability we denote by p. and leave it as it is;
2. We then create new e-transition with d = N new state with probability 1- p. leaving y the same; transitions to start at the new state and tape symbol.
3. We then change the remaining
These transformations yield a QPTM with a completely binarized transition function. An example this is shown in Fig. 4. Now note that any locally normalized pair of transitions with rational weights can be replaced by sequence of transitions whose probabilities are each (Knuth and Yao, 1976; Icard, 2020), 26 This, in conjunction with the previous transformation, allows us to convert our QPTM into PTM without changing the string probability.
Proof of Thm. 3.1
Theorem 3.1. QPTMs and 2PDA are strongly equivalent.
Proaf. (=>) We want show that for every QPTM, construct a strongly equivalent 2PDA. We do this in two steps: (1) construct candidate 2PDA and (2) we outline a weight- and greeeerres bijection between accepting paths, whose existence proves strong equivalence.
This step prevents this proof strategy from demonstrating strong equivalence in the backward direction hecause introduces path ambiguity. For this reason, we suspect that Ms and (PM are in fact not strongly equivalent.

---

Construction of P. Let M (Q, dM 9:: qip) be QPTM. The constructed 2PDA P (Qp, E, 9. 9p) will inherit M's alphabets. will also inherit all of M's states and add number additional ones, i.e., Qp = QUQQQEQ Q'. As we showcase later, the subset Q C Qp will be crucial the analysis of the relationship between the two models. The states of P will be a superset of those in M. For each transition in M, we define a transition in P as follows, depending on the direction the head moves after writing to the tape:
Transitions that leave the head in place, that is, transitions of the form (g,7) V/N (d', For to P.
each such transition in M, we add equally weighted new transition q un >7
(ii) Transitions that move the head to the right, i.e., (2:7) 9/n, (²), For each such transition in M, we add an equally weighted new transition M-7.7 o' to P.
(iii Transitions that move the head to the left, that is, transitions of the form T T (= (q,7) V/1, (gf m)) For any such transition 7 in M, we add an equally weighted transition ạ 9.7.7-12' 4r. followed by a transition dr
6->6
sm M7,, q with weight to P. Here, dr is a new state unique to transition т, and "/2 is 92-28
the symbol the top of the second stack before the transition.
A weight- and yield-preserving bijection. Given the construction outlined above, we now show the existence of weight- and preserving bijection between the paths of the two models. While are only interested in halting (accepting) paths, i.e., paths going from Q. Qp with non-zero weight, 27 we prove a stronger result that there exists a weight- and yield-preserving bijection between all Q-subpaths, a notion we will define below.
Definition D.1. Q-subpath in is a subpath whose last state corresponds to a state that also exists the original M. Recall that M' states are constructed to be a subset of those P.
(=) We will define a weight- and preeerriee mapping th1 from the subpaths ग the original M to the Q-subpaths πD in the P. Fix an arbitrary subpath π F. in M. Our proof proceeds by structural induction on the subpath relation: O.M < M > aM is strict subpath π M- Note that this is a well-founded ordering, making it suitable for induction.
Inductive Hypothesis. For all ØM M. the function ta is weight- and field-preserving
Base Case. The function 1 defined to map the empty subpath in M to the empty subpath P with weight and yield e. This preserves the weight and yield.
Inductive Case. Let M be an arbitrary non-empty subpath in M. As depicted in Fig. 5, let J. be the (strict) subpath of JM that omits the last transition TM- Then o' M is mapped as follows: d ++ (a This mapping exists and is weight- and yield-pree preserving by the inductive hypothesis. Now, seek extend the function t/ TM M TM-- By our construction of P, each of the transitions in TM is simulated either by single transition in P (case (i) and case (ii) two consecutive transitions in P (case (iii)). the two-transition case, the sequence of two actions is unique because the second action has a transition-dependent state name, e.g., 9TM Thus, we can extend di in the following manner:
(T(TT) - o TM) (1((m) o (1((TM) = o o TP
(13a)
tp
(1((M) = htw:://wlewwooo-ooooooooooea
oporoor
(13b)
Tport
2' Note that we treat any transitions that have 0 weight as non-existing, and vice versa. A careful treatment could distinguish weight O and non-existence in the model.

---

(1, mn ( 71) 7...
12/Rt
Us/h,
(2)
12)
(43. 73) 7
(44. (44:74) 74)
(g5- 75)
TM
5-5 q. 11,d, 91 92.12.72255
04.74:74
of
93
>>
q4
95
6
7/-
v1((m)
oprpp
(TTM)
Figure 5: Illustration of how ti maps a path in the original QPTM (top half) path in the 2PDA (bottom half). Note that those states with prime do not correspond to states in the original QPTM.
depending whether TM corresponds one (Eq. (13a)) two transitions (Eq. (13b)) in P. Note that the extension 1 preserves the weight and yield of π.- This is clear by inspecting the construction exactly one transition inherits TM's weight and yield. the two-transition case, the second transition given weight and the yield E.
(+=) Next, we define a weight- and jield-preserving mapping from the subpaths Ty in the constructed 2PDA to the subpaths M in the M. Fix an arbitrary Q-subpath TP in P. Our proof proceeds by structural induction the subpath relation: op < TP è op is strict Q-subpath of TP. Note that this is well-founded ordering, making it suitable for induction.
Inductive Hypothesis. For all dp < Tp, the function 4/2 is weight- and yield-preserving.
Base Case. The function 2 defined map the empty subpath in to the empty subpath in M with weight and yield e. This preserves the weight and yield.
Inductive Case.
Let ny be arbitrary non-empty Q-subpath in P. Consider the figure below:
21 11
Q1 +
Q2
V2.722 722
15
93
+
44
34-74:74 176
of
E,74.6 ->
95
E
Tppp'
L1) W//N m) .....
M2/R
Ma/L
(12, 72)
(13, 73)
(44. 74)
(45, 75)
rbz(ar))
TM
(2(
Figure 6: Illustration of how th maps path in the 2PDA (top half) to path in the original QPTM (bottom half). Note that those states with prime do not correspond to states in the original OPTM.
By construction, this path can be decomposed into strict Q-subpath op < Tp and either one or two additional transitions as defined in (i) (ii-, as shown in Fig. 6. In the single-transition case, post post-pended arp is either single transition in M (case (i) and case (ii)). In the two-transition case, post-pended Op pair of the two consecutive transitions of P that together simulate single transition in M (case (iii),, shown at the top of Fig. In the first case, 1/2 maps that action πp to its (unique) corresponding action in M. In the latter case, note that due to the uniqueness of the added named state d' for the transition of type (iii) in M, all non-zero- non-zero-weighted paths containing of P will contain both transitions

---

in P defined in (iii), consecutively. Such pairs of transitions have a corresponding transition in the original The the transition for which they were added. Thus, we can extend dhy in the following manner:
1/2 (2(T)) = v2( = 12((0)) 2/2 (2((T))
aM o TM
(14a)
del
TM
(2(TT)) = (2 = {2p) o Tp) = OMOTN
(14b)
del
TM
depending on whether TM corresponds one (Eq. (14a)) or two transitions (Eqq. (14b)) in P. Note that the extension 1/2 preserves the weight and yield. This is clear by inspecting the construction as exactly one transition inherits TM'S 's weight and yield. In the two-transition case, the second transition given weight and the yield E.
Wrapping up. Thus, we have defined a pair (t) and 1/22) of weight- functions that map arbitrary Q-subpaths in M to paths in P and vice versa. It is easy to see that the two maps are inverses of cach other; 2/2 undoes the operations of t/1, and vice versa. This means that V1 is bijection. Finally, because all halting paths in M are Q-subpaths, we conclude M and P are strongly equivalent.
reeld-preeeiinng total
(E) To prove the backward direction, we want to show that any 2PDA P has a strongly equivalent QPTM M. We proceed analogously: Given a 2PDA P, we construct candidate QPTM M and then sketch a path level weight- and preeeerrnn bijection, again in the form of two injective functions which are inverses of one another. This proves strong equivalence.
Construction of M. Let = (Q,E,T,8, 4: 4p) be an arbitrary probabilistic 2PDA. Now we define d. 9., 4p) to have the same alphabets Σ, I as P. Furthermore, we let M have a superset of the states of P, that is, we let Q. QUQ', where Q' are some additional states. We define the transitions of M by enumerating and distinguishing between all the possible transition types in P:
QPTM M = (QM,
(i) Transitions that do not pop push any symbols, i.c., q UnEE- q. For such transitions, we
define the equally weighted stay-in-place place operation (N) of the form (4,7) W/N (d',)) in M.
(ii) Transitions that pop a symbol and push a symbol to the same stack, i... (a) q
y-7.7 y-n.m of with >
73 # E or (b) q
ymm--e of with 72, 74 * E. Each transition of type (a) defines single QPTM 72-474
transition (q, s/N
(s) with the same weight as the original transition. Each transition of e/R type (b) defines two consecutive transitions (q.7) L/L (ar, 7), (AT: </ (g', ya), where we create new state 4r unique to the given transition in P. The weight of the first of the two new transitions in P equals the weight of the original transition in M, and the second one has weight (thus being the only possible continuation from state 4r).
(iii) Transitions that pop from one stack and push to the other stack, i.e., (a) q 0-7671 +
6
with 71,74 A & or (b) MO7E va, of with 72, 73 * e. A transition of type (a) defines a 72-15
transition in QPTM that moves the head to the right (weighted equally the original transition): (1) W/R (d'74), A transition of type (b) defines a QPTM transition moving to the left followed by stay-in-place operation that changes the symbol below the head: (a. 7) 4/4, (4r,7) (2) e/N, (d'rrs). Again, the weight of the first new transitions in P is chosen to be equal to the weight of the original transition in M and the latter has weight 1.
28 All paths in M are Q-subpaths by definition.

---

(iv) Transitions that push a symbol without popping one. These can be thought of as insertions that move all the symbols on the right side of the head the right. Thus, they can be simulated by sequences of actions by the QPTM. For instance, a transition of the form Min >e, d /where 7
Ya # can be simulated in M follows:
1.) Change the current symbol under the head (?) marker symbol not in the alphabet, e.g., Ji
2.) Go the end of the string and shift all the characters up to the marker one by one to the right, until back at the original position.
3.) Replace 4 with the symbol to be inserted (73).
Therefore, the sequence of such transitions is added to M for any transition of this form in the 2PDA. We preserve the weight of the original transition by defining the weight of the first transition in step 1.) to be the weight of the original transition in P and the weights of all following transitions in steps 2.) and 3.) to be 1.
(v) Transitions that pop from one or both stacks without pushing equally many symbols. These can be thought of as deletions that remove symbols from the M's tape and move all the symbols on the right of the head to the left. For instance, a transition q 1-7-00= o' where Y & E can be modeled using the strategy from (iv), where step 2.) changes shifting all the symbols to the left one by one until reaching the end of the string, then moving back the marker. We define the sequence of such transitions in M for any transition of this form in the 2PDA. Again, the first transition has the same weight as the original transition in P and all following new transitions have weight 1.
(vi) Transitions that pop symbols from both stacks and push to both stacks, i.c., q
q' where 72, Y3, 74 A e. Such transitions can be regarded as a composition of the two cases of (ii), performing first the simulation from (b) and then from (a). The chaining can be done by adding another intermediate state, 9r', Such transitions in the 2PDA therefore define the sequence of transitions (g.7) w//, (gT, 7), 72) e/R, (g+'s 74), (gr, s/N, (d':7s) in the QPTM. The weights are again chosen such that the weight of the first one corresponds to that of the original transition in P. and all following ones have weight 29
72-774
A weight- and a weight- and peeed-press bijection between halting paths of M and P. The reasoning is analogous to the one in the forward direction. While we are only interested in halting (accepting) paths, i.c., paths going from q. to 9p with non-zero weight, we again prove a stronger result that there exists weight- and yield-prec preserving bijection between all Q-subpaths.
bijection. With the construction above, we again show that there is
Definition D.2. A Q-subpath in M is a subpath whose last state corresponds to a state that also exists in the original QPTM. Note that P's states are constructed to be a subset of those in M.
(=) We define weight- and yield- preserving mapping th3 from the subpaths πр in the original P to the subpaths π. in the constructed M. Fix an arbitrary Q-subpath ाр in P. Our proof proceeds by structural induction the subpath relation: ap < πp > op is a strict Q-subpath of TT. Note that this is well-founded ordering, making it suitable for induction.
Inductive Hypothesis. For all ap - TP, the function tia is weight- and yield-preserving.
Base Case. The function 4/s is defined to map the empty subpath to itself with weight I and yield s. This preserves the weight and yield.
Note that the same kind of composition can be used to achieve popping or pushing more than one symbol in (iv) and (v).

---

q ااايييينا
32.72.72228
09-24,E-78
91 +
Q2
94
78
7p
(q) ( /n/N
(0l, +.. (22, 72)
92/R (93, 73) +
94. Ya)
3a/1
(gr, 14). 76)
5iR
(45, 76)
va(or)
TMTM"
(7(pp)
Illustration of how th maps a path in the original 2PDA (top half) to path in the QPTM (bottom half). Note that those states with prime do not correspond to states in the original 2PDA.
Figure 7:
Inductive Case. Let T be an arbitrary non-emply subpath in P. As depicted in Fig. 7, let a be the (strict) subpath of Tp that omits the last transition rp. Then, dp is mapped as follows: ap + (p((pp). This mapping exists and is weight- and yield-preserving by the inductive hypothesis. Now, we seek to extend the function 4/y to मp Op 7p. By construction of M, each of the transitions in Tp is simulated by a number of transitions in M. Importantly, the transitions corresponding any transition Tp in are unique the particular Tp due the P-transition -dpeddaat naming of the added states Q' in M. Thus, we can extend 4/ in the following manner:
(b((T))= = ppp e Tp) (p)) thy (TP) = O TM
(15a)
def TM
(T((p)) = 1/ c Tp) = (T)p
(T(PT)
OM R TM, ... ... TM.bip
(15b)
where T..I...... TM.brp the Lip transitions in M that the transition Tp corresponds to. Note that the extension d3 preserves the weight and yield of Tт. This is clear by inspecting the construction exactly one transition inherits TM'' 's weight and yield, while remaining transitions have weight and the yield e. (=) Next, we define a weight- and yield- preseerreg mapping from the subpaths тM in the constructed QPTM to the subpaths Tp in the P. Fix an arbitrary Q-subpath π in M. Our proof proceeds by structural induction on the subpath relation: αM < M + O.M is a strict Q-subpath of π πT Note that this is well- well-founded ordering, making it suitable for induction.
Inductive Hypothesis. For all σM TTM the function 4i4 is weight- and yield-preserving.
Base Case. The function thy defined to map the empty subpath in M to the empty subpath P with weight and yield e. This preserves the weight and yield.
Inductive Case. Let M be an arbitrary non-empty Q-subpath in M. Consider the figure below:
By construction, this path can be decomposed into strict Q-subpath α π. and either additional transitions defined in (i)-(vi), shown in Fig. 8. In the single-transition case, post-pended to a . either single transition in M (type (iia) and type (iia)). the multi-transition case, post-pended to a M is a sequence of consecutive transitions of M that together simulate a single transition in P. e.g. two consecutive new transitions added for a P-transition of type (iib) as shown in the example at the top Fig. 6. In the first case, 4/2 maps that action in π M to its (unique) corresponding action in P. In the case of multiple transitions, note that due to the uniqueness of the added named states in M (g/, for the transition of type (iib) in the example), all non-zero- non-eeeo-weighted paths containing such transition-specifie additional
"II cases (iib) and (iiib), l.pp = 2, and in case (vi) liep = 3. In cases (iv) and (v), Lep is linearly hounded by the number of symhols printed on the tape of M to the right of its head at the start of simulating P's transition.

---

(ي (و), m) + ........ (42, 72)
22/11
{93. 73) 1 +...... - (94, y4)
30/1
(1r
(a).(dr:7 75)
(g5, 76)
TMFM²
TM
nr 1 M.l,1-m,, Q1 Ge
02-72.772-55
Q4
5-5
Figure 8: Illustration of how 1 maps a path the original QPTM (top half) to a path in the 2PDA (bottom half).. Note that those states with prime do correspond states in the original 2PDA.
states M will contain all the transitions in M that belong its sequence, consecutively. Such sequences transitions have a corresponding transition in the original the the transition for which they were added. Thus, we can extend t in the following manner:
(T(TT)
() (T((TM) op rp
(16a)
(M(TTM valo TM, T= (1
T.LLIp) Op o Tp (16b)
depending on whether 7p corresponds to one (Eq. (16a)) or multiple transitions (Eq. (16b)) in M. Here again T......... T.M.up are the LTp transitions in M the transition Tp corresponds to. Note that the extension 4h preserves the weight and yield. This is clear by inspecting the construction as exactly one transition inherits 7p's is weight and yield. In the multi-transition case, the second transition is given weight and the yicld
Wrapping up. Thus, we have defined pair (1yy and 4/4) of weight-preserving, yield-preserving total functions that map arbitrary Q-subpaths in to paths M and vice versa. It is easy see that the two maps are inverses each other; 4/3 undoes the operations 4/4, and vice versa. This means that dhs is a bijection. Finally, because all halting paths in P are Q-subpaths, we conclude P and M are strongly equivalent. We therefore conclude that the classes 2PDA and QPTM are strongly equivalent.
E Proof of Thm. 3.2
The following theorem formalizes the informal claim made by Thm. 3.2, which says that every E-deterministic probabilistic 2PDAs admits strongly equivalent eRLMs, establishing lower bound the expressivity of eRLMs. Due to the E-determinism, the proof is simple extension of the weighted extension Minsky's construction recently detailed in Svete and Cotterell (2023)-ir it uses the corre- spondence between the paths in the 2PDA and the sRLM produced by Chung and Siegelmann's (2021) construction to define natural weighting of the paths resulting in weight- and yield-preserving mapping.
Theorem E.1. Let be a language model defined by the E-deterministic probabilistic 2PDA P. Ler R be an RNN over Eg as defined by Chung and Siegelmann's 's (2021) construction that furthermore defines
All paths in P are Q-subpaths by definition.

---

the sRLM pr with the ouiput matrix E E.IxD:
( = p 7,9)
der
for y Ee
(17)
if q = dp
(18)
if q + de
and the projection function π (x) sparsemax (x) argmin 2 |x 2/12- Then, holds that PR. is strongly equivalent to p.
Proof. We construct weight- and predd-preeering bijection between the paths in 2PDA and R. Let лр be path in P:
D1, B1,1,1-11
UN-IN-I 1 +, Oup
Tp = Q.
91
QN
0 +
12 -113
The definition of the RNN controller based on the construction by Chung and Siegelmann (2021) ensures that the hidden states h, of the RNN correctly updated, that is, that there is one-to-one mapping between the hidden states of the RNN and the configurations of the 2PDA at every step of the construction. This ensures that h, [_ 2c] for every Let v be the function mapping paths the 2PDA to those in R as
+ (TP)
hg h1
hN.
(19)
Due to the correctness of the RNN transition function, vē is yield-preserrt preserving. Moreover, the mapping is bijective-the one-to-one correspondence between the hidden states and the configurations of the 2PDA ensures that there is one-to-one correspondence between the 2PDA transitions and the transitions between the hidden states, which furthermore means that the expansion of the mapping to entire paths is bijective.
Furthermore, the form of the hidden states h of the RNN enables the simple transformation of h, into h = [T 7d] for every f, where y, the top symbol of stack 1 and qi the state of at time step Notice that by the definition E-determinism, hy contains all the information we need to determine the transition prohabilities of d given any input symbol E Eg. More precisely, holds that for all y E Eg
sparsemax (Eh:), = p (3 7,4)
(20)
Lastly, the definition of ( ensures that R outputs EOS if and only if the simulated 2PDA is in its final state, 9p- From Eq. (20), it is easy to see that the probability of πи is
N
p (TT
II P (ye
II (ve 12-1---1) = pr (b (TT)),
(21)
showing that d is indeed weight-preservingg which finishes the proof.
F Comparison Between Different Variants of Probabilistic Turing Machines
We have introduced a number of different formulations of PTMs (and 2PDA) with various additions and restrictions in the course of this work. this section of the appendix, we compare the types of distributions that can be expressed by each these variants of PTMs. For an illustrative overview of the distributions that can be expressed by the different models, see Fig. 9.
Definition F.1. PTM is deterministic if, for any configuration 4, 7 E Q x T, and any symbol y E Eg, there is at most one transition starting at that configuration and emitting y. Furthermore, if there is a transition starting in (q, 7) outputting E, both transitions must be identical.

---

2 2
deterministic PTM deterministic real-time PTM
1/2 -weighted
real-time PTM
PTM
deterministic QPTM
QPTM
2PDA
deterministic real-time QPTM
detemministio
rational- weighted
untestricted
real-tine
2PDA
real-time QPTM
E-deterpinistic
deterministic
QPIM?
real-ime
decoomiinitticc
PPDAY
Figure 9: schematic illustration of the different types of Turing machines and 2PDA and their corresponding place in hierarchy of distributions. The curves differentiate different types of distributions, where 2- means every string has binary probability, ž12-n| refers to the dyadic distributions, and Q and IR are the rational-valued and real-valued distributions, respectively. The colors of the boxes indicate which restrictions automata, from real- time and deterministic, via E-deterministic, to unrestricted. Finally, the horizontal line divides formulations of machines that have just two transition functions that are uniformly distributed vs. the case of finitely many rational-valuce transition functions. Note that the E-deterministic automata placed between the rational-valued and the real-valued distributions.
placed the
Note that the definition above is more restrictive than that of a general PTM, but a superset of the class of deterministic Turing machines, Mss which can be thought of as unweighted PTMs with the restriction that both transition functions are identical. is well-known result that Ms are computationally equivalent to PTMs. that is, they can recognize the same (unweighted) languages. However, in contrast to Ms, deterministic PTMs defined above can still express semimeasure strings, albeit trivial one (each string y that can be generated has a probability of 2-1vl of being generated).
Proposition F.1. deterministic PTM can only express distributions where each finite string has a binary probability, that is, probability of the form 2
Proof. Let y E E* be string. Because PTM is deterministic, there is unique path in PTM that accepts y. Let be the length of the accepting path. Then, (y) = a
Definition F22 A PTM is real-time if it has e-transitions.
Definition F.3. dyadic rational is a rational number whose numerator can be any integer and whose denominator is a power of 2. We denote the set of dyadic rationals with 2/2-n].2
Proposition F22. A real-time PTM can express only dyadic measures, that is, the measure of each string is dyadic rational.
Proof. Let y E Σ* be a string, and let n = l Because PTM is real-time, every path accepting has length n.. Moreover, since PTM is real-time, it may only have a finite number of accepting paths for any string. If PTT has k accepting paths for the string thne P (y) = k2-", which is dyadic rational.
note on the language expressivity of real-time Turing machines. While deterministic and non-deterministic Turing machines can recognize or generate the same languages, has been shown that all real-time languages are context-sensitive (Burkhard and Varaiya, 1971). In fact, there are real-time
Note that the binary rationals are a special case of dyadic rationals where the numerator has to he 1.

---

definable languages that are context-sensitive and not context-free. On the other hand, there are also context-free languages that are not real-time definable (Rosenberg, 1967). Real-time Turing machines with just one tape have been shown to only recognize regular languages (Tadaki et al., 2010). However, with just one more tape, the computational power increases dramatically (Rabin, 1963), allowing recognition of languages that are non-context-free (Rosenberg, 1967)-
We now turn to the investigation of rationally weighted PTMs, i.e., QPTMs. First, recall that an unrestricted QPTM is weakly equivalent to unrestricted PTM (Prop. 3.1). Furthermore, Icard (2020, Thm. 3) showed that PTMs define exactly the enumerable semimeasures (see Appendix G for details). This means that any enumerable real-valued semi-measure over strings can be expressed by a PTM, and, hence, a QPTM.
Proposition F.3. Real-time deterministic QPTMs are strictly less expressive than general QPTMs.
Proof. By Thm. G.I, PTMs, and hence QPTMs, express real-valued semimeasures over strings. For instance, there exists QPTM that generates the language E for the one-symbol alphabet Σ {a), such that the probability of a string of certain length given by a Poisson measure: p(a*) Pois(A, k)) A A.
for some X RT. Let us choose, e.g., X = 1. Then the probability of each string in Σ is an irrational number. However, RD QPTM has output symbol each time step with rational probability, and hence, there exists RD QPTM that express the above language.
Note that similar arguments can be made to show that both determinism as well as real-time on their own are enough to restrict distributions from such QPTMs to the rationals.
Corollary F.1. Deterministic 2PDA are strictly less expressive than non-deterministic 2PDA.
Proof. This follows from the strong equivalence QPTMs and 2PDA described in Thm. 3.1.
Finally, we leave the case of E-deterministic probabilistic automata for future work, but we hypothesize that it lies in the realm of real-valued (including irrational) distributions.
G Every eRLMs Has Weakly Equivalent 2PDA
In this section, we re-state basic definitions and theorems from computable analysis and then use them to show that the computational expressivity of =RLMs is bounded by that of 2PDA.
Definition G.1. Icard (2020, Ch. 3) A real number lower semi-computable there exists sequence of computably enumerable rationals 11 In E Q that is i) monotonically increasing in n and ii) converges to r from below, i.e, lim, you Qn r.
Definition G.2. A semimeasure over E* is called enumerable for all y E E" we have p(y) r for some that is lower semi-computable
Theorem G.1. Icard (2020, Thm. 3) Probabilistic Turing machines define exactly the enumerable semimeasures.
Proposition 3.2. Every sRLM has weakly equivalent 2PDA.
Proof. We first show that every sRLM defines an enumerable semimeasure. Let R be an sRLM defined over alphabet Σ. We seek show that the measure of any string y E E* computed by R lower semi- computable. In general, there are (countably) many runs that may generate string y. The measure of y R is the sum of all the weights all such runs. More formally, let (0 C Σg be an enumeration all the runs in R that generate the string E Σ", i.e., for each Dr. the yield of ÿ is y. Construct the following sequence
n
P(U))
(22)
Thus, limp-400 In = p(y) and nn is monotonically increasing in n. Furthermore, because R rationally weighted, every r. is rational. Next, note by Prop. 3.1 and Thm. 3.1, 1, the classes of PTM and 2PDA are

---

weakly equivalent. Then, combining this with Thm. G.I, have that 2PDA can express any enumerable semimeasure. This proves the claim.


Reviews:
[{"review_id": "z27KW04w6U", "reviewer": "Reviewer_BtV4", "summary": "", "questions": "Along the line of imposing realistic assumptions in analyzing expressivity, do you have insights on how bounded-precision and/or fixed network dimensions (such as number of layers and number of cells) affect expressivity?", "limitations": "", "rating": 4, "confidence": 2, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for taking the time to understand our work and for your review. \n\nWe appreciate that the topic of our paper is theoretical in nature. However, EMNLP has always included theoretical works alongside experimental ones. Furthermore, we believe that understanding the theoretical aspects of the models used by empirical research on a formal level will benefit researchers in improving the capabilities of these models beyond what they are capable of generating now. \n\nRegarding the step from Turing machines to probabilistic Turing machines being incremental, we would argue that it is, in fact, an important distinction to make, as modern language models do not operate as recognizers at all, simply accepting or rejecting strings. Instead, their ability to approximate probabilities of words and strings in context is integral to their functioning. Hence we contend that probabilistic Turing machines are a (much) more suitable and nuanced formal model, motivating our focus on proving their connection to recurrent language models.\n\nThank you for your question regarding more realistic assumptions of precision and model parameters. As we noted in the introduction, finite precision means in practice the capacity of RNNs is limited to that of finite-state machines.\nIn the Turing machine formulation, we chose to stick with infinite precision, in line with the classical paper by Siegelmann and Sontag. However, it is also possible to bound the computation space (precision and number of hidden neurons) in relation to the string length, e.g. imposing precision logarithmic in the length. While this was outside the scope of this work, it presents an interesting direction for future work since it might yield a tighter upper bound.", "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": "It is a well-written paper that brings the formal language result of Siegelmann and Sontag (1992) one step closer to the language modeling realities.", "reasons_to_reject": "The paper does not quite fit the main focus of the conference which is the empirical aspect of natural language processing. From the theoretical perspective, the extension from the Turing-complete problem to the probabilistic case is incremental rather than fundamental.", "questions_to_authors": "Along the line of imposing realistic assumptions in analyzing expressivity, do you have insights on how bounded-precision and/or fixed network dimensions (such as number of layers and number of cells) affect expressivity?", "paper_topic_and_main_contributions": "Siegelmann and Sontag (1992) established the result that RNNs with rational weights and unbounded computation time are Turing complete. This work extends the result to the probabilistic case, showing that such an RNN LM can simulate any probabilistic Turning machine. Moreover, this work also defines more realistic real-time rational PTMs and draw the connection between RLMs with such constraints with their PTM counterparts.\n\nThe paper is well-written. Despite its abstract nature, it is easy to follow. The work brings the result of 1992 closer to the realistic case of  language modeling.", "excitement": 4, "reproducibility": 3, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "PSj0UCx78m", "reviewer": "Reviewer_EjFc", "summary": "", "questions": "Question A. In light of the Turing completeness findings from Chung and Siegelmann (2021) regarding recurrent neural networks (RNNs) with finite precision and the exciting results presented by Merril et al. (2019-2022) on the capabilities and limitations of saturated RNNs, I am curious to understand the unique insights offered by your work. I ask this question with a genuine intention to ensure that I have not overlooked any novel perspectives your paper might bring, because as it stands, I am afraid that the current work does not seem to introduce new insights to the field.", "limitations": "", "rating": 3, "confidence": 4, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your detailed and thoughtful review. Thank you also for the additional references you suggested, we shall add them to the manuscript.\n\nRegarding your first point, thank you for pointing out that our contributions should be clarified in the introduction. To also answer your related point from the typos, grammar, and style section: \nWe do not claim to be reinventing probabilistic Turing machines. However, the distinction between a deterministic Turing machine, a probabilistic Turing machine, and a deterministic probabilistic Turing machine, especially in the context of real-time computation, has not been made before, at least to our knowledge. We will include an additional discussion to the paper relating all these different types of Turing machines to the types of distributions they can express, as well as their computational expressivity.\n\nRegarding your second point, we think that we have provided motivation in the Introduction section, where we point out that “LMs inherently work with probability distributions and do not simply decide language membership” (lines 34-41). Hence, our focus on the probabilistic case does not only more adequately fit the language models used in practice, but also allows us to relate this line of work to “the measure-theoretic foundations of LMs (Welleck et al., 2020; Meister et al., 2023; Du et al., 2022)”, see lines 125-130.\nFurthermore, as one of the references you mentioned points out, probabilistic Turing machines define different complexity classes to standard Turing machines. While it is still an unsolved problem to show whether or not e.g. the complexity classes P and RP are distinct, showing that RNN LMs can simulate any PTM in real-time is still a distinct, and potentially stronger, result.\n\nRegarding your last point, and also to answer your Question A at the same time: \nOur unique contribution is twofold: 1) extend Siegelmann and Sontag’s result, showing that RNN language models can not just simulate TMs but PTMs in real-time, generally regarded as a different and potentially stronger (in terms of complexity classes) computational model which is also better suited to theoretically explain language models.\n2) We provide a lower bound under more realistic conditions of real-time computation. In contrast to Merril’s work on saturated RNNs, which shows that RNNs with finite precision are limited to recognizing regular languages, we show that relaxing the precision requirement allows for a lower bound that is much more expressive than finite state automata, namely, real-time deterministic Turing machines. \n\nThank you for your pointers regarding representations of strings and symbols in our script, as well as the figures. We will change the symbols following your suggestion and change Figure 1.", "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": "* The paper focuses on an important problem in the study of language models, namely the computational expressivity of language models based on (Elman-type) recurrent neural networks (RNNs). It extends the Turing completeness result of RNNs to a probabilistic context, demonstrating that RNN-style language models with rational weights and arbitrary computation time can simulate a probabilistic Turing machine (PTMs). Moreover, the paper shows that these models, under real-time computation constraints, can simulate deterministic real-time PTMs.\n* The paper is well-written and relatively easy to follow. The proofs presented in the paper are also sound and convincing.\n* The first half of the paper provides a clear exposition of classical results in the study of Turing machines.", "reasons_to_reject": "* The unique contributions of the paper are not well-defined and difficult to discern. The authors claim to demonstrate that RLMs with rational weights and arbitrary computation time can capture the same probability distributions over strings as probabilistic Turing machines. However, this result does not appear to be surprising or novel.\n* On multiple occasions, the authors emphasize the fact that their analysis is on probability distributions rather than unweighted languages, but they fail to adequately motivate or explain the significance of this distinction. As a result, the entire analysis presented in the paper feels rather abstract and obscure.\n* The paper extensively covers well-known concepts and results up to its final page. However, to enhance its potential for publication, it should address Open Question 5.1 and delve into the precise computational power of a rationally weighted recurrent language model. This addition would provide valuable insights and contribute significantly to the existing literature. \n   * At present, the paper lacks original findings or conclusive answers to the questions it raises. To truly captivate readers, the authors should consider exploring the computational power of real-time recurrent or self-attention-based language models with finite precision and rational hidden states. Such an investigation would introduce a refreshing and exciting dimension to the study, elevating its significance and making it a valuable contribution to the field.", "questions_to_authors": "Question A. In light of the Turing completeness findings from Chung and Siegelmann (2021) regarding recurrent neural networks (RNNs) with finite precision and the exciting results presented by Merril et al. (2019-2022) on the capabilities and limitations of saturated RNNs, I am curious to understand the unique insights offered by your work. I ask this question with a genuine intention to ensure that I have not overlooked any novel perspectives your paper might bring, because as it stands, I am afraid that the current work does not seem to introduce new insights to the field.", "paper_topic_and_main_contributions": "This paper explores the computational power of language models based on recurrent neural networks (RNNs). In particular, it extends the Turing completeness result to the probabilistic case, demonstrating that a recurrent language model with rational weights and unlimited computation time can simulate any probabilistic Turing machine. \n\nSince real-world RNN language models process one symbol at a time in real-time, the above result is considered the maximum expressiveness of RNN-based language models. The paper further establishes a lower bound by demonstrating that these models can simulate deterministic real-time rational probabilistic Turing machines under the constraint of real-time computation.\n\nIn summary, the paper establishes that RNN-based language models with rational weights are as powerful as probabilistic Turing machines when computation time is unbounded. However, in practical real-time scenarios, their expressive power is limited to simulating deterministic real-time rational probabilistic Turing machines.", "excitement": 3, "reproducibility": 5, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {"Missing_References": "* Rabin, Michael O. \"Real time computation.\" Israel Journal of Mathematics 1, no. 4 (1963): 203-211.\n* Gill III, John T. \"Computational complexity of probabilistic Turing machines.\" In Proceedings of the sixth annual ACM symposium on Theory of computing, pp. 91-95. 1974.", "Typos_Grammar_Style_and_Presentation_Improvements": "* The purpose and significance of Figure 1 are unclear. It does not seem to contribute or enhance the overall understanding of the paper. \n* You might want to move Figure 2 to the first page.\n* L142: Is the word “novel” necessary in that sentence? You are not reinventing probabilistic Turing machines again.\n* L157: Why did you opt for the symbol $\\sigma$ to represent a sequence of text? Wouldn't $y$ (or $x$) be more suitable in this context, considering that some readers might associate $\\sigma$ with the sigmoid function?"}}, {"review_id": "k1syzeIWZg", "reviewer": "Reviewer_atVK", "summary": "", "questions": "Do authors have some insights what direction should be worked on for tighter bound/better characterization?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the time to read our work and for your review. \nWe acknowledge that both the upper and lower bounds are shown using a similar technique to Siegelmann and Sontag. We think that this gives new insights specifically because it relates known theoretical results about general recurrent networks to currently used language models that use a similar, albeit different architecture, in that we now involve a step of sampling outputs that is not present in the original formulation. \nTo answer your question, we believe one potential avenue for arriving at a tighter bound is to change the infinite precision assumption for one that allows for precision or space capacity as a function of the output length since this allows retaining a good practical approximation of computational power similar to that made when considering computers as Turing machines.\nFurthermore, there are language models that can adapt the computation time depending on factors such as the complexity of a task, meaning the unbounded computation time assumption of the upper bound may prove more relevant in the future.\nUpon acceptance, we will include both of these points in the discussion on potential future work.", "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": "The missings in the theory of the field makes theoretical contribution more important than before. Apart from the solid contribution that the paper has made including the upperbound and lowerbound of the RNNs, the lowerbound derivation actually comes from the observation of practical RNN usage, which I appreciate. \n\nThe paper is easily accessible by all NLP researchers, even people not very familiar with the formal language theory. ", "reasons_to_reject": "The paper doesn't introduce new proving techniques to give tighter bounds or offer further insights. The upperbound proof is an extension from Siegelmann and Sontag and the lowerbound proof follows the upperbound proving techniques. ", "questions_to_authors": "Do authors have some insights what direction should be worked on for tighter bound/better characterization?", "paper_topic_and_main_contributions": "This theoretical paper revisits the RNN expressiveness issues and make two contributions:\n- Upperbound: the paper extends the results of Siegelmann and Sontag (which shows that RNN with unbounded computation time are turing complete) that an RNN with unbounded computation time can simulate any distribution specified by a turning machine. Technically, this involves handling the output matrix so that it projects to the probability space that the corresponding Turing machine specifies.\n- Lowerbound: the paper insightfully notices that the unbounded computational time hypothesis is violated in practice where only linear computation time machines are used. Based on this observation, the paper uses similar techniques to upperbound proof to derive a lowerbound for linear RNN expressiveness and demonstrate the realtime deterministic Q probabilitic turing machine as a lower bound. ", "excitement": 4, "reproducibility": 4, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Pros:
- A strong theoretical result that RNN LMs can simulate probabilistic Turing machines.
- All reviewers agree the paper is exceptionally well-written, especially for a theory paper.

Cons:
- The result is incremental, extending an existing finding to a probabilistic rather than weighted model.
Decision: Accept-Main