230 views
1 votes
1 votes

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?

1 Answer

Related questions

0 votes
0 votes
0 answers
1
Xylene asked Sep 9, 2017
198 views
I think that answer should be decidable.
1 votes
1 votes
1 answer
3
Mk Utkarsh asked Jan 2, 2018
904 views
what is the difference between recursive enumerable and not recursive enumerable(not partially decidable)?