CS Paper Radar

Ontological free will as incompressible information adjunction: A noncomputability boundary beyond P versus NP

J{é}rome Clech

cs.LO ·submitted 2026-09-14 12:26 UTC · v1
theory

Abstract

We study a conditional model of ontological free will in which a pre-act state structures several coherent global continuations without intrinsically distinguishing one as the future actualisation. The topos-theoretic component is formalised by a choice sheaf and by the action of automorphisms preserving the pre-act data: the absence of a fixed point rules out any natural equivariant selection. An act changes an unpointed object into a pointed one and reduces its symmetry group to a stabiliser. Independently, a causal algorithmic incompressibility axiom imposes nearly maximal online description complexity on the actual choices. Uniformly observable post-act traces then allow their reconstruction. We prove a conditional transfer result: such traces must carry asymptotically all the singularisation information unavailable in the pre-act regime, and no uniform Turing predictor computes the choices from causal histories alone. The formalism proves neither that human beings satisfy the model nor a separation of P from NP; it identifies a boundary at which prediction concerns the existence of a computable function rather than its time complexity.

Closest papers

Nearest neighbours by meaning across the whole index.

Computational free will as global selection: from sheaf-theoretic gluing to a conditional separation of P and NP

cs.LO ·2026-08-31 ·Jerome Clech
unusual similarity 0.73
Abstract

We formalise computational free will by separating locally constrained admissibility from the selection of one global continuation. Global sections of a finite choice presheaf form an admissible set, GLUE; SELECT singles out the continuation realised at a pre-identified occurrence. A uniform trace relation certifies that continuation efficiently after the act, although it is assumed not to be uniformly anticipable in polynomial time from the prior occurrence input. Under explicit uniformity, balance, historical-completeness, and unique-projection assumptions, this trace defines a total FNP search relation with no deterministic polynomial-time selector. Thus existence of computational free will in the stated sense implies a separation between polynomially verifiable and polynomially solvable search, and hence that P differs from NP. The result is conditional and gives no unconditional class separation.

0.47

Substantive Agency and Computational Non-Anticipability: An Axiomatic Route to a Conditional Separation of P and N P

cs.LO ·2026-09-23 ·Jérome Clech
theory similarity 0.67
Abstract

This paper characterises substantive agency and identifies the additional bridges under which it has a standard complexity-theoretic consequence: conditionally, P __ = N P . The constitutive core separates coherent plurality, causal openness, anticipatory non-pointing, act-level singularisation, and endogenous sourcehood. Its temporal claim yields a two-sided modal result: exact passive pre-act selection is incompatible with jointly retaining singularising priority and invariance under causally inert informational extension. If every standard polynomial procedure is deployable in that passive form, the actualisation map $α$ has no polynomial-time selector. On an effective presentation, $α$ is therefore either computable outside FP or noncomputable. A separate certifiedactualisation protocol supplies polynomially bounded, polynomially verifiable traces with extensional unique projection. This is the constructive interface that turns historical actualisation into a total standard search relation; combined with the modal result, it places that relation in TFNP search \ FP search , from which a self-contained search argument yields P __ = N P . The result is a domain-relative conditional transfer theorem: it neither assumes polynomial non-anticipability in the definition of agency nor proves that human decision-making satisfies the bridge and certification premises.

0.20

Reconfigurable Action Theories: A Formal Foundation for Dynamically Composable Agent Harnesses

cs.AI ·2026-11-09 ·Jianmin Ji
similarity 0.60
Abstract

Action theories typically fix their vocabulary and causal laws, whereas agent harnesses can change their tools, providers, and policies during execution. We introduce Reconfigurable Action Theories (RAT), in which actions can change the action theory itself. A theory module in RAT contains a vocabulary, causal laws, and an initializer. A RAT configuration records the active modules and the world state. Module loading and unloading are represented by actions governed by ordinary causal laws. RAT retains the standard causal action semantics of its language fragment when the active module set is fixed. We give sufficient conditions for at most one next configuration, preservation of existing behavior when a module is added, and equal results when modules are loaded in either order. We establish the computational complexity of reasoning tasks in RAT and translate finite RAT systems into nonmonotonic causal theories and Answer Set Programming (ASP), preserving bounded executions. Experiments compare finite RAT models with executions of official DeepSeek Harness, Pi, and OpenHands implementations. RAT provides a formal basis for checking how component changes affect a harness's available actions, behavior, and reachable goals.

0.33

CIC + EM $\vdash$ Con(ZF): the consistency of ZF in type theory with excluded middle and no choice

cs.LO math.LO ·2026-09-19 ·Mario Carneiro
theorycode/data similarity 0.58
Abstract · 13 pages. Lean 4 formalization at https://github.com/digama0/ConZF

The sets-as-trees interpretation of set theory in a dependent type theory with an impredicative universe of propositions validates Zermelo set theory, and it validates Replacement if the type theory has a choice or description operator, which turns a functional relation into a function. It has been natural to expect that without such an operator the strength of the type theory drops well below that of $\mathrm{ZF}$. We show that it does not. In the type theory of Lean with two predicative universes, from excluded middle as the only assumption and with no axiom (no choice, no propositional extensionality, no quotients), we prove the consistency of $\mathrm{ZF}$, stated outright for a first-order proof system. The proof is formalized. The mechanism is the large elimination of the accessibility predicate over a type as large as the type of sets: a recursion on accessibility whose recursive calls are guarded by propositions, and whose later calls are indexed by the value of an earlier call, computes as a term any ordinal that is specified by a proposition through a well-founded tree of a certain shape. We give a rule that produces such a tree for every ordinal, unless some $V_ρ$ is already a model of $\mathrm{ZF}$; the rule does not choose a cofinal map into a limit ordinal but takes all definable ones at once. In the first case the sets-as-trees satisfy Replacement for arbitrary propositional relations. Either way $\mathrm{ZF}$ has a model. Finally, the double negation of excluded middle suffices, and what remains of it is exactly that membership is not not well-founded in the stable reading of sets; this in turn implies the double negation of Markov's principle.

0.46

Discrete Linear Ensemble Logic

cs.LO ·2026-08-11 ·Manfred Droste, Guo-Qiang Zhang
published similarity 0.57
Abstract

We study the discrete point-based fragment of Ensemble Logic $\EL(\Nat)$ over the natural numbers, a logic combining displacement $\varphi_u$, bounded metric modalities $\boldBox_t$ and $\mdiamond_t$ with additive bounds, Boolean connectives, and first-order quantification over $\Nat$. Motivated by the need for a unified symbolic layer for biomedical knowledge with temporal, spatial, genomic, and multimodal metric content, we develop the foundational discrete theory of the formalism. We give syntax and semantics, and prove a forward embedding of $\EL(\Nat)$ over a finite proposition set $\mathcal{P}$ into first-order monadic Presburger arithmetic $\FO(\Nat,<,+;\mathcal{P})$. This embedding yields the analytical upper bounds, while a reduction from nondeterministic two-counter machines with recurring control states proves that satisfiability is $Σ^1_1$-complete and validity is dually $Π^1_1$-complete. Expressively, $\EL(\Nat)$ strictly extends the star-free $ω$-languages and is incomparable with the $ω$-regular languages: it defines the non-$ω$-regular counting language $\{a^mb^mc^md^m\mid m\geq 1\}\cdotΣ^ω$, whereas a delimited parity language remains outside the logic by classical Presburger-arithmetic lower bounds. On the proof-theoretic side, we present a sound Hilbert system $\HEL$ and establish completeness relative to monadic Presburger validity as oracle, noting that completeness relative to plain Presburger arithmetic is impossible.

0.22

Co-Recursive Semantic Self-Extension: A Mathematical Foundation for Open-Ended Intelligence

cs.AI ·2026-10-22 ·Simon Hegelich, Bardh Prenkaj, Habiba Sarhan, Morteza Shahrezaye, Kolja Hegelich +2 more
similarity 0.57
Abstract

Artificial intelligence has advanced through scale, data, and computation, yet remains bounded by its representational framework. We ask what makes intelligence open-ended. Every inferential system selects meaningful distinctions, limiting what it can learn. Within a fixed purpose, performance reaches a ceiling set by its semantic domain. Teleological succession, in which purposes arise from earlier ones, faces a similar limit: Boolean-closed purpose-transformations exhaust their reachable semantic territory. We shift from purposes to inferential systems. Drawing on Kant and Gödel, we model cognitive states as partial evaluations over a formal language. Unresolved propositions may be undecided or undecidable. Reasoning can resolve the former but not the latter, leaving a frontier for extension. Non-trivial reductions of undecidable propositions expose undecidable intermediate premises whose reflective reification supports multiple decisive extensions. Finite trace-guided generation remains fallible, requiring meta-level selection and polycontextural exploration. Using Kolmogorov complexity, we show that no architecture with a fixed state description, transition mechanism, and initial condition can generate histories incorporating irreducible algorithmic information. Because physical systems are fixed in this sense, we examine collectives. Coupling finitely many finite agents does not remove the bound. Extension requires persistent external memory preserving semantic content and historical coordinates. Collective generative capacity depends on balancing overlap for transfer with difference for generation. We propose semantic self-extension as a design principle: intelligence should not merely resolve ambiguity within existing meanings, but transform unresolved structures into new spaces of meaning, generating new distinctions, questions, representations, and purposes.

0.51

Positive Topology and Feasible Refinement: Forcing Matrices, Positivity, and Information

cs.LO cs.AI ·2026-09-11 ·Mirco A. Mannucci, Giovanni Sambin
similarity 0.57
Abstract · 16 pages

We develop a conceptual and operational account of Positive Topology starting from a basic relation between points or models and observable properties. From this relation, two complementary structures emerge. The first captures universal refinement and cover: what must hold across all relevant cases and how information can be systematically refined. The second captures positivity and witnessed existence: what can be positively realized and sustained without relying on classical complements. A central result shows that the underlying relation between points and observables can be reconstructed from either of these induced structures. We also clarify the distinction between point-based and pointfree formulations: when points are available, positivity can be derived from the underlying forcing relation, while in the formal pointfree setting positivity is taken as primitive and its compatibility with cover is imposed axiomatically. We develop two complementary interpretations of the framework. The first is information-theoretic, viewing cover as refinement of partial information and positivity as witnessed feasibility. The second is game-theoretic, viewing positivity as the ability of a witness or hypothesis to survive successive legitimate refinements. The final part of the paper is deliberately programmatic. We outline how resource constraints, verification costs, and finite budgets can be incorporated into the framework. This leads to resource-sensitive notions of forcing, cover, positivity, and refinement, and raises new questions about how these structures behave as available resources change. Examples from medical diagnosis, legal reasoning, and AI systems illustrate the potential relevance of the approach to grounded, explainable, and resource-aware inference.

0.33

Two-Variable Logic with Arbitrarily Many Successor Relations

cs.LO ·2026-10-07 ·Jakub Michaliszyn, Piotr Witkowski
theory similarity 0.56
Abstract

We study two-variable first-order logic with a finite, input-dependent number of distinguished successor relations and arbitrary additional unary and binary predicates. Each distinguished relation must be the exact immediate-successor relation of some linear order on the common domain; the orders themselves are not available in the language and may have arbitrary order types. We prove that satisfiability belongs to 2NEXPTIME, uniformly in the number of successors. The proof gives finite certificates for possibly infinite models. A closure operation separates local neighbourhood descriptions, called star types, into those of bounded multiplicity and those that can be realized infinitely often. The bounded part is represented explicitly. Outside it, integer height vectors allow overlapping successor requirements to be matched without creating cycles or unintended identifications. Ordering the resulting path components densely then recovers exact successor relations. Consistent assignments of the additional binary predicates handle witnesses involving the bounded part. The same certificates decide infinite satisfiability in 2NEXPTIME and give a doubly exponential threshold above which a finite model guarantees an infinite model. A doubly exponentially large finite core can be forced with only two successors and unary predicates. For finite models, we prove that satisfiability subject to a bound on the total number of reference adjacencies lost by the other orders is NEXPTIME-complete, even when the budget is encoded in binary and the number of successors is part of the input.

0.50