Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2510.02560 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914072465768448 |
|---|---|
| author | Adejoh, Rosemary Jakoby, Andreas Mohanty, Sneha Schindelhauer, Christian |
| author_facet | Adejoh, Rosemary Jakoby, Andreas Mohanty, Sneha Schindelhauer, Christian |
| contents | We introduce and investigate the computational complexity of a novel physical problem known as the Pinball Wizard problem. It involves an idealized pinball moving through a maze composed of one-way gates (outswing doors), plane walls, parabolic walls, moving plane walls, and bumpers that cause acceleration or deceleration. Given the initial position and velocity of the pinball, the task is to decide whether it will hit a specified target point.
By simulating a two-stack pushdown automaton, we show that the problem is Turing-complete -- even in two-dimensional space. In our construction, each step of the automaton corresponds to a constant number of reflections. Thus, deciding the Pinball Wizard problem is at least as hard as the Halting problem. Furthermore, our construction allows bumpers to be replaced with moving walls. In this case, even a ball moving at constant speed -- a so-called ray particle -- can be used, demonstrating that the Ray Particle Tracing problem is also Turing-complete. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_02560 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | How Pinball Wizards Simulate a Turing Machine Adejoh, Rosemary Jakoby, Andreas Mohanty, Sneha Schindelhauer, Christian Computational Complexity We introduce and investigate the computational complexity of a novel physical problem known as the Pinball Wizard problem. It involves an idealized pinball moving through a maze composed of one-way gates (outswing doors), plane walls, parabolic walls, moving plane walls, and bumpers that cause acceleration or deceleration. Given the initial position and velocity of the pinball, the task is to decide whether it will hit a specified target point. By simulating a two-stack pushdown automaton, we show that the problem is Turing-complete -- even in two-dimensional space. In our construction, each step of the automaton corresponds to a constant number of reflections. Thus, deciding the Pinball Wizard problem is at least as hard as the Halting problem. Furthermore, our construction allows bumpers to be replaced with moving walls. In this case, even a ball moving at constant speed -- a so-called ray particle -- can be used, demonstrating that the Ray Particle Tracing problem is also Turing-complete. |
| title | How Pinball Wizards Simulate a Turing Machine |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2510.02560 |