# Is a language of some deciders decidable?

Is

$$L = \{ \langle M \rangle \mid M = (\{Q_1, Q_2, . . . , Q_{100}\}, \{0, 1\}, \{0, 1, \_\}, δ, Q_1, Q_2, Q_3) \text{ is a decider}\}$$

decidable?

I know

$$HALT_{TM}= \{ \langle M \rangle \mid M \text{ is a decider}\}$$

is not decidable, but in the case we are given a specific Turing Machine that has 100 states, alphabet $\{0,1\}$, tape alphabet $\{0, 1, \_\}$ (where _ is space), a transition function $\delta$, a start state $Q_1$, an accept state $Q_2$ and a reject state $Q_3$.

Checking that M is in the correct format is easy but is it possible to build a Turing Machine that decides $L$? I assume I can use the fact that $HALT_{TM}$ is undecidable to show that $L$ also is, but I am not sure how to proceed.

And I don't see how I could reduce $L$ to $A_{TM}$ to prove by contradiction that it is not decidable?

How should I proceed?

• Is $L$, according your definition, an infinite set? It's not completely clear to me: if you fix the states and the alphabet, I'd say there are only finitely many choices for $\delta$, etc. – chi Nov 13 '16 at 18:27
• Yes the number of such TMs is finite. For each state q, you have 100 possible transitions reading 1, 100 reading 0 and 100 reading blank. Since there are 100 states, there is 100^4 number of possible TMs that meet these requirements. Only a portion of these are deciders. – John Nov 13 '16 at 19:59
• I suspect the answer to this questions depends heavily on the choice of encoding $\langle \_ \rangle$. – Raphael Nov 14 '16 at 10:37

Note also that reducing $L$ to the halting problem wouldn't prove that $L$ is undecidable, since every recursively enumerable language reduces to the halting problem. You'd just be showing "If I could solve the halting problem, I could solve $L$, too." That's a bit like saying, "If I was the world's strongest man, I could lift an apple." Maybe you don't need to be so strong to do such a simple thing? If you want to prove that $L$ is undecidable by reductions, you need to reduce an undecidable language to $L$: then, you're saying, "If I could decide $L$, I'd be able to decide this undecidable language, and I know I can't do that."