= Turing machine regex tape notation
{c}
<Turing machine regex tape notation> is <Ciro Santilli>'s made up name for the notation used e.g. at:
* https://www.sligocki.com/2023/02/02/skelet-34.html
* https://www.sligocki.com/2022/06/10/ctl.html
Most of it is just regular <regular expression> notation, with a few differences:
* $0^{\inf}$ 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 `01`s 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>.
Back to article page