If regex describes FSAs, what string formats describe Turing machines?

Question

(Topic summary under the line.)

Regex, at least the formal definition featuring only | and *, is used to describe words accepted by a given FSA, but it can be transformed into the corresponding state diagram (by constructing a NFSA with epsilon transitions from "modules" that correspond to the concatenations, alternations and Kleene stars in the regex, and then deriving the DFSA from that). Thus, it is as if regex captures the "essence" of state diagrams, which are just oriented graphs; a way to encode the entire graph in a single string.

A DFSA needs to have as many outgoing transitions per each state as there are symbols in the chosen alphabet. Let's assume two for our alphabet L: 0 and 1. These symbols can be understood as if-else statements, the machine takes one path if it sees a 0, and a different path for 1. We can provide substitutions of the form 0->0A, where A is some set of tape instructions. Choosing the right syntax semantics for the context-free aspects of these strings then allows us to omit the 0's and 1's entirely. For example, replace ()* with [], so that [A]B reads "while 1, A, else end while, B". Similarly, since |L|=2, we can ultimately reduce every alternation to the form (A|B) (so for example no expressions of the "(A|B|C)" kind), and thus we can rephrase this as "if 1, A, else B, end if". Finally, for pesky cases where the while condition is inverted, we can define "![]" for now, which reads "while 0...".

Example Busy Beaver-esque automaton (state 1 = initial, state 0 = halting):

State 1: if ( read 1 ) { A; state = 2; } else { B; state = 0; }
State 2: if ( read 1 ) { C; state = 2; } else { D; state = 1; }

Where A, B, C, and D are instructions for the tape-manipulating machinery.
Compact code for this state-transition table: 2021
String representation of the instructions themselves: [A[C]D]B

Informal proof of the correctness of the above string: If the first read symbol is 0, the first [] won't execute and B will execute instead; the halting state will follow. Otherwise if 1, do A and transition to state 2 (not deducible from the string). Then, if read 1, do C and don't change states, aka "[C]". Finally, otherwise if 0, do D and go to state 1, which was the same as the initial one, ergo return to the beginning of the string (the first "[").

The very much esoteric language Brainfuck is notorious for its simplicity, and the only control flow it provides is a "while (true)"-style loop "[]". However, it is my suspicion that not every state diagram can be constructed in Brainfuck, or this experimental language of mine. For a machine with the code "2001", I couldn't find a string that wouldn't utilize gotos/breaks. (My attempt: [A(C*,D)]B, where * means to break from []; "(,)" as usual means if-else). It seems that while every state diagram can be converted into regex, once we give each edge a unique label and aim to preserve them and their paths, the task becomes impossible in some instances, namely when there is a loop with two or more exits.

---

My question: if FSAs have regex, what do Turing machines have? Is there some succinct way to represent their state diagrams using a single string? Brainfuck seems like a good candidate at first, but it probably cannot describe every possible state diagram; at least that is my guess. No one programs by drawing state diagrams, programs are written (stored) as inline strings of symbols, hence my interest.

Additional question: how come Brainfuck is Turing-complete without selections (if-else statements), how come iterations (while loops) can substitute for selections, and is there a human-friendly algorithm for this? (I am aware of the structured program theorem, but that one includes selections. I am seeking proof of the substitution claim.) Moreover, it seems like some state diagrams cannot be described solely using context-free structures and require gotos/breaks. Is there proof for this, and what does this tell us about Turing completeness or programming language design? (For one, I know it breaks the context-free syntax, but I wish to learn more.)

Answer 1

Any language that is accepted by a FSA can be accepted by a regular expression, and vice versa.

Any language that is accepted by a Turing machine can be accepted by an unrestricted grammar, and vice versa.

See the Chomsky hierarchy.

If you literally mean that you just want a string that describes a Turing machine, it is easy to obtain one: convert the specification of the Turing machine to text. This is basically the same idea as representing a program by its source code; the source code can be viewed as a single long string.

Since you asked about Brainfuck: Brainfuck is Turing complete. This means that any language that is accepted by a Turing machine can be accepted by a Brainfuck program, and vice versa. Pretty much nothing about Brainfuck is human-friendly, so while this statement can be proven, I don't expect a short human-friendly proof of it.

You might also be interested in https://en.wikipedia.org/wiki/Turing_completeness, What does being Turing complete mean?, Are there minimum criteria for a programming language being Turing complete?, Does a do-while loop suffice for Turing-completeness?.

Answer 2

There is indeed an extension of regular expressions that accepts the language of two-stack push-down automata, which has the same expressive power as Turing machines.

First off, to make the algebra more obvious, I'm going to define the operators using Kleene algebra notation.

$0$ is the empty set and $1$ is the zero-length string. Juxtaposition, or $\cdot$, means string concatenation, and $+$ means set union. The algebra satisfies the usual non-commutative semiring axioms:

$$A + B = B + A$$ $$A + (B + C) = (A + B) + C$$ $$A + 0 = 0 + A = A$$ $$A \cdot (B \cdot C) = (A \cdot B) \cdot C$$ $$A \cdot 1 = 1 \cdot A = A$$ $$A\cdot(B + C) = A \cdot B + A \cdot C$$ $$(A + B) \cdot C = A \cdot C + B \cdot C$$ $$0 \cdot A = A \cdot 0 = 0$$

Plus the axiom that addition (i.e. set union) is idempotent:

$$A + A = A$$

Plus, of course, the Kleene closure operator $A^*$, which I won't axiomatise here, but you know what it means.

Now let's think about single-stack PDAs. Probably the most straightforward way to express this is using Dirac notation. Intuitively, the "bra" $\left< \psi \right|$ pushes the stack symbol $\psi$ onto the stack, and the "ket" $\left| \psi \right>$ pops the stack symbol $\psi$.

It satisfies a few axioms. First off, brackets commute with terminal symbols:

$$a \left< \psi \right| = \left< \psi \right| a$$

$$a \left| \psi \right> = \left| \psi \right> a$$

When a bra meets a ket, they form a kind of orthonormal inner product:

$$\left< \psi \right| \left| \psi \right> = 1$$ $$\left< \psi \right| \left| \phi \right> = 0$$

Intuitively, pushing a stack symbol followed by popping the same symbol is equivalent to doing nothing, whereas pushing a stack symbol followed by popping a different symbol is not allowed, and so the language accepted by that sequence of operations is the null set.

Once you have those operators, you can do things like give a "PDA expression" which accepts the language $a^n b^n$:

$$ \left< 0 \right| \left( a \left< 1 \right| \right)^* \left( b \left| 1 \right>\right)^* \left| 0 \right>$$

To implement two-stack PDAs, and hence Turing machines, you simply need two kinds of push and pop, say $\left< \phi \right|_1$ and $\left< \phi \right|_2$. Coming up with interesting "Turing expressions" is left as an exercise.

And just to go down the rabbit hole, the Dirac notation is suggestive of how you could generalise this even further. "Classical" stacks give you an orthonormal inner product whose only values are $0$ and $1$. If you allowed other values of the inner product, this would give you a regular expression-like notation which can represent quantum Turing machines.