After reading about it in the textbook and in the web, i was wondering about the "turing recognizable" concept.

so for instance, if i take a simple language like:"L = {< M > | M ACCEPTS < M >}", then it should be a turing recognizable language since there can be a turing machine that halts and accepts strings in it, and for strings not in that language it doesn't halt or just skip them.

however, how can i build such a turing machine(i mean the pseudocode for it)?

i know it's quite a simple question, but i rose it out of curiosity so i could learn and from that to adapt to more complicated problems.

thank you very much for helping me


Let $U$ be a universal Turing machine. Then running $U$ on the input $\langle M \rangle, x$ will produce the same output as running $M$ on the input $x$ -- that's what it means for $U$ to be a universal Turing machine. Others have shown how to build a universal Turing machine.

Then, you can build a Turing machine to do what you want by using $U$: namely, on input $\langle M \rangle$, your Turing machine should run $U(\langle M \rangle, \langle M \rangle)$. Or, to put it another way, your Turing machine should make a second copy of the input it receives on the input tape, then run $U$. If you know how to build a Turing machine to copy a bit-string, and if you have a universal Turing machine $U$, you'll have a solution for your problem.

This might not sound very enlightening, but it's the easiest way to describe how you can do it. Programming Turing machines is incredibly tedious and usually not enlightening: it's like programming in a particularly nasty and human-unfriendly programming languages. Therefore, it's best avoided wherever possible. In this case, my solution lets you take advantage of the fact that someone else has already figured out how to build a universal Turing machine.

You might be wonder how to do that. Well, the basic idea is that you need to implement an interpreter for Turing machines. Pick your favorite programming language, like Python; could you write a Python program to interpret a Turing machine, one step at a time? I bet you could -- it's a simple matter of programming. Now you just need to do that, but this time instead of writing a Python program, you need to write a Turing machine -- a nastier and messier task that's far more tedious, but not conceptually different.

  • $\begingroup$ thank you very much for your enlightening answer, i'll dig deeper into it and sample implementations using python, it's very interesting $\endgroup$ – q2011 Mar 21 at 6:11
  • $\begingroup$ i was wondering, after reading the textbook, is it possible to use the diagonal method to show that this language is decidable? $\endgroup$ – q2011 Mar 22 at 21:05

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.