Complement of Universal Turing Machine - Does this exist?

In summary: TM i.e. L(TM). So in this case the UTM would not know about L(TM) even if it accepted strings from it. In summary, 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.
  • #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!
 
Last edited:
Physics news on Phys.org
  • #2
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.
 
  • #3
CRGreathouse said:
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.
 
Last edited:
  • #4
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.
 
  • #5
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?
 

What is a Universal Turing Machine?

A Universal Turing Machine is a theoretical computing machine that can simulate any other Turing Machine. It is capable of performing any computation that is possible on a Turing Machine, making it a fundamental concept in the study of computability and complexity.

What is the complement of a Universal Turing Machine?

The complement of a Universal Turing Machine is a theoretical concept that refers to a machine that can simulate the behavior of any Turing Machine, except that it outputs the opposite result. For example, if a Turing Machine outputs 1 for a certain input, its complement would output 0 for the same input.

Does the complement of a Universal Turing Machine exist?

The existence of the complement of a Universal Turing Machine is still a topic of debate among computer scientists. While it is possible to design a Turing Machine that simulates the behavior of a Universal Turing Machine's complement, there is no definitive proof that such a machine can exist.

What are the implications of the complement of a Universal Turing Machine existing?

If the complement of a Universal Turing Machine does exist, it would have significant implications in the field of computability and complexity. It could potentially lead to the creation of more powerful computing machines, as well as have implications for the limits of computation.

Is the complement of a Universal Turing Machine relevant to practical computing?

Currently, the complement of a Universal Turing Machine is mostly a theoretical concept and has no direct relevance to practical computing. However, the study of this concept can lead to a better understanding of the limits of computation and the fundamental principles of computer science.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
  • Programming and Computer Science
Replies
29
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
985
  • Programming and Computer Science
Replies
2
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
9
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
6
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
3
Views
2K
  • Programming and Computer Science
Replies
4
Views
2K
  • Programming and Computer Science
Replies
2
Views
717
Back
Top