Complement of Universal Turing Machine - Does this exist?

[controlfreak]

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!

 

[CRGreathouse]

The complement of a Turing machine need not be a Turing machine, otherwise testing for membership in recursively enumerable sets would be no different from testing membership in recursive sets.

 

[controlfreak]

The complement of a Turing machine need not be a Turing machine, otherwise testing for membership in recursively enumerable sets would be no different from testing membership in recursive sets.

Why?

Theorem: Given a TM1 which recognizes language L(TM1), there is always a TM2 which recognizes language L'(TM1)

Proof Idea:
Let us take all the strings a turing machine (TM1) accepts and make it a string set - we call that string set a language recognized by the turing machine - say L(TM1). Then I can always create a turing machine TM2 which simulates TM1 inside it and reverses the result - accept strings which TM1 rejects and reject strings which TM1 accepts. There are many theorems which are proven based on this possiblity. If such a turing machine exists that turing machine's accepted string set constitute of strings not present in L(TM1)

i.e.

L(TM2) = Complement of L(TM1).

QED

I define complement of turing machine TM1 as the turing machine TM2 which accepts a language complement to the language accepted by TM1. Technically I can't say complement of TM1 - doesn't have much meaning.

When you mean the complement of a turing machine is not always a turing machine - are you meaning it is something more than that? As far as I know Regular Languages, CFL and all types of recognizable languages are recognized by a turing machine. If there is a language which is not recognized by a turing machine, it cannot be recognized by any machine we know of (let it be DFA,NFA,Pushdown Automata...). Then we go to the realm of super turing machine and all that... That itself is a research field where there is a lot of debate.

In anycase what you essentially mean is my construction proof given above which indicates given a turing machine TM1 I can create another machine TM2 such that L(TM2) = L'(TM2) has a flaw. In my question I am specifically concerned about not any turing machine but specifically the universal turing machine. If so where is the flaw - that is what is bothering me.

I think the flaw is related to the strings which cause the UTM to loop... but not able to fully pinpoint it.

 

[controlfreak]

I think the loop is the problem.

If I state"

For recursively enumerable set, I can determine the "yes" answer for membership for certain elements in finite time (no loop), but for many other elements the definite "yes" or "no" answer cannot be reached because of the loop.

If a set is not even recursively enumerable "yes" for any element can't be reached in finite time.

But then that still doesn't cause a problem with my proof as UTM might reject certain strings which will be accepted by UTM'. This means UTM' also will have some strings which it can accept in finite time and some strings which will loop indefinitely and some it will reject in finite time. So the fate of UTM and UTM' are similar so why one machine's language is recursively enumerable and other's not.

Loop is the issue... don't know how.

 

[controlfreak]

It is how they have defined turing recognizable:

From Wikipedia

In computability theory, traditionally called recursion theory, a set S of natural numbers is called recursively enumerable, computably enumerable, semidecidable, provable or Turing-recognizable if:

* There is an algorithm that, when given an input number, eventually halts if and only if the input is an element of S.


So here it says because of "iff" in certain cases where the membership answer is "yes" the machine will halt but it will not halt at for any case where the answer is "no". So the complement machine will not halt for any "yes" answer but will halt for certain "no" answers and hence the complement machine will not say "yes" to any input in finite time and hence the issue.

But in this sort of definition - the language recognized by the UTM i.e. L(UTM) itself is not recursively enumerable as there would be strings which it can reject in finite time or strings for which the end state of reject state can be attained by UTM in finite time. Am I wrong here?? Take for example I construct a trivial turing machine (TMR) which rejects everything and it is one of the inputs to UTM as <TMR, w> which UTM can get to reject state immediately in finite time.

What the hell is wrong?