feat: multi-tape and nondeterministic Turing machines (TM+) #73

Closed
opened 2026-10-24 18:41:42 -05:00 by Ghost · 0 comments

Add multi-tape and nondeterministic Turing machines by extending the existing Tm type in place — authorized contract break (owner, 2026-10-24): the service went live today with no users, and one type is tidier than a parallel TmX. After this lands, the new shape becomes the frozen one and is documented in docs/reference.md.

Core (crates/rgxr-core/src/tm.rs)

  • Tm gains tapes: usize (serde default 1); transitions become state → read-tuple ("0,_") → Vec<TmAction>; list length > 1 ⇒ nondeterministic
  • Compat shim in the deserializer: accept the old shape (single action object, implied 1 tape) so existing saved docs keep loading
  • Engine: existing deterministic 1-tape loop stays as the fast path (current tests unchanged); BFS with visited set (PDA pattern: explored, config cap, truncated = inconclusive, shortest accepting path) when tapes > 1 or any action list > 1
  • Machine::Tm grade variant charges both paths to the shared work budget; TmRunResult gains explored + truncated

API: same endpoint POST /api/v1/tm/run, extended schemas in openapi.yaml; regen schema.d.ts; round-trip test updated

Web: same TM mode on the machines page + variant controls (tapes 1–4, ND via repeated transition lines); DSL: tapes N directive, per-tape transitions q0, 0, _ -> q1, X, R | _, R, repeated LHS allowed; multi-row tape UI; explored/truncated display; per-tape diagram edge labels; all strings bilingual (en+es)

Dojo: 2–3 verified tmLibrary.ts entries — {ww} via 2-tape copy-compare, palindromes via 2-tape, one ND machine with pruning — JS oracle tests extended, bilingual fields

Tests: old-shape shim, 2-tape ≡ 1-tape equivalence, ND pruning/truncation/timeout, adversarial budget test, API round-trip, DSL parse tests
CI: add bun run check to the web job (enforces Spanish coverage)

Other objects: if any other frozen shape would force duplicity or a messy design, breaking it is pre-authorized — document the break in the PR.
Constraints: no v* tags (test env tracks master; prod stays on the initial plan)

Add multi-tape and nondeterministic Turing machines by **extending the existing `Tm` type in place** — authorized contract break (owner, 2026-10-24): the service went live today with no users, and one type is tidier than a parallel `TmX`. After this lands, the new shape becomes the frozen one and is documented in `docs/reference.md`. **Core (`crates/rgxr-core/src/tm.rs`)** - `Tm` gains `tapes: usize` (serde default 1); transitions become `state → read-tuple ("0,_") → Vec<TmAction>`; list length > 1 ⇒ nondeterministic - Compat shim in the deserializer: accept the old shape (single action object, implied 1 tape) so existing saved docs keep loading - Engine: existing deterministic 1-tape loop stays as the fast path (current tests unchanged); BFS with visited set (PDA pattern: `explored`, config cap, `truncated` = inconclusive, shortest accepting path) when `tapes > 1` or any action list > 1 - `Machine::Tm` grade variant charges both paths to the shared work budget; `TmRunResult` gains `explored` + `truncated` **API:** same endpoint `POST /api/v1/tm/run`, extended schemas in openapi.yaml; regen `schema.d.ts`; round-trip test updated **Web:** same TM mode on the machines page + variant controls (tapes 1–4, ND via repeated transition lines); DSL: `tapes N` directive, per-tape transitions `q0, 0, _ -> q1, X, R | _, R`, repeated LHS allowed; multi-row tape UI; explored/truncated display; per-tape diagram edge labels; all strings bilingual (en+es) **Dojo:** 2–3 verified `tmLibrary.ts` entries — {ww} via 2-tape copy-compare, palindromes via 2-tape, one ND machine with pruning — JS oracle tests extended, bilingual fields **Tests:** old-shape shim, 2-tape ≡ 1-tape equivalence, ND pruning/truncation/timeout, adversarial budget test, API round-trip, DSL parse tests **CI:** add `bun run check` to the web job (enforces Spanish coverage) **Other objects:** if any other frozen shape would force duplicity or a messy design, breaking it is pre-authorized — document the break in the PR. **Constraints:** no `v*` tags (test env tracks master; prod stays on the initial plan)
Ghost closed this issue 2026-10-24 20:22:03 -05:00
Ghost added this to the SCRUM project 2026-10-24 20:48:22 -05:00
Sign in to join this conversation.
No labels
No milestone
No project
No assignees
1 participant
Notifications
Due date
The due date is invalid or out of range. Please use the format "yyyy-mm-dd".

No due date set.

Dependencies

No dependencies set

Reference
k8s-services/rgxr#73
No description provided.