Turing Machine WASM

Rust/WebAssembly parser and runtime for concrete deterministic, one-way-infinite Turing machines. Core execution follows Michael Sipser's Introduction to the Theory of Computation, 3rd edition, Section 3.1.

Symbols are Unicode scalar characters, represented by Rust's four-byte char type and JavaScript strings at the WASM boundary. A machine's alphabets are inferred from its transitions; blank is displayed as ⊔ and is always part of the tape alphabet. Transition tables may be partial, and execution reports an error if no transition exists for the current state and symbol.

Program syntax

model sipser-3e;
/// Accepts when the input contains a one.
program ContainsOne;
start q0;
accept q_accept;
reject q_reject;
q0, "0" -> q0, "0", R;
q0, "1" -> q_accept, "1", R;
q0, "#" -> q_reject, "#", R;
q0, blank -> q_reject, blank, R;

Quoted symbols accept JSON escapes and may contain any one character, including whitespace and punctuation:

q0, "λ" -> q1, " ", R;
q1, "," -> q_accept, "\\n", R;

Functions use the same concrete structure with function Name;. Composition, imports, namespaces, and module loading are host responsibilities rather than WASM runtime concepts.

model sipser-3e;
function NamespacedNot;
start module_1_q0;
accept q_next;
reject q_reject;
module_1_q0, "0" -> q_next, "1", R;
module_1_q0, "1" -> q_next, "0", R;
module_1_q0, "#" -> q_reject, "#", R;
module_1_q0, blank -> q_reject, blank, R;

Calling load replaces the concrete transition table and enters its start state while preserving the tape, head position, and cumulative step count. Hosts can therefore load namespaced functions lazily without expanding an entire composition in memory.

TypeScript API

import init, { Machine } from '@marcosousapoza/turing-machine-wasm'

await init()
const direct = new Machine(programSource, 'hello')
JSON.parse(direct.run(1_000_000))
JSON.parse(direct.load(nextConcreteFunctionSource))
JSON.parse(direct.set_tape('world'))
JSON.parse(direct.set_head(3))

set_tape and set_head replace the tape and head baselines used by reset. /// Markdown documentation is retained as metadata. WASM performs no network access and only handles one concrete machine definition at a time.

Development

cargo test
cargo clippy --all-targets -- -D warnings
wasm-pack build --target web --scope marcosousapoza