Dual-Tape Perspective and Generator Independence: The Algebraic Foundation of Real Boolean Turing Machines
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911602855378944 |
|---|---|
| author | Zheng, Jingwen Zheng, Bojin Wang, Weiwu |
| author_facet | Zheng, Jingwen Zheng, Bojin Wang, Weiwu |
| contents | 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). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_16390 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Dual-Tape Perspective and Generator Independence: The Algebraic Foundation of Real Boolean Turing Machines Zheng, Jingwen Zheng, Bojin Wang, Weiwu Computational Complexity 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). |
| title | Dual-Tape Perspective and Generator Independence: The Algebraic Foundation of Real Boolean Turing Machines |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2604.16390 |