Computational Complexity HT25, Properties of languages
Flashcards
@Justify that if $\Sigma$ is a finite alphabet, then the set of languages over $\Sigma^\ast$ is uncountable.
Suppose we could enumerate them $L _ 1, L _ 2, \ldots, L _ n, \ldots$. Create a table with the languages as the rows and all possible strings $s _ 1, s _ 2, \ldots, s _ m, \ldots$, and fill in the entries with a $0$ if $L _ i$ does not contain $s _ j$ and $1$ if it does.
Then create a new language by flipping the diagonal. This language must appear somewhere in the enumeration, but this would be a contradiction.
@Justify that there is a language $L \subseteq \Sigma^\ast$ such that $L \notin \mathsf{RE}$.
The set of Turing machines is countable, but the set of languages are uncountable.
@Define what it means for a language $L$ to be $\mathsf{RE}$-hard and $\mathsf{RE}$-complete.
- $\mathsf{RE}$-hard: For all $L’ \in \mathsf{RE}$, $L’ \le _ m L$.
- $\mathsf{RE}$-complete: $L$ is $\mathsf{RE}$-hard and $L \in \mathsf{RE}$.