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 Gdel-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: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)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).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?
Can an alphabet be extended in a reduction proof? (with sample problem)
computability;turing machines;reductions;undecidability;proof techniques