First, let’s make sure we have the correct understanding of what $\mathbb N^*$ is: $$\mathbb N^* = \{(x_1,x_2,\ldots,x_k) : k \in \mathbb N, \; \forall i \; x_i \in \mathbb N\}.$$ So $\mathbb N^*$ denotes the set of all finite-length tuples where each coordinate is an element of $\mathbb N$.

We’ll show $\mathbb N^*$ is encodable/countable. Consider the alphabet $\Sigma = \{{\texttt{0}},{\texttt{1}},{\texttt{2}},{\texttt{3}},{\texttt{4}},{\texttt{5}},{\texttt{6}},{\texttt{7}},{\texttt{8}},{\texttt{9}},{\texttt{\$}}\}$. Any element of $\mathbb N^*$ can be uniquely represented with a finite-length string where commas are replaced with ${\texttt{\$}}$. (Note that there is really no need to put the opening and closing parentheses for the tuple.) To make the encoding definition a bit more explicit, if $\text{Enc} : \mathbb{N} \to \Sigma_9^*$ is the usual encoding of the naturals with digits (where $\Sigma_9 = \{{\texttt{0}},{\texttt{1}},\ldots,{\texttt{9}}\}$), then $\text{Enc}':\mathbb N^* \to \Sigma^*$ is defined as follows: for $(x_1,x_2,\ldots,x_k) \in \mathbb N^*$, $$\text{Enc}'((x_1,x_2,\ldots,x_k)) = \text{Enc}(x_1){\texttt{\$}}\text{Enc}(x_2){\texttt{\$}} \ldots {\texttt{\$}}\text{Enc}(x_k).$$ In this case, it is rather obvious that $\text{Enc}'$ is an injective function (i.e. that every element of $\mathbb N^*$ maps to a unique finite-length string.) Or in other words, if two elements of $\mathbb N^*$ map to the same string, then it is clear that they represent the same element of $\mathbb N^*$. (Explicitly writing a proof of this would be too pedantic in our opinion.) This shows $\mathbb N^*$ is encodable, i.e. countable.

Similarly, we can conclude that $A^*$ is countable whenever $A$ is a countable set.

Part 1: We show that $\text{REGULAR}$ is undecidable via a reduction from $\text{HALTS}$ (i.e. we show that $\text{HALTS}$ reduces to $\text{REGULAR}$).

Suppose $M_\text{REG}$ decides $\text{REGULAR}$. We define a decider for $\text{HALTS}$ as follows

def M_HALTS(<TM M, string x>):
    <HELP> = 
    """def HELP(w):
        if w is of the form 0^n1^n for some natural number n:
            ACCEPT
        else:
            run M(x)
            ACCEPT"""
    return M_REG(<HELP>)

We now have to prove that $M_\text{HALTS}$ is a correct decider for $\text{HALTS}$. In order to do this, we consider all possible inputs to $M_\text{HALTS}$ and argue that it gives the correct output.

First, consider the case when the input is $\langle M, x \rangle$ such that $M(x)$ halts. Then notice that the helper TM we define accepts all strings, i.e. $L(HELP) = \Sigma^*$. Therefore $M_\text{REG}(\langle HELP \rangle)$ accepts (because $\Sigma^*$ is a regular language), which means $M_\text{HALTS}$ accepts, as desired.

Next, consider the case when the input is $\langle M, x \rangle$ such that $M(x)$ loops (in the context of TMs, the word “loops” is synonymous with “does not halt”). Then notice that $L(HELP) = \{0^n 1^n | n \in \mathbb{N} \}$ is irregular. Therefore $M_\text{REG}(\langle HELP \rangle)$ rejects, which means $M_\text{HALTS}$ rejects, as desired.

Thus, we’ve shown that $\text{HALTS} \leq \text{REGULAR}$, so $\text{REGULAR}$ is undecidable.

(Note that there is also the case when the input string to $M_\text{HALTS}$ does not correspond to a valid encoding of a TM $M$ together with a string $x$. We would like to remind you once again that even though this is not explicitly written, we implicitly assume that the first thing our machine $M_\text{HALTS}$ does is check whether the input is a valid encoding of a TM $M$ together with a string $x$. If it is not, the machine rejects. If it is, then it will carry on with the specified instructions. Recall that this step of checking whether the input string has the correct form is never explicitly written. And in the proof of correctness, we do not have to explicitly argue what happens if the input string does not have the expected format since we can assume this step is handled properly.)

Part 2: We show that $\text{DOLORES}$ is undecidable via a reduction from $\text{HALTS}$ (i.e. we show that $\text{HALTS}$ reduces to $\text{DOLORES}$).

Suppose $M_\text{DOLORES}$ decides $\text{DOLORES}$. We define a decider for $\text{HALTS}$ as follows

def M_HALTS(<TM M, string x>):
    <HELP> = 
    """def HELP(w):
        run M(x)
        ACCEPT"""
    return M_DOLORES(<HELP, HELP>)

We now argue we have a correct decider for $\text{HALTS}$ as in the previous part.

Suppose the input is $\langle M, x \rangle$ such that $M(x)$ halts. Then $HELP$ accepts all inputs. Therefore $M_\text{DOLORES}(\langle HELP, HELP \rangle)$ accepts, which means $M_\text{HALTS}$ accepts, as desired.

Suppose the input is $\langle M, x \rangle$ such that $M(x)$ loops. Then $HELP$ does not accept any inputs. Therefore $M_\text{DOLORES}(\langle HELP, HELP \rangle)$ rejects, which means $M_\text{HALTS}$ rejects, as desired.

Thus, we’ve shown that $\text{HALTS} \leq \text{DOLORES}$, so $\text{DOLORES}$ is undecidable.

Suppose that $M_\text{FINITE}$ decides $\text{FINITE}$.

We define a decider for $\text{TOTAL}$. In the description below, we use the symbol $\texttt{<=}$ (less than or equal to) to compare two strings. If string $x$ is less than or equal to string $y$, it means $x$ is lexicographically less than or equal to $y$ (this is a total order on the set of all finite-length strings).

def M_TOTAL(<TM M>):
    <HELP> = 
    """def HELP(w):
        for y <= w:
            run M(y)
        ACCEPT"""
    return not M_FINITE(<HELP>)

We now have to prove that $M_\text{TOTAL}$ is a correct decider for $\text{TOTAL}$. In order to do this, we consider all possible inputs to $M_\text{TOTAL}$ and argue that it gives the correct output.

Suppose the input string is $\langle M \rangle$ such that $M$ halts on all inputs. Then notice that $L(HELP) = \Sigma^*$. Therefore $M_\text{FINITE}(\langle HELP \rangle)$ rejects, which means $M_\text{TOTAL}$ accepts, as desired.

Suppose the input string is $\langle M \rangle$ such that $M$ does not halt on all inputs. Let $x$ be the lexicographically smallest string that $M$ does not halt on. Then $HELP$ will not accept any string lexicographically greater (or equal to) than $x$, as $M(x)$ will not halt. Since there are only finitely many strings lexicographically smaller than $x$, $L(HELP)$ is finite. Thus, $M_\text{FINITE}(\langle HELP \rangle)$ accepts, which means $M_\text{TOTAL}$ rejects, as desired.

The set is countable. We’ll use the fact that rationals are dense in the reals. We sketch the main idea without giving a full proof: Inject $S$ to $\mathbb Q$ by mapping each element $s$ of $S$ to some rational between $s$ and the next largest element of $S$.

Note: If you try to inject to $\mathbb N$ by mapping the smallest element of $S$ to $0$, the second smallest to $1$, etc. it won’t work. If $S=\{1, 1.5, 1.55, 1.555, \ldots , 3, \ldots\}$, the $3$ will not be assigned to anything.