For any algorithm PP such that will prove a string has complexity X (where complexity is the minimum amount of informational content necessary to specify it):
This algorithm is encoded by program OC, which iterates through every possible string until it finds one of complexity X>L. (L is at this point undefined.)
The program OC has complexity M. (This is the sneaky bit right here. You’ll see why in a moment.)
Any string output by OC has complexity M as an upper bound (being specified by program OC). Thus, L has an upper bound of M. Therefore, any algorithm PP cannot prove any string has a greater complexity than that necessary to specify the program OC which encapsulates it.
(This is a -very- rough approximation of the proof. Wikipedia’s is worse, at least in my view.)
Note that this doesn’t limit the complexity of any strings so much as the power of any algorithm PP and derivative program OC.
The proof works (roughly) like this:
For any algorithm PP such that will prove a string has complexity X (where complexity is the minimum amount of informational content necessary to specify it):
This algorithm is encoded by program OC, which iterates through every possible string until it finds one of complexity X>L. (L is at this point undefined.)
The program OC has complexity M. (This is the sneaky bit right here. You’ll see why in a moment.)
Any string output by OC has complexity M as an upper bound (being specified by program OC). Thus, L has an upper bound of M. Therefore, any algorithm PP cannot prove any string has a greater complexity than that necessary to specify the program OC which encapsulates it.
(This is a -very- rough approximation of the proof. Wikipedia’s is worse, at least in my view.)
Note that this doesn’t limit the complexity of any strings so much as the power of any algorithm PP and derivative program OC.