in "Introduction to Automata Theory, Languages and Computations" by Motwani, Ullman and Hopcroft, when they need to prove, for instance, Rice's theorem, they reduce the universal language, $L_u$, to the language $L_p$, where the latter is defined as the language containing the codes (binary) of all the TM $M$ such that $L(M) \in P$, where $P$ is a non-trivial property of $RE$ languages.

In the proof, they don't give the algorithm that converts an instance of $L_u$, $(M,w)$, to an instance of $L_p$, $<M'>$, but they give a description of $M'$, saying that this should be sufficient to convince the reader that a TM able to perform a conversion from $(M,w)$ to $<M'>$ exists.

I don't understand how this should be sufficient to convice myself that an instance-conversion algorithm exists. I mean: we are only describing $M'$, how can we be sure a TM is able to take $(M,w)$ as input and give us the binary code of $M'$?


1 Answer 1


This is very common. Specifying a Turing machine formally is super tedious and often not very insightful. It amounts to implementing a program, in a horribly inconvenient programming language. Writers typically assume that you already know how to write programs and that you can figure out how to implement something as a Turing machine, and leave it up to you to fill in those tedious details.

For instance, if I give you pseudocode of an algorithm, I am presuming that you will know how to turn that into an implementation. Same deal in these theorems: the author is trusting that you will know how to turn that description into an algorithm and then into code.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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