$L$ is decidable. Prove that "similar" language is also decidable

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?

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.

StackExchange Computer Science Q#71772, answer score: 2