PaperlayerView exact revision on arXiv

Source-linked AI summary

Non-recursive trade-offs for two-way machines

Christos Kapoutsis

arXiv:2610.11969v1cs.FL

TL;DR

The paper addresses how to establish non-recursive description-size trade-offs across machine conversions. It combines an emptiness result for a restricted two-counter automaton with a general theorem, showing that certain simulation and problem-solving capabilities suffice for non-recursive trade-offs in many conversions.

  • Problem

    Earlier non-recursive trade-off arguments were tied to particular conversions, including a space conversion derived from strict separation between n²-space and n²+ε-space machines.

    Source: §1.1 · p. 3

  • Method

    The paper combines unrecognizability of emptiness for promised bounded, terminating, threshold-obeying dca2s with a general theorem linking simulation and problem-solving capabilities to non-recursive trade-offs.

    Source: §6 · p. 13

  • Results

    When type A can solve a problem no type B machine can solve and simulate a unary two-way deterministic finite automaton with a linearly bounded counter, the A-to-B trade-off is non-recursive.

    Source: §1.1 · p. 4

  • Takeaways & Limitations

    The theorem applies to numerous conversions, including counter and head hierarchies and work-tape-symbol reductions.

    Source: §1.1 · p. 4, §6 · p. 13

    The authors do not know whether the emptiness problem remains unrecognizable for the specified 2-register automaton; if it does, the main theorem can be slightly strengthened.

    Source: §6 · p. 13

Abstract

from arXiv · show

If the machines of some type A have enough resources to (i) solve problems that no machine of type B can solve, and (ii) simulate any unary two-way deterministic finite automaton that has access to a linearly-bounded counter, then typically no recursive function can upper bound the increase in the size of description when a machine of type A is replaced by an equivalent machine of type B.

1 Introduction

Prior work established exponential and triple-exponential bounds in some machine conversions, but also non-recursive trade-offs when equivalents exist. This study gives a general criterion for non-recursive trade-offs and applies it to multiple conversions.

1 Introduction

  • Rabin and Scott proved an exponential 1nfa-to-1dfa bound; Stearns gave a triple-exponential bound when 1dpa equivalents exist, while Meyer and Fischer found non-recursive bounds for equivalent 1npas.For 1npas with 1dfa-equivalents, the bound grows faster than any computable function.Source: §1 · p. 3
  • Hartmanis showed that a recursive trade-off typically implies recognizability of the inadequacy problem, simplifying proofs of non-recursive trade-offs.Inadequacy asks whether a given machine has no equivalent of the less powerful type.Source: §1 · p. 3

1.1 This study

  • If type A can solve a problem no type B machine can solve and simulate a unary two-way deterministic finite automaton with a linearly bounded counter, the A-to-B trade-off is non-recursive.The paper presents this as a loose statement of its general theorem.Source: §1.1 · pp. 3–4
  • Applications include k+1-to-k counter and head reductions, k+2-to-k register reductions, and k+1-to-k work-tape-symbol reductions.The listed cases include deterministic and nondeterministic variants, with unary-input qualifications for some work-tape cases.Source: §1.1 · p. 4
  • The trade-off from three to two heads is non-recursive for simple two-way deterministic finite automata, and also from two heads or one-head two-way deterministic pushdown automata.The paper states the broader result for all k ≥ 2.Source: §1.1 · p. 4
  • The informal theorem statement omits conditions on machine types, descriptions, and size measurement; the paper says most interesting examples satisfy them trivially.The complete conditions are in Section 3.Source: §1.1 · p. 4

1.2 Outline

  • The framework also covers language descriptors beyond machines, including regular expressions and grammars.The paper points to for a concrete discussion of a special case involving two-way multi-head finite automata.Source: §1.2 · p. 4

2 Preliminaries

The preliminaries formalize how descriptional systems are compared and show that, under stated conditions, a recursive trade-off bound makes the inadequacy problem recognizable. They also define a promised emptiness problem for bounded two-counter automata, which remains unrecognizable.

2 Preliminaries

  • A promise problem separates yes- and no-instances, and recognition requires accepting every yes-instance while rejecting no-instances, possibly by looping.A reduction from an unrecognizable problem transfers unrecognizability to the target problem; a threshold language contains all strings above some length.Source: §2 · p. 5

2.1 Descriptional systems

  • A descriptional system maps names to languages and sizes; a trade-off bound limits the smallest equivalent D-description as a function of an E-description’s size.The trade-off is recursive when a computable upper bound exists; inadequacy asks whether an E-name has no equivalent D-name.Source: §2.1 · pp. 5–6
  • Under conditions (H1)–(H3), a recursive trade-off bound from E to D implies that the inadequacy problem from E to D is recognizable.The conditions require decidable systems, effective size computation, and an effective finite list covering the D-languages up to a given size.Source: §2.1 · p. 6

2.2 Multi-counter automata

  • A dca_k uses k nonnegative-integer counters, with the primary counter capped by its input bound; a machine is bounded when secondary counters also stay within that bound.The model is a simplified unary two-way deterministic finite automaton with access to k−1 counters.Source: §2.2 · p. 7
  • Emptiness remains unrecognizable for dca2s promised to be bounded, terminating, and to obey a threshold.The paper states that the proof will show this problem is Π1-complete.Source: §2.2 · p. 7

3 The main theorem

Theorem 3 makes non-recursive trade-offs follow from a separation between description systems and the ability of the stronger system to simulate bounded dca2s that terminate and obey a threshold. Its proof reduces dca2 emptiness to the inadequacy problem, and the reduction also works under an empty-or-co-finite language promise.

3 The main theorem

  • If (C1)–(C3) hold alongside (H1)–(H3), the trade-off from E to D is non-recursive.(C1) requires an E-name with no D-equivalent; (C2) supports constructing an E-name from a promised dca2; (C3) requires D-names for all co-finite languages.Source: §3 · p. 8
  • The reduction maps a dca2 z to an E-name ez whose language is e0's language joined with all strings whose lengths belong to z's language.If z's language is empty, ez has no D-equivalent; if it is co-finite, ez has a D-equivalent by (C3).Source: §3 · p. 8
  • The simulation condition (C2) lets E construct ez by simulating z on the input length, then using e0's behavior if z does not accept.The promised dca2 never rejects by looping, a condition noted as important to the construction.Source: §3 · p. 8
  • The emptiness problem remains unrecognizable when the dca2 is promised to be bounded, terminating, and threshold-obeying.The reduction's inadequacy problem remains unrecognizable even when E-names are promised either to have no D-equivalent or to denote a co-finite language.Source: §3 · p. 8
  • The threshold promise can be relaxed to knowing only that the dca2 language is empty or co-finite.Condition (C3) is automatic when D-names describe machines with finite-state control, since co-finite languages are regular.Source: §3 · p. 8

4 Programming counters

The section introduces counter-program operations for clearing, transferring, multiplying, dividing, and finding powers. It specifies when bounded-counter operations can fail and how auxiliary counters preserve values.

4 Programming counters

  • A counter can be cleared by repeatedly decreasing it until it reaches zero.The operation is denoted by X ←−0.Source: §4 · p. 9
  • Contents can be transferred from Y into X by clearing X, then repeatedly decreasing Y and increasing X.If X is primary and Y exceeds its upper bound, the transfer fails, restores Y, and leaves X at zero; Y's original contents are preserved.Source: §4 · p. 9
  • Using X as an auxiliary counter, the program can multiply or divide Y by a constant, returning a remainder for division.When an attempted increase of primary X exceeds its bound, the operation restores Y and sets the failure flag.Source: §4 · p. 9
  • With a third counter Z, the program can count iterations to calculate lg_a n, failing when n = 0.Another variant sets Y to the largest power of a no greater than X, using Z as auxiliary and leaving X unchanged.Source: §4 · p. 10
  • If Y and Z initially do not exceed X, the largest-power operation never makes any counter exceed X's original value.The counter-bound property applies throughout the operation.Source: §4 · p. 10

5 Proof of Lemma 2

Lemma 2 is proved by reducing the complement of the halting problem to emptiness for bounded, terminating, threshold-obeying dca2s. The construction successively encodes a computation-history search and simulates it with bounded counters.

5 Proof of Lemma 2

  • The constructed dca2 M′ is empty when M loops on z and nonempty when M halts on z.The reduction starts from the complement of the halting problem and produces a terminating, bounded, threshold-obeying dca2.Source: §5 · p. 10
  • A searches the n-bit strings on input 0^n for an encoded halting computation history, accepting if it finds one and otherwise rejecting.The encoding ensures that if A accepts an input, it accepts every longer input; A maintains exactly n non-blank tape cells.Source: §5 · p. 11
  • The dca3 B simulates A using counters L and R to encode the tape portions on either side of the head, with H storing the head symbol.B initializes its simulation from the input-dependent counter bound and rejects inputs below 30.Source: §5 · p. 11
  • During B's simulation, its counters stay at or below lg_30 n, so M′'s corresponding multiplication attempts succeed and its counters remain bounded.The proof concludes that M′ never exceeds n during initialization or simulation, establishing that M′ is bounded.Source: §5 · pp. 12–13
  • The dca2 M′ simulates B by encoding its counters J, L, and R in V as 2^j3^l5^r.It initializes V and simulates B's counter operations through multiplication and division.Source: §5 · pp. 12–13

6 Conclusion

The paper combines unrecognizable bounded-dca2 emptiness with a simulation-and-separation theorem to derive non-recursive trade-offs across machine conversions. It leaves open whether the emptiness result holds for a more restricted 2-register automaton.

6 Conclusion

  • Unrecognizable bounded-dca2 emptiness, combined with the theorem's simulation and separation conditions, yields non-recursive trade-offs in many conversions.The conditions require type A to solve problems type B cannot solve and simulate the relevant dca2s.Source: §6 · p. 13
  • The paper leaves open whether the emptiness problem remains unrecognizable for a 2-register automaton whose primary counter starts at n and whose increments never fail.If it does, the main theorem can be made slightly stronger.Source: §6 · p. 13
  • A successful simulation requires a condition that is not automatically met: counter bounds in the simulated machine depend on other counters, unlike the corresponding bounds in B.The passage identifies this as a necessary simulation condition.Source: §6 · p. 13
Loading 2610.11969v1…