1
$\begingroup$

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: https://i.stack.imgur.com/rG9kk.jpg

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

Improve this question
$\endgroup$
2
  • $\begingroup$ On the Imgur site no image is displayed following your link. $\endgroup$
    – Vor
    Dec 26, 2012 at 19:31
  • $\begingroup$ very strange, mind trying this link? i.imgur.com/CwnyS.png $\endgroup$
    – Sean
    Dec 26, 2012 at 19:51

1 Answer 1

Reset to default
1
$\begingroup$

(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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ hi, thank you, do you think the second expression, which i suggested can also be used for an expression for the alphabet? if not wuld you like to correct / point errors $\endgroup$
    – Sean
    Dec 27, 2012 at 21:21
  • $\begingroup$ @Sean: the first part of your expression is OK because by definition $\Sigma_A \subseteq \Gamma_A$; but the second term must be $... \cup (\Gamma_{A}\times \{\uparrow, ␣\})^{k} \cup ...$, furthermore the final $\Gamma_B = ... \cup \Sigma_A \cup ...$ is required if you set $\Sigma_B = \Sigma_A$ (the tape alphabet of a TM must be a superset of the input alphabet). Let me know if you still have some doubts. $\endgroup$
    – Vor
    Dec 27, 2012 at 21:50
  • $\begingroup$ ah, so to make sure of the superset property, we are required to introduce $$\cup \Sigma_A \cup $$, do i get it right? as for $$ \cup ( \Gamma_A \times \{\uparrow, ␣\})^k $$, the cup in stead of the cartesian product is to keep the tracks corresponding to input tape independent to the tracks corresponding to the working tapes, right? thank you very much. p.s. what command are you using for ␣? \textvisiblespace is not working for me. so i just copy the symbol from somewhere :) $\endgroup$
    – Sean
    Dec 27, 2012 at 23:04
  • $\begingroup$ @Sean: for what regards the superset property, ok; but in the comment I wrongly wrote a $\cup$; the correct version is: $... \times (\Gamma_{A}\times \{\uparrow, ␣\})^{k} \cup ...$ (as I correctly wrote in the answer): the cartesian product is needed to simulate all the combinations: (input tape symbol $\times \{\uparrow, ␣\}$) $\times$ (track 1 symbol $\times \{\uparrow, ␣\}$ ) $\times ... \times $ (track k symbol $\times \{\uparrow, ␣\}$); where $\{\uparrow, ␣\}$ are used to store the positions of the heads of the multitape machine. $\endgroup$
    – Vor
    Dec 28, 2012 at 0:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.