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?


1 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.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.