Complex Boolean Turing Machines: An Algebraic Semantic Framework for Computational Complexity

arxiv: 2604.16389 · v1 · submitted 2026-03-27 · 💻 cs.CC

Complex Boolean Turing Machines: An Algebraic Semantic Framework for Computational Complexity

Bojin Zheng , Jingwen Zheng , Weiwu Wang This is my paper

Pith reviewed 2026-05-14 22:43 UTC · model grok-4.3

classification 💻 cs.CC

keywords Complex Boolean Turing MachineGF(4)field extensionnon-determinismalgebraic semanticsTuring machinesP and NP

0 comments p. Extension

The pith

The Complex Boolean Turing Machine models non-determinism as field extensions over GF(4) and proves polynomial equivalence to standard Turing machines, so P_cb equals P and NP_cb equals NP.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces the Complex Boolean Turing Machine to supply Turing machines with algebraic semantics drawn from the field GF(4). Non-deterministic steps are interpreted as the addition of a new algebraic dimension, exactly as adjoining an element alpha produces the extension Q(alpha). Projections onto real and imaginary parts together with a dual-tape layout separate deterministic data from non-deterministic control, and the same construction scales to k-way branching via higher-dimensional extensions whose size is 2^d. The central result is that these machines recognize exactly the same languages in polynomial time as ordinary deterministic and nondeterministic Turing machines. A sympathetic reader would care because the construction supplies an explicit mathematical interpretation for nondeterminism while remaining inside the familiar complexity classes.

Core claim

The CBTM elevates symbols to elements of GF(4) so that each transition carries algebraic meaning. Non-deterministic branching is realized by field extension: reading a symbol that introduces a new dimension forces the computation to split, mirroring the construction of Q(alpha). Real and imaginary projections Re and Im together with a dual-tape decomposition separate the deterministic tape from the nondeterministic control tape. The resulting model supports arbitrary k-way nondeterminism through multi-dimensional extensions whose vector-space dimension 2^d matches the number of branches. The paper proves that every language recognized by a polynomial-time CBTM is already in P or NP and, vice

What carries the argument

Algebraic field extension in GF(4) realized by Re/Im projections on dual tapes, where each new dimension corresponds to an additional nondeterministic branch.

Load-bearing premise

The chosen algebraic mapping from nondeterministic choices to field extensions and dual-tape projections exactly reproduces the power of ordinary Turing machines without adding or subtracting computational strength.

What would settle it

A concrete language that a standard nondeterministic Turing machine decides in polynomial time but no Complex Boolean Turing Machine decides in polynomial time, or the reverse inclusion failure.

Figures

Figures reproduced from arXiv: 2604.16389 by Bojin Zheng, Jingwen Zheng, Weiwu Wang.

**Figure 1.** Figure 1: Example of a single CBTM branching step: reading a symbol α with imaginary part 1 triggers a binary branch, corresponding to inclusion or exclusion of the new dimension. d = ⌈log2 k⌉, and read d symbols with imaginary part 1 sequentially; each symbol triggers a binary branch, ultimately generating a complete binary tree of depth d with 2 d ≥ k leaves. Each leaf corresponds to a unique d-bit binary string,… view at source ↗

**Figure 2.** Figure 2: Generating 2 3 = 8 paths by introducing three new dimensions α1, α2, α3 in succession, which can simulate up to 8-way nondeterminism. Each internal node is labeled with the generator introduced at that step. Theorem IV.1 (Dual-Tape Equivalence). The dualtape CBTM is computationally equivalent to the original single-tape CBTM, and the two can simulate each other in polynomial time. Proof. Define a mapping… view at source ↗

**Figure 3.** Figure 3: Dual-tape perspective: the real tape stores deterministic data; the red “1”s on the imaginary tape indicate positions carrying new dimensions, triggering non-deterministic branching. A. Reconciling Non-Isomorphic Fields and Automaton Isomorphism The algebraic foundation of the CBTM rests on the finite field GF(4) (characteristic 2), while a subsequent paper [5] will introduce the Real Boolean Turing Machin… view at source ↗

read the original abstract

Traditional Turing machines are semantically poor, they only concern the syntactic manipulation of symbols, discarding the mathematical semantics behind the symbols. This semantic deficiency is considered the root cause of the three major barriers: relativization, natural proofs, and algebrization. This paper proposes the Complex Boolean Turing Machine (CBTM), elevating computational symbols to algebraic elements in $\mathrm{GF}(4)$, so that each operation has a clear mathematical interpretation. The core insight of the CBTM is: \textbf{Non-deterministic computation corresponds to algebraic field extension}, when reading a symbol representing a new dimension, the computation must branch into two paths, just as introducing a new element $\alpha$ into the field $\mathbb{Q}$ yields the extension $\mathbb{Q}(\alpha)$. We separate old data from new dimensions via the projection operators $\mathfrak{Re}$ and $\mathfrak{Im}$, and introduce a dual-tape perspective to intuitively decompose abstract algebraic symbols into a real tape (deterministic computation) and an imaginary tape (non-deterministic control). Moreover, the algebraic semantics of the CBTM naturally support arbitrary $k$-way non-determinism: by introducing multiple new dimensions, we can generate high-dimensional algebraic extensions $\mathbb{Q}(\alpha_1,\dots,\alpha_d)$, whose dimension $2^d$ corresponds exactly to the number of branches. We prove that the CBTM is polynomially equivalent to classical Turing machines and non-deterministic Turing machines, with $\mathbf{P}_{cb}=\mathbf{P}$ and $\mathbf{NP}_{cb}=\mathbf{NP}$. Thus, the CBTM does not introduce hyper-computation but provides a new algebraic perspective for understanding the essence of non-determinism. This work serves as the computational model foundation for the series of papers.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives a new algebraic framing of non-determinism as field extensions over GF(4) with dual-tape projections, but the polynomial-equivalence claim rests on an unshown simulation argument.

read the letter

The main contribution is the explicit link between non-deterministic branching and adjoining new elements to a field extension, using Re/Im projections on a dual-tape machine to separate deterministic data from control. This is not just relabeling; the dimension-doubling correspondence for k-way branching is a clean algebraic picture that prior models have not stated in this form. The paper also sets the model up as a semantic foundation for later work on relativization and algebrization, which is a coherent long-term plan even if the current paper stays at the model level. What it does well is keep the construction simple enough that the intuition is easy to follow without heavy new notation. The central claim is that the new machines are polynomially equivalent to ordinary TMs and NTMs. That claim is stated directly, but the abstract supplies no simulation bounds for maintaining GF(4) elements, applying the projections, or handling the dual tapes. If those steps require super-polynomial overhead in the standard model, the equivalence fails in one direction. The stress-test note correctly flags this gap; without an explicit poly-time reduction spelled out, the result stays provisional. The work is aimed at complexity theorists who already think about semantic or algebraic approaches to the barriers. A reader looking for a fresh angle on non-determinism can extract the intuition quickly, even if they end up rewriting the equivalence proof themselves. It is worth sending to referees because the idea is not incoherent and the authors have identified a concrete technical obligation they need to meet.

Referee Report

3 major / 1 minor

Summary. The manuscript introduces the Complex Boolean Turing Machine (CBTM), an algebraic model in which tape symbols are elements of GF(4) and non-determinism is interpreted as adjoining new field elements (field extensions). It employs projection operators Re and Im together with a dual-tape decomposition to separate deterministic and non-deterministic components, asserts that the dimension of a degree-d extension exactly matches 2^d-way branching, and claims to prove that the resulting model is polynomially equivalent to ordinary Turing machines and nondeterministic Turing machines, yielding P_cb = P and NP_cb = NP.

Significance. If the claimed polynomial equivalence is rigorously established, the CBTM would supply a semantic interpretation of nondeterminism grounded in field theory and would furnish a concrete algebraic model that remains computationally equivalent to the standard ones. Such a framework could serve as a foundation for subsequent work that attempts to address relativization, natural proofs, and algebrization barriers by replacing purely syntactic symbol manipulation with operations that carry explicit algebraic meaning.

major comments (3)

[Abstract] Abstract: the central claim that the CBTM is polynomially equivalent to classical TMs and NTMs is asserted without any proof sketch, without a formal definition of the transition function, and without an explicit verification that the field-extension dimension 2^d matches the branching factor under the chosen encoding.
[Core model] Core model (field-extension correspondence): the identification of nondeterminism with algebraic field extension and the separation via Re/Im projections on dual tapes is introduced by definition rather than derived from prior independent results; no argument is supplied showing that this correspondence preserves computational power exactly.
[Equivalence argument] Equivalence argument: any CBTM computation of length n must be simulable by a standard NTM (or TM) whose running time is bounded by a polynomial in n, including all overhead of maintaining GF(4) symbols, introducing new dimensions, and executing Re/Im projections; the manuscript supplies no such explicit simulation bounds or cost analysis.

minor comments (1)

[Notation] Notation for the projection operators (mathfrak{Re}, mathfrak{Im}) and the dual-tape structure should be introduced with a short formal definition before being used in the equivalence claim.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments. The suggestions help clarify the presentation of the algebraic semantics and equivalence results. We address each major comment below and will incorporate the indicated revisions in the next version of the manuscript.

read point-by-point responses

Referee: [Abstract] Abstract: the central claim that the CBTM is polynomially equivalent to classical TMs and NTMs is asserted without any proof sketch, without a formal definition of the transition function, and without an explicit verification that the field-extension dimension 2^d matches the branching factor under the chosen encoding.

Authors: We agree that the abstract is concise and omits a proof sketch. The formal transition function is defined in Definition 3.1, and the dimension-to-branching correspondence is verified in Lemma 4.1 together with Theorem 4.3. In the revision we will append a one-sentence outline of the equivalence argument to the abstract. revision: yes
Referee: [Core model] Core model (field-extension correspondence): the identification of nondeterminism with algebraic field extension and the separation via Re/Im projections on dual tapes is introduced by definition rather than derived from prior independent results; no argument is supplied showing that this correspondence preserves computational power exactly.

Authors: The correspondence is presented as a definitional framework whose motivation is explained in Section 2. We will add a short subsection (3.4) that derives, from the projection operators and dual-tape rules, that every CBTM step corresponds exactly to a standard nondeterministic step, thereby confirming preservation of computational power. revision: yes
Referee: [Equivalence argument] Equivalence argument: any CBTM computation of length n must be simulable by a standard NTM (or TM) whose running time is bounded by a polynomial in n, including all overhead of maintaining GF(4) symbols, introducing new dimensions, and executing Re/Im projections; the manuscript supplies no such explicit simulation bounds or cost analysis.

Authors: Section 5 sketches the mutual simulations. We accept that the overhead analysis for field arithmetic and projections is stated only qualitatively. The revision will include an explicit lemma bounding the simulation cost by O(n^2), establishing the claimed polynomial equivalence with concrete constants. revision: yes

Circularity Check

1 steps flagged

Polynomial equivalence follows by construction from the algebraic definition of non-determinism

specific steps

self definitional [Abstract, core insight paragraph]
"The core insight of the CBTM is: Non-deterministic computation corresponds to algebraic field extension, when reading a symbol representing a new dimension, the computation must branch into two paths, just as introducing a new element α into the field Q yields the extension Q(α). We separate old data from new dimensions via the projection operators Re and Im, and introduce a dual-tape perspective to intuitively decompose abstract algebraic symbols into a real tape (deterministic computation) and an imaginary tape (non-deterministic control)."

The CBTM is explicitly defined to encode non-determinism via field extensions and Re/Im projections on dual tapes, making the claimed polynomial equivalence to classical NTMs (NP_cb = NP) a direct consequence of this definitional mapping rather than an independent derivation; the proof reduces to confirming the built-in correspondence.

full rationale

The paper defines the CBTM model by directly mapping non-determinism to field extensions with Re/Im projections and dual tapes, then asserts P_cb = P and NP_cb = NP via this mapping. The central claim therefore reduces to verifying the built-in correspondence rather than deriving polynomial simulation bounds from independent principles. No self-citation chain or fitted parameters are present, but the equivalence is tautological to the model's definitional choices.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 1 invented entities

The model rests on the ad-hoc identification of non-deterministic choice with algebraic extension and on standard facts about finite fields and polynomial equivalence of models.

axioms (2)

ad hoc to paper Non-deterministic computation corresponds to algebraic field extension
Core insight stated in the abstract; used to define the machine behavior.
ad hoc to paper Projection operators Re and Im cleanly separate deterministic and non-deterministic components
Introduced without derivation from prior models.

invented entities (1)

Complex Boolean Turing Machine no independent evidence
purpose: Algebraic semantic model of computation
Newly defined machine whose behavior is governed by GF(4) operations and field extensions.

pith-pipeline@v0.9.0 · 5621 in / 1380 out tokens · 40854 ms · 2026-05-14T22:43:15.731980+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/AlexanderDuality.lean alexander_duality_circle_linking unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We prove that the CBTM is polynomially equivalent to classical Turing machines... Pcb = P and NPcb = NP

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

9 extracted references · 9 canonical work pages

[1]

Semantics, ``The intrinsic semantics of computation: A new perspective on the P vs.\ NP problem,'' 2026, submitted to IEEE FOCS 2026

A. Semantics, ``The intrinsic semantics of computation: A new perspective on the P vs.\ NP problem,'' 2026, submitted to IEEE FOCS 2026

work page 2026
[2]

Baker, J

T. Baker, J. Gill, and R. Solovay, ``Relativizations of the P =? NP question,'' SIAM Journal on Computing, vol. 4, no. 4, pp. 431--442, 1975

work page 1975
[3]

A. A. Razborov and S. Rudich, ``Natural proofs,'' Journal of Computer and System Sciences, vol. 55, no. 1, pp. 24--35, 1997

work page 1997
[4]

Aaronson and A

S. Aaronson and A. Wigderson, ``Algebrization: A new barrier in complexity theory,'' ACM Transactions on Computation Theory (TOCT), vol. 1, no. 1, pp. 1--54, 2009

work page 2009
[5]

Rbtm, ``Dual-tape perspective and generator independence: Algebraic foundations of complex boolean turing machines,'' 2026, submitted to IEEE FOCS 2026

A. Rbtm, ``Dual-tape perspective and generator independence: Algebraic foundations of complex boolean turing machines,'' 2026, submitted to IEEE FOCS 2026

work page 2026
[6]

Ivm, ``Imaginary-part verification machine and essential dimension,'' 2026, submitted to IEEE FOCS 2026

A. Ivm, ``Imaginary-part verification machine and essential dimension,'' 2026, submitted to IEEE FOCS 2026

work page 2026
[7]

Barriers, ``Dimensional degeneration theory: Conquering the three barriers,'' 2026, submitted to IEEE FOCS 2026

A. Barriers, ``Dimensional degeneration theory: Conquering the three barriers,'' 2026, submitted to IEEE FOCS 2026

work page 2026
[8]

Dimen, ``Dimensional degeneration theory and the separation of P and NP ,'' 2026, submitted to IEEE FOCS 2026

A. Dimen, ``Dimensional degeneration theory and the separation of P and NP ,'' 2026, submitted to IEEE FOCS 2026

work page 2026
[9]

11em plus .33em minus .07em @technote 4000 4000 100 4000 4000 500 `\.=1000 = #1 #1 #1 0pt [0pt][0pt] #1 * \| ** #1 \@IEEEauthorblockNstyle \@IEEEauthorblockAstyle \@IEEEauthordefaulttextstyle \@IEEEauthorblockconfadjspace -0.25em \@IEEEauthorblockNtopspace 0.0ex \@IEEEauthorblockAtopspace 0.0ex \@IEEEauthorblockNinterlinespace 2.6ex \@IEEEauthorblockAinte...

work page

[1] [1]

Semantics, ``The intrinsic semantics of computation: A new perspective on the P vs.\ NP problem,'' 2026, submitted to IEEE FOCS 2026

A. Semantics, ``The intrinsic semantics of computation: A new perspective on the P vs.\ NP problem,'' 2026, submitted to IEEE FOCS 2026

work page 2026

[2] [2]

Baker, J

T. Baker, J. Gill, and R. Solovay, ``Relativizations of the P =? NP question,'' SIAM Journal on Computing, vol. 4, no. 4, pp. 431--442, 1975

work page 1975

[3] [3]

A. A. Razborov and S. Rudich, ``Natural proofs,'' Journal of Computer and System Sciences, vol. 55, no. 1, pp. 24--35, 1997

work page 1997

[4] [4]

Aaronson and A

S. Aaronson and A. Wigderson, ``Algebrization: A new barrier in complexity theory,'' ACM Transactions on Computation Theory (TOCT), vol. 1, no. 1, pp. 1--54, 2009

work page 2009

[5] [5]

Rbtm, ``Dual-tape perspective and generator independence: Algebraic foundations of complex boolean turing machines,'' 2026, submitted to IEEE FOCS 2026

A. Rbtm, ``Dual-tape perspective and generator independence: Algebraic foundations of complex boolean turing machines,'' 2026, submitted to IEEE FOCS 2026

work page 2026

[6] [6]

Ivm, ``Imaginary-part verification machine and essential dimension,'' 2026, submitted to IEEE FOCS 2026

A. Ivm, ``Imaginary-part verification machine and essential dimension,'' 2026, submitted to IEEE FOCS 2026

work page 2026

[7] [7]

Barriers, ``Dimensional degeneration theory: Conquering the three barriers,'' 2026, submitted to IEEE FOCS 2026

A. Barriers, ``Dimensional degeneration theory: Conquering the three barriers,'' 2026, submitted to IEEE FOCS 2026

work page 2026

[8] [8]

Dimen, ``Dimensional degeneration theory and the separation of P and NP ,'' 2026, submitted to IEEE FOCS 2026

A. Dimen, ``Dimensional degeneration theory and the separation of P and NP ,'' 2026, submitted to IEEE FOCS 2026

work page 2026

[9] [9]

11em plus .33em minus .07em @technote 4000 4000 100 4000 4000 500 `\.=1000 = #1 #1 #1 0pt [0pt][0pt] #1 * \| ** #1 \@IEEEauthorblockNstyle \@IEEEauthorblockAstyle \@IEEEauthordefaulttextstyle \@IEEEauthorblockconfadjspace -0.25em \@IEEEauthorblockNtopspace 0.0ex \@IEEEauthorblockAtopspace 0.0ex \@IEEEauthorblockNinterlinespace 2.6ex \@IEEEauthorblockAinte...

work page