Universal Turing Machines with Simple Encodings of Their Tape.

55 Views Asked by At

I am seeking a small $2$-symbol Universal Turing machine $U$ such that if $T$ is a Turing machine written to the tape of $U$ somehow, and I wish for $U$ to simulate $T$ with its tape initialized to $n$, then there is some easily computable way of writing $n$ to the tape of $T$. The known smallest $2$-symbol UTMs seem to have obscenely complicated representations of the tape of $T$, making them impractical for my purposes. I'd like a UTM with not too many states, where how to read and write to the tape $T$ is obvious. To ask a precise question: Does there exist an explicit (so the table of states is available somewhere or easily computed) $2$-symbol $1$-tape universal Turing machine $U$ with fewer than say $100$ states, such that to simulate $T$ with tape initialized to $n$, I encode $T$ somehow on the left half of the tape of $U$, and I encode $n$ in unary or binary on the right half? If necessary, feel free to drop the assumption of a single tape, or use some other simple encoding instead of binary or unary.