[Solved]: Using a step-counting function in a Turing Machine construction

Problem Detail: 

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.

Asked By : Roy Simpson

Answered By : Vor

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$

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/3487