1
$\begingroup$

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.

$\endgroup$
6
  • 1
    $\begingroup$ 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). $\endgroup$
    – Vor
    Sep 10, 2012 at 14:41
  • 1
    $\begingroup$ 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. $\endgroup$ Sep 10, 2012 at 21:59
  • $\begingroup$ 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 ? $\endgroup$
    – Vor
    Sep 12, 2012 at 9:25
  • $\begingroup$ 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. $\endgroup$ Sep 12, 2012 at 9:39
  • $\begingroup$ 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'$. $\endgroup$
    – Vor
    Sep 12, 2012 at 12:52

1 Answer 1

3
$\begingroup$

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$

$\endgroup$
8
  • $\begingroup$ 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? $\endgroup$ Sep 10, 2012 at 12:48
  • $\begingroup$ 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... $\endgroup$ Sep 10, 2012 at 14:21
  • $\begingroup$ @RoySimpson: see my new edit :) $\endgroup$
    – Vor
    Sep 10, 2012 at 15:17
  • $\begingroup$ 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. $\endgroup$ Sep 10, 2012 at 22:52
  • $\begingroup$ @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). $\endgroup$
    – Vor
    Sep 11, 2012 at 6:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.