0
$\begingroup$

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?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
0
$\begingroup$

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 :)

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – serendipity
    May 24, 2021 at 12:45
  • $\begingroup$ 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$. $\endgroup$
    – Jan Chomiak
    May 25, 2021 at 13:11
  • $\begingroup$ If this is not clear to You I'd suggest reading about Universal Turing Machines $\endgroup$
    – Jan Chomiak
    May 25, 2021 at 13:13

Your Answer

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

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