Cover Image

Dual-Tape Perspective and Generator Independence: The Algebraic Foundation of Real Boolean Turing Machines

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Zheng, Jingwen, Zheng, Bojin, Wang, Weiwu
Format:	Preprint
Published:	2026
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Complex Boolean Turing Machines: An Algebraic Semantic Framework for Computational Complexity
by: Zheng, Bojin, et al.
Published: (2026)

The Radical Solution and Computational Complexity
by: Zheng, Bojin, et al.
Published: (2024)

The Algebraic Cost of a Boolean Sum
by: Orzel, Ian, et al.
Published: (2025)

Metastability-Containing Turing Machines
by: Bund, Johannes, et al.
Published: (2026)

An origami Universal Turing Machine design
by: Assis, Michael
Published: (2024)

How Pinball Wizards Simulate a Turing Machine
by: Adejoh, Rosemary, et al.
Published: (2025)

Fagin's Theorem for Semiring Turing Machines
by: Badia, Guillermo, et al.
Published: (2025)

Efficient Turing Machine Simulation with Transformers
by: Li, Qian, et al.
Published: (2025)

Simulating Polynomial-Time Nondeterministic Turing Machines via Nondeterministic Turing Machines
by: Lin, Tianrong
Published: (2024)

Stochastic Process Turing Machines
by: Wolpert, David, et al.
Published: (2024)

Black-Box PWPP Is Not Turing-Closed
by: Hubáček, Pavel
Published: (2026)

Iterative Optimization of Multidimensional Functions on Turing Machines under Performance Guarantees
by: Boche, Holger, et al.
Published: (2025)

Flat origami is Turing Complete
by: Hull, Thomas C., et al.
Published: (2023)

Instance complexity of Boolean functions
by: Liu, Alison Hsiang-Hsuan, et al.
Published: (2023)

When Does Sparsity Help for k-Independent Set in Hypergraphs and Other Boolean CSPs?
by: Fritsch, Timo, et al.
Published: (2026)

Constant Bit-size Transformers Are Turing Complete
by: Li, Qian, et al.
Published: (2025)

Prime Successor Irreducibility: Turing Machine Complexity, Kolmogorov Complexity, and Weakness-Based Formulations
by: Goertzel, Ben, et al.
Published: (2026)

Ideal Membership Problem for Boolean Minority and Dual Discriminator
by: Bharathi, Arpitha P., et al.
Published: (2024)

Boolean Functions with Minimal Spectral Sensitivity
by: Prūsis, Krišjānis, et al.
Published: (2024)

On Boolean PCSPs with Polynomial Threshold Polymorphisms
by: Michno, Katzper
Published: (2025)

Special Coverings of Sets and Boolean Functions
by: Margaryan, Stepan
Published: (2024)

Inverse Intersections for Boolean Satisfiability Problems
by: Homer, Paul W.
Published: (2025)

Nearest Neighbor Complexity and Boolean Circuits
by: DiCicco, Mason, et al.
Published: (2024)

Boolean PCSPs through the lens of Fourier Analysis
by: Banakh, Demian, et al.
Published: (2026)

Topological entropy of Turing complete dynamics
by: Bruera, Renzo, et al.
Published: (2024)

Turing Completeness and Sid Meier's Civilization
by: de Wynter, Adrian
Published: (2021)

Local Correction of Linear Functions over the Boolean Cube
by: Amireddy, Prashanth, et al.
Published: (2024)

Low Degree Local Correction Over the Boolean Cube
by: Amireddy, Prashanth, et al.
Published: (2024)

Boolean Circuit Complexity and Two-Dimensional Cover Problems
by: Cavalar, Bruno P., et al.
Published: (2025)

Boolean functions on high-dimensional expanders
by: Dikstein, Yotam, et al.
Published: (2018)

Diagonalization of Polynomial-Time Deterministic Turing Machines via Nondeterministic Turing Machines
by: Lin, Tianrong
Published: (2021)

The Counting General Dominating Set Framework
by: Zheng, Jiayi, et al.
Published: (2026)

Heuristics Optimization of Boolean Circuits with application in Attribute Based Encryption
by: Ionita, Alexandru, et al.
Published: (2023)

Range Avoidance in Boolean Circuits via Turan-type Bounds
by: Kuntewar, Neha, et al.
Published: (2025)

On the Complexity of Techniques That Make Transition Systems Implementable by Boolean Nets
by: Devillers, Raymond, et al.
Published: (2022)

Ask, and it shall be given: On the Turing completeness of prompting
by: Qiu, Ruizhong, et al.
Published: (2024)

Infinite Time Turing Machines and their Applications
by: Weerawarana, Rukmal, et al.
Published: (2025)

On the Rational Degree of Boolean Functions and Applications
by: Iyer, Vishnu, et al.
Published: (2023)

Algebraic Pseudorandomness in $VNC^0$
by: Andrews, Robert
Published: (2025)

On the Existence of Algebraic Natural Proofs
by: Chatterjee, Prerona, et al.
Published: (2020)