How does a Turing machine with one tape read its input?

Question

It's often implicitly assumed that we don't have to pay much attention to the difference between the program (which specifies the function being computed) and the input (the value on which that function is evaluated) when reasoning about Turing machines. In particular, people are often happy to assume that the program and inputs are encoded on the same two-sided tape. How this actually works out okay isn't obvious to me though.

Let's say I have a UTM, $\Phi_f$, which has a partially filled two-sided tape specifying a program for calculating the function $f$. Since the program is a finite set of symbols, it begins on cell $b$ and ends on cell $e$ where $b < e$. Now I want to encode the input on the same tape, so I begin at cell $b-1$ and work in the negative direction to encode my specific input, taking up as much space as I need.

My understanding is that as long as the encoding methodology I use to specify the inputs is computable and fixed in advanced, I can use any input encoding I want. The fact that it needs to be fixed in advanced is clear, since the actual program for calculating $f$ for two different encodings is very likely different. Intuitively, it makes sense that I can use any encoding I want because if we fix some standard "base" encoding then computing $f$ on an input encoded by the function $g$ is the same as computing $f(g^{-1})$ on an input encoded by the base encoding.

I have two questions:

1. Is the above correct? In particular, is it always possible to pick an encoding and a function, and then find a single program that computes $f$ on an arbitrary input using that encoding?
2. On the tape, what does the operation of the TM look like? The symbols used to encode the input have a meaning to the TM as a program (or can), and that seems like it could cause problems. For example, the (2, 18) UTM has symbols that always result in the head moving left and others resulting in the head always moving right. It seems like if you chose those symbols to encode the input you could run into problems where the UTM could never escape the input section of the tape.

EDIT: You can read about the (2, 18) UTM I mention for free here. The table presented on page 237 of the journal / page 23 of the PDF shows the table defining the machine. It's a bit hard to read, but it's two main columns each with three subcolumns. A row of $q_1\;1c_2\;Lq_1$ is read "if you are in state $q_1$ and read the symbol $1$ write the symbol $c_2$, move Left, and transition to state $q_1$. The row with a dash instead of a transition is the halting condition.

Answer 1

The situation here is that we would like to a construct universal Turing machine UTM $U$ with a two-sided tape. Let $T$ be a given arbitrary Turing machine (of certain kind) that computes a partial function $f$. ($T$ is call a "program" in the question.)

The question is how we will run $U$ to simulate $T$. In particular, how will we encode the input to $T$ so that the encoded input will be put on the tape of $U$ and how $U$ will be able to read that input.

Following the receipt given in the question, as a first step, we will fill a part of the tape, called the program section, to encode the transition rules of $T$. It begins on cell $b$ and ends on cell $e$ where $b < e$. Suppose we want to encode $J$, an input to $T$ on the same tape, so we begin at cell $b-1$ and work in the negative direction to encode that input, taking up as much space as we need. The head of $U$ will be put on cell $b-1$.

The first issue we encounter is how $U$ can tell the part of the tape that encodes the transition rules of $T$. We can design $U$ to solve this easily by the following one of the simple techniques.

• Put one or more special symbols around cell $b$ and cell $e$ inside the program section so that $U$ will know when $U$'s head is coming in or out of the program section.
• We can require the program section be encoded in a set of symbols that is disjoint with the set of the symbols that is used to encode the input to $T$.

I hope that above make it clear how $U$ can read the input $J$ to $T$.

Is it always possible to pick an encoding and a function, and then find a single program that computes $f$ on an arbitrary input using that encoding?

I am not sure what you are asking exactly. Given an effective injective encoding (that can be decoded effectively), we can always use that encoding as the encoding of $J$ for some particular UTM, as long as that UTM has enough states and capable transitional rules to differentiate the input and program section.

On the tape, what does the operation of the TM look like?

I assume you meant for the UTM $U$. Its behavior is rather simple conceptually at a high level for all universal machines in the article as shown by the following excerpt.

(i) On the first stage, the UTM searches the code $P$, corresponding to the code $A_r$, and then the UTM deletes the codes $A_r$, and $A_s$, (i.e. it deletes the mark between them). (ii) On the second stage, the UTM writes the code $P_r$ in $Q_R$ of the tape in the reversed order. (iii) On the third stage the UTM restores its own tape for a new cycle of modelling.

More generally, $U$'s head read what is the symbol that should be read by $T$. Make a marker on the tape to indicate that cell of the tap is the current cell the head of $T$ is on. Then $U$'s head goes back to the program section to find the rule the corresponds to that symbol for $T$ and $T$'s state (that can be recovered from $U$' state). The result of the transition rule of $T$ is encoded in the $U$' state. Then $U$'s head locates the cell that contains that current symbol for $T$. Then according to the transition rule of $T$ encoded in $U$'s state, modify the cell and goes to the next cell.

What happens can be somewhat more complex when $U$'s modifies the program section and restore it afterwards from time to time.

The symbols used to encode the input have a meaning to the TM as a program (or can), and that seems like it could cause problems. For example, the (2, 18) UTM has symbols that always result in the head moving left and others resulting in the head always moving right. It seems like if you chose those symbols to encode the input you could run into problems where the UTM could never escape the input section of the tape.

Yes, problems could happen if the transition rules for $U$ is not specified correctly. However, I cannot find any problem like that with the U(2,18) of that article.