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

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 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.