0
$\begingroup$

Assume that $L$ is decidable. Is the following language decidable? $$ L' = \{w \mid \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, \ldots\}$, 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?

$\endgroup$
2
1
$\begingroup$

Your answer is correct . . . if you have a bound on the length of $u$ (that is, $u$ has to be no longer than $w$). However, the definition looks like it doesn't include this: e.g. it seems that if $ab\in L$ then $abcccccccccc$ would be in $L'$. If this is the case, it's not hard to show that $L'$ is not decidable.

$\endgroup$
1
  • $\begingroup$ you obviously right, but I cannot see how to prove that it is undecidable, please hint me. $\endgroup$ – user376326 Mar 21 '17 at 19:20

Your Answer

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