Turing Machine Enumeration: NKS versus Lexicographical

Turing Machines (TMs) are among the simplest computational models that can perform any computational task that can be mechanized. A TM consists of an infinite tape of cells extending both to the left and right, with a head moving over these cells and performing tasks on them. Each cell has a color. The head can be in various states. Depending on the state of the head and the color of the cell under the head, the head performs its task. The task is writing a color on the cell, moving the tape either left or right, and going to a new state (possibly the same as before).
There are various very simple ways to enumerate all possible Turing machines with a given number of states and colors.
Sometimes people get confused by the NKS enumeration, as they would have done the enumeration in a way that is called lexicographical. The only difference between the NKS and lexicographical enumeration is the order in which they enumerate: where the lexicographical enumeration starts with the lowest state and whitest (lowest) color, the NKS enumeration starts with the highest state and the whitest/lowest color.
This Demonstration makes the small difference between NKS coding and lexicographical coding visible.
The so-called changing transitions in this Demonstration are those transitions that will change by increasing the TM code by one, and can be made to light up in pink.
  • Contributed by: Joost J. Joosten (Universidad de Sevilla, Group for Logic, Language and Information)


  • [Snapshot]
  • [Snapshot]
  • [Snapshot]
    • Share:

Embed Interactive Demonstration New!

Just copy and paste this snippet of JavaScript code into your website or blog to put the live Demonstration on your site. More details »

Files require Wolfram CDF Player or Mathematica.

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.
Step-by-Step Solutions »
Walk through homework problems one step at a time, with hints to help along the way.
Wolfram Problem Generator »
Unlimited random practice problems and answers with built-in step-by-step solutions. Practice online or make a printable study sheet.
Wolfram Language »
Knowledge-based programming for everyone.
Powered by Wolfram Mathematica © 2018 Wolfram Demonstrations Project & Contributors  |  Terms of Use  |  Privacy Policy  |  RSS Give us your feedback
Note: To run this Demonstration you need Mathematica 7+ or the free Mathematica Player 7EX
Download or upgrade to Mathematica Player 7EX
I already have Mathematica Player or Mathematica 7+