That's a tad contrived... I was thinking more along the lines of whether such an estimate could be useful in any of the traditional applications stymied by the Halting Problem, such as showing the equivalence of two functions, anti-virus checking, model checking, running sandboxed functions, resource limits, peephole optimization, etc.
It's all the same, really. You can do all those things, but probabilistically, up to the probabilities allowed by how long you've run the program for. Unless and until the program halts, there will always be some chance that you were wrong about its nonhalting and it does actually halt. If it actually doesn't halt, your confidence that it doesn't will asymptotically approach 1.0 in the limit.
Can you motivate the construction any? I doubt it's as simple as 1/n timesteps because that would be too convenient, but what is it?
It's not 1/n timesteps, yeah. It's more along the lines of "Halting times for long-running programs turn out to be algorithmically non-random, which means we use this class of functions called incompressibility cut-off functions to bound the measure of halting times." Beyond that, I'd have to start and finish a couple of textbooks (at least an intro to topology and then Calude's own Information and Randomness) to explain more deeply.
It doesn't help that Calude tends to use different notation in his papers from the standard notations used for studying Kolmogorov complexity/AIT.
It's all the same, really.
Not really. 'You can bet on halting' is not a use. There is no website I can go to which has 24/7 gambling on randomly-generated lambda functions which I can use that code to clean up on; there is no lambda function e-sports league where competitors race to write or crack their rival's functions, etc. This could be said of any method for calculating probabilities of anything: 'you can bet on it!' That's not what I mean by use. What I meant are some of the applied tasks, but I'm not clear exactly on whether this probability appl...
Your job, should you choose to accept it, is to comment on this thread explaining the most awesome thing you've done this month. You may be as blatantly proud of yourself as you feel. You may unabashedly consider yourself the coolest freaking person ever because of that awesome thing you're dying to tell everyone about. This is the place to do just that.
Remember, however, that this isn't any kind of progress thread. Nor is it any kind of proposal thread. This thread is solely for people to talk about the awesome things they have done. Not "will do". Not "are working on". Have already done. This is to cultivate an environment of object level productivity rather than meta-productivity methods.
So, what's the coolest thing you've done this month?
(Previous Bragging Thread)