Registered: Apr 2008
Posts: 1

Assume

L(UTM) is the language recognized by UTM , a language which constitute string set <M,w> where M is the description of a turing machine and w is any string.

Prove L'(UTM) - complement of L(UTM) is not turing recognizable.

Note:

I am looking for a proof which doesnt invoke the theorem that if L and L' are turing recognizable (recursively enumerable) L is turing decidable (recursive).


I am having this problem because...

I am thinking I can always construct a TM called NOT(universal turing machine) which simulates UTM and reverses the result. If such a turing machine exists is its language not L'(UTM)?

I know I am wrong somewhere but not sure where.

Report this post to a moderator | IP: Logged

Registered: Oct 2003
Posts: 103

To find your mistake, if there is one, you would have to provide more details.

If your language L, written as sequences of {0,1}, is 1-L'==L'/.{0->1,1->0}, then L' is not necessarily the same thing as the complement of L. For instance, L=={{0,1},{1,0}} where they are the same.

Report this post to a moderator | IP: Logged