Cover Image

How Pinball Wizards Simulate a Turing Machine

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Adejoh, Rosemary, Jakoby, Andreas, Mohanty, Sneha, Schindelhauer, Christian
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
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)

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)

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

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

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

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)

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

Cypher is Turing-Complete: A Formal Proof via 2-Counter Machine Simulation
by: Halftermeyer, Pierre
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)

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

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

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)

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

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

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

Simulation of Turing machines with analytic discrete ODEs: FPTIME and FPSPACE over the reals characterised with discrete ordinary differential equations
by: Blanc, Manon, et al.
Published: (2023)

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)

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

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

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

Simulating Time With Square-Root Space
by: Williams, R. Ryan
Published: (2025)

Small Even Covers, Locally Decodable Codes and Restricted Subgraphs of Edge-Colored Kikuchi Graphs
by: Hsieh, Jun-Ting, et al.
Published: (2024)

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

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

Symmetric Parameterised Holants on Hypergraphs: Towards a Classification for Parameterised VCSPs
by: Aivasiliotis, Panagiotis, et al.
Published: (2025)

Rigorous Implications of the Low-Degree Heuristic
by: Hsieh, Jun-Ting, et al.
Published: (2026)

Toward a Characterization of Simulation Between Arithmetic Theories
by: Monroe, Hunter
Published: (2026)

d-QBF with Few Existential Variables Revisited
by: Grigorjew, Andreas, et al.
Published: (2026)

A Survey on the Applications of Zero-Knowledge Proofs
by: Lavin, Ryan, et al.
Published: (2024)

Breaking the Temporal Complexity Barrier: Bucket Calculus for Parallel Machine Scheduling
by: Mohammad, Noor Islam S.
Published: (2026)

On the Hardness of the Drone Delivery Problem
by: Bartlmae, Simon, et al.
Published: (2025)

An even simpler hard variant of Not-All-Equal 3-SAT
by: Darmann, Andreas, et al.
Published: (2024)