1
$\begingroup$

Complement of equality problem of Turing machines is unrecognizable or not-recognizable but How? As per my knowledge it is recognizable if you can decide its accept condition but not reject condition and the opposite is the case with unrecognizable. But in complement-Eq problem of TM if a string/input accepted by one but not by other you can Accept it, and reject condition will be undecidable so it should be Turin-recognizable.

$\endgroup$
0

1 Answer 1

1
$\begingroup$

Let's start with the definition of recognizable:

A language $L$ is recognizable if there exists a Turing machine $T$ such that if $x \in L$ then $T$ halts on $x$, and if $x \notin L$ then $T$ does not halt on $x$.

You haven't specified what you mean by "complement of equality problem of Turing machines", so let me assume that you mean the language $L$ consisting of pairs $(T_1,T_2)$ of Turing machines which do not recognize the same language, that is, there exists $x$ such that $T_1$ halts on $x$ and $T_2$ doesn't, or vice versa.

You could try recognizing $L$ by going over all words $x$, and for which one, checking whether $T_1$ halts on $x$ and $T_2$ doesn't, or vice versa. While you can recognize that $T_1$ halts on $x$, you cannot recognize that $T_2$ doesn't halt on $x$, so this strategy fails.

To show that this language is unrecognizable, you can use a reduction from the non-halting problem. Suppose that $T$ is a Turing machine, and we want to determine whether it doesn't halt on the empty input. Construct a new Turing machine $T_1$ which erases its input and transfers control to $T$, and let $T_2$ be a fixed Turing machine which immediately halts. Then $(T_1,T_2) \in L$ iff $T$ does not halt on the empty input.

$\endgroup$
1
  • $\begingroup$ Ok got it. In first example we also don't design the accept condition, for example if both halts on x we have to pick another input to prove inequality. And language could be infinite. am i right? I am asking because i have to do it without using theorems and reduction method. $\endgroup$
    – sadia
    Commented May 6, 2021 at 5:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.