I am wondering how to represent signed number, vector, matrix on binary tape of Turing machine to consume the smallest possible amount of memory.

For signed number it is obvious: encode sign as a single bit and sum it with the length of number representation $\lceil\log_2(\mathrm{abs}\,(n)+1))\rceil$.

But how is it possible to represent a vector of numbers with different size. How to consume minimal amount of memory?


Note that the usual representation of signed integers in binary is not the one you propose.

In general, though, being super-efficient about coding in Turing machines isn't really important. We mainly use Turing machines for:

  • computability, where we don't care about efficiency at all;
  • complexity, where we only care about efficiency up to constant or even polynomial factors.

We don't use Turing machines for real computation where we care about the "real" efficiency, where making your program twice as fast makes it twice as good.

So, from the point of view of Turing machines, it's completely adequate to code vectors and so on by something like the following. Pick any sensible format for the individual data items and write those out with each bit doubled (i.e., $1011$ becomes $11001111$). Then separate each item with $01$. This means that storing the vector/matrix/whatever takes "twice as many bits as it should" but that constant factor just isn't important for the things we use Turing machines for.


I see 3 ways of doing it:

  1. Storing the length and the items
  2. Storing a bit after each item indicating whether it's the last item (can't store the empty list)
  3. Storing a bit before each potential item indicating whether there are any more items

BTW, I think your number representation has no way to figure out where it ends.

  • $\begingroup$ If you store the length, how do you know when one item ends and the next begins? If you put single bits between the items, how do you know whether those bits are part of an item or not? For example, does $1110$ mean "$1$ and there's another item, which is $1$, and that's the end of the list" or "$111$ and there are no more items"? $\endgroup$ – David Richerby Sep 23 '18 at 15:01
  • $\begingroup$ @DavidRicherby It would depend on the number representation having a definite end point $\endgroup$ – Solomon Ucko Sep 23 '18 at 15:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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