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


Here is my new Turing machine: Turing Machine


  • $\begingroup$ Your basic idea will work, but whether the details are right depends on the precise formalization of Turing machines you're working with. Does your concept of Turing machine have a concept of a transition out of a stopping state? That looks a bit strange. $\endgroup$ – Henning Makholm Nov 21 '15 at 20:11
  • $\begingroup$ Hmmm.. I'm not exactly sure. I've been reading it out of our textbook. The name of our textbook is: Automata, Computability and Complexity by Elaine Rich. I'll edit the question and put a Turing machine that they created out of the textbook. $\endgroup$ – Anon Nov 21 '15 at 21:22

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.

  • $\begingroup$ In the book the $ and # are what the Turing machine writes in place of a's and b's, respectively, so that it can make sure there are the same number of a's as b's. But I thought a blank would represent the end of the string, so could I add another state, say q3, and make q0 and q1 point to it if they contain a blank square? $\endgroup$ – Anon Nov 22 '15 at 17:30
  • $\begingroup$ I added the new turing machine to the question! $\endgroup$ – Anon Nov 22 '15 at 17:42

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.