Hmm, perhaps i misinterpreted your message. I thought “N=BB(message_length(P))” was some code referring to the string length of my message, I’ll feel stupid if it wasn’t.
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.
Is there some fixed number of cases that is sufficient to establish conclusively an arbitrary proposition? Is there some fixed N that is large enough for any P?
I don’t think so. There are only O(k^N) strings of length N. It would be very strange if there were only finitely many true claims about the integers.
Here is a proposed proof sketch, by the way.
Suppose for contradiction that there were some N such that all true claims about natural numbers had proofs of length less than N. Necessarily, there is a least such N, call it N’, for which that’s true. Take P as some proposition with a proof of length N’. Take P2 as some other proposition. The proof of (P and P’) is going to have length longer than N’, since it has to include P as a subproof and at least one additional line for P and P’.
This violates our assumption, QED.
P and P’ doesn’t seem like a very interesting proposition, but I don’t know a way to formalize “interesting”. I think there are probably are only finitely many claims that a finite mathematical mind can possibly find interesting.
Pretty sure this can’t happen. We stipulated that we had the shortest proof for P. How did P and P’ get proved without proving P first? Or alternatively, without there being a shorter proof available for P without P’?
What if P = “The prime numbers are infinite or there are exactly 1337 of them” and P’ = “There are not exactly 1337 prime numbers.”
The shortest way to prove P involves proving (P and P’), which is the statement “The prime numbers are infinite.” It would take a roundabout argument indeed to exclude all finite cardinalities besides 1337, without also excluding 1337 and accidentally proving (P and P’).
I don’t have an example to hand. I just have a feeling that there might be some case where the shortest proof of (P and P’) is a component of the shortest proof of P, rather than the other way around.
Ha, I just got it. Pretty good, of course x<N holds for all numbers you try. But of course, there is a simple one line proof that ~P(N+1), so the inductive-conjecture with x<N certainly has a proof in the negative. This only applies to P where there is no proof of the existence of a counter example.
I understood (perhaps wrongly?) the original question to be “is there some fixed N that is sufficient regardless of P?” Did you mean instead “does there exist some P that has a finite sufficient N?”?
Wouldn’t a counterexample itself be proof of the existence of the counterexample?
If counterexamples are a subset of proofs of the existence of a counterexample, then:
(No counterexamples < N AND no simple proof of a counterexample) IMPLIES
(No counterexamples < N AND no counterexample) IMPLIES
(No counterexample)
But the absence of a counterexample is identical with the truth of the conjecture, which is what we were trying to prove. Once you are willing to look at N+1, by induction you are looking at all the positive integers, which takes forever.
Let P(x) be “x < N”.
Contrariwise, let N=BB(message_length(P)).
Aw ouch, why so cold? (though I admit quite clever.)
Cold?
Hmm, perhaps i misinterpreted your message. I thought “N=BB(message_length(P))” was some code referring to the string length of my message, I’ll feel stupid if it wasn’t.
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.
Could you elaborate on what question that is your answer to? Is that an answer to one of my questions? I might just be confused.
Is there some fixed number of cases that is sufficient to establish conclusively an arbitrary proposition? Is there some fixed N that is large enough for any P?
I don’t think so. There are only O(k^N) strings of length N. It would be very strange if there were only finitely many true claims about the integers.
Here is a proposed proof sketch, by the way. Suppose for contradiction that there were some N such that all true claims about natural numbers had proofs of length less than N. Necessarily, there is a least such N, call it N’, for which that’s true. Take P as some proposition with a proof of length N’. Take P2 as some other proposition. The proof of (P and P’) is going to have length longer than N’, since it has to include P as a subproof and at least one additional line for P and P’.
This violates our assumption, QED.
P and P’ doesn’t seem like a very interesting proposition, but I don’t know a way to formalize “interesting”. I think there are probably are only finitely many claims that a finite mathematical mind can possibly find interesting.
I don’t think this necessarily follows. Suppose the last few lines of the proof of P read something like:
Pretty sure this can’t happen. We stipulated that we had the shortest proof for P. How did P and P’ get proved without proving P first? Or alternatively, without there being a shorter proof available for P without P’?
What if P = “The prime numbers are infinite or there are exactly 1337 of them” and P’ = “There are not exactly 1337 prime numbers.”
The shortest way to prove P involves proving (P and P’), which is the statement “The prime numbers are infinite.” It would take a roundabout argument indeed to exclude all finite cardinalities besides 1337, without also excluding 1337 and accidentally proving (P and P’).
I don’t have an example to hand. I just have a feeling that there might be some case where the shortest proof of (P and P’) is a component of the shortest proof of P, rather than the other way around.
Ha, I just got it. Pretty good, of course x<N holds for all numbers you try. But of course, there is a simple one line proof that ~P(N+1), so the inductive-conjecture with x<N certainly has a proof in the negative. This only applies to P where there is no proof of the existence of a counter example.
I understood (perhaps wrongly?) the original question to be “is there some fixed N that is sufficient regardless of P?” Did you mean instead “does there exist some P that has a finite sufficient N?”?
Wouldn’t a counterexample itself be proof of the existence of the counterexample?
If counterexamples are a subset of proofs of the existence of a counterexample, then:
(No counterexamples < N AND no simple proof of a counterexample) IMPLIES
(No counterexamples < N AND no counterexample) IMPLIES
(No counterexample)
But the absence of a counterexample is identical with the truth of the conjecture, which is what we were trying to prove. Once you are willing to look at N+1, by induction you are looking at all the positive integers, which takes forever.