Search

The Schrodinger’s cat paradox has troubled physicists for many years and many ways to solve it has been provided so far. In this paper I will try to provide a different method of solving the Paradox with the help of logical machine and it will look like a hybrid of Wigner’s no-go theorem and the machine of Godel in his Incompleteness Theorems. And due to the machine the paradox will not require any human intervention to measure the state of the cat, whether it is alive or dead, while the measurement will be made by humans with regard to the statement given out by the machine.

We take a magical tour in algebraic logic, which is the natural interface between universal algebra and mathematical logic, starting from classical results on neat embeddings due to Andreḱa, Henkin, Nemeti, Monk and Tarski, all the way to recent novel results in algebraic logic using so-called rainbow constructions. Highlighting the connections with graph theory, model theory, and finite combinatorics, this article aspires to present topics of broad interest in a way that is hopefully accessible to a large audience. Other topics dealt with include the interaction of algebraic and modal logic, the so-called (central still active) finitizability problem, Godels’s incompleteness Theorem in guarded fragments, counting the number of subvarieties of $$\textsf {RCA}_{\omega }$$ which is reminiscent of Shelah’s classification theory and the interaction of algebraic logic and descriptive set theory as means to approach Vaught’s conjecture in model theory. The paper has a survey character but it contains new results and new approaches to old ones (such as the interaction of algebraic logic and descriptive set theory).

We present an abstract development of Gödel’s incompleteness theorems, performed with the help of the Isabelle/HOL proof assistant. We analyze sufficient conditions for the applicability of our theorems to a partially specified logic. In addition to the usual benefits of generality, our abstract perspective enables a comparison between alternative approaches from the literature. These include Rosser’s variation of the first theorem, Jeroslow’s variation of the second theorem, and the Świerczkowski–Paulson semantics-based approach. As part of the validation of our framework, we upgrade Paulson’s Isabelle proof to produce a mechanization of the second theorem that does not assume soundness in the standard model, and in fact does not rely on any notion of model or semantic interpretation.

© 2019 Elsevier B.V. Intensional computations are those that query the internal structure of their arguments. In a higher-order setting, such queries perform program analysis. This is beyond the expressive power of traditional term rewriting systems, such as lambda-calculus or combinatory logic, as they are extensional. In such settings it has been necessary to encode or quote the program before analysis. However, there are intensional calculi, specifically confluent term rewriting systems, that can analyse higher-order programs within the calculus proper, without quotation; there are even programs that produce the Goedel numbers of their program argument. This paper summarizes the current situation. Highlights include the following observations. We have known since 2011 that the simplest intensional calculus, SF-calculus, supports arbitrary queries of closed normal forms, including equality, pattern-matching, searching and self-interpretation. Recent work, verified using the Coq proof assistant, has shown that all recursive programs can be represented as closed normal forms in SF-calculus, and even in combinatory logic. Thus, we can here deduce that SF-calculus (but not combinatory logic) can define queries of programs. These results are compatible with direct support for lambda-abstraction. Although these results conflict with the traditional understanding of expressive power of combinatory logic and λ-calculus, as developed by Church and Kleene, our recent publication has shown that their approach is compromised by its reliance on encodings. To drive the point home, this paper uses a non-standard encoding to lambda-define a trivial solution of the Halting Problem.

The article compares two different approaches of incorporating probability into coalition logics. One is based on the semantics of games with stochastic transitions and the other on games with the stochastic failures. The work gives an example of a non-trivial property of coalition power for the first approach and a complete axiomatization for the second approach. It turns out that the logical properties of the coalition power modality under the second approach depend on whether the modal language allows the empty coalition. The main technical results for the games with stochastic failures are a strong completeness theorem for the logical system without the empty coalition and an incompleteness theorem which shows that there is no strongly complete logical system in the language with the empty coalition.

The chapter starts with an overview of information theory, how information is measured and how it is encoded in messages and transmitted. The ambiguity of coding with numeric alphabets is exposed with an analogy from computer science. An unambiguous coding is shown with reference to Godel’s incompleteness theorem.

This chapter is about the ontology and epistemology of mathematical objects. The core problem for an empiricist is that conceiving mathematical objects as existing independently of human thinking makes it impossible to understand how we can have mathematical knowledge, while the alternative, a constructivist conception, resolves the epistemological problem, but entails the identification of truth with provability. That entails that the law of excluded middle must be dismissed as a generally valid logical principle. The identificaiton of truth with provability is furthermore problematic when taking into account Godel’s first incompleteness theorem. The chapter ends with suggesting a modified constructivism, which keeps the distinction between truth and provability, thus avoiding counter arguments based on Godel’s theorem.

In the mid-1970s, Gregory Chaitin proved a novel incompleteness theorem, formulated in terms of Kolmogorov complexity, a measure of complexity that features prominently in algorithmic information theory. Chaitin further claimed that his theorem provides insight into both the source and scope of incompleteness, a claim that has been subject to much criticism. In this article, I consider a new strategy for vindicating Chaitin’s claims, one informed by recent work of Bienvenu, Romashchenko, Shen, Taveneaux, and Vermeeren that extends and refines Chaitin’s incompleteness theorem. As I argue, this strategy, though more promising than previous attempts, fails to vindicate Chaitin’s claims. Lastly, I will suggest an alternative interpretation of Chaitin’s theorem, according to which the theorem indicates a trade-off that comes from working with a sufficiently strong definition of randomness—namely, that we lose the ability to certify randomness.

This paper presents a theoretical approach to complexity engineering by considering the complex thinking framework proposed by Edgar Morin. The main foundations of this approach are an open system design, emergence, randomness inclusion, and Gödel incompleteness, which are contextualized using real-word instructive problems. Considering these concepts, several conjectures related to engineering activity and engineering education are presented taking several Brazilian catastrophes as counterexamples.

The mathematical foundations of machine learning play a key role in the development of the field. They improve our understanding and provide tools for designing new learning paradigms. The advantages of mathematics, however, sometimes come with a cost. Godel and Cohen showed, in a nutshell, that not everything is provable. Here we show that machine learning shares this fate. We describe simple scenarios where learnability cannot be proved nor refuted using the standard axioms of mathematics. Our proof is based on the fact the continuum hypothesis cannot be proved nor refuted. We show that, in some cases, a solution to the ‘estimating the maximum’ problem is equivalent to the continuum hypothesis. The main idea is to prove an equivalence between learnability and compression. Not all mathematical questions can be resolved, according to Godel’s famous incompleteness theorems. It turns out that machine learning can be vulnerable to undecidability too, as is illustrated with an example problem where learnability cannot be proved nor refuted.

Incompleteness theorems of Gödel, Turing, Chaitin, and Algorithmic Information Theory have profound epistemological implications. Incompleteness limits the ability of evolutionary processes to find optimal solutions.

In this article I am going to argue for the possibility of a transcendental source of logic based on a phenomenologically motivated approach. My aim will be essentially carried out in two succeeding steps of reduction: the first one will be the indication of existence of an inherent temporal factor conditioning formal predicative discourse and the second one, based on a supplementary reduction of objective temporality, will be a recourse to a time-constituting origin which has to be assumed as a non-temporal, transcendental subjectivity and for that reason as possibly the ultimate transcendental root of pure logic. In the development of the argumentation and taking into account W.V. Quine’s views in his well-known Word and Object, a special emphasis will be given to the fundamentally temporal character of universal and existential predicative forms, to their status in logical theories in general, and to their underlying role in generating an inherently non-finitistic character reflected, for instance, in the undecidability of certain infinity statements in formal mathematical theories. This is shown also to concern metatheorems of such vital importance as Godel’s incompleteness theorems in mathematical foundations. Moreover in the course of the discussion the quest for the ultimate limits of predication will lead to the notions of separation and intentional correlation between an ‘observing’ subject and the object of ‘observation’ as well as to the notion of syntactical individuals taken as the irreducible non-analytic nuclei-forms within analytical discourse.

Motivated by the problem of finding finite versions of classical incompleteness theorems, we present some conjectures that go beyondNP≠coNP. These conjectures formally connect computational complexity with the difficulty of proving some sentences, which means that high computational complexity of a problem associated with a sentence implies that the sentence is not provable in a weak theory, or requires a long proof. Another reason for putting forward these conjectures is that some results in proof complexity seem to be special cases of such general statements and we want to formalize and fully understand these statements. Roughly speaking, we are trying to connect syntactic complexity, by which we mean the complexity of sentences and strengths of the theories in which they are provable, with the semantic concept of complexity of the computational problems represented by these sentences.We have introduced the most fundamental conjectures in our earlier works [27, 33–35]. Our aim in this article is to present them in a more systematic way, along with several new conjectures, and prove new connections between them and some other statements studied before.

Coq is built around a well-delimited kernel that perfoms typechecking for definitions in a variant of the Calculus of Inductive Constructions (CIC). Although the metatheory of CIC is very stable and reliable, the correctness of its implementation in Coq is less clear. Indeed, implementing an efficient type checker for CIC is a rather complex task, and many parts of the code rely on implicit invariants which can easily be broken by further evolution of the code. Therefore, on average, one critical bug has been found every year in Coq. This paper presents the first implementation of a type checker for the kernel of Coq (without the module system and template polymorphism), which is proven correct in Coq with respect to its formal specification and axiomatisation of part of its metatheory. Note that because of Gödel's incompleteness theorem, there is no hope to prove completely the correctness of the specification of Coq inside Coq (in particular strong normalisation or canonicity), but it is possible to prove the correctness of the implementation assuming the correctness of the specification, thus moving from a trusted code base (TCB) to a trusted theory base (TTB) paradigm. Our work is based on the MetaCoq project which provides metaprogramming facilities to work with terms and declarations at the level of this kernel. Our type checker is based on the specification of the typing relation of the Polymorphic, Cumulative Calculus of Inductive Constructions (PCUIC) at the basis of Coq and the verification of a relatively efficient and sound type-checker for it. In addition to the kernel implementation, an essential feature of Coq is the so-called extraction: the production of executable code in functional languages from Coq definitions. We present a verified version of this subtle type-and-proof erasure step, therefore enabling the verified extraction of a safe type-checker for Coq.

A practical viewpoint links reality, representation, and language to calculation by the concept of Turing (1936) machine being the mathematical model of our computers. After the Godel incompleteness theorems (1931) or the insolvability of the so-called halting problem (Turing 1936; Church 1936) as to a classical machine of Turing, one of the simplest hypotheses is completeness to be suggested for two ones. That is consistent with the provability of completeness by means of two independent Peano arithmetics discussed in Section I. Many modifications of Turing machines cum quantum ones are researched in Section II for the Halting problem and completeness, and the model of two independent Turing machines seems to generalize them. Then, that pair can be postulated as the formal definition of reality therefore being complete unlike any of them standalone, remaining incomplete without its complementary counterpart. Representation is formal defined as a one-to-one mapping between the two Turing machines, and the set of all those mappings can be considered as “language” therefore including metaphors as mappings different than representation. Section III investigates that formal relation of “reality”, “representation”, and “language” modeled by (at least two) Turing machines. The independence of (two) Turing machines is interpreted by means of game theory and especially of the Nash equilibrium in Section IV. Choice and information as the quantity of choices are involved. That approach seems to be equivalent to that based on set theory and the concept of actual infinity in mathematics and allowing of practical implementations.

The key ingredient for Gӧdel’s Incompleteness Theorems is the so-called Gӧdelisation process which allows us to code terms, formulae and even proofs within PA.

This short and informal article shows that, although Godel's theorem is valid using classical logic, there exists some four-valued logical system that is able to prove that arithmetic is both sound and complete. This article also describes a four-valued Prolog in some informal, brief and intuitive manner.

International audience; For several years, we have worked on the usage of theorem proving techniques to validate Multi-Agent Systems. In this article, we present a preliminary case study, that is part of larger work whose long-term goal is to determine how proof tools can be used to help to develop error-free Multi-Agent Systems. This article describes how an error caused by a synchronisation problem between several agents can be identied by a proof failure. We also show that analysing proof failures can help to nd bugs that may occur only in a very particular context, which makes it dicult to analyse by standard debugging techniques. 1 Introduction This article takes place in the general context of the validation of Multi-Agents Systems, and more specically in the tuning stage. Indeed, for several years now, we have worked on the validation of MAS thanks to proof techniques. This is why the designed the GDT4MAS model (Mermet and Simon, 2009) has been designed, which provides both formal tools to speciy Multi-Agent Systems and a proof system that generates automatically , from a formal specication, a set of Proof Obligations that must be proven to guarantee the correctness of the system. In the same time, we have begun to study how to answer to the following question: What happens if the theorem prover does not manage to carry out the proof ?. More precisely, is it possible to learn anything from this failures (that we call in the sequel proof failures), in order to de-bug the MAS ? Answering to this question in a general context is tricky. Indeed, a rst remark is that a proof failure may occur in three dierent cases: • rst case: a true theorem is not provable (Gödel Incompleteness Theorem). Indeed, theorems generated by GDT4MAS are rst-order logic formulae, with arithmetic, which is typically the contexy where Gödel has established that there are non provable true theorems; • second case: a true theorem can not be automatically proven by the prover because rst-ordre logic is semidecidable. It means that there is not any automatic strategy that can prove all probable theorems. An ad hoc strategy must be provided by an expert. • third case: an error in the MAS specication has led to generate a false theorem that, hence, cannot be proven. So, when a proof failure is considered, the rst problem is to determine the case it corresponds to. It would be rather long and o-topic to give complete explanations here. However, it is important to knwow that the proof system has been designed to generate theorems that have good chances to be proven by standard strategies of provers, without requiring the expertise of a human. Moreover, unprovable true theorems generally do not correspond to real cases. Thus, in most cases, a proof failure will correspond to a mistake in the specication, and this is the context that is considered in the sequel. The subject of our study is then the following: if some generated proof obligations are note proven automatically, can we learn from that in order to help to correct the specication of the MAS ? So, the main idea is to check wether proof failures can be used to detect, even correct bugs in the specication of the MAS. Indeed, contrary to what is presented in (Das-tani and Meyer, 2010), where authors consider

Powers of recursion are often adduced for ‘recombinant innovation’. The onset of the digital economy, based on operations on discretely encoded information, has renewed interest in this. Digital computing has a provenance with the John von Neumann dynamical systems theory based on complex biological systems. How can digital agents innovate? The Godel-Turing-Post (GTP) logic is shown to be necessary to generate innovation based structure changing Type 4 dynamics of the Wolfram-Chomsky schema. GTP logic specifies the only known syntactic procedures that allow digital agents to initiate protean behaviours that mark exit strategies from known listable sets of digital technologies to produce novelty and surprises. The first is metaanalyses or offline simulations. The second is a fixed point which entails a two place encoding of negation or opposition, typically referred to as the Godel sentence. It is postulated that in phenomena ranging from the genome to human proteanism, the Godel sentence is a ubiquitous syntactic construction without which escape from hostile agents qua the Liar is not possible and digital agents become entrained within fixed repertoires. The only recursive best response function of a two person adversarial game that can implement strategic innovation in a lock-step formation of an arms race is the productive function of the Emil Post (1944) set theoretic proof of the Godel incompleteness result. This also overturns the customary view of game theorists that surprise and innovation cannot be a Nash equilibrium of a game.

© 2016 The Author(s) Lambda-SF-calculus can represent programs as closed normal forms. In turn, all closed normal forms are data structures, in the sense that their internal structure is accessible through queries defined in the calculus, even to the point of constructing the Goedel number of a program. Thus, program analysis and optimisation can be performed entirely within the calculus, without requiring any meta-level process of quotation to produce a data structure. Lambda-SF-calculus is a confluent, applicative rewriting system derived from lambda-calculus, and the combinatory SF-calculus. Its superior expressive power relative to lambda-calculus is demonstrated by the ability to decide if two programs are syntactically equal, or to determine if a program uses its input. Indeed, there is no homomorphism of applicative rewriting systems from lambda-SF-calculus to lambda-calculus. Program analysis and optimisation can be illustrated by considering the conversion of a programs to combinators. Traditionally, a program p is interpreted using fixpoint constructions that do not have normal forms, but combinatory techniques can be used to block reduction until the program arguments are given. That is, p is interpreted by a closed normal form M. Then factorisation (by F) adapts the traditional account of lambda-abstraction in combinatory logic to convert M to a combinator N that is equivalent to M in the following two senses. First, N is extensionally equivalent to M where extensional equivalence is defined in terms of eta-reduction. Second, the conversion is an intensional equivalence in that it does not lose any information, and so can be reversed by another definable conversion. Further, the standard optimisations of the conversion process are all definable within lambda-SF-calculus, even those involving free variable analysis. Proofs of all theorems in the paper have been verified using the Coq theorem prover.

© 2018, Springer Nature Switzerland AG. In this paper we consider well-known MU puzzle from Goedel, Escher, Bach: An Eternal Golden Braid book by D. Hofstadter, as an infinite state safety verification problem for string rewriting systems. We demonstrate fully automated solution using finite countermodels method (FCM). We highlight advantages of FCM method and compare it with alternatives methods using regular invariants.

The nonuniversality in computation theorem NCT states that no computer capable of a finite and fixed number of basic operations per time unit can be universal. This result, obtained in 2005, disproves major prevailing dogmas in computer science, on the strength of several counterexamples that differ significantly from one another. Thus, the NCT shows that the Church–Turing thesis CTT is false: It is not true that the Turing Machine can execute any computation possible on any other computer. It also disproves the inflated CTT, whereby there exists a universal computer, that is, a physical device capable of carrying out any computation conceivable. At the heart of the NCT is a refutation of the simulation principle, which states that any computation possible on a general-purpose computer can be simulated, more or less efficiently, on any other general-purpose computer . While more than 10 years have now elapsed since the NCT was established, the result is still widely misunderstood. This state of affairs is due to a number of misconceptions about the nature of the counterexamples and the significance of the NCT. The purpose of this paper is to dispel these misconceptions and convey the simple, yet important idea that universality in computation cannot be achieved, except by a computer capable, each time unit, of an infinite number of basic operations executed in parallel.

Open ended evolution seeks computational structures whereby creation of unbounded diversity and novelty are possible. However, research has run into a problem known as the “novelty plateau” where further creation of novelty is not observed. Using standard algorithmic information theory and Chaitin’s Incompleteness Theorem, we prove no algorithm can detect unlimited novelty. Therefore observation of unbounded novelty in computer evolutionary programs is nonalgorithmic and, in this sense, unknowable.

We begin this chapter from the consideration the basic properties that determine the system: integrity, internal and external attributive features that determine the system, that is, distinguishing precisely this system from all others, in the language of algebraic formalization. Then the integrity property is generalized to the case of P-integrity and P-internal and P-external attributive characteristics of the system, allowing to classify the properties of the system according to their various components. The notions of a quasi-stable system with respect to the property P and the innovation system with respect to the property P are introduced. While constructing the algebraic formalization of smart systems, we shall take into account the Godel incompleteness theorem, the essence of which is that it is impossible to describe the system by using the means of this system only. As well a hierarchy of different levels links of the system is constructed. A theorem on the description of the system’s links is proved. In addition, on the base of the theory of binary relations constructed by A. I. Mal’tsev, a classification of the binary relations of a system of each finite level is upbuild. The obtained results are applied to construct smart system’s axiomatic and to models describing the system’s synergistic effects and the processes of system’s decomposition and synthesis.

This paper presents a new perspective on the Lucas-Penrose arguments, which attempt to connect Godel’s incompleteness theorems to the thesis of mechanism in the philosophy of mind. I begin by taking a close look at Hilary Putnam’s own response to Lucas-Penrose, which is widely taken to be decisive. I shall largely concur, but there is more to be learned. I will suggest that certain non-monotonic models of mathematical reasoning significantly alter the philosophical context for these arguments. I go on to describe a structural constraint on the rational coherence of the alternative cognitive evolutions allowed by these models. In the presence of that constraint, it is shown that if the evolutions allowed by such a model are mediated by an effective rule of revision, then the model is incapable of capturing certain inductive inferences of the most elementary kind.

By the modern form of Godel’s First Incompleteness Theorem, we know that there are sentences (in the language of ZFC) that are neither provable nor refutable from the usual ZFC axioms for mathematics (assuming, as is generally believed, that ZFC is free of contradiction). Yet it is clear that the usual examples are radically different from normal mathematical statements in several glaring ways such as the mathematically remote subject matter and the essential involvement of uncharacteristically intangible objects. Starting in 1967, we embarked on the Concrete Mathematical Incompleteness program with the principal aim of developing readily accessible thematic mathematical research areas with familiar mathematical subject matter replete with examples of such incompleteness involving only characteristically tangible objects. The many examples developed over the years represent Concrete Mathematical Incompleteness ranging from weak fragments of finite set theory through ZFC and beyond. The program has reached a mature stage with the development of Emulation Theory. Emulation Theory, in its present basic developed form, involves finite length tuples of rational numbers. Only the usual ordering of rationals is used, and there is no use of even addition or multiplication. The basics are fully accessible to early undergraduate mathematics majors and gifted high school mathematics students, who will be able to engage with some simple nontrivial examples in two and three dimensions, with illustrations. In this paper, we develop the positive side of the theory, using various levels of set theory for systematic development. Some of these levels lie beyond ZFC and include familiar large cardinal hypotheses. The necessity of the various levels of set theory will be established in a forthcoming book (Concrete Mathematical Incompleteness in preparation).

Since their inception, the Perspectives in Logic and Lecture Notes in Logic series have published seminal works by leading logicians. Many of the original books in the series have been unavailable for years, but they are now in print once again. This volume, the eleventh publication in the Lecture Notes in Logic series, collects the proceedings of the Annual European Summer Meeting of the Association for Symbolic Logic, held in 1995. It includes papers in the core areas of set theory, model theory, proof theory and recursion theory, as well as the more recent topics of finite model theory and non-monotonic logic. It also includes a tutorial on interactive proofs, zero-knowledge and computationally sound proofs that reported on recent developments in theoretical computer science, and three plenary lectures dedicated to the foundational and technical evolution of set theory over the past 100 years.

We shall use Godel’s Second Incompleteness Theorem to show that consistency is not possibility, and then argue that the argument does serious damage to some theories of modality where consistency plays a major but not exclusive role.

Purpose – Deontical impure systems are systems whose object set is formed by an s-impure set, whose elements are perceptuales significances (relative beings) of material and/or energetic objects (absolute beings) and whose relational set is freeways of relations, formed by sheaves of relations going in two-way directions and at least one of its relations has deontical properties such as permission, prohibition, obligation and faculty. The paper aims to discuss these issues. Design/methodology/approach – Mathematical and logical development of human society ethical and normative structure. Findings – Existence of relations with positive imperative modality (obligation) would constitute the skeleton of the system. Negative imperative modality (prohibition) would be the immunological system of protection of the system. Modality permission the muscular system, that gives the necessary flexibility. Four theorems have been formulated based on Gödel's theorem demonstrating the inconsistency or incompleteness of DISs. For each constructed systemic conception can happen to it one of the two following things: either some allowed responses are not produced or else some forbidden responses are produced. Responses prohibited by the system are defined as nonwished effects. Originality/value – This paper is a continuation of the four previous papers and is developed the theory of deontical impure systems.

The view that mathematics is theorem proving, hence the method of mathematics is the axiomatic method, and the view that mathematics is problem solving, hence the method of mathematics is the analytic method, lead to two different concepts of demonstration: axiomatic demonstration and analytic demonstration . This chapter highlights the limitations of axiomatic demonstration. It maintains that analytic demonstration is the basic concept of demonstration and that, in terms of this concept, it is possible to deal with the question of the depth of demonstrations and theorems. On this basis, the chapter characterizes a view of mathematics, called the heuristic view, in terms of the following features: mathematics is problem solving by the analytic method; mathematical objects are hypotheses human beings make to solve mathematical problems by the analytic method; and analytic demonstration is the basic concept of demonstration.

In 1939, Alan Turing attended a seminar in Cambridge, England, given by Ludwig Wittgenstein, on the foundations of mathematics. Alan Turing contributed, in significant ways, to our modern notion of an algorithm, the idea that launched untold thousands of computer programs. He also did pioneering work with early computers; devised the idea of an in-principle computer now known as the “Turing machine”; is responsible for the “Turing test,” a thought experiment used to think about the potential for machine intelligence; and is co-named in the “Church-Turing Thesis,” which is a specific proposal for how the notion of algorithm can be related to basic mathematical formalism. Ludwig Wittgenstein was in his day, and continues to be held to be, one of the greatest philosophers of the twentieth century.

It is shown that an unexpected logical exposition of Dirac 3-polarizer experiment leads to a bipolar equilibrium-based geometrical and logical architecture for the unification of mind, light and matter. It is argued that, without light as a bridge, mind-matter unification would be impossible. An axiomatic proof is presented for the unification with an extension to Godel's incompleteness theorems. Bipolar knowledge representation is illustrated in computational psychopharmacology and information conservational quantum computing. The logical basis of this work is philosophically distinguished from that of Aristotle, Leibniz and Bohr.

Kumaraswamy Vela Velupillai74 presents a constructivist perspective on the foundations of mathematical economics, praising the views of Feynman in developing path integrals and Dirac in developing the delta function. He sees their approach as consistent with the Bishop constructive mathematics and considers its view on the Bolzano-Weierstrass, Hahn-Banach, and intermediate value theorems, and then the implications of these arguments for such "crown jewels" of mathematical economics as the existence of general equilibrium and the second welfare theorem. He also relates these ideas to the weakening of certain assumptions to allow for more general results as shown by Rosser51 in his extension of Gödel's incompleteness theorem in his opening section. This paper considers these arguments in reverse order, moving from the matters of economics applications to the broader issue of constructivist mathematics, concluding by considering the views of Rosser on these matters, drawing both on his writings and on personal conversations with him.

We can never emulate their meekness, soft servants of durable material: they live without pretension in complicated relays and electrical circuits. Speed, docility are their strength. One asks: “What is 2 × 2?”—“Are you a machine?” They answer or refuse to answer, depending on what you demand. There are, however, other machines as well, more abstract automatons, bolder and more inaccessible, which eat their tape in mathematical formulae. They imitate in language. In infinite loops, farther and farther back in their retreat towards more subtle algorithms, more recursive functions. They are logical and describe themselves. As when a man with a hand-mirror pressed against his nose in front of a mirror sees in infinite rows the same image multiplied in a shrinking, darkening corridor of glass. It is a Godel theorem as good as any. He sees infinity, but what he does not see is his face. (From Goran Printz-Pahlson´s poem “The Turing Machine” published in Sag minns du skeppet Refanut? Samlade dikter 1950–1983 (1984) Bonniers, Stockholm).

The process of evolutionary diversification unfolds in a vast genotypic space of potential outcomes. During the past century there have been remarkable advances in the development of theory for this diversification, and the theory's success rests, in part, on the scope of its applicability. A great deal of this theory focuses on a relatively small subset of the space of potential genotypes, chosen largely based on historical or contemporary patterns, and then predicts the evolutionary dynamics within this pre-defined set. To what extent can such an approach be pushed to a broader perspective that accounts for the potential open-endedness of evolutionary diversification? There have been a number of significant theoretical developments along these lines but the question of how far such theory can be pushed has not been addressed. Here a theorem is proven demonstrating that, because of the digital nature of inheritance, there are inherent limits on the kinds of questions that can be answered using such an approach. In particular, even in extremely simple evolutionary systems a complete theory accounting for the potential open-endedness of evolution is unattainable unless evolution is progressive. The theorem is closely related to G\"odel's Incompleteness Theorem and to the Halting Problem from computability theory., Comment: Journal of the Royal Society, Interface 2011

There are many kinds of limitative results in the sciences, some of which are philosophical. I am interested in examining one kind of limitative result in the neurosciences that is mathematical-a result secured by the Gödel incompleteness theorems. I will view the incompleteness theorems as independence results, develop a connection with independence results in set theory, and then argue that work in the neurosciences (as well as in molecular, systems and synthetic biology) may well avoid these mathematical limitative results. In showing this, I argue that demonstrating that one cannot avoid them is a computational task that is beyond the computational capacities of finitary minds. Along the way, I reformulate three philosophical claims about the nature of consciousness in terms of the Gödel incompleteness theorems and argue that these precise reformulations of the claims can be disarmed.

Edward O. Wilson has defined consilience as a strong reductionist program in science. This paper proposes an ontological approach to consilience, which allows for an emergentist interpretation. The methodological basis is naturalism, which is defined through some fundamental notions such as the unity of the world and the impossibility of the detached observer. Naturalism includes, for example, evolutionary epistemology. It does not imply a reductionist approach to human mind and society, but to the contrary the convergence of Naturwissenschaften und Geisteswissenschaften. A major reference point is the naturalization of the Godel theorem, presaged by Hayek in his Sensory Order. Its implications match recent insights of the brain sciences, such as modularization and complex interaction between reason and intuition, which are being received by neuroeconomics research. The Godel theorem is also related to fundamental theorems about randomness, such as Chaitin’s theorems. The world is random in the sense of being singular, which, however, we cannot perceive adequately because our knowledge is propositional, hence relies on provability in a general sense. This diagnosis matches with certain economic approaches to entrepreneurship and uncertainty, such as Shackle’s. The relation between regularity and singularity evolves during the expansion of the universe, according to the theories of Chaisson and Brooks/Wiley, and can be measured as increasing information content that emerges from the growing differential between possible entropy and realized entropy. The difference reflects the growing number of constraints on possible states of the world. These processes are triggered by a continuous flow of energy, in particular through dissipative systems, which minimize entropy internally and maximize externally. From this, the ontological principle of bimodality is deduced, i.e. every state of the world is matterenergy and knowledge. Knowledge is interpreted as non-referential, i.e. as the outcome of a universal process of variation, selection and retention, which also applies for the human mind, including referential (propositional) knowledge only as a special case. This allows to interpret technology and institutions as carriers of knowledge.

The problem addressed, in this chapter, pertains to how to represent and apply knowledge to best facilitate its extension and use in problem solving. Unlike deductive logics (e.g., the predicate calculus), an inherent degree of error is allowed for so as to greatly enlarge the inferential space. This allowance, in turn, implies the application of heuristics (e.g., multiple analogies) to problem solving as well as their indirect use in inferring the heuristics themselves. This chapter is motivated by the science of inductive inference. Examples of state-space search, linguistic applications, and a focus methodology for generating novel knowledge (components) for wartime engagement for countering (cyber) threats (WAMS) are provided.

The nature of the scientific method has been a main concern of philosophy from Plato to Mill. In that period logic has been considered to be a part of the methodology of science. Since Mill, however, the situation has completely changed. Logic has ceased to be a part of the methodology of science, and no Discourse on method has been written. Both logic and the methodology of science have stopped dealing with the process of discovery, and generally with the actual process of scientific research. As a result, several first-rate scientists, from Feynman and Weinberg to Dyson and Hawkins, have concluded that philosophy has become useless and totally irrelevant to science. The aim of this paper is to give some indications as to how to develop a logic concerned with the process of discovery and a methodology of science dealing with the actual process of scientific research.

It is well understood and appreciated that Godel's Incompleteness Theorems apply to sufficiently strong, formal deductive systems. In particular, the theorems apply to systems which are adequate for conventional number theory. Less well known is that there exist algorithms which can be applied to such a system to generate a godel-sentence for that system. Although the generation of a sentence is not equivalent to proving its truth, the present paper argues that the existence of these algorithms, when conjoined with Godel's results and accepted theorems of recursion theory, does provide the basis for an apparent paradox. The difficulty arises when such an algorithm is embedded within a computer program of sufficient arithmetic power. The required computer program (an AI system) is described herein, and the paradox is derived. A solution to the paradox is proposed, which, it is argued, illuminates the truth status of axioms in formal models of programs and Turing machines.

In 1981, Paris and Wilkie raised the open question about whether and to what extent the axiom system IΣ0 did satisfy the Second Incompleteness Theorem under Semantic Tableaux deduction. Our prior work showed that the semantic tableaux version of the Second Incompleteness Theorem did generalize for the most common definition of IΣ0 appearing in the standard textbooks. However, there was an alternate interesting definition of this axiom system in the Wilkie–Paris article in the Annals of Pure and Applied Logic 35 (1987), pp. 261–302 which we did not examine in our year-2002 article in the Journal of Symbolic Logic. Our first goal is to show that the incompleteness results of our prior paper can generalize in this alternate context. We will also develop a formal analysis, using a new technique called Passive Induction, that is simpler than the formalism we had used before. A further reason our results are of interest is that we have shown in a companion paper published in Electronic Notes in Theoretical Computer Science 165 (2006), pp. 213–226 that some very unorthodox axiomizations for IΣ0 are anti-thresholds for the Herbrandized version of the Second Incompleteness Theorem. Thus, different axiomizations for IΣ0 have nearly fully opposite incompleteness properties. This paper is self-contained. It will not require a knowledge of our earlier results.

D. Hilbert raised the problem to prove consistency of formalized mathematics. In this paper I will expound its background and the status quo of the consistency proofs. First let me explain the intended significance of proving consistency, and a background idea to divide mathematical objects in two, i. e., transfinite/finitary objects. Next I will discuss impacts of the incompleteness theorems to the problem and their interpretation. Finally let me give sketches of the practice of the consistency proofs due to G. Gentzen et al. and their significance, and the present state of the consistency proofs.

Unintended effects are well known to economists and sociologists and their consequences may be devastating. The main objective of this article is to formulate a mathematical theorem, based on Godel's famous incompleteness theorem, in which it is shown, that from the moment deontical modalities prohibition, obligation, permission, and faculty are introduced into the social system, responses are allowed by the system that are not produced, however, prohibited responses or unintended effects may occur. © 2014 Wiley Periodicals, Inc. Complexity 21: 342-354, 2015

Welcome to ACM SIGMOD Record's series of interviews with distinguished members of the database community. I'm Marianne Winslett, and I have here with me Moshe Vardi, who holds an endowed professorship at Rice University and is a former chair of their Computer Science Department. Before joining Rice, Moshe was a manager at IBM Almaden Research Center. Moshe is an ACM Fellow, a AAAI Fellow, a co-winner of the Goedel Prize, and a member of the U.S. National Academy of Engineering and the European Academy of Sciences. His research interests include databases, verification, complexity theory, and multi-agent systems, and his PhD is from the Hebrew University of Jerusalem. So Moshe, welcome!

We now know both that hypercomputation (or super-recursive computation) is mathematically well-understood, and that it provides a theory that according to some accounts for some real-life computation (e.g., operating systems that, unlike Turing machines, never simply output an answer and halt) better than the standard theory of computation at and below the “Turing Limit.” But one of the things we do not know is whether the human mind hypercomputes, or merely computes—this despite informal arguments from Gödel, Lucas, Penrose and others for the view that, in light of incompleteness theorems, the human mind has powers exceeding those of TMs and their equivalents. All these arguments fail; their fatal flaws have been repeatedly exposed in the literature. However, we give herein a novel, formal modal argument showing that since it's mathematically possible that human minds are hypercomputers, such minds are in fact hypercomputers. We take considerable pains to anticipate and rebut objections to this argument.

If □ is conceived as an operator, i.e., an expression that gives applied to a formula another formula, the expressive power of the language is severely restricted when compared to a language where □ is conceived as a predicate, i.e., an expression that yields a formula if it is applied to a term. This consideration favours the predicate approach. The predicate view, however, is threatened mainly by two problems: Some obvious predicate systems are inconsistent, and possible-worlds semantics for predicates of sentences has not been developed very far. By introducing possible-worlds semantics for the language of arithmetic plus the unary predicate □, we tackle both problems. Given a frame consisting of a set W of worlds and a binary relation R on W, we investigate whether we can interpret □ at every world in such a way that □⌜A⌝ holds at a world w∈W if and only if A holds at every world v∈W such that wRv. The arithmetical vocabulary is interpreted by the standard model at every world. Several ‘paradoxes’ (like Montague's Theorem, Godel's Second Incompleteness Theorem, McGee's Theorem on the ω-inconsistency of certain truth theories, etc.) show that many frames, e.g., reflexive frames, do not allow for such an interpretation. We present sufficient and necessary conditions for the existence of a suitable interpretation of □ at any world. Sound and complete semi-formal systems, corresponding to the modal systems K and K4, for the class of all possible-worlds models for predicates and all transitive possible-worlds models are presented. We apply our account also to nonstandard models of arithmetic and other languages than the language of arithmetic.

Logic and Computing are appropriate formal languages for Biology, and we may well be surprised by the strong analogy between software and DNA, and between hardware and the protein machinery of the cell. This chapter examines to what extent any biological entity can be described by an algorithm and, therefore, whether the Turing machine and the halting problem concepts apply. Last of all, I introduce the concepts of recursion and algorithmic complexity, both from the field of computer science, which can help us understand and conceptualise biological complexity.

Flow analysis, such as control-flow, data-flow, and exception-flow analysis, usually depends on relational operations on flow sets. Unfortunately, set related operations, such as inclusion and equality, are usually very expensive. They can easily take more than 97% of the total analyzing time, even in a very simple analysis. We attack this performance bottleneck by proposing Godel hashes to enable fast and precise flow analysis. Godel hashes is an ultra compact, partial-order-preserving, fast and perfect hashing mechanism, inspired by the proofs of Godel's incompleteness theorems. Compared with array, tree, traditional hash, and bit vector-backed set implementations, we find Godel hashes to be tens or even hundreds of times faster for performance in the critical operations of inclusion and equality. We apply Godel hashes in real-world analysis for object-oriented programs. The instrumented analysis is tens of times faster than the one with original data structures on DaCapo benchmarks.