Universality of Turing Tumble of Finite Size
摘要
The Turing Tumble is a mechanical puzzle game that simulates the operations of a computer processor using marbles and various mechanical components. The game allows for a visual representation of the computation and is widely used in the educational context. It was shown to be Turing-complete providing that an appropriate infinite configuration of the board, an infinite marble supply and the possibility to construct arbitrarily long frictionless gear chains are available. In this paper we show the computational universality of the game for a finite configuration and no unbounded gear chains. The only source of infinity is the supply of marbles and the unbounded drop capacity. We also provide a thoughtful analysis of the computation representation in Turing Tumble and discuss the possible input and output types.