[Solved]: alphabet of a single tape turing machine that simulates a multitape TM

Problem Detail: 

First of all sorry, if this question already exists, in that case, pointing to the right direction will be appreciated.

Secondly, sorry, if the question is below the expected level of Niveau, but all help appreciated.

In the textbook by J. Hromkovic, named "Theoretical Computer Science, Introduction to Automata, Computability, Complexity, Algorithmics", in Page 110, in the 2003 edition, i note that the alphabet of a single tape TM which simulates a multitape TM is given by

$$ \Gamma_{single\ tape} = (\Sigma_{multi\ tape} \cup \{¢,␣ , $ \})\times \{\uparrow , ␣ \} \times (\Gamma_{multi\ tape}\cup\{ ␣,\uparrow\})^{k} \cup \Sigma_{multi\ tape} \cup \{¢\} $$

should that not be, instead:

$$ (\Gamma_{multi\ tape} \cup \{¢,␣ , $ \})\times \{\uparrow , ␣ \} \times (\Gamma_{multi\ tape}\cup\{ ␣,\uparrow\})^{k} \cup \{¢\} ? $$

according to the book, the single tape TM splits its tape in "tracks" , see image i scanned from the book: http://imgur.com/CwnyS

because, the last $¢$ is the primary left end marker, the first two terms of the Cartesian product series is responsible for the top two track, the rest $k$ tracks are constructed by the term which has k in exponent.

all help is appreciated. sorry for the dummy question. i am a meteorologist, who takes his past time in computer programming.

ps, i can neither embed (is that the correct term?) the ¢ character by \cent nor the ␣ by \textvisiblespace in a post like this. does stackexchange use a different command for those? thank you

Asked By : Sean

Answered By : Vor

(I successfully downloaded the image).

It is not clear in the picture what is the difference between $\Sigma$ and $\Sigma_A$, however looking at the definition of Exercise 4.12 I think that the author simply distinguishes the input alphabet $\Sigma_A$ from the working alphabet $\Gamma_A$ (tape alphabet); so in order to simulate:

the input tape of A (with symbols from $\Sigma_A$) plus the $k$ tapes of A (with symbols from $\Gamma_A$)

it uses $\Sigma_A$ in the first term of the Cartesian product.

Be careful that you didn't copy exactly the $\Gamma_B$ of the book (you wrongly put a $\cup$ where the book puts a $\times$):

$\Gamma_{B} = (\Sigma_{A} \cup \{¢,␣ , \$ \})\times \{\uparrow, ␣ \} \times (\Gamma_{A}\times \{\uparrow, ␣\})^{k} \cup \Sigma_{A} \cup \{¢\}$

The final $\Sigma_A$ is probably used to represent the initial input of the multitape machine A "as-is" (and satisfies the requirement that the input alphabet must be a subset of the working alphabet); but I think it is a little bit confusing (and perhaps the $ symbol should also be included with the final ¢)

The first steps of the simulation of B should be: copy the input to the "hypotethetical" track 0 of B, initializing the head pointers of the "hypothetical" tracks 1,..,k of B.

Best Answer from StackOverflow

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