2
$\begingroup$

After having searched a bit, it seems I can't find terminology or references for this outermost class, 2Σ* in blue -- see below. What is it describing?

enter image description here

$\endgroup$
4
  • 2
    $\begingroup$ It's the power set of all sentences over $\Sigma$. In other words, it is all possible languages built from the alphabet $\Sigma$, since a language is just a subset of $\Sigma^*$, and the power set describes all possible subsets of a set. $\endgroup$
    – rici
    Nov 18, 2021 at 18:11
  • 1
    $\begingroup$ Several comments on the diagram. 1. A language is either "recognizable" or "not recognizable"; there should be no room outside of these two boxes. 2. Whether $\text{NP} \neq \text{P}$ is not known/proved. 3. Whether $\text{PSPACE}\neq\text{EXPTIME}$ is not known/proved. 4. Any given language can be included in a "Turing degree." $\endgroup$
    – John L.
    Nov 18, 2021 at 18:58
  • $\begingroup$ @JohnL. it seems to be missing caveats like "contained in" or <= or ?=, rather than a distinct = or . I don't have a caption for this figure. $\endgroup$ Nov 19, 2021 at 14:19
  • $\begingroup$ Good point. However, had I drawn the diagram, I would have drawn the boundary of a box differently, such as dotted lines, if the box does not mean strict containment by the area outside of it. $\endgroup$
    – John L.
    Nov 19, 2021 at 15:52

1 Answer 1

2
$\begingroup$

$2^{\Sigma^{*}}$ means the powerset of the full language $\Sigma^{*}$. It means the set of all subsets of $\Sigma^{*}$, including the empty set and $\Sigma^{*}$ itself, i.e., all possible languages with alphabet $\Sigma$.

Here is the simple understanding. When we want to describe a language $X$ with alphabet $\Sigma$, for each string $w$ in $\Sigma^{*}$, there are $2$ choices, including $w$ in $X$ or excluding $w$ from $X$. All these choices are independent.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.