How Turing Machine Can Never Stop?

My professor discussed the following Turing machine M' on input (,x):

• Generate number n

• Run M on X, for n steps

• If M stops, accept

I don't understand No.3

If we are running M on input X for final number of steps then there is no way for M not to stop... so why he wrote if M stops?

Its an informal phrasing. I think it's easiest to stay with informal wording and just use more words to clarifiy.

M' cannot "run M for n steps, in the most literal of notation. You instead run another Turing machine, which I will call Mi, where the "i" means "insturmented." This new Turing machine has a few properties

• Its input tape is initially filled with a counter (initially set to n) followed by X.

• It provably decrements this counter towards zero. After some number of decrements occur, the state of the tape is identical to the state that M leaves the tape in after n steps (this is what they mean by "simulating." It's not the same machine, but it yields the same results)

• It halts when the counter hits 0, or when it is done simulating a step of M that would cause M to halt.

It is actually reasonably trivial to construct such a machine. It is typically much slower than M, but Turing completeness is not concerned with that.

So what M' does is actually write n to the tape, followed by X. It then executes Mi, which, when it completes, either leaves a zero or a non-zero value in the counter. M' then uses that value to determine whether the simulated M halted, or if Mi had to cut it off beacuse it had run the specified number of steps.

This is, of course, one implementation. It doesn't have to be exactly that structure. But this is one structure which can be used to construct the proof your professor is using.

StackExchange Computer Science Q#146531, answer score: 5