Knowing how a Universal Turing Machines works and its capabilities, is it possible to obtain the collection M = {M0 , M1 , M2 , M3, … } of all possible Turing Machines?

If so, can we prove that a language L = {wj |wj not accepted by Mj } is not accepted by the Universal Turing Machine?


1 Answer 1


Enumerating all the possible TMs is a boring programming exercise. We do not need to use the UTM at all here -- we only have to generate the representation of all TMs and output it, using the chosen encoding of TMs as words.

The UTM does not accept your language $L$ since it accepts another language, namely $\{\langle M,w\rangle \ |\ \mbox{$M$ accepts $w$}\}$.


Your Answer

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

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