4
$\begingroup$

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$...

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Ran G. Feb 13 '16 at 21:16
  • $\begingroup$ @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$. $\endgroup$ – Dan D-man Feb 13 '16 at 22:26
  • $\begingroup$ 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? $\endgroup$ – Ran G. Feb 14 '16 at 7:52
  • $\begingroup$ @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$. $\endgroup$ – Dan D-man Feb 14 '16 at 9:07
  • $\begingroup$ 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? $\endgroup$ – Ran G. Feb 14 '16 at 21:57
-1
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ What? Why the <- direction makes sense? What if $x \in L_2$? $\endgroup$ – Ran G. Apr 29 '16 at 2:44
  • $\begingroup$ 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$. $\endgroup$ – Shreesh Apr 29 '16 at 12:29
  • $\begingroup$ <- means $f(x) \in L \Rightarrow x \in L_{halt}$ and $f(x) = x = "\langle" M "," w "\rangle"$. $\endgroup$ – Shreesh Apr 29 '16 at 13:27
  • $\begingroup$ 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}$. $\endgroup$ – Ran G. Apr 29 '16 at 13:36
  • $\begingroup$ 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. $\endgroup$ – Shreesh Apr 29 '16 at 14:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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