# Reduction of Turing-machine language

How to show that the following language is undecidable using reduction on the halting problem?

$$L: = \{w \in \{0,1\}^* |$$ TM $$M$$ with $$w = \langle M \rangle$$ does not accept any input $$\}$$

When TM doesn't accept any input, does it mean that the Turing machine halts or it just rejects any words?

And how to show that this language is not semi-decidable? I think to do it with a complement but I don't know how to start. Should I use the Rice's theorem in this proof?

I'd assume that a TM does not accept any input if for every input $$w$$ it either loops or halts and rejects.

The general approach to show some language is undecidable goes as follows:

1. Assume that there exists a machine $$M$$ that recognizes the language you are given
2. Take some language that you know is undecidable
3. Create a machine $$N$$ that using $$M$$ solves the undecidable language
4. Since the language is undecidable, you have reached a contradiction

Do you see how being able to answer the question "is it true that machine $$T$$ doesn't accept any input?" would help you answering the question "does machine $$T'$$ accept $$\epsilon$$?"?

Hint: Sometimes it is useful to create a machine that ignores its input!

About semi-decidability: There's a theorem that says that a language is decidable if and only if it is semi-decidable and its complement is semi-decidable. Once you prove that your language is undecidable you can easily check that its component is semi-decidable, which immediately gives you that the language itself cannot be semi-decidable.

Regarding Rice's Theorem: Generally I'd say it is a very useful theorem, but I would recommend to solve some undecidability exercises using just pure contradictory reasoning, since it allows you to understand the concept of reducing one problem to another better, in my opinion :)

• Thank you for explanations, I proved at last that this language is undecidable. But I got stuck in proving that it's not semi-decidable. I know that one of the properties of semi-decidability is when TM accepts the language, which is not this case. How to check that the complement is semi-decidable? Should I use characteristic function? May 24, 2021 at 12:45
• There's a trick to this - assume $M \in \bar{L}$ that is machine $M$ accepts some word. The problem is we don't know what word that is. If we just ran $M$ on the empty input and then $0$, then $1$ then $00$ and so on, we could never find the word $M$ accepts because for example $M$ loops on $\epsilon$. What you do is the following - enumerate all binary words $w_0, w_1, w_2, \ldots$ (you don't actually write them anywhere) and in the $i$-th step run $M$ on words $w_0, \ldots, w_i$ for $i$ steps each. This way if $M$ accepts $w_k$ you will eventually find out that $M$ accepts $w_k$. May 25, 2021 at 13:11
• If this is not clear to You I'd suggest reading about Universal Turing Machines May 25, 2021 at 13:13