Is the following language L undecidable?
L = {M | M is a Turing machine description and there exists an input x of length k such that M halts after at most k steps}
I think it is but I couldn't prove it. I tried to think of a reduction from the halting problem.
Review: An instance of the halting problem asks whether Turning machine N halts on input y. The problem is known to be undecidable (but semidecidable).
Your language L is indeed undecidable. This can be shown by reducing the halting problem to L:
This reduction is valid because:
Finally, the halting problem is undecidable, therefore L is undecidable.