This is a valid method of deciding whether a program hangs. Another very simple approach is searching for global state recurrences (if your program goes back to exact same state at least once, and it is deterministic, then it never halts).
Note this has no bearing on the Halting problem though (famously proven impossible). You cannot decide whether an arbitrary very complicated program halts -- it may do all sorts of weird stuff that doesn't involve any of the previous behavior (having necessary subfunctions never terminate or global recurrence) -- it could try counting up to infinity until a certain complicated binary function of the number is true, then you have to decide the truthiness of this arbitrary function. In general you face a self-referential problem: imagine you try deciding whether a program of size N halts if it runs for too long. You'd need a program (say of size K) that produces a function f(N) of maximum running time for programs of size up to N -- then you could just check whether a program runs for more than f(N) steps. But by definition your program cannot run for more than f(K) steps, thus it cannot output a number greater than 2^(f(K)). Thus your program can only decide finitely many instances, and is not an algorithm (instead it is a sort of compressed look up table).
The proof of the Halting problem undecidability is more general, but uses similar self-referential arguments.
I like to think of it this way: an algorithm is really a compressor function. It compressed an infinite set of (input->output) relations into a finite program. But some infinite sets are inherently incompressible -- think a string of random numbers -- and in particular the set of all programs. Incompressible (actually finitely compressible) sets must exist because otherwise you would have infinitely many different sets that are output of finitely many programs, which is obviously impossible (this is the pigeonhole principle).
I like the idea behind your compression analogy, but it doesn't quite work. In particular, you assume the solution when saying that the set of all programs is incompressible. Indeed, there are programs which operate on the set of all programs, e.g. trivially "is the first bit of the program a 1".
I think you're correctly proving that non-computable functions exist (though the proof needs to mention countable vs uncountable infinities I think, based on a power set over the input/output set), but you still need some sort of self referential statement to prove the halting problem.
Oh yea my bad, I meant the set of all halting functions (which is (program->halts)) -- those are incompressible (again actually finitely compressible). The set of all programs can be trivially enumerated depending on the Turing machine (it's usually just a form of the set of binary natural numbers).
Note I did not prove incompressibility, only that there exist some incompressible functions; indeed there are as many functions as there are real numbers (in cardinality), so almost every function is incompressible! (imagine all different strings of random bits) For the halting function I believe the proof is a little involved and can be found on the book "Elements of Information Theory".
I find wikipedia's proof (https://en.wikipedia.org/wiki/Halting_problem#Proof_concept) not quite illuminating though, since it is a basic proof by contradiction. Those tend to leave you wondering if you cannot replace the halting function halt(x) with a self-reference-free function halt_noself(x). Compressibility give a wider intuition that sure, there are special subsets of the halting function (program->halts) that are compressible, but in general it will be incompressible, and therefore a program will only be able to decide finitely many sequential programs -- and this table can only be done by a "luck-based" search: you test the programs to see if they halt. The ones that do not halt in any reasonable amount of time, you may try searching the space of proofs that it doesn't halt. This search is again undecidable, because at some point there will be a program which doesn't halt but that you cannot prove.
So in some ways the best you can do is grow the list with holes such as "program 1 halts, program 2 does not halt (proof), ...., program k-1 halts, program k ???, program k+1 halts, ..." -- you may never be able to fill any particular hole. You can also build a set of heuristics to accelerate both the simulation of the programs (to show they halt) and the evaluation of proofs (to show they do not halt).
This is essentially the process by which we do mathematics, or even computer science :) We use a growing set of heuristics to prove statements we deem "interesting" or "useful", and sometimes simple statements will come up (such as Collatz conjecture, Goldbach's, Twin primes, Riemman hypothesis, ...) that we cannot prove and we do not know if we will ever be able to.
Note this has no bearing on the Halting problem though (famously proven impossible). You cannot decide whether an arbitrary very complicated program halts -- it may do all sorts of weird stuff that doesn't involve any of the previous behavior (having necessary subfunctions never terminate or global recurrence) -- it could try counting up to infinity until a certain complicated binary function of the number is true, then you have to decide the truthiness of this arbitrary function. In general you face a self-referential problem: imagine you try deciding whether a program of size N halts if it runs for too long. You'd need a program (say of size K) that produces a function f(N) of maximum running time for programs of size up to N -- then you could just check whether a program runs for more than f(N) steps. But by definition your program cannot run for more than f(K) steps, thus it cannot output a number greater than 2^(f(K)). Thus your program can only decide finitely many instances, and is not an algorithm (instead it is a sort of compressed look up table).
The proof of the Halting problem undecidability is more general, but uses similar self-referential arguments.
I like to think of it this way: an algorithm is really a compressor function. It compressed an infinite set of (input->output) relations into a finite program. But some infinite sets are inherently incompressible -- think a string of random numbers -- and in particular the set of all programs. Incompressible (actually finitely compressible) sets must exist because otherwise you would have infinitely many different sets that are output of finitely many programs, which is obviously impossible (this is the pigeonhole principle).