Do limitations on computability and computational resources have any consequences for epistemology?

Question

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?

Answer 1

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.

Answer 2

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.