1
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – chi Nov 13 '16 at 18:27
  • $\begingroup$ 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. $\endgroup$ – John Nov 13 '16 at 19:59
  • $\begingroup$ I suspect the answer to this questions depends heavily on the choice of encoding $\langle \_ \rangle$. $\endgroup$ – Raphael♦ Nov 14 '16 at 10:37
3
$\begingroup$

I don't fully understand the details of your question (especially the notation that you've used).

However, the language you're asking about appears to be finite (something like the language of descriptions of all Turing machines that halt for all inputs and have at most 100 states), and every finite language is decidable. You could, in principle, produce a list of all the strings in your language, and then just design a Turing machine that accepts exactly that list of strings.

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."

|cite|improve this answer
$\endgroup$
  • $\begingroup$ So I can essentially build a TM that contains a list of every distinct decider turing machine of 100 states, and then compare the input to see if it matches any of these machines. If it matches one of them, then the input is acceoted, but if it matches none, it gets rejected. $\endgroup$ – John Nov 13 '16 at 20:03
  • $\begingroup$ @John Exactly. Of course, in reality, that list would be far too long to ever work out but that's the principle. $\endgroup$ – David Richerby Nov 13 '16 at 20:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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