Buchumschlag

Metastability-Containing Turing Machines

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Bund, Johannes, Leshem, Amir, Medina, Moti
Format:	Preprint
Veröffentlicht:	2026
Schlagworte:	Computational Complexity
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Small Hazard-free Transducers
von: Bund, Johannes, et al.
Veröffentlicht: (2018)

Codes for Metastability-Containing Addition
von: Bund, Johannes, et al.
Veröffentlicht: (2026)

An origami Universal Turing Machine design
von: Assis, Michael
Veröffentlicht: (2024)

How Pinball Wizards Simulate a Turing Machine
von: Adejoh, Rosemary, et al.
Veröffentlicht: (2025)

Fagin's Theorem for Semiring Turing Machines
von: Badia, Guillermo, et al.
Veröffentlicht: (2025)

Complex Boolean Turing Machines: An Algebraic Semantic Framework for Computational Complexity
von: Zheng, Bojin, et al.
Veröffentlicht: (2026)

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

Simulating Polynomial-Time Nondeterministic Turing Machines via Nondeterministic Turing Machines
von: Lin, Tianrong
Veröffentlicht: (2024)

Stochastic Process Turing Machines
von: Wolpert, David, et al.
Veröffentlicht: (2024)

Black-Box PWPP Is Not Turing-Closed
von: Hubáček, Pavel
Veröffentlicht: (2026)

Iterative Optimization of Multidimensional Functions on Turing Machines under Performance Guarantees
von: Boche, Holger, et al.
Veröffentlicht: (2025)

Efficient Turing Machine Simulation with Transformers
von: Li, Qian, et al.
Veröffentlicht: (2025)

Flat origami is Turing Complete
von: Hull, Thomas C., et al.
Veröffentlicht: (2023)

Prime Successor Irreducibility: Turing Machine Complexity, Kolmogorov Complexity, and Weakness-Based Formulations
von: Goertzel, Ben, et al.
Veröffentlicht: (2026)

Topological entropy of Turing complete dynamics
von: Bruera, Renzo, et al.
Veröffentlicht: (2024)

Turing Completeness and Sid Meier's Civilization
von: de Wynter, Adrian
Veröffentlicht: (2021)

Diagonalization of Polynomial-Time Deterministic Turing Machines via Nondeterministic Turing Machines
von: Lin, Tianrong
Veröffentlicht: (2021)

Ask, and it shall be given: On the Turing completeness of prompting
von: Qiu, Ruizhong, et al.
Veröffentlicht: (2024)

Constant Bit-size Transformers Are Turing Complete
von: Li, Qian, et al.
Veröffentlicht: (2025)

Infinite Time Turing Machines and their Applications
von: Weerawarana, Rukmal, et al.
Veröffentlicht: (2025)

The Computational Boundary of Inference: Capability Internalization, Training, and the Turing Jump
von: Lu, Chien-Ping
Veröffentlicht: (2026)

A conservative Turing complete $S^4$ flow
von: Suárez-Serrato, Pablo
Veröffentlicht: (2023)

Perfect diffusion is $\mathsf{TC}^0$ -- Bad diffusion is Turing-complete
von: Liu, Yuxi
Veröffentlicht: (2025)

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

Cypher is Turing-Complete: A Formal Proof via 2-Counter Machine Simulation
von: Halftermeyer, Pierre
Veröffentlicht: (2026)

Polynomial Identity Testing and Reconstruction for Depth-4 Powering Circuits of High Degree
von: Shpilka, Amir, et al.
Veröffentlicht: (2026)

On Factorization of Sparse Polynomials of Bounded Individual Degree
von: Chuyoon, Aminadav, et al.
Veröffentlicht: (2026)

A note reviewing Turing's 1936
von: Cattabriga, Paola
Veröffentlicht: (2013)

A Hypergraph Container Method on Spread SAT: Approximation and Speedup
von: Han, Zicheng, et al.
Veröffentlicht: (2026)

On the Complexity of Hazard-Free Formulas
von: Arazi, Leah London, et al.
Veröffentlicht: (2024)

Quantum Kolmogorov complexity and quantum correlations in deterministic-control quantum Turing machines
von: Lemus, Mariano, et al.
Veröffentlicht: (2023)

What If Turing Had Preceded Gödel?
von: Oberhoff, Sebastian
Veröffentlicht: (2024)

PLS-completeness of string permutations
von: Scheder, Dominik, et al.
Veröffentlicht: (2025)

Multiplicative Turing Ensembles, Pareto's Law, and Creativity
von: Kolpakov, Alexander, et al.
Veröffentlicht: (2025)

The Algebraic Cost of a Boolean Sum
von: Orzel, Ian, et al.
Veröffentlicht: (2025)

Lower Bounds for Set-Multilinear Branching Programs
von: Chatterjee, Prerona, et al.
Veröffentlicht: (2023)

Improved Debordering of Waring Rank
von: Shpilka, Amir
Veröffentlicht: (2025)

Algorithms and Turing Kernels for Detecting and Counting Small Patterns in Unit Disk Graphs
von: Nederlof, Jesper, et al.
Veröffentlicht: (2023)

Turing in the shadows of Nobel and Abel: an algorithmic story behind two recent prizes
von: Gamarnik, David
Veröffentlicht: (2025)

$\mathsf{QAC}^0$ Contains $\mathsf{TC}^0$ (with Many Copies of the Input)
von: Grier, Daniel, et al.
Veröffentlicht: (2026)