by Ciro Santilli (@cirosantilli, 34)
Turing machine regex tape notation is Ciro Santilli's made up name for the notation used e.g. at:
Most of it is just regular regular expression notation, with a few differences:
  • denotes the right or left edge of the (zero initialized) tape. It is often omitted as we always just assume it is always present on both sides of every regex
  • A, B, C, D and E denotes the current machine state. This is especially common notation in the context of the BB(5) problem
  • < and > next to the state indicate if the head is on top of the left or right element. E.g.:
    11 (01)^n <A 00 (0011)^{n+2}
    indicates that the head A is on top of the last 1 of the last sequence of n 01s to the left of the head.
This notation is very useful, as it helps compress long repeated sequences of Turing machine tape and extract higher level patterns from them, which is how you go about understanding a Turing machin in order to apply Turing machine acceleration.

Ancestors (10)

  1. Turing machine decider
  2. Halting problem
  3. Decision problem
  4. Computational problem
  5. Computer science
  6. Computer
  7. Information technology
  8. Area of technology
  9. Technology
  10. Home

Incoming links (1)

View article source

Discussion (0)

+ New discussion

There are no discussions about this article yet.

Articles by others on the same topic (0)

There are currently no matching articles.
See all articles in the same topic + Create my own version