Computational Complexity

Here, by introducing a version of “Unexpected hanging paradox” first we try to open a new way and a new explanation for paradoxes, similar to liar paradox. Also, we will show that we have a semantic situation which no syntactical logical system could support it. Finally, we propose a claim in Theory of Computation about the consistency of this Theory. One of the major claim is:Theory of Computation and Classical Logic leads us to a contradiction.

I argue that considerations about computational complexity show that all finite agents need characteristics like those that have been called epistemic virtues. The necessity of these virtues follows in part from the nonexistence of shortcuts, or efficient ways of finding shortcuts, to cognitively expensive routines. It follows that agents must possess the capacities – metavirtues –of developing in advance the cognitive virtues they will need when time and memory are at a premium.

Hilbert's ε-calculus is based on an extension of the language of predicate logic by a term-forming operator εx. Two fundamental results about the ε-calculus, the first and second epsilon theorem, play a rôle similar to that which the cut-elimination theorem plays in sequent calculus. In particular, Herbrand's Theorem is a consequence of the epsilon theorems. The paper investigates the epsilon theorems and the complexity of the elimination procedure underlying their proof, as well as the length of Herbrand disjunctions of existential (...) theorems obtained by this elimination procedure. (shrink)

Many cognitive scientists, having discovered that some computational-level characterization f of a cognitive capacity φ is intractable, invoke heuristics as algorithmic-level explanations of how cognizers compute f. We argue that such explanations are actually dysfunctional, and rebut five possible objections. We then propose computational-level theory revision as a principled and workable alternative.

We report a mathematical construction that is autological, universal and tautological. The autological property allows the derivation of the laws of physics from the construction, while the other two properties explain why the construction is universally and necessarily applicable to the world. The construction can explain the World at its most fundamental level up to and including the derivation of the familiar laws of physics. It is formulated as a statistical ensemble of feasible mathematics (an algorithmic information theory analog to (...) statistical physics) and its domain is the set of all analytical statements of logic ---here they take the role of the permissible facts of the world. The familiar laws of physics are emergent from the ensemble as entropic laws; this includes special relativity, general relativity, dark energy, the Schrödinger equation, the Dirac equation, quantum field theory, the speed of light as a maximal speed, and the space-time background. Furthermore, the construction provides tentative solutions in regard to the quantum measurement problem, the unification of physics and the arrow of time. In this context, the laws of physics are interpreted as the limits applicable to the feasible verification of the elements of the set of all analytical facts (they limit the actual facts of the world). The scope is universal (applies to the whole world), it is constructed tautologically (is irrefutable) and it is autological (allows the derivation of the laws of physics) ---thus, it is a tentative final theory. (shrink)

From algorithmic information theory (and using notions of algorithmic thermodynamics), we introduce *feasible mathematics* as distinct from *universal mathematics*. Feasible mathematics formalizes the intuition that theorems with very long proofs are unprovable within the context of limited computing resources. It is formalized by augmenting the standard construction of Omega with a conjugate-pair that suppresses programs with long runtimes. The domain of the new construction defines feasible mathematics.

Advancement in cognitive science depends, in part, on doing some occasional ‘theoretical housekeeping’. We highlight some conceptual confusions lurking in an important attempt at explaining the human capacity for rational or coherent thought: Thagard & Verbeurgt’s computational-level model of humans’ capacity for making reasonable and truth-conducive abductive inferences (1998; Thagard, 2000). Thagard & Verbeurgt’s model assumes that humans make such inferences by computing a coherence function (f_coh), which takes as input representation networks and their pair-wise constraints and gives as output (...) a partition into accepted (A) and rejected (R) elements that maximizes the weight of satisfied constraints. We argue that their proposal gives rise to at least three difficult problems. (shrink)