Timeline for Union of halting-like problem and non-halting-like problem
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 22, 2020 at 8:42 | vote | accept | Rnj | ||
| Jan 22, 2020 at 6:51 | comment | added | Shaull | Yes, exactly. The bit makes this union "artificial". Perhaps think about it this way: suppose the halting problem is a white puzzle-piece, with a weird shape (i.e. a difficult problem). The non-halting problem is the complement white piece, which is also weird. But when you join them, you get a nice rectangle (i.e. an easy problem). However, when you have the extra bit, these pieces have different colors, so while you get a rectangle, it is not nice, and you can tell which piece is which. | |
| Jan 22, 2020 at 3:51 | comment | added | Rnj | I am still struggling to get how union of halting and non halting problem is recursive, but adding extra bit to them make their union non recursive. The linked problem says, all we have to do is to check the encoding of input problem is of the form $\langle M,w\rangle$. Why adding extra bit makes such encoding check impossible? Is it because the bit indicates whether the string belongs to $L_0$ or $L_1$ and if it belongs to $L_1$ then we are supposed to check if $M$ does not halt on $w$ which is not possible as $L_1$ is not recursively enumerable? | |
| Jan 21, 2020 at 13:10 | comment | added | Shaull | Well, these are different problems. The bit at the end makes a big difference. It makes it sort of a "disjoint union" rather than a standard union, which means that even after the union, you can tell which word comes from which language, as opposed to the question you linked to. | |
| Jan 21, 2020 at 12:48 | comment | added | Rnj | This answer proves union of halting and non halting problem is decidable. I was asking whether $L_0\cup L_1$ is also decidable. If not, why? especially because they look very similar to halting and not halting problems, respectively. | |
| Jan 21, 2020 at 12:43 | comment | added | Shaull | I'm applying the distributivity of $\vee$ over $\wedge$, but I eliminate the contradicting cases, such as $b=1\wedge b=0$. The second thing you wrote doesn't make sense. There is no such thing as a "halting language", and the union of a recognizable language and a non-recognizable language (if that's what you mean) can be anything -- either recognizable or not, depends on the languages. | |
| Jan 21, 2020 at 12:41 | comment | added | Rnj | I didnt get your rearrangement. Are you doing (A+B)(C+D)=AD+BC ? If yes, is it valid? My main doubt is somewhat different. Union of halting and non halting problem is recursive. Then how just adding a bit to both of them make their union not recursive? | |
| Jan 21, 2020 at 11:13 | history | answered | Shaull | CC BY-SA 4.0 |