开发者

Prove that this language is undecidable

开发者 https://www.devze.com 2023-03-19 09:04 出处:网络
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}

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:

  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.

0

精彩评论

暂无评论...
验证码 换一张
取 消