What this language mean? I have to define a Turing machine for it.

Question

I'm tasked with defining a Turing machine for the language below. However I simply do not understand what this language means due to its notation.

A Tm M = $( Q,\Sigma ,\Gamma ,\delta , q_0, q_a, q_r)$ is given. We want to define a Tm (not necessarily standard, could have more than one tape) that decides this language :

{$\Omega$ uqv $\Omega$ u'q'v' : u,v,u',v' $\in$ ($\Gamma$ \ {blank symbol})*, q,q' $\in$ Q and (u,q,v) $\Rightarrow$ (u',q',v') according to M}

on the alphabet $\Sigma ' = Q \cup (\Gamma $ \ {blank symbol}) $\cup$ {$\Omega$}

I have trouble understanding what the language mean in the first place. Would love to have an explanation because without it I can't solve this.

Answer 1

I think a string here like $uqv$ means that the machine $M$ is in state $q$, that $u$ is the part of the tape to the left of its head, and $v$ is the part of the tape to the right of its head. The first symbol in $v$ is the symbol that is being scanned by $M$'s head.

A string like $$\Omega\, uqv\, \Omega\, u'q'v'$$ should be interpreted as a statement about $M$. It means:

If $M$ is in state $q$, and the tape has $uv$ on it, with $M$'s head over the first symbol in $v$,
then $M$ will go into state $q'$, and leave $u'v'$ on the tape, with its head on the first symbol of $v'$.

Your job is to define a machine $M_W$ that accepts the strings that are true statements about what $M$ would do.

The mysterious-looking $\Omega$ symbol is just a delimiter, so that your machine $M_W$, looking at an input string, can know where $v$ ends and $u'$ begins. Without the $\Omega$, inputs to $M_W$ would be ambiguous. $M_W$ would get a string like $1011x000101y0000$, and although it could know that $v\,u' = 000101$ it wouldn't know which part of $000101$ was $v$ and which was $u'$. With the $\Omega$ your machine is given $\Omega1011x000\Omega101y00000$ and can see that $v=000$ and $u'=101$, because there is an $\Omega$ symbol separating them.

We don't need delimiters in $uqv$ or $u'q'v'$ because $q$ is the name of a state, and separates the $u$ and $v$ parts, which are strings from $M$'s tape alphabet $\Gamma$. There is no ambiguity.

$M_W$ will depend on $M$, so it's not really a single machine; it's a family of machines, one for each possible machine $M$ that you might be given. You are being asked not to build a particular machine, but to describe a method which you could use to build $M_W$ once you are told what $M$ is.

The input to $M_W$ is not a sequence of configurations as you suggested in the comments. The input is only two configurations: one for before ($uqv$), and one for after ($u'q'v'$). Your machine $M_W$ will decide if $M$, presented with the “before” configuration, would turn it into the “after” configuration.

Your machine $M_W$ will get a string. Then:

1. $M_W$ should check first that the string is in the correct form $\Omega\, uqv\, \Omega\, u'q'v'$. If not, it should reject. (It is acceptable for $M_W$ to reject by failing to halt.)
2. It should set up $uv$ on a the tape somewhere, perhaps on an auxiliary tape.
3. It should simulate what $M$ would do, if it were in state $q$, looking at the $uv$ on its tape, with its head at the first symbol of $v$.
4. It should check that $M$ would go into state $q'$. If $M$ would go into some other state, $M_W$ should reject.
5. It should check that $M$ would leave $u'v'$ on the tape. If $M$ would leave something else on the tape, $M_W$ should reject.
6. It should check that $M$'s head would be over the first symbol of $v'$ on the tape. If $M$'s head is somewhere else, $M_W$ should reject.
7. If $u'q'v'$ correctly describes the configuration of $M$ after it has dealt with $uqv$, then $M_W$ should accept.

In step 3, the “simulate” step, probably the easiest thing to do is to have $M_W$ actually change the $uv$ on the tape to whatever $M$ would have changed it to. Then $M_W$ can check that the $u'$ and $v'$ from its input matches what is actually on the tape.

Important: The thing that is missing in all of this is: where is $M$'s input used? I said that $\Omega\, uqv\, \Omega\, u'q'v'$ should be understood to mean that $M$ turns $uqv$ into $u'q'v'$. But $M$ won't do anything if $M$ isn't given any input from $\Sigma^\ast$. To know what $M$ will do, $M_W$ needs to know what the input to $M$ is. $M_W$ definitely doesn't get $M$'s input as part of its own input string, because $\Sigma \not\subset\Sigma'$.

Is $M$'s input given to $M_W$ on one of $M_W$'s tapes? Or perhaps $M_W$ is supposed to tell us whether there is any input that would cause $M$ to turn $uqv$ into $u'q'v'$? The problem must say, but you didn't tell us.

If this isn't clear, please leave a comment.