On reflection, I’m not sure the formula is quite right, but...
message_length(P) is the size in bits of the shortest possible computer program that evaluates the property P.
BB is the busy beaver function, which gives the largest number that can be output by any program of a given length.
The general idea is that, given a formal notion of the complexity of the predicate, you can place a hard upper bound on which numbers it can ‘reach’. I don’t think the actual formula I gave was correct, but I don’t see how to fix it at the moment.
Ahh, yea good solution. I remember reading about this on wolfram mathworld, look it up there. If you don’t find it exactly it’ll be in a citation.
As I understand things though it isn’t a reasonable solution because the turing machine would have to have more states than the natural universe allows to actually find the answer for many non-halting problems.
On reflection, I’m not sure the formula is quite right, but...
message_length(P) is the size in bits of the shortest possible computer program that evaluates the property P.
BB is the busy beaver function, which gives the largest number that can be output by any program of a given length.
The general idea is that, given a formal notion of the complexity of the predicate, you can place a hard upper bound on which numbers it can ‘reach’. I don’t think the actual formula I gave was correct, but I don’t see how to fix it at the moment.
Ahh, yea good solution. I remember reading about this on wolfram mathworld, look it up there. If you don’t find it exactly it’ll be in a citation.
As I understand things though it isn’t a reasonable solution because the turing machine would have to have more states than the natural universe allows to actually find the answer for many non-halting problems.