Turing Machines with Memory

Initializing live version
Download to Desktop

Requires a Wolfram Notebook System

Interact on desktop, mobile and cloud with the free Wolfram Player or other Wolfram Language products.

A Turing machine (TM) uses an infinite tape with cells on it. At every update, a head, represented by a triangle, reads the color of the cell it is over, writes a color onto the same cell, and then moves either left or right.


A memory Turing machine looks back steps to see what color the current cell was back then. Everything else stays the same compared to regular TMs. Turing machines with memory allow for more complex behavior than a regular TM.

Simply click on a cell under "initial conditions" to edit it, and then observe the Turing machine's reaction.


Contributed by: Vladimir Feinberg (August 2012)
Open content licensed under CC BY-NC-SA




[1] S. Wolfram, A New Kind of Science, Champaign, IL: Wolfram Media, 2002 p. 78.

Feedback (field required)
Email (field required) Name
Occupation Organization
Note: Your message & contact information may be shared with the author of any specific Demonstration for which you give feedback.