4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I'm not sure why you think that the a UTM has symbols that always result in the head moving left. This is not how a UTM works. A UTM accepts as input two arguments, a description of a Turing machine and an input to the Turing machine, and simulates the former on the latter. In particular, it has to go back and forth between the part describing the Turing machine and the rest of the tape. So it won't have a symbol that causes it to always move left (or right). $\endgroup$ – Yuval Filmus Jun 16 at 7:54
  • $\begingroup$ Can you add an easily accessible url to "the (2,18) UTM"? $\endgroup$ – Apass.Jack Jun 17 at 3:50
  • $\begingroup$ @YuvalFilmus In the (2, 18) UTM by Rogozhin the symbol $\overrightarrow{1}$ causes the head to move to the right in both states. In fact, about half of the symbols either always produce a left motion or always produce a right motion. $\endgroup$ – Stella Biderman Jun 17 at 14:38
  • $\begingroup$ Perhaps you could describe this machine? I’m not aware of it. $\endgroup$ – Yuval Filmus Jun 17 at 14:39
  • 1
    $\begingroup$ The paper specifies it, when it explains how to encode the input. I believe just 1 and $c$. $\endgroup$ – Yuval Filmus Jun 18 at 4:01
3
+100
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "the ordinary programs/softwares/executables, which are, in fact, roughly the input to the CPU" should be "the ordinary programs/softwares/executables, which are, in fact, a kind of the input to the CPU" $\endgroup$ – Apass.Jack Jun 22 at 15:56
  • $\begingroup$ I don't understand this answer. The question is about universal Turing machines, which do have a description of a TM plus an input to that machine as input. $\endgroup$ – reinierpost Jun 22 at 16:58
  • $\begingroup$ @reinierpost Thanks for the feedback. It looks like the confusion arises also because of the particular kind of universal Turing machines (UTM) in that article. There are different definitions of UTM. For example, this smallest UTM does not fit your description of UTM well in the sense that there is no obvious separation of the input TM and its input. I will try addressing this sort of confusion in the answer. $\endgroup$ – Apass.Jack Jun 22 at 17:31
  • $\begingroup$ This answer makes me feel like I am not getting my question across at all. If you have a fixed UTM, $\Phi$, and want to use it to compute the function $f(a)$ you need to provide it two things for the input. You need to provide $f$ and you need to provide $a$. My understanding is that $\Phi$ can uniformly compute $f$, meaning that there is a partial assignment to the input of $\Phi$ such that $\Phi$ will compute the function $f$ and the unfilled portion of the input can be used to specify $a$. My question is about how independent the coding of $f$ and $a$ can be for a uniform $\Phi_f$. $\endgroup$ – Stella Biderman Jun 23 at 8:48
  • 1
    $\begingroup$ @StellaBiderman I just rewrote my answer completely. $\endgroup$ – Apass.Jack Jun 24 at 3:41

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.