Do Turing undecidability and computational complexity considerations (NP-hardness, etc...) have consequences for epistemology? If X function or propostion is undecidable or requires an intractable amount of resources to be calculated, is it still considered knowable?
asked Dec 3, 2015 at 22:03
-
A related question would be whether "knowability" is intrinsic to a function or proposition, or if it can only be stated with respect to a larger environment within which the knowing occurs. A related physical analogy might be a slip of paper with some words written on it covered by a piece of cardboard. One could say the words on the paper can be "knowable" because you can lift the cardboard. Now put the paper and cardboard into a large bonfire which you are several paces away from...– Cort AmmonDec 4, 2015 at 0:47
-
If it is reasonable to assume the paper will burn before you can find a way to rescue it, are the words on the paper "knowable?"– Cort AmmonDec 4, 2015 at 0:50
Add a comment
|
2 Answers
So far considerations based on computational resources are consequential only to a small group of philosophers known as radical anti-realists, who extend strict finitism to epistemology. Unlike constructivists and moderate anti-realists (intuitionists) like Dummett, who are usually satisfied with computability in principle radical anti-realists insist on more than that, "practical feasibility". In particular, they would reject the law of excluded middle even for computable predicates.
One of the suggestions for epistemic logic of radical anti-realism, given by Dubucs and Marion, is to use polynomial time computability as formalization of "practical feasibility", so presumably they would be sympathetic to the kind of concerns like NP-hardness of reducing higher level theories to lower level ones. For now at least, classical and even mainstream anti-realist epistemologies are satisfied with doing it "in principle".
See Vidal-Rosset's review, and Dubucs-Marion original paper.
I would say YES regarding the NP problem. See the Fundamental Theorem of Arithmetics. It is a theorem, so it is knowable as being true and demonstrable. However, if you can factorize a number in NP time then you're a god and you screwed the whole Internet.
Studying propositions as being a valid reasoning has nothing to do with the involved time or number of steps. The implications NP/NPC/NPH would have are similar to the implications of God's Machine trying to detect a collision: It is just an annoying matter of time, but not of reasoning validity.
Regarding the problem of undecidability, the emblematic problem here is the Halting Problem, and yes, it has epistemologic implications. Basically: There are some limits to your ability to prove something under your own system and, under a Turing-scheme system, such problem is expressed in terms of undecidable (or semi-decidable) problems like this.