I want to prove that: $\{\langle M, n, w\rangle \mid \text{$M$ has $n$ states, $w ∈ \Sigma^*$ and $M ∈ B(n,w)$}\}$ is undecidable.

Here $w$ is a string and $B(n,w)$ is the set of all $n$-state machines that halt on input $w$ after exactly the maximum number of steps. I don't know how to prove this. I tried finding another language to apply the reduction method but also to no avail. Can anybody help me with this?

  • 1
    $\begingroup$ What does "the maximum number of steps" mean? $\endgroup$ – nekketsuuu Dec 27 '16 at 5:18
  • $\begingroup$ Halting computations take a certain number of steps before they halt, and since there are only finitely many computations on n-state machines given input w, there is a number of steps that is the maximum for all these halting computations $\endgroup$ – user7342931 Dec 27 '16 at 10:27

Given a Turing machine $M$ of $n$ states and a word $w$, you could solve the halting problem for $(M,w)$ if you knew the maximal number of steps $f(n,w)$ that a Turing machine $M$ with $n$ states can spend on $w$. If your language were decidable then you could compute $f(n,w)$ by trying all Turing machines on $n$ states until you find one in $B(n,w)$.

I'll let you figure out the details on your own.

| cite | improve this answer | |
  • $\begingroup$ So I have to use reduction to the Halting problem? $\endgroup$ – user7342931 Dec 27 '16 at 10:31
  • $\begingroup$ I'll let you figure out the rest of the details. $\endgroup$ – Yuval Filmus Dec 27 '16 at 10:37

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.