Dual-Tape Perspective and Generator Independence: The Algebraic Foundation of Real Boolean Turing Machines
For theoretical computer science, this work provides an algebraic foundation for non-deterministic computation, but it is incremental as it extends existing concepts without demonstrating new computational capabilities.
The paper concretizes the abstract generator of the Complex Boolean Turing Machine as √2 to define the Real Boolean Turing Machine (RBTM) with a dual-tape perspective, and proves the Generator Independence Theorem showing that computational power is independent of the specific generator choice. This establishes that non-determinism fundamentally relies on introducing an element incommensurable with the base field.
The Complex Boolean Turing Machine (CBTM) characterizes non-deterministic computation using the abstract generator $α$, but the abstractness of $α$ makes it difficult to understand intuitively. In this paper, by concretizing $α$ as the algebraic number $\sqrt{2}$, we introduce the \textbf{Real Boolean Turing Machine (RBTM)} and propose the \textbf{dual-tape perspective}, decomposing each tape into a real tape (storing rational coefficients $a$) and an imaginary tape (storing irrational coefficients $b$). The ``1''s on the imaginary tape intuitively mark the locations of ``new dimensions,'' laying a physical foundation for subsequent dynamic dimension tracking. More importantly, we prove the \textbf{Generator Independence Theorem}: computational power is independent of the specific choice of generator, whether using $\sqrt{2}$, $\sqrt{3}$, or the imaginary unit $i$, the corresponding automata are isomorphic. This reveals that the essence of non-determinism lies in the fact of ``introducing a new element incommensurable with the base field,'' rather than the algebraic identity of the generator. Furthermore, we introduce the \textbf{generator extraction operator} and analyze its limitations within a static framework, highlighting the necessity of introducing a dynamic IVM. The RBTM serves both as a visualized instance of the CBTM and as a bridge to the subsequent dynamic dimension tracking of the Imaginary-part Verification Machine(IVM).