Consider a language $A \subseteq \Sigma^*$ consisting of a subset of Turing machine descriptions. Say that $A$ is semantic if $\langle M\rangle \in A$ and $\mathcal{L}(M)=\mathcal{L}(N) \implies \langle N\rangle \in A$, where we recall that $\mathcal{L}(M) = \{ x \in \Sigma^* : M \textrm{ accepts } x \}$.
Prove that there are only two languages that are both semantic and decidable.
Consider some alphabet $\Sigma \subseteq \{0,1,2,3\}$. Say that a language $L \subseteq \Sigma^*$ is ISOD-enumerable (for “increasing sum of digits enumerable”) if it can be enumerated by a Turing machine in an order $x_1, x_2, x_3, \ldots$ such that each string in $L$ appears exactly once, and the sum of the digits in $x_{i+1}$ is always at least the sum of the digits in $x_i$ for each $i=1,2,3,\ldots$.
Such an enumerator could output the sequence $112, 123, 11212, 322, \ldots$, but $123$ cannot be followed by $112$.
Give a characterization of which alphabets $\Sigma \subseteq \{0,1,2,3\}$ are such that
$L \subseteq \Sigma^*$ is decidable $\iff$ $L$ is ISOD-enumerable,
and prove that your characterization is correct.
Review the definition of a context-free grammar (CFG). If $G$ is a CFG, we let $\mathcal{L}(G)$ denote the language that $G$ generates. In the following, $(01)^* = \{ \epsilon, 01, 0101, 010101, 01010101, \ldots\}$, where $\epsilon$ is the empty string.
As Farzam pointed out, only one of the following statements can be true. Decide which is true and prove it:
Given a CFG $G$, determining whether $\mathcal{L}(G) = (01)^*$ is undecidable.
Given a CFG $G$, determining whether $\mathcal{L}(G) \supseteq (01)^*$ is decidable.
\begin{align*} \textrm{VERTEX-COVER} &= \left\{ \langle G,k \rangle : G \textrm{ has a vertex cover of size at most } k \right\} \\ \textrm{DOM-SET} &= \left\{ \langle G,k\rangle : G \textrm{ has a dominating set of size at most } k \right\}. \end{align*}
Prove that $\textrm{VERTEX-COVER} \leq_P \textrm{DOM-SET}$.Consider a mapping $\varphi : \Sigma \to \Sigma^+$ that maps characters of the alphabet to finite length strings (recall that $\Sigma^+$ is the set of finite length strings over $\Sigma$ whose length is at least 1). For a word $w = w_1 w_2 \cdots w_n \in \Sigma^*$, we define
$$ \varphi(w) = \varphi(w_1) \varphi(w_2) \cdots \varphi(w_n). $$ Consider the following two statements: