Wolfram Demonstrations Project

In this Demonstration we show how Turing machines (TM) can be emulated by other simple systems, namely, register machines (RM) and tag systems (TS).

There are three views.

1. A compressed register machine that emulates a Turing machine, which is obvious when one looks at the Turing machine in centered format.

2. How a register machine rule can emulate a Turing machine rule with requisite detailed emulation.

3. A tag system rule that emulates a Turing machine rule and the tag system that emulated a Turing machine.

For the details of how these emulations are conducted, see Stephen Wolfram's A New Kind of Science, pp. 670–672, Emulating Cellular Automata with Other Systems.

Contributed by: Abigail Nussey

Based on a program by: Todd Rowland

Embed Interactive Demonstration New!

RELATED RESOURCES

Mathematica » The #1 tool for creating Demonstrations and anything technical.	Wolfram\|Alpha » Explore anything with the first computational knowledge engine.	MathWorld » The web's most extensive mathematics resource.	Course Assistant Apps » An app for every course— right in the palm of your hand.
Wolfram Blog » Read our views on math, science, and technology.	Computable Document Format » The format that makes Demonstrations (and any information) easy to share and interact with.	STEM Initiative » Programs & resources for educators, schools & students.	Computerbasedmath.org » Join the initiative for modernizing math education.

Emulation of Turing Machines by Tag Systems and Register Machines