I'm writing about Turing machines and often need to denote the tape. I'm using exponential tapes, i.e. a repetition count for each symbol.

I usually use something similar to $(x_k^{e_k})_{1 \leq k \leq m} \text{ Q } (x_k^{e_k})_{m+1 \leq k \leq n}$ (latex: $(x_k^{e_k})_{1 \leq k \leq m} \text{ Q } (x_k^{e_k})_{m+1 \leq k \leq n}$) with $x_k$ the symbols and $e_k$ their exponents. The head in state $Q$ is at position $m$.

What (very slightly) annoys me about this is the need to include $Q$. Without it, it would just be $(x_k^{e_k})_{1 \leq k \leq n}$ (latex: $(x_k^{e_k})_{1 \leq k \leq n}$) , which is must easier to read.

The transitions may change various symbols and exponents at the same time, while $Q$ almost always stays in the same spot.

How should I note this down? Is there an easy to understand (and parse) notation which is shorter but still carries the same information? I could not find a solution in the papers I read. Or maybe I should just carry on, because this isn't an issue at all?


1 Answer 1


This is just a convention. You can write a configuration as the tuple that has the same information. Eg, a possible way to write a configuration is as the tuple $$Config= (tape,state,pos)$$

where $tape$ is the non empty tape content, $state$ is the current state, and $pos$ is the position of the head.

This is fully equivalent to the method you use, which makes sense for other succinct description of configurations. Tho only thing to bear in mind, is that people are used to the 1-string-head-inside convention you describe in the question, so if you change it, you need to be very clear and explicit about it.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.