My question goes like this:

Write an algorithm (in pseudocode) that on input $w$, checks that $w$ encodes a valid Turing machine $\langle M\rangle$. e.g, you need to validate that the structure is correct, that $\delta(q_a,a)$ is undefined for every symbol $a$, etc.

Unfortunately, I got no idea how to tackle it. I have a clue that induction might be needed, but it didn't help me. Any help will be appreciated. Thank you!

  • 1
    $\begingroup$ Whose question is that again? Hint: you are asked to check the syntax. Look at the formal definition of $\langle \_ \rangle$ and write an ad-hoc parser. Or, alternatively, model the syntax using a CFG and use a standard parsing algorithm. $\endgroup$ – Raphael May 17 '16 at 9:56

The encoding $\langle M \rangle$ of a TM, has a specific structure. All you need your algorithm to do, is to verify that the input string $w$ possesses the "correct" structure of a valid encoding.

Note, that there are many possible ways to define the encoding $\langle M \rangle$. For instance one possible such encoding, for $M=(Q,q_0,F,\Gamma,\Sigma, \sqcup, \delta)$ is $$ 1^{|Q|}01^{|\Gamma|}01^{|\Sigma|}0\delta_100\delta_200 \ldots \delta_{last}000$$ where each $\delta_i$ is one line of the transition function, such that if, for instance $\delta(q,a) = \{ p, b, d\}$ we encode it as $1^q01^a01^p01^b01^d$ with $d$ being the direction where the head moves, say Left=1, Right=2, Stay=3.

Remember that other encodings are possible, it depends on your definition!

However, assuming the above definition, I think you should be able to come up with an algorithm to verify if the encoding is valid or not.

For instance, is the input $w=0000000$ valid ?

no, because it contains no states $Q$, etc.

What will you need to check for validity? Basically, only the following

0. that the formatting looks correct (no extra characters, ends with 000, etc,)
1. that all the sets exist (and behave correctly, e.g., $|\Gamma|>|\Sigma|$)
2. that $\delta$ is well defined (think, what does this mean)...


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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