How many bits representation of data on tape of Turing machine consumes

Question

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?

Answer 1

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.

Answer 2

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.