{"id":"b036458e-1f02-4ab2-8fdd-3a6e3e6cbe23","arxiv_id":"2607.06155","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"Finite-state tools add only log|M| bits to finite-precision recurrent controllers, while a single tape tool yields Turing completeness with O(log|Q|+log|Γ|) bits, realized exactly by one-layer selective SSMs.","lead":"This paper proves a sharp dichotomy: finite-state tools add nothing to finite-precision recurrent models, but a single tape tool makes them Turing complete. It matters because it gives an exact account of when tool use genuinely increases AI computational power versus merely adding convenience.","discovery_kind":"unclear","skeptic_critique":{"model":"glm-5.2","headline":"No significant objection identified. The dichotomy is proved constructively with correct proofs; the resource conventions in Appendix B are transparent and the matching lower bound (Thm 23) closes the gap.","rationale":"The reader correctly identified the resource conventions (Remark 20) as the weakest assumption, and this is indeed the place where the results are most convention-dependent. However, the paper is transparent about these conventions, proves a matching lower bound (Theorem 23) showing the conventions are necessary for the logarithmic result, and explicitly explains the compatibility (Remark 24). The proofs I checked are correct: the one-hot construction (Lemma 12), the Turing simulation (Theorem 7), the affine maps in the logarithmic construction (Eqs. 1–3), and the congruence/nilpotent orbit argument (Theorem 23). The reader's assessment of HIGH confidence and ACCEPT is appropriate. The informal nature of 'selectivity is essential' (Remark 14) is a minor gap but does not affect any formal claim, since the paper only asserts sufficiency of selectivity for the positive results. No verdict adjustment is needed.","tokens_in":17590,"tokens_out":3339,"duration_ms":226367,"concrete_test":"Verify the congruence argument in Theorem 23 by brute force for small B (e.g., B=4,5,6): enumerate all equivalence relations on Z_B, check that only equality and the universal relation are preserved by both s and c. If any nontrivial congruence survives for some B, the lower bound argument would need revision for that case.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I reviewed each major result for correctness and internal consistency. Proposition 4 (product-state simulation) is a standard construction executed correctly. Theorem 7 (Turing completeness via tape) has a clear invariant and faithful simulation. Lemma 12 (one-hot SSM realization) correctly defines A_ω columnwise so that A_ω e_i = e_{δ(s_i,ω)}, with zero biases — the induction is clean. Theorem 13 composes Theorem 7 and Lemma 12 without issue. Theorem 19 (logarithmic simulation) uses affine maps (Eqs. 1–3) that I verified are genuinely affine: ℓ(u) in Eq. 2 is the linear functional e_{s_read}^T u, and the bias term η·e_{U,0} is linear in η. The counter requires O(log B) bits, the flag and fixed universal-controller register are O(1). Theorem 23's lower bound is the most technical result: the automaton (Z_B, s, c) has only trivial congruences (verified: any nontrivial subgroup H forces 1 ∈ H via the s-map interaction), and the nilpotent orbit argument correctly yields B−1 linearly independent vectors. The resource conventions in Remark 20 (free tape, uncharged readout) are explicitly stated, and Remark 24 explains why the logarithmic and linear results are compatible. The paper does not overclaim: it clearly separates what each convention buys. The only thing approaching a concern is that 'selectivity is essential' (Remark 14) is stated informally without a formal impossibility proof for non-selective SSMs with tape access — but this does not affect any stated theorem, as the paper only claims sufficiency of selectivity, not necessity in the tape-augmented setting.","agreement_with_reader":"agree"},"referee_report":{"model":"glm-5.2","summary":"This paper studies when external tool access increases the expressive power of finite-precision recurrent models. The authors model any such model as a deterministic finite-state controller interacting with an oracle through a finite interface. They prove a sharp dichotomy: (1) finite-state bounded-interface oracles can be internalized at a cost of only log|M| + O(1) bits (Proposition 4), leaving the system finite-state; (2) a single tape oracle with local read/write/move commands yields Turing completeness with O(log|Q| + log|Γ|) bits of controller memory (Theorem 7). They further show this construction is realized exactly by a one-layer selective affine SSM with binary one-hot hidden states, {0,1} transition matrices, and zero biases (Theorem 13). A concrete exponential separation is given via EQ_n (Theorem 9). The supplementary material provides a fully explicit constant (C_0 = 9), a logarithmic oracle-assisted universal simulation (Theorem 19), and a matching lower bound showing that without external memory, exact one-step realization of an arbitrary B-state transition map requires dimension exactly B-1 (Theorem 23).","tokens_in":17819,"tokens_out":1206,"duration_ms":237942,"significance":"The paper provides a clean, exact, and constructive characterization of tool-augmented recurrent computation. The dichotomy is well-motivated and the results are fully formal. Particular strengths include: (a) the constructive proofs with explicit constants (e.g., C_0 = 9 in Appendix A); (b) the exact SSM realization with zero biases and binary transition matrices (Lemma 12), which makes the positive result architecture-specific rather than abstract; (c) the matching lower bound (Theorem 23) that closes the gap between the logarithmic oracle-assisted simulation and the linear direct-realization requirement, with a transparent explanation of why the two are compatible (Remark 24). The resource conventions in Appendix B are explicitly stated, which is commendable. The paper is largely self-contained, citing Neary and Woods (2009) only for the existence of a fixed universal Turing machine.","major_comments":[{"comment":"Remark 14 states informally that a fixed linear time-invariant (non-selective) SSM 'is not automatically able to implement arbitrary finite-state control.' This is a meaningful claim that is naturally suggested by the contrast between the selective construction (Theorem 13) and the lower bound (Theorem 23), but it is not formally proved in the manuscript. The paper is careful to say 'is not claimed' and 'is not automatically able,' so this does not affect any stated theorem. However, since selectivity is identified as 'the architectural ingredient that suffices for exact finite control' (Section 9), a brief formal statement of what non-selective SSMs with tape access cannot do—or an explicit acknowledgment that this is left as an open question—would strengthen the narrative. This is a minor gap in framing rather than a load-bearing issue for any theorem.","section":null}],"minor_comments":[{"comment":"Section 8.2: The action alphabet Act includes 'stay' as a command, but the tape oracle in Section 5 (Definition 6) does not list 'stay' among its commands. The appendix (Appendix A) does include 'stay.' A brief note reconciling these definitions, or a forward reference, would improve clarity.","section":null},{"comment":"Theorem 19, Eqs. (1)-(3): The notation D_ω for the one-hot transition matrices of the scanner/universal controller is introduced without explicit definition of the subscript set. It would help to state that D_ω is defined for ω ∈ {ok, ⊔, 0, 1} and that D_0, D_1 apply when the universal controller reads tape symbols 0 or 1 during its own operation.","section":null},{"comment":"Table 1: The row 'none, EQ_n ≥ 2^n states —' lists the tool as 'none' but does not specify controller memory. For consistency with other rows, it could note '≥ n bits' or '≥ 2^n states.'","section":null},{"comment":"Lemma 18: The encoding length bound |⟨M⟩| ≤ cB log₂(B+1) uses a constant c whose value is not made explicit. While this is standard for an O-notation result, the paper's emphasis on making constants explicit (cf. C_0 = 9 in Appendix A) suggests that providing a value or an explicit bound on c would be consistent with the paper's own standards.","section":null},{"comment":"The paper uses both 'selective affine SSM' and 'selective affine state-space controller' in different places. Standardizing the terminology would improve readability.","section":null}],"recommendation":"minor_revision","confidential_remarks":"The reader's assessment is thorough and accurate. I verified the key constructions independently: Proposition 4 is a standard product construction, Theorem 7's simulation loop has a clear invariant, Lemma 12's columnwise definition of A_ω is correct, and Theorem 23's congruence argument (showing that the automaton (Z_B, s, c) has only trivial congruences) checks out. The nilpotent orbit argument correctly yields B-1 linearly independent vectors. The resource conventions in Remark 20 are transparent and the paper does not overclaim. The only item I would flag for the authors' attention is the informal Remark 14, but since it does not underpin any theorem, minor revision is appropriate. The paper is a good fit for the journal."},"author_rebuttal":{"model":"glm-5.2","summary":"We thank the referee for a careful and positive reading. The report identifies one minor gap in framing: Remark 14 informally notes that non-selective (fixed LTI) SSMs are not automatically able to implement arbitrary finite-state control, but this claim is not formally proved. We agree this is a framing gap, not a load-bearing issue for any theorem, and will address it in revision.","responses":[{"response":"We agree with the referee that Remark 14 makes an informal claim that deserves sharper framing. To be precise about what we can and cannot currently say: (1) What we have proved: Theorem 23 shows that without external memory, exactly realizing an arbitrary B-state transition map in one affine recurrent update requires dimension B-1, for any number of triangular selective-affine layers. Since selectivity is a generalization of the non-selective (fixed LTI) case, this lower bound applies a fortiori to non-selective SSMs. (2) What we have not proved: a formal impossibility result for non-selective SSMs *with* tape access. The tape-access setting introduces oracle interactions that complicate the direct-realization argument, and we have not extended the lower-bound machinery to that setting. We will revise Remark 14 to state this distinction explicitly: the non-selective case is constrained by Theorem 23 in the no-external-memory regime, but whether non-selective SSMs with tape access can or cannot achieve Turing completeness is left as an open question. This is an honest acknowledgment of the boundary of our results and does not affect any stated theorem.","revision_made":"yes","referee_comment":"Remark 14 states informally that a fixed linear time-invariant (non-selective) SSM 'is not automatically able to implement arbitrary finite-state control.' This is a meaningful claim... but it is not formally proved in the manuscript. A brief formal statement of what non-selective SSMs with tape access cannot do—or an explicit acknowledgment that this is left as an open question—would strengthen the narrative."}],"tokens_in":17282,"tokens_out":454,"duration_ms":131735,"standing_objections":[]},"desk_editor":{"model":"glm-5.2","letter":"Bottom line: this is a correct paper with a clean dichotomy — finite-state tools add log|M| bits, a tape tool gives Turing completeness with O(log|Q|+log|Γ|) bits — and the proofs all check out. The most valuable result is the lower bound in Theorem 23 (B−1 dimensions necessary for direct realization without external memory), which uses a nice congruence argument on the automaton (Z_B, s, c) and a nilpotent-orbit dimension argument. That is the genuinely original technical contribution here. The rest is standard automata theory executed correctly: the product-state simulation (Prop 4) is the usual cross-product construction, the tape simulation (Thm 7) is the standard TM simulation loop with a clear invariant, and the one-hot SSM realization (Lemma 12, Thm 13) is a straightforward encoding where A_ω is defined columnwise to map e_i to e_{δ(s_i,ω)} with zero biases. All fine, all correct, but not deep. The paper is honest about what is standard and what is new, which I appreciate. The resource conventions in Appendix B are transparently stated: the tape is free external memory, and the readout table is not charged to the recurrent-memory budget. This makes the logarithmic simulation (Thm 19) correct but somewhat unsurprising — you are hard-coding the machine description in the readout and copying it to the tape, so of course the recurrent state only needs a counter. Remark 24 explains why this is compatible with the B−1 lower bound, and the explanation is fair: they answer different questions. One soft spot: Remark 14 notes that selectivity is essential but only informally. There is no impossibility result for non-selective SSMs with tape access. This does not affect any stated theorem (the paper only claims sufficiency), but it leaves a natural open question unaddressed. Minor. The EQ_n separation (Thm 9) is a clean concrete instance of the gap — 2^n states without tools, constant with the tape — and serves its purpose well. This paper is for readers who want the exact resource accounting for tool-augmented recurrent computation stated precisely and proved from first principles. It delivers that. It deserves a serious referee.","headline":"Solid, correct paper giving a clean dichotomy for tool-augmented recurrent models. Proofs check out. The main novelty is the framing and exact resource accounting, not the constructions themselves, which are mostly standard automata theory. The lower bound (Thm 23) is the most original piece.","tokens_in":18410,"tokens_out":1049,"would_cite":false,"duration_ms":107428,"reading_group":"no","serious_thinker":"no","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"glm-5.2","headline":"Tape tool makes finite-state SSMs Turing complete","keywords":[],"falsifier":"If a fixed (non-selective) linear recurrent model with one common transition matrix could be shown to simulate arbitrary Turing machines with tape access, the claim that selectivity is essential would be falsified.","tokens_in":17650,"feed_emoji":"📼","tokens_out":1068,"duration_ms":118975,"temperature":0.7,"pith_summary":"This paper proves a sharp dichotomy about when giving external tools to a finite-precision recurrent model actually increases what it can compute. The central object is a deterministic finite-state controller — the abstraction that any fixed finite-precision recurrent model (including state-space models) reduces to, since B bits of internal state yield at most 2^B configurations. The authors show that finite-state tools with bounded interfaces add essentially nothing: the controller can internalize the tool's state at a cost of only log|tool memory| + O(1) bits, remaining a finite-state machine. But a single minimal infinite-state tool — a tape supporting only local read, write, and move commands — makes the controller Turing complete. A controller with just O(log|Q| + log|Gamma|) bits of internal memory (constant in input length) can simulate any single-tape Turing machine with state set Q and alphabet Gamma. The paper then proves this construction is realized exactly by a one-layer selective affine state-space model (SSM) with binary one-hot hidden states, {0,1} transition matrices, and zero biases. Selectivity — the ability of the transition matrix to depend on the current observation token — is the essential architectural ingredient. The paper provides a concrete exponential separation: deciding string equality EQ_n requires 2^n controller states without tools, but a single constant-size controller with tape access solves it for all n. In the supplement, the authors sharpen both directions: O(log B) recurrent bits suffice to simulate any B-state Turing machine by offloading the machine description onto the tape, while without external memory, exactly realizing an arbitrary B-state transition map in one affine update requires dimension exactly B-1, for any number of layers.","feed_headline":"Tape tool makes finite-state SSMs Turing complete","feed_subtitle":"A sharp dichotomy: finite-state tools add almost nothing, but one unbounded tape tool grants full Turing completeness with logarithmic","key_machinery":"A deterministic finite-state controller interacting with a tape oracle through local read/write/move commands, realized exactly by a one-layer selective affine SSM with one-hot binary hidden states and {0,1} transition matrices.","core_discovery":"The paper's core discovery is that the expressivity boundary for tool-augmented finite-precision recurrent models is determined entirely by whether the tool has bounded or unbounded state. Finite-state tools are internalizable at logarithmic cost and leave the system finite-state; one unbounded tape tool yields Turing completeness with logarithmic internal memory. This boundary is realized exactly in a one-layer selective affine SSM architecture, where input-dependent (selective) transition matrices with binary entries and zero biases suffice to implement arbitrary finite control. The matching impossibility result — that direct realization of a B-state transition map without external memory,","pith_inferences":["The sharpness of the dichotomy suggests that intermediate tools — those with unbounded but structured state (e.g., a counter, a stack) — should yield intermediate expressivity classes between regular and recursively enumerable, potentially mapping onto known levels of the Chomsky hierarchy. The paper's framework could likely formalize this.","If selectivity is the key architectural ingredient, one could test whether empirically trained selective SSMs (like Mamba) develop input-dependent transition patterns that resemble the one-hot finite-control structure the paper constructs, by inspecting learned matrices on tool-use tasks.","The resource-accounting conventions that distinguish the logarithmic from the linear bound suggest a design principle: for practical systems, hard-coding machine descriptions in readout parameters and using the tape as external memory may be far more parameter-efficient than attempting to encode transition logic in recurrent state alone."],"forward_implications":["If the paper's model is right, the practical question of whether a tool-augmented language model can exceed regular-language expressivity reduces to a single architectural test: does the tool maintain unbounded state?","The exact SSM construction shows that input-dependent transition matrices are the minimal architectural feature enabling Turing-complete behavior — a fixed transition matrix cannot realize arbitrary finite control, which constrains the design of SSM architectures intended for tool use.","The exponential EQ_n separation provides a concrete benchmark: any finite-precision recurrent model claiming tool-augmented expressivity should be testable on equality-checking tasks where the gap between 2^n and constant is observable at moderate n.","The dichotomy between the logarithmic oracle-assisted bound and the linear direct-realization bound quantifies exactly what external persistent memory and machine-specific readout parameters buy, giving a precise resource tradeoff for system designers."],"fun_headline_variants":["Tool state boundary governs recurrent model expressivity","Finite-state tools internalize; one unbounded tape enables Turing completeness","Single tape tool grants Turing completeness to finite SSMs","Selective affine SSMs implement arbitrary control with one tape tool","Tool expressivity hinges on bounded versus unbounded state"],"cache_read_input_tokens":0,"weakest_assumption_plain":"The exact realization by a selective affine SSM requires that the transition matrix can be selected based on the current observation token, and the logarithmic improvement in the appendix additionally relies on the conventions that the tape is free external memory and that fixed parameters and readout tables are not charged to the recurrent-memory budget.","fun_headline_variants_meta":{"raw":{"variants":["Tool state boundary governs recurrent model expressivity","Finite-state tools internalize; one unbounded tape enables Turing completeness","Single tape tool grants Turing completeness to finite SSMs","Selective affine SSMs implement arbitrary control with one tape tool","Tool expressivity hinges on bounded versus unbounded state"]},"model":"glm-5.2","effort":"high","cost_usd":0.0,"raw_usage":{"total_tokens":778,"prompt_tokens":698,"completion_tokens":80,"prompt_tokens_details":null},"tokens_in":698,"tokens_out":80,"duration_ms":22010,"temperature":1.0,"reasoning_tokens":null,"cache_read_input_tokens":0,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-08T14:52:18.614949+00:00","model_set":{"reader":"glm-5.2"},"falsifier":"If a fixed (non-selective) linear recurrent model with one common transition matrix could be shown to simulate arbitrary Turing machines with tape access, the claim that selectivity is essential would be falsified.","supporting_citations":[],"review_version":1}