The Halting problem proof can be seen as the following programs:
Ends(P, I) is a program that detects (returns true or false) if the program P will halt or not with the input I
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:
- Diag(Diag) halts if Diag(Diag) doesn't halt
- 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:
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.
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):
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.
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?