# Using a step-counting function in a Turing Machine construction

I have an question relating to the elementary foundations of Turing Machine theory. I would like to have a clarification of the status of a function $\phi$ (a mapping between TM indexes) I shall introduce in the formal question after the preamble. First to the preamble.

Let us assume that we have a fixed Turing Machine language and corresponding Universal Turing Machine. Thus ${TM_i}$ is an enumeration of machines, with UTM say as the Universal Machine in that enumeration. Let us also introduce a numerical parameter c for this example: (for example c = 500).

Now execution of any TM can be simulated on UTM.

EDIT (Explaining notation) I am using some notation in this question which I shall outline here. Let S be an arbitrary input string for TM, then I shall write:

$$UTM(TM_i; S)$$

to indicate that $TM_i$ is using S as its input. So we will have the equation: $$UTM(TM_i; S) = TM_i(S)$$ since UTM is Universal, and its purpose is simply to simulate TMs on their input. If S is a composition of x,y I shall write: $$UTM(TM_i;x,y)$$

(End notation discussion.)

Let us modify UTM to UTM2 (and using the above notation) with the following property when a given $TM_i$ is executed on UTM2:

$UTM_2(TM_i;c,x) = UTM(TM_i;c,x) = TM_i(x)$ if $TM_i$ requires c steps or less to compute the output

$UTM_2(TM_i;c,x)=0$ if $TM_i(x)$ requires at least c steps for computation

EDIT The original question with this second condition has been answered. In this edit I would like to modify the condition to the following (introducing UTM3 which also meets the first condition):

$UTM_3 (TM_i; c, x) = [s]$ if $TM_i (x)$ requires at least c steps for computation.

In this expression [s] is the string on the tape which results after c steps of computation by $TM_i$ on Input. (EDIT The corresponding state of $TM_i$ will not be a Final state (ACCEPT or REJECT), but just an arbitrary state $q_j$. This is because UTM3 stops executing after c steps, ignoring the Turing Machine convention requiring termination only in Final states.) As a result (almost) all input strings x, including those with |x| > c will be modified (in a maximum of c string positions) - expressed in Language terms many such strings will just have their ACCEPTANCE calculation prematurely terminated in a non-Final state - but some strings of arbitrary length will still be ACCEPTED by some Turing Machines in less than c steps (IE those for which ACCEPTANCE requires examining less than the first c terms.)

So under UTM2/3 the output is determined partly by a (hidden) step counting function. Here UTM2/3 has taken on some of the role of an operating system, by monitoring the actual steps taken by the simulated machines, and using some step-counting variable to behave as above.

(EDIT: We show below that UTM2/3 is a Universal Machine)and so capable of executing any TM - on any argument - it is provided with, at least as far as c steps. Despite this limitation I believe that an infinite number of (TM,input) pairs will result in a non-zero output. So most TMs executed on UTM2/3 will not behave as they do on UTM. In UTM3 the outputs will explicitly depend on x,i and c.(End preamble.)

The question is whether any given $TM_i$ can be modified into $TM_{\phi (i,c)}$ with the property that (generalising to arbitrary c):

$UTM_3(TM_i; c, x)$ = $UTM (TM_{\phi(i,c)}; x)$ (for all $x$ and $c$)

EDIT2\phi Both questions for the $\phi(i,c)$ have been answered. For reasons discussed below I want to modify the definition to $\phi(i)$. This new definition is:

$UTM_3(TM_i; c, x)$ = $UTM (TM_{\phi(i)}; c,x)$ = $TM_{\phi(i)}(c,x)$ (for all $x$ and $c$)

This condition is meant to ensure that $TM_{\phi (i)}$ is a correct simulation of $TM_i$. The specific questions to be proven about $\phi: (i) \rightarrow i$ are: (i) Is $\phi$ well defined and non-trivial; (ii) Is $\phi$ recursive; (iii) Is $\phi$ non-recursive?

In the LHS of the above definitions c is an input, which is ignored by $TM_i$ but used by UTM3 to determine the stopping stage. Asking for $\phi(x,c)$ made this a fixed parameter built into the definition of $TM_{\phi(x,c)}$. However the correct UTM simulation will be given c as in the modified equation RHS. This parameter needs to be used by $TM_{\phi(i)}$ along with its own input x, to construct the correct simulation. (EDIT) Of course since the UTM is a regular Universal Machine it simply simulates the execution of $TM_{\phi(i)}$ - the parameters on its tape - like c - are meant for its TM's only.

Note that a special symbol u could be introduced switching off the UTM3 counts, and so

$$UTM3(TM_i;u,x) = UTM(TM_i;u,x) = TM_i(x)$$

Also the same problem can be formulated for the original UTM2 (with modified $\phi$).

This question is a simplification of a problem I am trying to understand (I am a math but not a CS major, but have some textbooks like Hopcroft/Ullmann), and I hope that I can get some clarification on this piece.

• Why do you write "UTM3 ($TM_i$) c Input" and at the end "UTM3 ($TM_i$, c, Input)"? Do you mean $UTM_3(TM_i,c,x)$ in both cases? (use $x$ instead of "input"). Please use uniform notation in order to make the question more readable. Furthermore remember that in the standard notion/definition the "output" of a TM (or UTM) is ACCEPT or REJECT (or never halt).
– Vor
Sep 10 '12 at 14:41
• I have tried to improve the equation formatting. If your last sentence refers (in part) to the odd end state of UTM3, namely at string [s], then this will not be either ACCEPT nor REJECT in general. UTM3 will just stop at an arbitrary state $q_j$. I have added some text into the main body on this unusual aspect of UTM3. Sep 10 '12 at 21:59
• in the last edit, it is not clear what is the difference between UTM3 and UTM: now both have 3 parameters: $TM_i, c$ and $x$. What is the meaning of $c$ for UTM ?
– Vor
Sep 12 '12 at 9:25
• I have added a sentence, just to clarify that parameter c on the UTM tape is just another part of the input for $TM_{\phi(i)}$: it wont modify UTM in any way. Sep 12 '12 at 9:39
• ok. to build $TM_{\phi(i)}$ just add a counter (initially set to $c$) and for every $TM_i$ transition $(q,a)\rightarrow (q',a',D)$ add an "interleaved subroutine" that checks and decrement the $c$ counter. If $c$ = 0 halts, otherwise return to state $q'$.
– Vor
Sep 12 '12 at 12:52

The answer is yes.

A possible quick approach: UTM2($TM_i$,c,x) $\neq 0$ only on $|x| \leq c$ so you can build $TM_{\phi(i,c)}$ simply simulating $TM_i$ on all inputs and hard encoding its output on the finite input strings $|x| < c$, the index of the resulting TM is the value of $\phi(i,c)$

EDIT2: another approach that can work to simulate tape content (UTM3 in your last edit) is the following:

• from $TM_i$ build $TM_{\phi(i,c)}$ using $|Q|*c$ states, where Q is the set of states of $TM_i$.
• every $(q_j,a) \rightarrow (q_k,b,L)$ transition of $TM_i$ is mapped to $c$ transitions on $TM_{\phi(i,c)}$ in this way: $(q_j^m,a) \rightarrow (q_k^{m+1},b,L)$ with $(1 \leq m \leq c-1)$
• make state $q_j^m$ accepting if the corresponding $q_j$ in $TM_i$ is accepting

This guarantees that $TM_{\phi(i,c)}$ runs exactly for $c$ steps and the tape content is the same of $TM_i$

• Thanks this is clear. Unfortunately it means that I have over-simplified my original problem too far. I really want the tape at step c to be the last printed value at this stage. This will mean that for |x| > c there are non-null values on the tape, for all x. Should I modify this Question or ask another? Sep 10 '12 at 12:48
• I have now EDITED the Question introducing UTM3 to clarify the generalisation I wanted. $\phi$ is now for UTM3. In UTM3 I am not sure how "tape content simulation" would work since the set of x to check is now unbounded, unlike in the UTM2 case where x was bounded by |x|<c. Perhaps I am missing something simple again... Sep 10 '12 at 14:21
• @RoySimpson: see my new edit :)
– Vor
Sep 10 '12 at 15:17
• I am still working through bullet two of your answer. Let us assume that the initial state of $TM_i$ is $q_0$ with initial transition $(q_0,a)\rightarrow (q_2,b,L)$. There will be c corresponding transitions in $TM_\phi$: $(q_0^1,a)\rightarrow (q_2^2,b,L)$, $(q_0^2,a)\rightarrow (q_2^3,b,L)$... etc. But surely only $q_0^1$ is the initial state of $TM_\phi$ with these other transitions never used? Consequently only $q_2^2$ ever gets entered in $TM_\phi$, etc. So at the moment I dont see how these new transitions and corresponding states actually get used. Sep 10 '12 at 22:52
• @RoySimpson: many of them will not be used; e.g. every state $q_k^m$ not connected to $q_0^1$ (the only initial state) or at distance $d \geq m$ from it, will never be entered, but this doesn't matter (you can also have unused transitions in $TM_i$ itself).
– Vor
Sep 11 '12 at 6:39