Turing Tumble

Last updated
A beginner's Turing Tumble layout Turing Tumble game board.jpg
A beginner's Turing Tumble layout

Turing Tumble is a game and demonstration of logic gates via mechanical computing.

Contents

Description

Named after Alan Turing, the game could, in the abstract, duplicate the processes of any computer whatsoever if the game field itself were sufficiently large. This follows because the game is P-complete by the circuit value problem and PSPACE-complete if an exponential number of marbles is allowed. [1] [2] The device has implications for nanotechnology. [3] [4]

The game is advertised as Turing complete: an extension of the game that allows an infinitely large board and infinitely many pieces has been shown to be Turing complete via simulations of both Rule 110 for cellular automata, as well as of Turing machines. [5] [6]

Although it resembles a pachinko machine in its aesthetic use of gravity-fed metal balls, it is primarily a teaching device in the fundamentals of logic-computer programming, and as such is an example of gamification. The framing device in the included comic book features an astronaut who must solve 60 increasingly difficult logic problems which illustrate the fundamentals of computer programming.

History

The impetus of the puzzles included with the device was the frustration of the programmer and chemistry professor Paul Boswell (along with his wife, Alyssa Boswell, a DIY maker), then at the University of Minnesota, at the lack of computing prowess of other scientists which was necessary for their own projects. Boswell was already well known for programming complex games for Texas Instruments computers. The inventors were also inspired by the Digi-Comp II, a precursor from the late 1960s. [7]

Components

A Turing Tumble machine has the following parts:

Reception

Critically, the device has received high praise for its concept and execution, [8] albeit with some caveats (the recommended age being 8+). [9]

The computing game has won the Parents' Choice Gold Award, [10] and won in the category "Best Toys of the Year 2018" under the aegis of the American Specialty Toy Retailing Association. [11]

Related Research Articles

In computability theory, the Church–Turing thesis is a thesis about the nature of computable functions. It states that a function on the natural numbers can be calculated by an effective method if and only if it is computable by a Turing machine. The thesis is named after American mathematician Alonzo Church and the British mathematician Alan Turing. Before the precise definition of computable function, mathematicians often used the informal term effectively calculable to describe functions that are computable by paper-and-pencil methods. In the 1930s, several independent attempts were made to formalize the notion of computability:

<span class="mw-page-title-main">Finite-state machine</span> Mathematical model of computation

A finite-state machine (FSM) or finite-state automaton, finite automaton, or simply a state machine, is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number of states at any given time. The FSM can change from one state to another in response to some inputs; the change from one state to another is called a transition. An FSM is defined by a list of its states, its initial state, and the inputs that trigger each transition. Finite-state machines are of two types—deterministic finite-state machines and non-deterministic finite-state machines. For any non-deterministic finite-state machine, an equivalent deterministic one can be constructed.

<span class="mw-page-title-main">History of computing hardware</span>

The history of computing hardware covers the developments from early simple devices to aid calculation to modern day computers.

<span class="mw-page-title-main">Turing machine</span> Computation model defining an abstract machine

A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algorithm.

In computability theory, a system of data-manipulation rules is said to be Turing-complete or computationally universal if it can be used to simulate any Turing machine. This means that this system is able to recognize or decide other data-manipulation rule sets. Turing completeness is used as a way to express the power of such a data-manipulation rule set. Virtually all programming languages today are Turing-complete.

<span class="mw-page-title-main">Conway's Game of Life</span> Two-dimensional cellular automaton devised by J. H. Conway in 1970

The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970. It is a zero-player game, meaning that its evolution is determined by its initial state, requiring no further input. One interacts with the Game of Life by creating an initial configuration and observing how it evolves. It is Turing complete and can simulate a universal constructor or any other Turing machine.

<span class="mw-page-title-main">Alonzo Church</span> American mathematician and computer scientist (1903–1995)

Alonzo Church was an American mathematician, computer scientist, logician, and philosopher who made major contributions to mathematical logic and the foundations of theoretical computer science. He is best known for the lambda calculus, the Church–Turing thesis, proving the unsolvability of the Entscheidungsproblem, the Frege–Church ontology, and the Church–Rosser theorem. Alongside his doctoral student Alan Turing, Church is considered one of the founders of computer science.

<span class="mw-page-title-main">Dana Scott</span> American logician (born 1932)

Dana Stewart Scott is an American logician who is the emeritus Hillman University Professor of Computer Science, Philosophy, and Mathematical Logic at Carnegie Mellon University; he is now retired and lives in Berkeley, California. His work on automata theory earned him the Turing Award in 1976, while his collaborative work with Christopher Strachey in the 1970s laid the foundations of modern approaches to the semantics of programming languages. He has also worked on modal logic, topology, and category theory.

Computer science is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. One well known subject classification system for computer science is the ACM Computing Classification System devised by the Association for Computing Machinery.

<span class="mw-page-title-main">History of computing</span>

The history of computing is longer than the history of computing hardware and modern computing technology and includes the history of methods intended for pen and paper or for chalk and slate, with or without the aid of tables.

Reversible computing is any model of computation where the computational process, to some extent, is time-reversible. In a model of computation that uses deterministic transitions from one state of the abstract machine to another, a necessary condition for reversibility is that the relation of the mapping from states to their successors must be one-to-one. Reversible computing is a form of unconventional computing.

<span class="mw-page-title-main">History of computer science</span>

The history of computer science began long before the modern discipline of computer science, usually appearing in forms like mathematics or physics. Developments in previous centuries alluded to the discipline that we now know as computer science. This progression, from mechanical inventions and mathematical theories towards modern computer concepts and machines, led to the development of a major academic field, massive technological advancement across the Western world, and the basis of a massive worldwide trade and culture.

<span class="mw-page-title-main">Digi-Comp I</span>

The Digi-Comp I was a functioning, mechanical digital computer sold in kit form. It was originally manufactured from polystyrene parts by E.S.R., Inc. starting in 1963 and sold as an educational toy for US$4.99.

<span class="mw-page-title-main">Digi-Comp II</span> Marble-based mechanical toy computer

The Digi-Comp II was a toy computer invented by John "Jack" Thomas Godfrey (1924–2009) in 1965 and manufactured by E.S.R., Inc. in the late 1960s, that used 12 inch (12.5 mm) marbles rolling down a ramp to perform basic calculations.

Unconventional computing is computing by any of a wide range of new or unusual methods. It is also known as alternative computing.

A chemical computer, also called a reaction-diffusion computer, Belousov–Zhabotinsky (BZ) computer, or gooware computer, is an unconventional computer based on a semi-solid chemical "soup" where data are represented by varying concentrations of chemicals. The computations are performed by naturally occurring chemical reactions.

<span class="mw-page-title-main">Billiard-ball computer</span> Type of conservative logic circuit

A billiard-ball computer, a type of conservative logic circuit, is an idealized model of a reversible mechanical computer based on Newtonian dynamics, proposed in 1982 by Edward Fredkin and Tommaso Toffoli. Instead of using electronic signals like a conventional computer, it relies on the motion of spherical billiard balls in a friction-free environment made of buffers against which the balls bounce perfectly. It was devised to investigate the relation between computation and reversible processes in physics.

<span class="mw-page-title-main">Computer</span> Automatic general-purpose device for performing arithmetic or logical operations

A computer is a machine that can be programmed to automatically carry out sequences of arithmetic or logical operations (computation). Modern digital electronic computers can perform generic sets of operations known as programs. These programs enable computers to perform a wide range of tasks. The term computer system may refer to a nominally complete computer that includes the hardware, operating system, software, and peripheral equipment needed and used for full operation; or to a group of computers that are linked and function together, such as a computer network or computer cluster.

<span class="mw-page-title-main">Mechanical computer</span> Computer built from mechanical components such as levers and gears

A mechanical computer is a computer built from mechanical components such as levers and gears rather than electronic components. The most common examples are adding machines and mechanical counters, which use the turning of gears to increment output displays. More complex examples could carry out multiplication and division—Friden used a moving head which paused at each column—and even differential analysis. One model, the Ascota 170 accounting machine sold in the 1960s calculated square roots.

Hardware security is a discipline originated from the cryptographic engineering and involves hardware design, access control, secure multi-party computation, secure key storage, ensuring code authenticity, measures to ensure that the supply chain that built the product is secure among other things.

References

  1. Johnson, Matthew (April 2019). "Turing Tumble is P(SPACE)-Complete". Algorithms and Complexity. Lecture Notes in Computer Science. Vol. 11485. pp. 274–285. doi:10.1007/978-3-030-17402-6_23. ISBN   978-3-030-17401-9. S2CID   159042415.
  2. Hoover, H. James (2019-05-26). "Turing Tumble is P-Complete". sites.ualberta.ca. Archived from the original on 2020-07-27.
  3. Tomita, Takahiro (20–22 June 2018). "Constructing Reversible Logic Elements on Turing Tumble Model" (PDF). Proceedings of Automata 2018: 25–32. Archived (PDF) from the original on 2020-05-06. Retrieved 2019-12-10. (NB. A longer version was published in 2019.)
  4. Tomita, Takahiro; Lee, Jia; Isokawa, Teijiro; Peper, Ferdinand; Yumoto, Takayuki; Kamiura, Naotake (2019-09-03). "Universal logic elements constructed on the Turing Tumble". Natural Computing . Springer-Verlag. 19 (9): 787–795. doi:10.1007/s11047-019-09760-8. eISSN   1572-9796. ISSN   1567-7818. S2CID   201714072. Archived from the original on 2020-07-27. Retrieved 2020-07-27. (NB. A short version of this paper was presented at AUTOMATA 2018.)
  5. Pitt, Lenny (2023-02-28). "Turing Tumble is Turing-Complete". Theoretical Computer Science. 948: 113734. arXiv: 2110.09343 . doi:10.1016/j.tcs.2023.113734. S2CID   239016461.
  6. "Proof of Turing Completeness?". Turing Tumble Community Bboard. 2018-07-17.
  7. Frauenfelder, Mark (2017-04-30). "Cool marble-powered mechanical computer to solve logic problems". BoingBoing. Archived from the original on 2020-07-27. Retrieved 2019-12-10.
  8. Hall, Stephen (2018-12-05). "Review: Turing Tumble". Geeks Under Grace. Archived from the original on 2019-12-02. Retrieved 2019-12-10.
  9. "Turing Tumble: A Timberdoodle Review". MamaBeanAz. 2019-09-15. Archived from the original on 2020-07-27. Retrieved 2019-12-10.
  10. "Turing Tumble: Build Marble Powered Computers". Parents Choice Foundation.
  11. "AMERICAN SPECIALTY TOY RETAILING ASSOCIATION ANNOUNCES 2018 BEST TOYS FOR KIDS AWARD WINNERS" (PDF). 2018-07-13.