Prof. Schönhage's Mysterious Machines
arXiv:2108.08606v11 citations
Originality Synthesis-oriented
AI Analysis
This work offers an incremental contribution to theoretical computer science by simplifying the proof of Turing completeness for Schönhage machines.
The authors tackled the problem of simulating Rule 110 cellular automaton iterations by constructing a simple Schönhage Storage Modification Machine, providing an alternative proof of Turing completeness for these machines.
We give a simple Schönhage Storage Modification Machine that simulates one iteration of the Rule 110 cellular automaton. This provides an alternative construction to Schönhage's original proof of the Turing completeness of the eponymous machines.