# Decidability of decision problems

Can somebody give intuition how to answer those questions? From one side I can say that most of them are undecidable because we can reduce the halting problem to them (or halting problem can appear because we don't know about given TM anything so it can behave unpredictably, can simply loop on any input), but on another hand in question 2. we don't know much about machine, however I can hardcore all words into my TM as far as given language is finite. Also, for question 1. I'm able to create TM which checks if the output of M is even-length (I would classify this problem as semi-decidable).

What type of the following decision problems are: decidable, partly decidable, or even undecidable:

1. Does the language of the given machine M contain only even-length words?

2. Does the given M machine accept a finite language size of which is less than 2019?

3. We say that language A is prefixless if no word belonging to A is a prefix of any other word from A. For example, language A = {0, 10, 110, 1110, ...} is prefixless, while language B = {0, 1, 00, 11, 000, 111, ...} does not have this property (for example, because 0 is the prefix 00). Consider the following language (decision problem): L = {⟨M⟩ | L (M) is prefixless}.

4. Is the given recursive function a surjection?

5. Is the given recursive function an injection?

6. Does the machine M stop at bb?

7. Does the machine M accept the empty language?

• If you don't know it yet, Rice's Theorem is really helpful for questions like these. – Rick Decker Sep 7 '19 at 14:27
• Should "surrender" be "surjection"? – Noah Schweber Sep 7 '19 at 17:13
• Also, in (2) should "language" be "string"? – Noah Schweber Sep 7 '19 at 17:22
• @NoahSchweber you are right about "surjection", sorry I'll fix it, and in (2) should be said that power of language is less than 2019 (there are no more than 2019 words in language) – Maksym Sep 7 '19 at 19:49

A good rule of thumb is to use Church's thesis: can you personally solve the problem? While this is of course informal, in practice it works very well after you develop a bit of experience with Turing machines. (That said, ultimately the theorem you'll learn and use here is Rice's theorem.)

By way of example, let's first consider the following two sets:

• Those Turing machines which halt (on input $$0$$) in at most $$42$$ steps.

• Those Turing machines which halt (on input $$0$$) and output $$42$$.

It should be fairly easy to see that we can informally compute the former: given a Turing machine, just run it on input $$0$$ for $$42$$ steps and see what happens. The latter, though, is harder: if I'm presented with a candidate Turing machine, if I know it halts I can run it until it halts and check whether the output is $$42$$, but in the absence of that information I seem to be stuck since I don't see a way around the infinite search involved in "wait until it halts, if it ever does."

So now let's look at a couple candidates on your list.

• (1): in principle, we'd need to check each possible input to be confident that a Turing machine has the desired property: a single counterexample tells is it doesn't, but we don't know where such a counterexample might be and so as we go along checking all possible strings we'll never be fully confident that there isn't a counterexample (= a string of odd length which is accepted) which we just haven't found yet.

• (2): Here, there are only finitely many things we need to check, namely all those strings of length $$<2019$$. However, think about what's involved in checking a single candidate: the only a priori way to tell that a Turing machine doesn't accept a string is to run it forever, and "at the end of forever" you'll know that it in fact doesn't accept that string, but that's clearly bonkers. So there's still an infinite search involved, and this appears undecidable.

Now how do we make further distinctions between the undecidable sets - in particular, between semidecidable (more commonly, computably enumerable) and not-even-semidecidable?

Again, Church's thesis is the key: is it the case that, in order to be certain that something is in our set, we need to see some finite amount of information? If so, then it's computably enumerable. Otherwise, it's not - and in particular, if it's falsified by a counterexample (instead of verified by a witness) its complement is computably enumerable. So our Church's thesis analysis of (1) and (2) says that each is not even computably enumerable.

• Thank you, your answer inspired me to learn more about Rice's theorem, now after I learned it I assume that problems 1,2,3,6 and 7 are undecidable because those properties of languages are non-trivial. Correct me if I am wrong. What about problems 4 and 5? – Maksym Sep 7 '19 at 22:38
• @Maksym They're also undecidable since they're nontrivial properties of functions. – Noah Schweber Sep 7 '19 at 22:48
• thank you very much for your answer – Maksym Sep 8 '19 at 7:34