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 pr开发者_运维百科oblem.
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:
- For the halting problem instance (N, y), create a new machine M for the L problem.
- On input x, M simulates (N, y) for length(x) steps.
- If the simulation halted within that number of steps, then M halts. Otherwise, M deliberately goes into an infinite loop.
This reduction is valid because:
- If (N, y) does halt eventually in k steps, then M will halt for all inputs of length k or greater, thus M is in L.
- Otherwise (N, y) does not halt, then M will not halt for any input string no matter how long it is, thus M is not in L.
Finally, the halting problem is undecidable, therefore L is undecidable.
精彩评论