A New Kind of Science: The NKS Forum > Pure NKS > Prove that the complement of UTM's language is not turing recognizable.
Author
Sridhar

Registered: Apr 2008
Posts: 1

Prove that the complement of UTM's language is not turing recognizable.

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

04-30-2008 07:09 AM
Todd Rowland
Wolfram Research
Maryland

Registered: Oct 2003
Posts: 116

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

05-27-2008 01:41 PM

wolframscience.com  |  wolfram atlas  |  NKS online  |  Wolfram|Alpha  |  Wolfram Science Summer School  |  web resources  |  contact us