Wolfram Demonstrations Project

12,000+ Open Interactive Demonstrations
Powered by Notebook Technology »

Turing Machine Enumeration: NKS versus Lexicographical

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.

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).

[more]

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.

[less]

Contributed by: Joost J. Joosten (Universidad de Sevilla, Group for Logic, Language and Information) (March 2011)
Open content licensed under CC BY-NC-SA

Snapshots

Details

detailSectionParagraph
Embed Code

Take advantage of the Wolfram Notebook Emebedder for the recommended user experience.

Related Demonstrations More by Author
Browse all topics
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.
Send