f(n) defined as the smallest number such that all proveable statements with a length of n characters can be proved in f(n) characters or less, and f(n) = 0 if there are no proveable statements with length n.
So if f(30) = 500 that means "Every 30characterstatement has a 500(or less)characterproof or it cannot be proved at all"
I'm pretty sure this function exists for all whole number values of n. Although if we replace 'proveable' with 'true' then incompleteness may become an issue.
I think incompleteness also gives us this: there is no computable function g(n) such that we can know that g(n) > f(n) for all n
Interesting function
Moderators: gmalivuk, Moderators General, Prelates

 Posts: 139
 Joined: Tue Nov 07, 2006 6:36 pm UTC
 Location: Fremont, CA
 skeptical scientist
 closedminded spiritualist
 Posts: 6142
 Joined: Tue Nov 28, 2006 6:09 am UTC
 Location: San Francisco
In fact, there is no computable function g such that g(n)>f(n) for all n, even if we didn't know it (if there were, the set of provable statements would be computable, and that would give you a complete extension of PA).
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.
"With math, all things are possible." —Rebecca Watson
"With math, all things are possible." —Rebecca Watson
Who is online
Users browsing this forum: No registered users and 8 guests