Now define D , the diagonal set of strings:
$D=\left \{ w\epsilon \Sigma ^{*} \right \}$ where $w$ is not in $f\left ( w \right )$
- Call the correspondence $f$ is countable set $\Sigma ^{*}$
- For example
- $f\left ( \varepsilon \right )=L_{0}$ ,i.e. NULL string
- $f\left ( 0 \right )=L_{1}$ , string only contain a $'0'$
- $f\left ( 1 \right )=L_{2}$ for all even length string of infinite language etc.
Now, the question is
1) is D countable?
2) is D decidable?