# Turing Machine Enumeration: NKS versus Lexicographical

Requires a Wolfram Notebook System

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

Requires a Wolfram Notebook System

Edit on desktop, mobile and cloud with any Wolfram Language product.

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]
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## Permanent Citation

"Turing Machine Enumeration: NKS versus Lexicographical"

http://demonstrations.wolfram.com/TuringMachineEnumerationNKSVersusLexicographical/

Wolfram Demonstrations Project

Published: March 7 2011