Explore BrainMass
Share

Turing-recognizable language

This content was COPIED 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 March 21, 2019, 2:23 pm ad1c9bdddf
https://brainmass.com/computer-science/theoretical-computer-science/turing-recognizable-language-121808

Attachments

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.

$2.19