5 hours ago
- Multiway Turing machines (NDTMs) are explored as minimal models of concurrent computing and quantum mechanics.
- Simple multiway Turing machine rules can produce surprisingly complex behavior, unlike ordinary Turing machines.
- With s=1, k=2, p=3 (single head state, two colors, three rule cases), multiway Turing machines may achieve computation universality.
- Causal invariance and confluence in multiway systems are studied, with some rules allowing branching and merging of paths.
- Busy beaver problems for multiway Turing machines consider maximal halting times and number of states across branches.
- Multispace visualization combines spatial and branchial dimensions to depict multiway Turing machine evolution.
- Finite-tape multiway Turing machines show state transition graphs with varying connectivity and halting conditions.