[Math] Construct a deterministic Turing machine that decides the language $L=\{w\in\{a, b\}\mid w\text{ contains an occurrence of }ab\}$

formal-languageslogicturing-machines

So we are asked to construct a deterministic Turing machine. I have constructed a Turing machine, but I'm not sure if it's correct.

Here is my Turing machine:

Turing machine

For the question above, I'm just making sure I'm on the right track!

The next question is:
Describe in clear English a Turing machine that semi-decides the language

$$L = \{\langle M\rangle\mid M\text{ accepts the binary encodings of at least 3 prime numbers}\}$$

I'm not sure what it means to "semi-decide" a language… So this question, I'm stuck, any guidance is greatly appreciated.

Here is a an example of a Turing machine created out of our textbook. This is for an input string L = {a^i b^j : 0 ≤ j ≤ i}. The output string will then be L = {a^n b^n : 0 ≤ n}.

enter image description here

EDIT:

Here is my new Turing machine:
Turing Machine

Thanks!

Best Answer

For the first question, your basic idea works, but I think you need to be more careful about how your machine will stop. Note that in the example machine from the book, there are no transitions out of the stopping state 6; entering a stopping state means that the machine stops working.

On the other hand, the example machine does contain transitions for symbols \$, #, and $\Box$ that are not in the alphabet of the input strings. I suspect those symbols are supposed to help the machine find out when it has reached the end of the string; but for details you need to consult the book because different authors use different conventions in this regard. (I'd guess that $\Box$ stands for a blank square of the tape and \$ might signal the end of the input, but I can't offhand guess what the purpose of # would be).

In any case your machine will need to do something in case it reaches the end of the input without having seen ab. Again you will need to consult the book to find out the exact conventions it uses for how a Turing machine should signal that it "rejects" the input.

A Turing machine is said to semi-decide a language $L$ iff

  1. For all strings $w\in L$, the machine will halt on input $w$.
  2. For all strings $w\notin L$, the machine will keep running forever on input $w$.

(There are minor but nonessential differences between authors here. Some allow the machine to halt with either an "accept" or a "reject" output; in that case a semi-deciding Turing machine is allowed to either reject or run forever when its input is not in $L$).

Thus you're asked to sketch a Turing machine $T$ whose input is a description of a different machine $M$, and $T$ should halt if and only if there exists three different primes that $M$ all halt on.

When you're being asked to "describe $T$ in clear English", the main point is that you're not supposed to show it state for state (which would be extremely long and unwieldy), but just give a clear overall description about how it processes its input.

Related Question