answer = option D
How $4mn+m$ is the answer? don't know. A teacher who has been teaching TOC for GATE for many year told that he couldn't find the solution to this question, but that's the answer for it.
Solution:
We are required to simulate this turing machine. This means that we need an alternative turing machine(coz it asks how many $\textbf{symbols}$ do we need) that can function like this turing machine but have symbols which are among one of the options below.
Now to see how option D $4mn+m$ works,
Consider an alternative turing machine $B$ such that it has only 2 internal states and atmost $4mn+m$ symbols, can simulate this turing machine $A$.
The internal states of $B$ are $\alpha$ and $\beta$.
Machine $B$ acts like machine $A$, by carrying the information of internal state of $A$ via symbols present on its own tape under the reading head and in the cell of the tape that the reading head of $A$ will visit next(machine $B$ also has a copy of the input tape which is given to $A$).
Machine $B$ uses a back and forth bouncing process to keep track of which state $A$ is in and also what elementary symbol is needed to be put back on the tape, so that its own output matches the output of machine $A$.
During the bouncing process the symbol printed in the new cell works like a counter that ends on the current state of $A$ also, retaining information as to the symbol that was printed previously in this cell.
The symbol on the tape of machine $B$ should be either $m$ elementary symbols or $4mn$ more symbols.
We need $4mn$ more symbols have a generic form :
$$B_{i,j,x,y}$$
where, $i=\{1, 2, 3, 4, \dots m\}$ corresonds to $m$ symbols
$j=\{1, 2, 3, 4, \dots n\}$ corresonds to $n$ internal states of $A$ machine
$x$ = to represent if our bouncing process the cell is transmitting information or receiving it; i.e. what is the machine doing there Read/Write
$y$ = R or L next move of read pointer of machine $B$ should be towards left or right, this is for that bouncing process
Here, we see that by combination of $i, j, x, y$ we have total number of such symbols present on the tape = $m \times n \times 2 \times 2 = 4mn$
as earlier defined we need to have elementary symbols on the tape too which are to be same as those in machine $A$, they are $m$ in number
so we have a total of $4mn + m$ symbols for machine $B$ which it can put on the tape.
The operation table of machine $B$ is defined as:
if input tape of machine $A$ contains the symbol $A_{13}$ then at the corresponding place in input tape of machine $B$ the symbol present will be $B_{13}$
One instance of bouncing operation in this method to result in the simulation of machine $A$ is given in the first image posted in this answer it is in accordance with the given operation table. Using this information we can do a walkthrough and see that the simulation is possible.
Machine $A$ can be a $UTM$.
