:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Author:	Hubáček, Pavel
Format:	Preprint
Published:	2026
Subjects:	Computational Complexity
Online Access:	https://arxiv.org/abs/2602.23809
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

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

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

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

Black-Box Crypto is Useless for Pseudorandom Codes
by: Garg, Sanjam, et al.
Published: (2025)

Randomized Black-Box PIT for Small Depth +-Regular Non-commutative Circuits
by: Bharadwaj, G V Sumukha, et al.
Published: (2024)

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

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)

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

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

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

Dual-Tape Perspective and Generator Independence: The Algebraic Foundation of Real Boolean Turing Machines
by: Zheng, Jingwen, et al.
Published: (2026)

The Computational Boundary of Inference: Capability Internalization, Training, and the Turing Jump
by: Lu, Chien-Ping
Published: (2026)

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)

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

A conservative Turing complete $S^4$ flow
by: Suárez-Serrato, Pablo
Published: (2023)

Black-Box Identity Testing of Noncommutative Rational Formulas in Deterministic Quasipolynomial Time
by: Arvind, V., et al.
Published: (2023)

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

Perfect diffusion is $\mathsf{TC}^0$ -- Bad diffusion is Turing-complete
by: Liu, Yuxi
Published: (2025)

Privately Estimating Black-Box Statistics
by: Steinke, Günter F., et al.
Published: (2025)

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

Compression of Voxelized Vector Field Data by Boxes is Hard
by: Zhang, Simon
Published: (2025)

Rethinking the Role of Positional Encoding: Sliding-Window Transformers without PE Remain Turing Complete
by: Li, Qian, et al.
Published: (2026)

A note reviewing Turing's 1936
by: Cattabriga, Paola
Published: (2013)

What If Turing Had Preceded Gödel?
by: Oberhoff, Sebastian
Published: (2024)

Risk of Bad Tails: CVaR-Aware Pandora's Box and Prophet Inequality
by: Ji, Jingwei
Published: (2026)

Quantum Kolmogorov complexity and quantum correlations in deterministic-control quantum Turing machines
by: Lemus, Mariano, et al.
Published: (2023)

Multiplicative Turing Ensembles, Pareto's Law, and Creativity
by: Kolpakov, Alexander, et al.
Published: (2025)

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

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

Pushing Blocks via Checkable Gadgets: PSPACE-completeness of Push-1F and Block/Box Dude
by: Ani, Hayashi, et al.
Published: (2024)

Algorithms and Turing Kernels for Detecting and Counting Small Patterns in Unit Disk Graphs
by: Nederlof, Jesper, et al.
Published: (2023)

Turing in the shadows of Nobel and Abel: an algorithmic story behind two recent prizes
by: Gamarnik, David
Published: (2025)

A Quantum Pigeonhole Principle and Two Semidefinite Relaxations of Communication Complexity
by: Dvořák, Pavel, et al.
Published: (2024)

Lower Bounds on Cardinality of Reducts for Decision Tables from Closed Classes
by: Ostonov, Azimkhon, et al.
Published: (2024)

Exponential Separation Between Powers of Regular and General Resolution Over Parities
by: Bhattacharya, Sreejata Kishor, et al.
Published: (2024)

Deterministic and Strongly Nondeterministic Decision Trees for Decision Tables from Closed Classes
by: Ostonov, Azimkhon, et al.
Published: (2023)

Local Enumeration and Majority Lower Bounds
by: Gurumukhani, Mohit, et al.
Published: (2024)