Ranging from Alan Turing’s seminal 1936 paper to the latest work on Kolmogorov complexity and linear logic, this comprehensive new work clarifies the relationship between computability on the one hand and constructivity on the other. The authors argue that even though constructivists have largely shed Brouwer’s solipsistic attitude to logic, there remain points of disagreement to this day. Focusing on the growing pains computability experienced as it was forced to address the demands of rapidly expanding applications, the content maps (...) the developments following Turing’s ground-breaking linkage of computation and the machine, the resulting birth of complexity theory, the innovations of Kolmogorov complexity and resolving the dissonances between proof theoretical semantics and canonical proof feasibility. Finally, it explores one of the most fundamental questions concerning the interface between constructivity and computability: whether the theory of recursive functions is needed for a rigorous development of constructive mathematics. This volume contributes to the unity of science by overcoming disunities rather than offering an overarching framework. It posits that computability’s adoption of a classical, ontological point of view kept these imperatives separated. In studying the relationship between the two, it is a vital step forward in overcoming the disagreements and misunderstandings which stand in the way of a unifying view of logic. (shrink)

The proofs of Kleene, Chaitin and Boolos for Gödel's First Incompleteness Theorem are studied from the perspectives of constructivity and the Rosser property. A proof of the incompleteness theorem has the Rosser property when the independence of the true but unprovable sentence can be shown by assuming only the (simple) consistency of the theory. It is known that Gödel's own proof for his incompleteness theorem does not have the Rosser property, and we show that neither do Kleene's or Boolos' (...) proofs. However, we show that a variant of Chaitin's proof can have the Rosser property. The proofs of Gödel, Rosser and Kleene are constructive in the sense that they explicitly construct, by algorithmic ways, the independent sentence(s) from the theory. We show that the proofs of Chaitin and Boolos are not constructive, and they prove only the mere existence of the independent sentences. (shrink)

This paper applies the 10-step neurocognitive model of Judgemental Philosophy, which explains the human judgment process, to propose a new theoretical explanation for the phenomenon of hallucination in Large Language Models (LLMs). The Judgemental Philosophy model includes the Constructivity and Coherence Verification (CC) stage and the Implicit/Explicit Resonance (R) stage in the process from sensory input to social normatization. The CC stage is primarily associated with Event-Related Potentials (ERPs) like N400 and P600, related to language processing and integration, and (...) the activity of some areas in the temporal and frontal lobes. The Resonance (R) stage is a whole-system state that forms the foundation of judgment possibility; Implicit Resonance is associated with P300 and brainwave phase synchronization, reflecting the simultaneous activation of widespread brain networks, while Explicit Resonance is associated with post-P300 activity and higher-order cognitive areas like the frontal cortex. This paper argues that LLMs largely possess the CC ability, which involves constructing linguistic structures and maintaining internal consistency based on learned data, but lack the whole-system 'resonance' state essential for the organic judgment process, especially the Explicit Resonance stage linked to conscious awareness. It is inferred that LLM hallucination occurs because, while having the ability to generate plausible and consistent content (CC), LLMs lack the process (R) of 'resonating' with the real world or existing knowledge systems to form the foundation of judgment possibility and verify the generated content. This provides insight into the fundamental differences between human judgment and AI and offers a new theoretical perspective for addressing the AI hallucination problem. (shrink)

Definitionally: _strongly effectively immune_ sets are infinite and their c.e. subsets have _maximums_ effectively bounded in their c.e. indices; whereas, for _effectively immune_ sets, their c.e. subsets’ _cardinalities_ are what’re effectively bounded. This definitional difference between these two kinds of sets is very nicely paralleled by the following difference between their _complements_. McLaughlin: _strongly_ effectively immune sets can_not_ have _immune complements_; whereas, the main theorem herein: _effectively_ immune sets can_not_ have _hyperimmune complements_. Ullian: _effectively_ immune sets _can_ have _effectively_ immune (...) complements. The main theorem _improves_ Arslanov’s, effectively hyperimmune sets can_not_ have _effectively_ hyperimmune complements: the _improvement_ omits the second ‘_effectively_’. Two _natural_ examples of _strongly effectively immune_ sets are presented with new cases of the first proved herein. The first is the set of minimal-Blum-size programs for the partial computable functions; the second, the set of Kolmogorov-random strings. A proved, _natural_ example is presented of an _effectively dense simple_, _not_ strongly effectively simple set; its complement is a set of maximal run-times. Further motivations for this study are presented. _Kleene_ recursion theorem proofs herein emphasize how to conceptualize them. Finally, is suggested, future, related work—illustrated by a first, _natural_, _strongly effectively_ $$\Sigma _2^0$$-_immune set_—included: solution of an open problem from Rogers’ book. (shrink)

We review and contrast three ways to make up a formal Euclidean geometry which one might call constructive, in a computational sense. The starting point is the first-order geometry created by Tarski.

This paper reinterprets and expands upon Judgemental Philosophy framework, particularly the concept of the Judgemental Triad (Constructivity, Coherence, Resonance). It centrally argues that Resonance is not merely a resultant characteristic or structural element of judgement, but a fundamental driving force that impels individuals to actively construct new meaning (Constructivity) and integrate it into more comprehensive systems of Coherence. From this perspective, the occurrence and resolution of the "r-cc gap" internally, along with the role of curiosity, are re-illuminated as (...) dynamic explorations toward new Constructivity and Coherence. The problem of distinguishing illusion from reality is also understood as a complex facet of this pursuit, where, as an aspect of Resonance failure, illusion can sometimes involve the subject's active choice of 'conscious compromise' or 'voluntary self-deception' in response to practical constraints or internal needs. Furthermore, this paper analyzes how the driving force of Resonance extends beyond the individual's internal world, through intersubjective relations (S9: Intersubjective Resonance), to co-construct social meaning and Coherence. Ultimately, this culminates in the formation of social norms (S10: Normative Codification & Transmission) as an expression of a collective, resonant desire to institutionalize the most comprehensive forms of Constructivity and Coherence. Finally, the paper considers the epistemological implications of this expanded discussion for questions concerning the ultimate foundation of our experienced reality, such as the "brain in a vat" hypothesis, contending that meaningful reality is a dynamic process constituted and sustained through the incessant interplay of multi-layered Constructivity, Coherence, and lived Resonance. (shrink)

This is a survey of Gödel's perennial preoccupations with the limits of finitism, its relations to constructivity, and the significance of his incompleteness theorems for Hilbert's program, using his published and unpublished articles and lectures as well as the correspondence between Bernays and Gödel on these matters. There is also an important subtext, namely the shadow of Hilbert that loomed over Gödel from the beginning to the end.

Book Review: Dubucs, J., & Bourdeau, M.. Constructivity and Computability in Historical and Philosophical Perspective. Springer Netherlands, XI. 214, pp. ISBN: 978-94-017-9216-5 978-94-017-9217-2, €83.29.

We analyze some extensions of Martin-Löf 's constructive type theory by means of extensional set constructors and we show that often the most natural requirements over them lead to classical logic or even to inconsistency.

This paper advocates for a revival of Leibniz’ mathesis universalis as proof theory together with his claim for theoria cum praxi under the conditions of modern foundational research of mathematics and computer science. After considering the development from Leibniz’ mathesis universalis to Turing computability (Chap. 1 ), current foundational research programs are analyzed. They connect proof theory with computational applications - proof mining with program extraction (Chap. 2 ), reverse mathematics with constructivity (Chap. 3 ) and intuitionistic type theory (...) with proof assistants (Chap. 4 ). The foundational program of univalent mathematics is inspired by the idea of a proof-checking software to guarantee correctness, trust and security in mathematics (Chap. 5 ). In the age of digitalization, correctness, security and trust in algorithms turn out to be general problems of computer technology with deep societal impact. They should be tackled by mathesis universalis as proof theory (Chap. 6 ). (shrink)

Constructibility and complexity play central roles in recent research in computer science, mathematics and physics. For example, scientists are investigating the complexity of computer programs, constructive proofs in mathematics and the randomness of physical processes. But there are different approaches to the explication of these concepts. This volume presents important research on the state of this discussion, especially as it refers to quantum mechanics. This `foundational debate' in computer science, mathematics and physics was already fully developed in 1930 in the (...) Vienna Circle. A special section is devoted to its real founder Hans Hahn, referring to his contribution to the history and philosophy of science. The documentation section presents articles on the early Philipp Frank and on the Vienna Circle in exile. Reviews cover important recent literature on logical empiricism and related topics. (shrink)

This chapter concerns the problem of the relation of classical mathematics to intuitionistic mathematics. This problem was far from having a precise answer in the late twenties and in fact Felix Kaufmann formulated a conjecture to the effect that classical mathematics without the axiom of choice was intuitionistically acceptable. Heinrich Behmann gave a “proof” of this claim that was, at the time, accepted by Carnap as sound. However, Gödel was able to show that the proof was wrong. While the proof (...) did not stand, the debate (which involved Kaufmann, Behmann, Carnap, Bernays, and Gödel) provides a rich picture of a crucial moment in the development of the foundations of mathematics and contains some small gems such as the topological analysis of proofs given by Behmann. (shrink)

Constructibility and complexity play central roles in recent research in computer science, mathematics and physics. For example, scientists are investigating the complexity of computer programs, constructive proofs in mathematics and the randomness of physical processes. But there are different approaches to the explication of these concepts. This volume presents important research on the state of this discussion, especially as it refers to quantum mechanics. This `foundational debate' in computer science, mathematics and physics was already fully developed in 1930 in the (...) Vienna Circle. A special section is devoted to its real founder Hans Hahn, referring to his contribution to the history and philosophy of science. The documentation section presents articles on the early Philipp Frank and on the Vienna Circle in exile. Reviews cover important recent literature on logical empiricism and related topics. (shrink)