Prove that this language is undecidable

Question

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.

Acrimonious

k is a fixed constant here, right? – Dkl

no. If k is fixed then it is decidable I think – Acrimonious

Forgive me if this is a naive approach, but-- if I want to know whether a machine X halts (without input), can I enclose it in another machine Y which will ignore input? That is, if you run Y with any input, Y will just run X, perhaps with a fixed number of steps of overhead? If so then X halts iff Y is a member of L, so L is undecidable. Is this a workable approach? Or must Y erase the input or something? – Seedman

You can do that. Or Y can run on X if its input is X and loop otherwise. the problem here is that X is unknown. – Acrimonious

Answer 1

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:

1. For the halting problem instance (N, y), create a new machine M for the L problem.
2. On input x, M simulates (N, y) for length(x) steps.
3. 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.

Canonicals