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$) EDIT2phi 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
