3
$\begingroup$

Assume that $L$ is decidable. Is the following language decidable? $$ L' = \{w | \text{ there is } u \in L \text{ such that u and w are equal to at most two positions.}\}$$

For example, let $u=abcd$. The following words are equal to $u$ at most two positions: $\{aba, agg, ab, zzz, dsa, ...\}$, but not $\{ abc, zbcd \}$

My approach:

A language is decidable iff some enumerator enumerates the language in lexicographic order.

I use above theorem.

So, $L$ is decidable. Therefore, let's take enumerator $E$ for it. Let We construct a $TM'$ for $L'$. Let enumerator $E$ be connected to $TM'$. For every input $w$ given to $TM'$ the $TM'$ compare it position by position with every string $v$ generated by $E$ in lexicographical order till $|v|\le|w|$ If number of the same positions $>2$ reject $w$. Otherwise, accept.

Ok?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ What does it mean "such that $u$ and $w$ are equal to at most two positions"? I read it as in: it might be that $u[0] = w[0]$ or that $u[1] = w[1]$ but surely $u[k] \neq w[k], k > 1$, i.e. $L'$ only contains words that are very different from L. $\endgroup$
    – Bakuriu
    Mar 19, 2017 at 21:17
  • $\begingroup$ We don't usually grade assignments here. Do you have any particular point which you are not sure about in your solution? $\endgroup$
    – Yuval Filmus
    Mar 19, 2017 at 21:45
  • $\begingroup$ @Bakuriu, I edited. YuvalFilmus, I solved a problem and I have doubts is it correct. It is not my assigment, even. I am just learning on my own, is it strange? $\endgroup$
    – user68041
    Mar 19, 2017 at 22:22
  • $\begingroup$ Cross-posted: cs.stackexchange.com/q/71772/755, math.stackexchange.com/q/2194238/14578. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. $\endgroup$
    – D.W. ♦
    Mar 28, 2017 at 23:04

1 Answer 1

Reset to default
2
$\begingroup$

Let's consider for simplicity the language $$ L'' = \{ w : \text{there exists $u \in L$ such that $u,w$ disagree on all positions} \} $$ instead of your more complicated one.

Consider the language $$ L = \{ 0^n10^m : \text{the $n$th Turing machine halts on the empty input after exactly $m$ steps} \}, $$ which is computable. You can check that $1^n0 \in L''$ iff the $n$th Turing machine halts, hence $L''$ is not computable.

In order to answer your original question, just repeat each bit 3 times.

Improve this answer
$\endgroup$
2
  • $\begingroup$ thanks. I don't understand your solution. Especially, I cannot see what do you mean by: $L = \{ 0^n10^m : \text{the $n$th Turing machine halts after $m$ steps} \}$. What do you mean that TM halts after $m$ steps? After all, you cannot claim it because number of step taken by MT depends on input. $\endgroup$
    – user68041
    Mar 21, 2017 at 19:22
  • $\begingroup$ Run it on the empty input. $\endgroup$
    – Yuval Filmus
    Mar 21, 2017 at 19:38

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.