4 ms·
The method of proof of P!=NP will undoubtedly tell us something deeply fundamental about computation and therefore logic and therefore philosophy. That complexi
by danharaj 8y ago
The method of proof of P!=NP will undoubtedly tell us something deeply fundamental about computation and therefore logic and therefore philosophy. That complexity theory is so difficult thus far is in itself philosophically interesting.
- goldenkey 8y agoSeems directly related to philosophy via the Busy Beaver[1] function. Every statement about all integers, ie. Goldbach's conjecture, can map to a predicate P(n). P(n) is either true for all integers or fails at a least n. This least n must be less than BB(program_size(P)). We can look at the predicates that don't fail, and take their negation also, ~P(n), which clearly does fail at n=1. These predicates are all P such that P(1) is true or ∄n P(n) is true. They take up a percentage of the space of all predicates (analog of Chaitin's constant[2]). Meaning that in the distribution of all possible predicates, a certain proportion are just (∞,1) and (1,∞) mappings, while the rest of the predicates have mappings bounded by their program size. It seems that because of the pigeonhole principle and the mappings already "wasted" on (1,∞) and (∞,1), the rest of our distribution gets restricted to bounded levels of expressive power. The literal allowance of statements that are false trivially, or true for everything, limits the power of all of the remaining statements that now have to position themselves as finitary AND confined by that proportionality. The universe is a very weird place. [1] https://en.wikipedia.org/wiki/Busy_beaver https://en.wikipedia.org/wiki/Busy_beaver [2] http://en.wikipedia.org/wiki/Chaitin%27s_constant http://en.wikipedia.org/wiki/Chaitin%27s_constant