Im having some difficulty understanding how the following two concepts could be related.
Equivalence between TMs as is commonly tought
According to this site answer, to prove a standard TM model to be equivalent to some non standard TM model (some variant) we need to do two things:
- For any std TM $T$, find a non-std TM $T'$ such that $L(T)=L(T')$
- For any non-std TM $T$, find a std TM $T'$ such that $L(T)=L(T')$
The following is how i understand this endeavour.
I guess, as is somewhat standard notation, $L(T)$ means the accepted (also termed recognized or semi-decided) language of a TM $T$, that is, the strings for which $T$ halts in a final state.
Then, this is the same as proving that for any language $L \subseteq \Sigma^*$, there exists a std MT $T$ such that $L(T)=L$ if and only if exists a non-std TM $T'$ such that $L(T')=L$. The proof is tipically done in two parts.
For example, for the only if direction, suppose we have some std MT $T$ such that $L(T)=L$. Then we show how to construct a non-std TM $T'$ that simulates $T$, and we also show that $L(T)=L(T')$ proving: $$ \forall w \in \Sigma^* : w \in L(T) \iff w \in L(T')$$
The other direction can be done in analogous way.
A definition of simulation
I had never seen before an specific definition of simulation in introductory texts (i guess they try not to be unnecessary formal). But consider the following definition taken from this online notes (4.6. Multi tape Turing machines, simulation):
In those notes, the author proves that multi tape TMs are equivalent to standard TMs. In order to do so, it looks like he is not just saying both must accepts the same inputs, but also the output in tape must be equal.
Here it comes the first question. What $ln(T_1) \subseteq ln(T_2)$ could possibly mean?. I ask this because there is no mention of it in these notes. Some things come to my mind:
- There are two typos and he mean $L(T_1) \subseteq L(T_2)$ instead. But does it make sense?.
- Is $ln(T_1)$ the logarithm of a TM? what ... ??
Also, the autor correctly uses $L(T_1)$ in other places, so it looks like $ln(.)$ have some meaning.
Even if i cant tell what exactly is $ln(T_1)$, i see this definition is trying to match the machines outputs ($T_1(w)=T_2(w)$). If we think of Turing Machines (and other Turing-complete models) as general computing devices, not just language recognizers or deciders, it seems to me that this should be the correct (or at least more general) way to prove two Turing Machine are equivalent in power. IIRC TMs as computing devices can also be used as language recognizers, but the reciprocal is not true. So what we really want is to prove that the two models compute exactly the same set of functions, and this requires to compare input and output.
Following my previous reasoning, my second question: Is the equivalence between TMs as defined earlier just proving two TM models are equivalent as acceptors but not as general computing machines?
And if the answer is negative, why would be sufficient to prove the equivalence in that apparently weaker way?
EDIT: comparing popular literature and possible answer for Q2
I found in Elements of the theory of computation (2nd edition, 1997) - Papadimitriou & Lewis a theorem of the same result mentioned earlier:
Theorem 4.3.1 (Any k-tape Turing machine can be simulated by a single-tape machine)
Let $M=(K,\Sigma,\delta,s,H)$ be a k-tape Turing machine for some $k \geq 1$. Then there is a standard Turing machine $M'=(K',\Sigma',\delta',s',H)$, where $\Sigma \subseteq \Sigma'$, and such that the following holds: For any input string $x \in \Sigma^*$, $M$ on input $x$ halts with output $y$ on the first tape if and only if $M'$ on input $x$ halts at the same halting state, and with the same output $y$ on its tape.
I think this is some evidence in favor of my initial thoughts. For a TM model defined to be used as a computing device (and also can be used as acceptor machine), the theorem assert that for every halting input (on the same final state) the output in tape is the same, that is $M(x)=M'(x)=y$.
We can compare this with Introduction to the theory of computation (3rd edition, 2012) - Sipser same but simpler statement:
Every multitape Turing machine has an equivalent single-tape Turing machine.
but here "equivalent" for Sipser just means the same notion used to compare other simpler automatas, i.e. they must accept the same language. This make sense because Sipser defines TMs especially as acceptor/decider machines with two special halting states.
I conclude the answer for my second question is that equivalence depends on how TMs are conceived (accept/reject vs computing). This explains the different treatment it receives among the authors, and hence my apparent confusion. The linked question to this site is asking about TMs accepting strings, so the answer makes sense to me.
EDIT: some remarks on the definitions and possible answer for Q1
According to those notes:
- $T_1(w)$ means the output of $T_1$ on $w$.
- $T_1(w)=T_2(w)$ means $T_1$ and $T_2$ have same output on $w$ if both terminate on $w$, otherwise neither terminate.
I think @GBat is right, the notation is for "input": $\mathit{In}(T)$. It makes sense because the author want to compare TMs as functions, so presumably he is saying that:
$T_2$ simulate $T_1$ if the domain of $T_2$ includes the domain of $T_1$ (that is $\mathit{In}(T_1) \subseteq \mathit{In}(T_2)$) and for every valid input for $T_1$: $T_1(w)=T_2(w)$.
The author also notes that $T_2$ could have a wider input domain than $T_1$ and consequently compute more than $T_1$, but the what really matters is that $T_2$ can also deal with $T_1$ input.
I guess this is answers my first question. But it would be nice to see an alternative definition/notion for a "simulate" relation to compare. My doubts are on the requirement $\mathit{In}(T_1) \subseteq \mathit{In}(T_2)$, is really necessary?, but at the same time i don't think is wrong.
