Explore BrainMass

Turing-recognizable language

This content was STOLEN from BrainMass.com - View the original, and get the already-completed solution here!

Let A be a turing-recognizable language consisting of descriptions of Turing machines, {M1, M2,...}, where every Mi is a decider. Prove that some decidable language D is not decided by any decider Mi whose description appears in A. (Hint: You may find it helpful to consider an enumerator for A.)

© BrainMass Inc. brainmass.com December 19, 2018, 11:30 pm ad1c9bdddf


Solution Preview

This problem uses the powerful method of diagonalization developed by George Cantor.

To understand diagonalisation better, read the following after reading the proof attached. Also try to read chapter 4 of ...

Solution Summary

Turing-recognizable language is described.