# Prove that $\{\langle M, n, w\rangle \mid \text{$M$has$n$states,$w ∈ \Sigma^*$and$M ∈ B(n,w)$}\}$ is undecidable

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?

• What does "the maximum number of steps" mean? – nekketsuuu Dec 27 '16 at 5:18
• 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 – 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)$.