# Doubt with the halting problem undecidable proof

The Halting problem proof can be seen as the following programs:

1. Ends(P, I) is a program that detects (returns true or false) if the program P will halt or not with the input I

2. Diag( P ): is a program that

2.1 Halts if P( P ) doesn't halt

2.2 Doesn't halt if P (P) halts

If we use (2) with input Diag it state:

1. Diag(Diag) halts if Diag(Diag) doesn't halt
2. Diag(Diag) doesn't halt if Diag(Diag) doesn't halt

Which by contradiction is proven that the program Ends can't exist.

Until here everything is fine. But What if instead of thinking on halt or never halt, we think in steps.

What if I do the following analogy:

1. Ends( P, I, S ) is a program that detects (returns true or false) if the program P with the input I, it will halt in less or equal S steps.

2. Diag( P, S) = Diag( P ): is a program that:

2.1 That halts in less or equal than S steps if Ends( P, P, S ) doesn't halts in less or equal than S steps.

2.2 That doesn't halts in less or equals than S steps if Ends( P, P, S ) halts in less or equal than S steps.

if we use (2):

1. Diag( Diag) halts in less or equal than S steps if Ends( Diag, Diag, S ) doesn't halt in less or equal than S steps.

2. Diag ( Diag ) doesn't halt in less or equals than S steps if Ends( Diag, Diag, S ) halt in less or equal than S steps.

Which is the almost the same contradiction, and in this case Ends is possible to build.

What I'm doing wrong?

The main problem with your analogy is the construction of Diag. The usual proof goes as follow:

1. Assume Ends exists.
2. Then we can construct Diag with a Turing machine calling Ends. As follows:

Diag(P) = If Ends(P,P) then Loop indefinitely Else Terminates.

What you are doing is the following:

1'. Construct Ends(P,I,S).

2'. Construct Diag(P,S).