Prove that this language is unsolvable

Question

Is the following language L unsolvable?

L = {M | M is a Turing machine description and there is an input x of length k such that M stops after no more than k steps}

I think it is, but I could not prove it. I tried to think about reducing the problem with stopping.

Answer 1

Overview. The stop problem instance asks if the Turning N machine stops at input y. It is known that the problem is unsolvable (but half-resolved).

Your language L is really insoluble . This can be shown by reducing the stop problem to L:

• For an instance of stopping problem (N, y), create a new machine M for problem L.
• At input x, M simulates (N, y) for steps of length (x).
• If the simulation is stopped during this number of steps, M stops. Otherwise, M deliberately goes into an infinite loop.

This reduction is valid because:

• If (N, y) eventually stops at k steps, then M will stop for all inputs of length k or more, so M is in L.
• Otherwise (N, y) does not stop, then M does not stop at any input line, no matter how much it is, so M is not in L.

Finally, the stopping problem is unsolvable; therefore, L is unsolvable.