- #1
controlfreak
- 58
- 0
Complement of Universal Turing Machine - Does this exist??
I am kind of confused in terms of the creation of machine which does NOT (Universal Turing Machine). I mean I construct a TM which will simulate UTM and accept strings it rejects and rejects strings it accepts. So if L(UTM) defined as <M,w> = <Turing Machine (TM) Description,string passed which is accepted by TM> is recognizable by UTM then L'(UTM) should be recoginizable by NOT(UTM) which is also a TM. But then if L(UTM) and L'(UTM) is turing recognizable then L(UTM) becomes decidable which is wrong as that is the crux of Turing and in turn Godel's undecidability theorem. So I MUST be missing some fundamental point here and not sure what that is. Please Help!
I am kind of confused in terms of the creation of machine which does NOT (Universal Turing Machine). I mean I construct a TM which will simulate UTM and accept strings it rejects and rejects strings it accepts. So if L(UTM) defined as <M,w> = <Turing Machine (TM) Description,string passed which is accepted by TM> is recognizable by UTM then L'(UTM) should be recoginizable by NOT(UTM) which is also a TM. But then if L(UTM) and L'(UTM) is turing recognizable then L(UTM) becomes decidable which is wrong as that is the crux of Turing and in turn Godel's undecidability theorem. So I MUST be missing some fundamental point here and not sure what that is. Please Help!
Last edited: