wolframscience.com

A New Kind of Science: The NKS Forum : Powered by vBulletin version 2.3.0 A New Kind of Science: The NKS Forum > Pure NKS > Prove that the complement of UTM's language is not turing recognizable.
  Last Thread   Next Thread
Author
Thread Post New Thread    Post A Reply
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

Old Post 04-30-2008 07:09 AM
Sridhar is offline Click Here to See the Profile for Sridhar Edit/Delete Message Reply w/Quote
Todd Rowland
Wolfram Research
Maryland

Registered: Oct 2003
Posts: 113

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

Old Post 05-27-2008 01:41 PM
Todd Rowland is offline Click Here to See the Profile for Todd Rowland Click here to Send Todd Rowland a Private Message Click Here to Email Todd Rowland Edit/Delete Message Reply w/Quote
Post New Thread    Post A Reply
  Last Thread   Next Thread
Show Printable Version | Email this Page | Subscribe to this Thread


 

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

Forum Sponsored by Wolfram Research

© 2004-14 Wolfram Research, Inc. | Powered by vBulletin 2.3.0 © 2000-2002 Jelsoft Enterprises, Ltd. | Disclaimer | Archives