[Prove that the complement of UTM's language is not turing recognizable.] - A New Kind of Science: The NKS ForumA New Kind of Science: The NKS Forum
Pages:1
Prove that the complement of UTM's language is not turing recognizable.
(Click here to view the original thread with full colors/images)
Posted by: Sridhar
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.
Posted by: Todd Rowland
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.
Forum Sponsored by Wolfram Research
© 2004-2008 Wolfram Research, Inc. | Powered by vBulletin 2.3.0 © 2000-2002 Jelsoft Enterprises, Ltd. |
Disclaimer
vB Easy Archive Final - Created by Xenon and modified/released by SkuZZy from the Job Openings