5
$\begingroup$

Let \begin{align*} L_1 &=\{\langle M,w\rangle \mid M\text{ halts on }w\}\\ L_2 &=\{\langle M,w\rangle \mid M\text{ does not halt on }w\}\,. \end{align*} Here $M$ represents encoding of a Turing machine (T.M.) and $w$ is the input string. What is the class of $L=L_1 \cup L_2$?

I read that the union would be a regular language as a string has to belong to either $L_1$ or $L_2$ (i.e., halt or not halt) so their union would be a regular language.

I have a doubt. Suppose we assume $L$ as a recursively enumerable (R.E.) language then there exists a T.M. which halts on all "yes" cases. Here yes cases means strings which belong to either $L_1$ or $L_2$. So, if a string belongs to $L_2$, then the T.M. should halt which means that we are able to halt and say "yes" even if machine doesn't halt on this string (according to condition of $L_2$). This solves halting problem and hence assumption is not correct and so $L$ should be non recursively enumerable.

I know that there is some flaw in the explanation given above but I am not able to find it.

Can someone please help me?

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ You talk about "the T.M.", but there is more than one floating about. I suspect if you try to be careful about which T.M. you are talking about in each case -- say, by naming them! -- you will discover the flaw in your argument. A machine which decides membership in $L$ need not be capable of deciding membership in $L_1$ nor of deciding membership in $L_2$ as a subroutine. $\endgroup$
    – Daniel Wagner
    Sep 6, 2017 at 1:52
  • $\begingroup$ @Daniel Wagner, so for L1 and L2 we have same TM and for L is it the different one ? $\endgroup$
    – Zephyr
    Sep 6, 2017 at 4:26
  • 1
    $\begingroup$ There's even more machines than that. $L_1$ and $L_2$ are languages that range over all possible machines. But yes: a hypothetical machine that decides $L$ is potentially different than the ones given by any particular string from $L_1$ or $L_2$. $\endgroup$
    – Daniel Wagner
    Sep 6, 2017 at 5:29

2 Answers 2

Reset to default
9
$\begingroup$

The language $L = L_1 \cup L_2$ consists of all pairs $\langle M,w \rangle$ where $M$ is a description of a Turing machine and $w$ is a word. This language is not necessarily regular (it depends on the exact encoding), but it is certainly decidable. All you have to do, given an input, is to decide whether it is of the form $\langle M,w \rangle$.

Note that deciding $L$ bears no relation to the halting problem. My description of $L$ doesn't refer to whether $M$ halts on $w$ or not. Here is a similar example. Let $f$ be an uncomputable integer-valued function. The function $g := 1-f$ is uncomputable as well, yet $f + g$ is computable.

Improve this answer
$\endgroup$
2
  • $\begingroup$ By exact encoding do you mean that there may be some strings which do not have a valid TM code , so we can't say all binary strings belonging to sigma* belong to L? $\endgroup$
    – Zephyr
    Sep 6, 2017 at 11:48
  • 1
    $\begingroup$ There might be some strings that don't encode a Turing machine. For example, suppose that the input is an integer, and the tape alphabet is ASCII. Then "123" encodes an integer but "Hi" doesn't. $\endgroup$
    – Yuval Filmus
    Sep 6, 2017 at 11:49
5
$\begingroup$

a string has to belong to either L1 or L2 (i.e halt or not halt) so their union would be a regular language.

This is a false statement. There is no chain of reasoning so it's hard to tell where the problem is.

Maybe it's a language issue. Consider this statement:

Every string (over some alphabet $\Sigma$) belongs to either $L_1$ or $L_2$. (*)

If that is true, then $L_1 \cup L_2 = \Sigma^*$ which is indeed regular.

Whether it is true depends on the encoding $\langle \_,\_ \rangle$. If it is surjective¹, then (*) is true; otherwise it's not.

I have a doubt. Suppose we assume L as recursively enumerable language then there exists a T.M which halts on all "yes" cases. Here yes cases means strings which belong to either L1 or L2. So, if a string belongs to L2, then the T.M should halt which means that we are able to halt and say "yes" even if string doesn't halt (according to condition of L2). This solves halting problem and hence assumption is not correct and so L should be non recursively enumerable.

You make a basic (but understandable and common) mistake: somebody promises you that an algorithm exists, and you go ahead an assume you know how the algorithm must work: clearly, the algorithm must check if either case happens! No, not if membership in the union can be checked in other, simpler ways.

This misconception is very widespread among novices. My favorite related example is the computability of whether $\pi$ contains $0^k$. Try to understand why that's the case, then revisit this question.

Now, for arbitrary $L_1 \in \mathrm{RE}$ and $L_2 \not\in \mathrm{RE}$ we don't know anything.

  • If $L_1 = \emptyset \in \mathrm{RE}$ we get $L_1 \cup L_2 = L_2 \not\in \mathrm{RE}$.
  • If $L_1 = \Sigma^* \in \mathrm{RE}$ we get $L_1 \cup L_2 = \Sigma^* \in \mathrm{RE}$.
  1. This is certainly possibly: Both the sets of all TMs and the set of all words are countably infinite, so we know there are bijections between either set and $\mathbb{N}$. The bijections can be lifted to pairs, and the result then bijectively maps to any universal language (your choice of alphabet). Of course, nobody outside of recursion theory uses such an encoding; it's unreadable. Then, the hardness of $L_1 \cup L_2$ depends on the specific encoding at hand.
Improve this answer
$\endgroup$
5
  • $\begingroup$ Actually I have a basic doubt. As the language is regular, it has to be R.E. Now for language to be R.E, it has to halt on strings in L2 as well. But we know that machine does not halt for strings in L2 . So even for "yes" cases the T.M doesn't halt because of strings in L2. So it has to be non R.E. I am sorry if I am being silly but I am really not able to find fault in this. $\endgroup$
    – Zephyr
    Sep 5, 2017 at 20:41
  • 2
    $\begingroup$ @Zephyr how do you "know" that? You know that $M$ doesn't halt on $w$, but this doesn't tell anything about the machine of $L$ halting on $\langle M, w \rangle$. $\endgroup$
    – Paŭlo Ebermann
    Sep 5, 2017 at 21:08
  • $\begingroup$ @Paulo Ebermann, I am assuming at first that L is recursively enumerable for proof. So if L is R.E then it has to halt for strings in L2 as even strings in L2 belong to L right (yes case)? $\endgroup$
    – Zephyr
    Sep 5, 2017 at 21:13
  • $\begingroup$ Yes. Sorry, my comment was targeted at next sentence "But we know that machine does not halt for Strings in $L_2$.". You don't know this, you just are lifting some property of the tuples you are encoding to the resulting string. $\endgroup$
    – Paŭlo Ebermann
    Sep 5, 2017 at 21:18
  • 2
    $\begingroup$ @Zephyr If you write down your argument in formal detail, you'll notice that you're talking about different machines. $\endgroup$
    – Raphael ♦
    Sep 5, 2017 at 21:18

Your Answer

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

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