Can an alphabet be extended in a reduction proof? (with sample problem)

Question

So I am working on solving a problem on whether following language is decideable:

$L = \{n \in \mathbb{N} \mid M_n$ never freezes (for any input)$\}$, where $n$ is the Gödel-number of a Turing machine.

The model for Turing machines that we use operates on a one-side-unbounded tape, so "freezing" in this context means going "out-of-bounds" on the other side of the tape. We also define a Turing machine as the tuple $(K,\Sigma,\delta,s)$, where $K$ is the set of states, $\delta$ is the transition function and $s$ is the starting state ($\notin K$).

Now I have an idea on how to prove it is not decideable by reduction, but it requires me to construct a new DTM which operates on a new alphabet $\Sigma' := \Sigma \cup \{§\}$, and assume that $§ \notin \Sigma$. (where $\Sigma$ is the alphabet of the machine $M_n$)

My idea is as follows: We prove that $L^c=\{n\in\mathbb{N}\mid M_n $freezes for at least one input$\}$ is undecideable. For that, we construct a DTM $Extend$ which takes $n$ as input. $Extend$ modifies the $n$ so that we get a new machine that operates exactly as $M_n$ would, except with the following tweaks:

1. For any (state,letter) pair with the $\delta$ function value $\delta(q,\sigma)=(h,\sigma')$ (where h is the halting state), we replace the function value with $(q_{|K|+1},\sigma')$ (so now the machine never halts on its own)

2. Introduce a new state $q_{|K|+1}$, where $\delta(q_{|K|+1},\sigma)=(q_{|K|+1},\sigma)$ (so if this state is reached the TM goes into an infinite loop).

3. We introduce a new letter to the alphabet, let's say '$§$', and set it so that $\delta(q,§)=(h,\#)$ (where # is the blank symbol) (so it only halts if any point it reads '$§$') All of these are turing-computable steps (if we look at $\delta$ as a table of values for every (state,letter) pair (finite), it's the same as going through the table once, changing values as necessary, adding a row and adding a column).

Now we create a new DTM $M_j$ which works as follows (on input $n$): $>Extend \to L_{\#} \to S_R \to L \to § \to R \to R_{\#}$, where $L_{\#}, R_{\#}$ is a TM which goes left or right respectively until it encounters a blank, and $S_R$ is a TM which shifts the word to the right of it by a blank (so $s,\underline{\#}w\# \vdash^*_{S_R}h,\#\underline{\#}w\#$). So $M_j(w)$ works as follows: $s,\#n\underline{\#} \vdash^*_{M_j} h,§\#n_{Extend}\underline{\#}$

We know that the set $\mathcal{E}=\{ n\in\mathbb{N} \mid M_n$ accepts $\emptyset \}$ is in $\text{co-RE}$. This means $\mathcal{E}^c = \{ j\in \mathbb{N} \mid M_j$ accepts at least one input $\}$ is recursively enumerable, but not decideable. Since our new DTM $M_j$ only accepts iff $n$ would freeze for at least one input, this means that $n\in L^c \Leftrightarrow j\in \mathcal{E}^c$ and the reduction proof would be complete.

But again, I am not sure if the transformation of $n$ I made (by introducing the letter '$§$' to $\Sigma$) is allowed. Can someone clarify this for me?

Answer 1

A (computable) reduction from problem P to problem Q is a (computable) function that takes an instance of P to an instance of Q. In your case $P=\mathcal{E}^c$ and $Q = L^c$. So your reduction is "legal" (that is, conforms to the definition of reduction) if it takes an instance of $\mathcal{E}^c$ to an instance of $L^c$. That's all a function has to do in order to be a reduction.

(In principle there is no such thing as an instance of a problem – every string over the appropriate alphabet is an instance. But let's ignore this small issue.)