Skip to main content
Computer Science

Return to Question

More descriptive title
Source Link
John L.
John L.
  • 39.1k
  • 4
  • 34
  • 91

Undecidable: Given a TM $M$, is there $w$ on which a TM M $M$ halts after $\leq w$|w|$ steps?

The detailed question is:

  Is there a word $w$ on which a TM M $M$ halts after a maximum of $|w|$ (word length) steps?

More formerly, is the language below decidable? $$H=\{\langle M\rangle \mid \text{ TM $M$ halts after a maximum of $|w|$ steps for some word }w \}$$

I highly assume, that this problem is not decidable because in the worst case you have to test every word that exists (infinite) to realize, that the TM never holds. However this isn't a proof and I have to proofeprove this questionconclusion (without the Rice's theorem).

My idea was to use the subroutine technique to "convert" the problem into the halt-problem, the $\epsilon$-halt-problem or the total halt problem. I have no idea on how to turn this problem into an existing one - could you help me here please?

Undecidable: $w$ on which a TM M $M$ halts after $\leq w$ steps

The detailed question is:

  Is there a word $w$ on which a TM M $M$ halts after a maximum of $|w|$ (word length) steps?

I highly assume, that this problem is not decidable because in the worst case you have to test every word that exists (infinite) to realize, that the TM never holds. However this isn't a proof and I have to proofe this question (without the Rice's theorem).

My idea was to use the subroutine technique to "convert" the problem into the halt-problem, the $\epsilon$-halt-problem or the total halt problem. I have no idea on how to turn this problem into an existing one - could you help me here please?

Undecidable: Given a TM $M$, is there $w$ on which $M$ halts after $\leq |w|$ steps?

The question is: Is there a word $w$ on which a TM $M$ halts after a maximum of $|w|$ (word length) steps?

More formerly, is the language below decidable? $$H=\{\langle M\rangle \mid \text{ TM $M$ halts after a maximum of $|w|$ steps for some word }w \}$$

I highly assume, that this problem is not decidable because in the worst case you have to test every word that exists (infinite) to realize, that the TM never holds. However this isn't a proof and I have to prove this conclusion (without the Rice's theorem).

My idea was to use the subroutine technique to "convert" the problem into the halt-problem, the $\epsilon$-halt-problem or the total halt problem. I have no idea on how to turn this problem into an existing one - could you help me here please?

Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Source Link
Werlin
Werlin
  • 21
  • 1
  • 2

Undecidable: $w$ on which a TM M $M$ halts after $\leq w$ steps

The detailed question is:

Is there a word $w$ on which a TM M $M$ halts after a maximum of $|w|$ (word length) steps?

I highly assume, that this problem is not decidable because in the worst case you have to test every word that exists (infinite) to realize, that the TM never holds. However this isn't a proof and I have to proofe this question (without the Rice's theorem).

My idea was to use the subroutine technique to "convert" the problem into the halt-problem, the $\epsilon$-halt-problem or the total halt problem. I have no idea on how to turn this problem into an existing one - could you help me here please?