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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Universality of Turing Tumble of Finite Size

  • Artiom Alhazov,
  • Rudolf Freund,
  • Sergiu Ivanov,
  • Sergey Verlan

摘要

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.