Notes - 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.
@Prove that the language
\[L :=\mathsf{Accept_{TM} } = \\{\langle M, x \rangle : M \text{ accepts }x\\}\]
is recursively enumerable but not decidable via a diagonalisation argument.
$L$ is recursively enumerable since to decide membership we can just use a universal Turing machine to simulate $M$ on $x$.
But suppose that it is also decidable.
Construct a table $A$ where the rows are encodings of Turing machines and the columns are all possible strings. Set $A[i, j] = 1$ if and only if $M _ i$ accepts $s _ j$.
Construct a new language by flipping the diagonal, i.e. $s _ i \in L’ \iff \langle M _ i, s _ i \rangle \notin L$.
If $L$ is decidable, then $L’$ is also decidable. But if $L’$ is decidable, then there exist some Turing machine $M _ i$ that appears among the rows of the table. This leads to a contradiction, since this Turing machine would have to accept $s _ i$, but by definition it doesn’t.
Hence $L$ cannot be decidable.
@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}$.