This project extends classical Turing machine mechanics from traditional 1D tapes to complex, abstract graph topologies.
The primary objective is autonomous graph traversal under strict local-memory constraints, culminating in a proven upper-bound configuration for
Unlike traditional graph traversal algorithms (like BFS or DFS) that rely on global positioning, coordinate maps, or unique vertex IDs, the traversal mechanics in this project are strictly localized. The Turing machine has no access to node labels or global coordinate tracking. At any given moment, the machine's behavior is dictated solely by: its current internal state.The symbol written on the current vertex.The number of available edges/directions at the current vertex. The machine modifies the symbols on the vertices as it transitions, using the graph itself as its infinite read/write tape.
The framework implements five distinct graph topologies along with custom traversal rule sets designed for each: 1.) 1D Unidirectional and Bidirectional Infinite Tapes: The classical Turing machine environment, visualized as an infinite sequence of square cells where the head transitions bi-directionally. 2.) 2D Grid Networks: Expansion into coordinate-free planar grids, utilizing directional transition logic (Up, Down, Left, Right) to execute patterns like expanding spirals. 3.) n-Ary Trees (Binary & Beyond): Hierarchical structures traversed via a structural "breadcrumb" method, mapping parent-child relationships solely through local edge choices. 4.) n-Regular Graphs (Cyclic & Beyond): Topologies where paths loop back on themselves, requiring careful symbol management to prevent infinite local loops.
A major milestone of this project is the formalization and proof of the state-symbol configuration limit on tree structures.
Theorem: The upper bound of the configuration required for a deterministic Turing machine to successfully traverse and map an arbitrary n-ary tree without getting trapped or lost is provably (2,2n), where 2 represents the maximum number of internal machine states required and 2n represents the maximum size of the alphabet (symbols per node).