And before I could scribble a damned thing, Calude went and solved it six months ago. The Halting Problem, I mean.
Cool. If I get the meaning of the result well, it’s that if you run a random program for some number of steps and it doesn’t halt, then (depending on the exact numbers) it will be unlikely to halt when run on a supercomputer either, because halting times have low density. So almost all programs halt quickly or run a really really long time. Is this correct? This doesn’t quite let you approximate Chaitin’s omega, but it’s interesting that you can approximate a bounded variant of Chaitin’s omega (like what percentage of Turing machines halt when run for 10^50 steps). I can see how this would let you solve the halting problem well enough when you live in a bounded universe.
Cool. If I get the meaning of the result well, it’s that if you run a random program for some number of steps and it doesn’t halt, then (depending on the exact numbers) it will be unlikely to halt when run on a supercomputer either, because halting times have low density. So almost all programs halt quickly or run a really really long time. Is this correct?
Yep. Or, to put it a little tiny bit more accurately, you get a halting probability for your particular Turing machine, conditioned on the number of steps for which you’ve run it.
This doesn’t quite let you approximate Chaitin’s omega
Well technically, you can approximate Chaitin’s omega from below just as Chaitin himself describes in his book. You’ll just only be able to calculate finitely many digits.
I can see how this would let you solve the halting problem well enough when you live in a bounded universe.
Which we do ;-). You could run until you get past a desired threshold of probability (hypothesis testing), or you could use a bounded-rationality approach to vary your surety of nonhalting with your available processing power.
But overall, it gives you a way to “reason around” the Halting Problem, which, when we apply it to the various paradoxes of self-reference… you can see where I’m going with this.
Cool. If I get the meaning of the result well, it’s that if you run a random program for some number of steps and it doesn’t halt, then (depending on the exact numbers) it will be unlikely to halt when run on a supercomputer either, because halting times have low density. So almost all programs halt quickly or run a really really long time. Is this correct? This doesn’t quite let you approximate Chaitin’s omega, but it’s interesting that you can approximate a bounded variant of Chaitin’s omega (like what percentage of Turing machines halt when run for 10^50 steps). I can see how this would let you solve the halting problem well enough when you live in a bounded universe.
Yep. Or, to put it a little tiny bit more accurately, you get a halting probability for your particular Turing machine, conditioned on the number of steps for which you’ve run it.
Well technically, you can approximate Chaitin’s omega from below just as Chaitin himself describes in his book. You’ll just only be able to calculate finitely many digits.
Which we do ;-). You could run until you get past a desired threshold of probability (hypothesis testing), or you could use a bounded-rationality approach to vary your surety of nonhalting with your available processing power.
But overall, it gives you a way to “reason around” the Halting Problem, which, when we apply it to the various paradoxes of self-reference… you can see where I’m going with this.