# Proving a certain superset the halting language is not recursive

Let $\Sigma =\{ 0, 1\}$. Let $val:\Sigma^* \rightarrow \mathbb{N}$ be a function that given a string returns its decimal value, and $L_{halt} = \{\langle M\rangle \langle w\rangle \mid M$ halts on $w \}$.

I define the following language:

$L=\{ x \mid x\neq x^R \wedge (x\in L_1 \vee x\in L_2 \vee x\in L_3)\}$

where:

• $L_1=\{ x \mid x\in L_{halt} \wedge x^R \in L_{halt} \wedge val(x)<val(x^R) \}$
• $L_2=\{ x \mid x\notin L_{halt} \wedge x^R \notin L_{halt} \wedge val(x)<val(x^R) \}$
• $L_3=\{ x \mid x\in L_{halt} \wedge x^R \notin L_{halt} \}$ (in this language there is no requirement on $val$ function)

That is, a string in $L$ has 3 options how to look like.

Intuitively I can feel that $L\notin R$, but I do not know how to approach a formal proof for this.

I tried using a reduction $L_{halt} \leq L$, and then since $L_{halt}\notin R$ I can deduce that $L\notin R$, but I could not find a reduction that will work.

The closest thing I could come up with is using an intermediate reduction, first defining $L_{halt}^{'} =\{ 1 x 0 \mid x \in L_{halt} \}$ and then easily $L_{halt} \leq L_{halt}^{'}$ and all I have to do is $L_{halt}^{'} \leq L$, so my idea for reduction was given $x=1y0$ then $f(x)=y$ (the reduction returns $y$), but then this reduction has a problem if $y\notin L_{halt}$ and $y^R\notin L_{halt}$ then it might be possible that $val(y) < val(y^R)$ and then $f(x)=y\in L$ but $y\notin L_{halt}^{'}$...

I'm kind of stuck at how my reduction should work?

I'm also assuming that any string from $\Sigma^*$ is a possible encoding of a $<M><w>$, that is I cannot assume something about the encoding itself and also every word is a possible encoding of $\langle M\rangle \langle w\rangle$...

• Can you try to figure out what strings are not in $L$? i.e., $L_1$--$L_3$ cover quite a lot of strings. what strings are not covered by any of them? Feb 13 '16 at 21:16
• @RanG. , yes for example: $x$ s.t. $x=x^R$ are one kind. Other options include: $x$ s.t. $x\in L_{halt}$ and $x^R\in L_{halt}$ but $val(x) \geq val(x^R)$ (example for someone not in $L_1$), $x$ s.t. $x\notin L_{halt}$ and $x^R\notin L_{halt}$ and $val(x) \geq val(x^R)$ (example for not being in $L_2$) and another example $x$ s.t. $x\notin_{halt}$ and $x^R\in L_{halt}$, this is for not being in $L_3$. Feb 13 '16 at 22:26
• Your first example is correct, the second is misleading. Take $a$ and $b$ such that $val(a)<val(b)$. Can they be outside $L_1 \cup L_2 \cup L_3$, that is, not included in any of these three? Feb 14 '16 at 7:52
• @RanG., when comparing using $val$ function I always compare $a$ to $a^R$, not to an arbitrary $b$. I will clarify my example: if $a\in L_{halt}$ and $a^R \in L_{halt}$ and $val(a) > val(a^R)$ then $a$ will not be in $L_1$. It is also obvious that $a$ will not be in $L_2, L_3$ because the languages' requirements differ. But -- $a^R$ will be in $L_1$ since, denote $c=a^R$, so $c =a^R \in L_{halt}$ and $c^R = a\in L_{halt}$ and $val(c) = val(a^R) < val(a) = val(c^R)$. That is, if $a, \,a^R \in L_{halt}$ and $val(a) > val(a^R)$ then $a\notin L_1$ but $a^R\in L_1$. Similarly for $L_2$. Feb 14 '16 at 9:07
• OK, I may have mis0read the question. So for any pair $(a,b)$ where $a=b^R$ and $a<b$, $a$ is always in $L$, but $b$ is in $L$ only if it is not in $L_{halt}$? Doesn't this give you a reduction ? Or am I mis-reading again? Feb 14 '16 at 21:57

Main idea of the proof is since $L$ is kind of superset of $L_{halt}$ we select reduction in such a way that we always deal with only that subset of $L$ which resembles $L_{halt}$.

First let us choose any encoding such that if $\langle M,w \rangle \in L_{halt}$ then $\langle M,w \rangle^R \not\in L_{halt}$. $L_{halt}$ is undecidable in every reasonable encoding so this is okay. Also this will be true for most of the encodings if we include $\langle \rangle$ also in the encoding. (Reverse will be $\rangle w^R, M^R \langle$). Also we should have $val(\langle) > val(\rangle)$. I assume that $val$ is calculated as a number with base $|\Gamma|$ where $\Gamma$ is the tape alphabet. In the question decimal base is mentioned, which means the same. We need to add extra 4 bits (= 1 decimal digit) in each cell if we do not have enough space for new symbols.

For this encoding we can have an identity reduction for valid input of the form $\langle M,w \rangle$. For invalid input not of the form $\langle M,w \rangle$ we shall reduce the input to $\langle\epsilon,\epsilon\rangle$ which does not belong to $L$. Let us call this reduction $f$. We assume that in our encoding $\langle\epsilon,\epsilon\rangle \not\in L_{halt}$.

We can now easily prove $x \in L_{halt}$ if and only if $f(x) \in L$.

($\Rightarrow$)
Let $x = \langle M,w \rangle \in L_{halt}$.
Then clearly $val(x) > val(x ^R)$.
And $\langle M,w \rangle^R \not\in L_{halt}$.
Therefore $\langle M,w \rangle \in L_3$ and hence $\langle M,w \rangle \in L$ as naturally $x \neq x^R$, Symbols $\langle,\rangle$ ensures that $x \neq x^R$.

($\Leftarrow$)

Note it $f(x) = \langle \epsilon, \epsilon \rangle$ then it does not belong to $L$. So take the other valid cases.

Let $f(x)= y =\langle M,w \rangle \in L$.
Then $\langle M,w \rangle \in L_3$, as $val(y) > val(y^R)$.
This gives us $\langle M,w \rangle \in L_{halt}$ straight away.

The idea of this proof holds even if we are given a specific encoding for $L$ as well.

1) If the encoding for $L$ is such that we do not have begin symbol $\langle$ and end symbol $\rangle$. Also assume $x_{reject}$ is a string such that $x_{reject} \not\in L$. We can easily find such a string as $L \neq \Sigma^*$. In this case the strings got by reduction will not be necessarily in $L_3$. We also assume our encoding of turing machines is such that we can find a string $\alpha$ such that $0^*\alpha$ is never a proper prefix.

To always get strings in $L_3$ we define the reduction as follows. All invalid input strings which are not of the form $\langle M,w \rangle$ are reduced to $x_{reject}$, and all valid input strings which are of the form $\langle M,w \rangle$ are reduced to $\langle M',w\alpha^R0^{|M'|+1}\rangle$. $M'$ will remove suffix $\alpha^R0^*$ and then behave as $M$.

With this reduction the proof given above can be modified slightly to prove that $L$ is undecidable.

If the encoding for $L$ is such that $\langle$ and $\rangle$ are always included and $val(\langle) < val(\rangle)$ then in the reductions given above we will always get strings from set $L_1$ and $L_2$. In this case by using $\alpha^R0^*$ suffix it is easier to get reduced strings from set $L_2$. Then it is better to reduce language $\overline{L_{halt}}$ which is also undecidable to $L$ to prove undecidability of $L$.

• What? Why the <- direction makes sense? What if $x \in L_2$? Apr 29 '16 at 2:44
• I have selected reduction such that "$\langle$" $M,w$ "$\rangle$" instance always reduces to an $L_3$ instance. In reduction it is okay to always reduce to a subset of target problem instances. So if $x$ is an instance of Halting problem then $f(x)$ will be always an instance of $L_3$, never an instance of $L_2$. Apr 29 '16 at 12:29
• <- means $f(x) \in L \Rightarrow x \in L_{halt}$ and $f(x) = x = "\langle" M "," w "\rangle"$. Apr 29 '16 at 13:27
• In your encoding, if ⟨M,w⟩ is in $L_{halt}$ then it maps to $L_3$, but if it is not, it may map to $L_2$, and still belong to $L$. If you don't think this is possible, you should add a proof. in the $\Leftarrow$ direction you must start with an arbitrary input in $L$ and prove it is in $L_{halt}$. Apr 29 '16 at 13:36
• It can't be in $L_2$ because $val(x) > val(x^R)$. Remeber we have selected $val("\langle") > val("\rangle")$. So $x \not\in L_{halt} \Rightarrow f(x) \not\in L$ is still true. Apr 29 '16 at 14:03