Search

What can humans compute in their heads? We are thinking of a variety of cryptographic protocols, games like sudoku, crossword puzzles, speed chess, and so on. For example, can a person compute a function in his or her head so that an eavesdropper with a powerful computer—who sees the responses to random inputs—still cannot infer responses to new inputs? To address such questions, we propose a rigorous model of human computation and associated measures of complexity. We apply the model and measures first and foremost to the problem of 1) humanly computable password generation and then, consider related problems of 2) humanly computable “one-way functions” and 3) humanly computable “pseudorandom generators.” The theory of human computability developed here plays by different rules than standard computability; the polynomial vs. exponential time divide of modern computability theory is irrelevant to human computation. In human computability, the step counts for both humans and computers must be more concrete. As an application and running example, password generation schemas are humanly computable algorithms based on private keys. Humanly computable and/or humanly usable mean, roughly speaking, that any human needing—and capable of using—passwords can if sufficiently motivated generate and memorize a secret key in less than 1 h (including all rehearsals) and can subsequently use schema plus key to transform website names (challenges) into passwords (responses) in less than 1 min. Moreover, the schemas have precisely defined measures of security against all adversaries, human and/or machine.

Computability theory forms the foundation for much of theoretical computer science. Many of our great unsolved questions stem from the need to understand what problems can even be solved. The greatest question of computer science, P vs. NP, even sidesteps this entirely, asking instead how efficiently we can find solutions for the problems that we know are solvable. For many students both at the undergraduate and graduate level, a first exposure to computability theory follows a standard sequence on data structures and algorithms and students often marvel at the first results they see on undecidability - how could we possibly prove that we can never solve a problem? This book, in contrast with other books that are often used as first exposures to computability, finite automata, Turing machines, and the like, focuses very specifically on the notion of what is computable and how computability theory, as a science unto itself, fits into the grander scheme. The book is appropriate for advanced undergraduates and beginning graduate students in computer science or mathematics who are interested in theoretical computer science. Robič sidesteps the standard theoretical computer science progression - understanding finite automata and pushdown automata before moving into Turing machines - by setting the stage with Hilbert's program and mathematical prerequisites before introducing the Turing machine absent the usual prerequisites, and then introducing advanced topics often absent in introductory texts. Most chapters are relatively short and contain problem sets, making it appropriate for both a classroom text or for self-study.

This article investigates emergence and complexity in complex systems that can share information on a network. To this end, we use a theoretical approach from information theory, computability theory, and complex networks. One key studied question is how much emergent complexity (or information) arises when a population of computable systems is networked compared with when this population is isolated. First, we define a general model for networked theoretical machines, which we call algorithmic networks. Then, we narrow our scope to investigate algorithmic networks that optimize the average fitnesses of nodes in a scenario in which each node imitates the fittest neighbor and the randomly generated population is networked by a time-varying graph. We show that there are graph-topological conditions that cause these algorithmic networks to have the property of expected emergent open-endedness for large enough populations. In other words, the expected emergent algorithmic complexity of a node tends to infinity as the population size tends to infinity. Given a dynamic network, we show that these conditions imply the existence of a central time to trigger expected emergent open-endedness. Moreover, we show that networks with small diameter compared to the network size meet these conditions. We also discuss future research based on how our results are related to some problems in network science, information theory, computability theory, distributed computing, game theory, evolutionary biology, and synergy in complex systems., This is a revised version of the research report no. 4/2018 at the National Laboratory for Scientific Computing (LNCC), Brazil

The low academic results and mathematical difficulties experienced by students in learning theoretical computer science have been one of the reasons why many undergraduate students postpone the study of their theoretical subjects until absolutely necessary. For this reason, some optional theoretical subjects have been postponed for the last years, and in some cases, not included in the curricula due to lack of students. In order to reverse this problematic situation in theoretical computing education, it is essential that students acquire as soon as possible an intuitive and progressive knowledge of the main theoretical computing concepts and their associated skills and abilities. To achieve this goal, in this paper we offer a complete educational methodology to systematically introduce questions of computability and algorithmic complexity, in the early years of computer science and mathematics degrees, from the results of impossibility that are already included in the curriculum of CS-geared mathematics courses. To provide clear evidence of the impact of the applicability of the proposed methodology, we analyze the experimental results and student feedback we have obtained to confirm that the introduction of theoretical computing questions from impossibility results increases students' academic results in theoretical computing subjects, and motivation and interest in studying mathematical subjects of beginning level of computer science.

The paper provides concrete evidence of the applicability and usefulness of web-based tools for the teaching and learning of the untyped \(\lambda \)-calculus. In particular, it has been shown that the web application Lambda Viewer can be used as a powerful e-learning tool that allow learners to construct/verify partial stages of \(\beta \)-reductions or entire computations of them in a step-by-step fashion. Moreover, one of the great advantages of the use of web apps in education is that they provide constant feedback that reinforce unconventional aspects of the \(\lambda \)-calculus like Currying. Finally, a sequence of examples illustrates in detail that the combination of teacher’s explanations and screenshots of the Lambda Viewer’s output is more didactically convenient than the feedback of the program by itself.

The formal study of computer malware was initiated in the seminal work of Fred Cohen in the mid 80s who applied elements of the Theory of Computation in the investigation of the theoretical limits of using the Turing Machine formal model of computation in detecting viruses. Cohen gave a simple but realistic, formal, definition of the characteristic actions of a computer virus as a Turing Machine that replicates itself and then proved that constructing a Turing Machine that recognizes viruses (i.e. Turing Machines that act like viruses) is impossible, by reducing the Halting Problem, which is undecidable, to the problem of recognizing a computer virus. In this paper we complement Cohen’s approach along similar lines, based on Recursion Function Theory and the Theory of Computation. More specifically, after providing a simple generalization of Cohen’s definition of a computer virus, we show that the malware/non-malware classification problem is undecidable under this new definition. Moreover, we show that to any formal system, there correspond infinitely many, effectively constructible, programs for which no proof can be produced by the formal system that they are either malware or non-malware programs. In other words, given any formal system, one can provide a procedure that generates, systematically, an infinite number of impossible to classify, within the formal system, programs.

Superintelligence is a hypothetical agent that possesses intelligence far surpassing that of the brightest and most gifted human minds. In light of recent advances in machine intelligence, a number of scientists, philosophers and technologists have revived the discussion about the potential catastrophic risks entailed by such an entity. In this article, we trace the origins and development of the neo-fear of superintelligence, and some of the major proposals for its containment. We argue that such containment is, in principle, impossible, due to fundamental limits inherent to computing itself. Assuming that a superintelligence will contain a program that includes all the programs that can be executed by a universal Turing machine on input potentially as complex as the state of the world, strict containment requires simulations of such a program, something theoretically (and practically) infeasible., Comment: 7 pages, 5 figures

Theory of computation deals with developing mathematical models of computation. This area of research is divided into three subareas: complexity theory, computability theory and automata theory. We mostly review basic structures of automata theory which are languages and finite state automata in this chapter. A language is defined over a set of symbols called an alphabet. A finite state machine is a mathematical tool to model a computing system. Unlike a combinational circuit, a finite state machine has a memory and its behavior and output depends on its current input and its current state. A finite state automata is a finite state machine with no outputs; instead, it has final states called accepting states. A finite state automata can be used to recognize a language conveniently. We review languages, finite state machines, finite state automata, language recognition in this chapter and conclude the first part with the Turing machine named after Alan Turing, which is a more general type of a finite state machine. We then have a short review of complexity theory with the basic complexity classes.

Nature-inspired computing is a type of human-designed computing motivated by nature, which is based on the employ of paradigms, mechanisms, and principles underlying natural systems. In this article, a versatile and vigorous bio-inspired branch of natural computing, named membrane computing is discussed. This computing paradigm is aroused by the internal membrane function and the structure of biological cells. We first introduce some basic concepts and formalisms of membrane computing, and then some basic types or variants of P systems (also named membrane systems ) are presented. The state-of-the-art computability theory and a pioneering computational complexity theory are presented with P system frameworks and numerous solutions to hard computational problems (especially NP -complete problems) via P systems with membrane division are reported. Finally, a number of applications and open problems of P systems are briefly described.

From the creation of the field of Membrane Computing in 1998, several research lines havebeen opened. On the one hand, theoretical questions like the computational power and thecomputational efficiency of P systems have been studied. In this sense, several techniquesto demonstrate the ability of these systems to provide solutions to computational problemshave been explored. The study of efficient(polynomial-time) solutions to presumably hardproblems for finding thin frontiers of efficiency is a very active area. On the other hand,several applications in biology, ecology, economy, robotics and fault diagnosis, amongothers, have been investigated. Real systems with some characteristics seem to be easyto model with membrane systems due to their behaviour. In this work, a survey of thetheoretical part will be given, explaining techniques both in the field of computabilitytheory and in the field of computational complexity theory. Ministerio de Economía, Industria y Competitividad TIN2017-89842-P (MABICAP)

We discuss the difficulties in stating an analogue of the Church-Turing thesis for algorithmic randomness. We present one possibility and argue that it cannot occupy the same position in the study of algorithmic randomness that the Church-Turing thesis does in computability theory. We begin by observing that some evidence comparable to that for the Church-Turing thesis does exist for this statement: in particular, there are other reasonable formalizations of the intuitive concept of randomness that lead to the same class of random sequences (the Martin-Lof random sequences). However, we consider three properties that we would like a random sequence to satisfy and find that the Martin-Lof random sequences do not necessarily possess these properties to a greater degree than other types of random sequences, and we further argue that there is no more appropriate version of the Church-Turing thesis for algorithmic randomness. This suggests that consensus around a version of the Church-Turing thesis in this context is unlikely.

We introduce a framework for online structure theory. Our approach generalises notions arising independently in several areas of computability theory and complexity theory. We suggest a unifying approach using operators where we allow the input to be a countable object of an arbitrary complexity. Thus we will begin a view that online algorithms can be viewed as a sub-area of computable analysis. We will give a new framework which (i) ties online algorithms with computable analysis, (ii) shows how to use modifications of notions from computable analysis, such as Weihrauch reducibility, to analyse finite but uniform combinatorics, (iii) show how to finitize reverse mathematics to suggest a fine structure of finite analogs of infinite combinatorial problems, and (iv) see how similar ideas can be amalgamated from areas such as EX-learning, computable analysis, distributed computing and the like. Conversely, we also get an enrichment of computable analysis from ideas from the analysis of classical online algorithms.

Many readers will be familiar with the Computational Complexity blog, started in 2003 by Lance Fortnow and, since 2007, co-blogged by Bill Gasarch. Professor Gasarch is also the first author of Problems with a Point, which is based on 24 of Gasarch's Computational Complexity blog posts, most of them significantly expanded or reworked with contributions from co-author Clyde Kruskal. The book presents us with 24 stories, problems, or theorems ?with a point." Indeed, most chapters have an opening subsection with the pleasingly succinct title ?Point," in which the point of the chapter is summarized, implicitly justifying the selection of the corresponding blog post for inclusion in the book. The Computational Complexity blog is known for the surprisingly wide ambit of its topics (officially ?fun stuff in math and computer science"). This breadth is reflected in the book, which features chapters on a variety of topics, including: the usage of mathematical terms in mainstream publications; what makes a good math competition problem?; what makes a math problem interesting?; what constitutes an elegant proof?; discussion of natural (?sane") reductions; and some healthy lessons about when and how to apply mathematical skepticism and intuition. The accessibility of the selection is admirable: most chapters can be appreciated by a strong high school mathematician, while a few require elementary knowledge of complexity or computability theory.

The concept of computable functions (as developed by Godel, Church, Turing, and Kleene in the 1930's) has been extensively studied, leading to the modern subject of recursive function theory. However recent work by category theorists has led to a more conceptual and abstract foundation of computability theory—Turing categories. A Turing category models the notion of partial map as well as recursive computation, using methods of categorical algebra to formalize these concepts. The goal of this work is to provide a formal framework for analyzing this categorical model of computation. We use the Coq Proof Assistant, which implements the Calculus of (co)Inductive Constructions (CIC), and we build on an existing Coq library for general category theory. We focus on both formalizing Turing categories and on building a general framework in the form of a well-structured Coq library that can be further extended. We begin by formalizing definitions, propositions, and proofs pertaining to Turing categories, and then instantiate the more general Turing category formalism with a CIC description of the category which explicitly models the language of partial recursive functions.

Reversible computing is both forward and backward deterministic. This means that a uniquely determined step exists from the previous computational configuration (backward determinism) to the next one (forward determinism) and vice versa. We present the reversible primitive recursive functions (RPRF), a class of reversible (endo-)functions over natural numbers which allows to capture interesting extensional aspects of reversible computation in a formalism quite close to that of classical primitive recursive functions. The class RPRF can express bijections over integers (not only natural numbers), is expressive enough to admit an embedding of the primitive recursive functions and, of course, its evaluation is effective. We also extend RPRF to obtain a new class of functions which are effective and Turing complete, and represent all Kleene’s $$\upmu $$ -recursive functions. Finally, we consider reversible recursion schemes that lead outside the reversible endo-functions.

Relativizing computations of Turing machines to an oracle is a central concept in the theory of computation, both in complexity theory and in computability theory(!). Inspired by lowness notions from computability theory, Allender introduced the concept of "low for speed" oracles. An oracle A is low for speed if relativizing to A has essentially no effect on computational complexity, meaning that if a decidable language can be decided in time $f(n)$ with access to oracle A, then it can be decided in time poly(f(n)) without any oracle. The existence of non-computable such A's was later proven by Bayer and Slaman, who even constructed a computably enumerable one, and exhibited a number of properties of these oracles as well as interesting connections with computability theory. In this paper, we pursue this line of research, answering the questions left by Bayer and Slaman and give further evidence that the structure of the class of low for speed oracles is a very rich one., A preliminary version of this paper was published in the proceedings of the STACS 2018 conference

Algorithmic fractal dimensions—constructs of computability theory—have recently been used to answer open questions in classical geometric measure theory, questions of mathematical analysis whose statements do not involve computability theory or logic. We survey these developments and the prospects for future such results.

In the previous chapters we have defined the basic notions and concepts of a theory that we are interested in, Computability Theory. In particular, we have rigorously defined its basic notions, i.e., the notions of algorithm, computation, and computable function. We have also defined some new notions, such as the decidability and semi-decidability of a set, that will play key roles in the next chapter (where we will further develop Computability Theory). As a side product of the previous chapters we have also discovered some surprising facts, such as the existence of the universal Turing machine. It is now time to start using this apparatus and deduce the first theorems of Computability Theory. In this chapter we will first prove several simple but useful theorems about decidable and semi-decidable sets and their relationship. Then we will deduce the so-called Padding Lemma and, based on it, introduce the extremely important concept of the index set. This will enable us to deduce two influential theorems, the Parametrization Theorem and the Recursion Theorem. We will not be excessively formal in our deductions; instead, we will equip them with meaning and motivation wherever appropriate.

We introduce geometric consideration into the theory of formal languages. We aim to shed light on our understanding of global patterns that occur on infinite strings. We utilise methods of geometric group theory. Our emphasis is on large scale geometries. Two infinite strings have the same large scale geometry if there are colour preserving bi-Lipschitz maps with distortions between the strings. Call these maps quasi-isometries. Introduction of large scale geometries poses several questions. The first question asks to study the partial order induced by quasi-isometries. This partial order compares large scale geometries; as such it presents an algebraic tool for classification of global patterns. We prove there is a greatest large scale geometry and infinitely many minimal large scale geometries. The second question is related to understanding the quasi-isometric maps on various classes of strings. The third question investigates the sets of large scale geometries of strings accepted by computational models, e.g. B\"uchi automata. We provide an algorithm that describes large scale geometries of strings accepted by B\"uchi automata. This links large scale geometries with automata theory. The fourth question studies the complexity of the quasi-isometry problem. We show the problem is $\Sigma_3^0$-complete thus providing a bridge with computability theory. Finally, the fifth question asks to build algebraic structures that are invariants of large scale geometries. We invoke asymptotic cones, a key concept in geometric group theory, defined via model-theoretic notion of ultra-product. Partly, we study asymptotic cones of algorithmically random strings thus connecting the topic with algorithmic randomness., Comment: 12 pages

International audience; We formalise the undecidability of solvability of Diophantine equations, i.e. polynomial equations over natural numbers, in Coq's constructive type theory. To do so, we give the first full mechanisation of the Davis-Putnam-Robinson-Matiyasevich theorem, stating that every recursively enumerable problem-in our case by a Minsky machine-is Diophantine. We obtain an elegant and comprehensible proof by using a synthetic approach to computability and by introducing Conway's FRACTRAN language as intermediate layer.

Solomon Marcus (1925–2016) was one of the founders of the Romanian theoretical computer science. His pioneering contributions to automata and formal language theories, mathematical linguistics and natural computing have been widely recognised internationally. In this paper we briefly present his publications in theoretical computer science and related areas, which consist in almost ninety papers. Finally we present a selection of ten Marcus books in these areas.

I develop a theory of counterfactuals about relative computability, i.e. counterfactuals such as If the validity problem were algorithmically decidable, then the halting problem would also be algorithmically decidable, which is true, and If the validity problem were algorithmically decidable, then arithmetical truth would also be algorithmically decidable, which is false. These counterfactuals are counterpossibles, i.e. they have metaphysically impossible antecedents. They thus pose a challenge to the orthodoxy about counterfactuals, which would treat them as uniformly true. What's more, I argue that these counterpossibles don't just appear in the periphery of relative computability theory but instead they play an ineliminable role in the development of the theory. Finally, I present and discuss a model theory for these counterfactuals that is a straightforward extension of the familiar comparative similarity models.

We formalise the computational undecidability of validity, satisfiability, and provability of first-order formulas following a synthetic approach based on the computation native to Coq's constructive type theory. Concretely, we consider Tarski and Kripke semantics as well as classical and intuitionistic natural deduction systems and provide compact many-one reductions from the Post correspondence problem (PCP). Moreover, developing a basic framework for synthetic computability theory in Coq, we formalise standard results concerning decidability, enumerability, and reducibility without reference to a concrete model of computation. For instance, we prove the equivalence of Post's theorem with Markov's principle and provide a convenient technique for establishing the enumerability of inductive predicates such as the considered proof systems and PCP.

In previous papers I have characterized four ways of reasoning in Peirce’s philosophy, and four ways of reasoning in Computability Theory. I have established their correspondence on the basis of the four pairs of choices regarding two dichotomies, respectively the dichotomy between two kinds of Mathematics and the dichotomy between two kinds of Logic. In the present paper I introduce four principles of reasoning in theoretical Physics and I interpret also them by means of the four pairs of choices regarding the above two dichotomies. I show that there exists a meaningful correspondence among the previous three fourfold sets of elements. This convergence of the characteristic ways of reasoning within three very different fields of research - Peirce’s philosophy, Computability theory and physical theories - suggests that there exists a general-purpose structure of four ways of reasoning. This structure is recognized as applied by Mendeleev when he built his periodic table. Moreover, it is shown that a chemist applies all the above ways of reasoning at the same time. Peirce’s professional practice as a chemist applying at the same time this variety of reasoning explains his stubborn research into the variety of the possible inferences.

We overview logical and computational explanations of the notion of tractability as applied in cognitive science. We start by introducing the basics of mathematical theories of complexity: computability theory, computational complexity theory, and descriptive complexity theory. Computational philosophy of mind often identifies mental algorithms with computable functions. However, with the development of programming practice it has become apparent that for some computable problems finding effective algorithms is hardly possible. Some problems need too much computational resource, e.g., time or memory, to be practically computable. Computational complexity theory is concerned with the amount of resources required for the execution of algorithms and, hence, the inherent difficulty of computational problems. An important goal of computational complexity theory is to categorize computational problems via complexity classes, and in particular, to identify efficiently solvable problems and draw a line between tractability and intractability. We survey how complexity can be used to study computational plausibility of cognitive theories. We especially emphasize methodological and mathematical assumptions behind applying complexity theory in cognitive science. We pay special attention to the examples of applying logical and computational complexity toolbox in different domains of cognitive science. We focus mostly on theoretical and experimental research in psycholinguistics and social cognition.

Classic computability theory is based on sequential models of computation, like Turing machines [21, 5, 12]. It is sometimes argued that Turingcomplete models of computations are equally expressive. However, we argue that there are problems in distributed computing, such as the Last Man Standing problem [22, 9], that are not solvable in the Turing-complete model CCS(25,12)[10], while they are solvable within finite, nonpermissive [9] Petri nets, a class of nets extending conservatively finite Petri nets with inhibitor arcs. Hence, we argue that Petri nets, in their many facets, are more suitable than sequential models of computation to assess the relative expressive power of different languages for distributed systems. In doing so, we put the basis for distributed computability theory, as a generalization of sequential (or Turing) computability theory.

This paper deals with the foundations of mathematics and computer science, domain theory in particular; the latter studies certain ordered sets, called domains, with close relations to topology. Conceptually speaking, domain theory provides a highly abstract and general formalisation of the intuitive notions ‘approximation’ and ‘convergence’. Thus, a major application in computer science is the semantics of programming languages. We study the following foundational questions: (Q1) Which axioms are needed to prove basic results in domain theory? (Q2) How hard it is to compute the objects in these basic results?

We investigate the common recursive structure of history-dependent dynamic models in science and engineering. We give formal semantics in terms of a hybrid algebraic-coalgebraic scheme, namely course-of-value iteration. This theoretical approach yields categories of observationally equivalent model representations with precise semantic relationships. Along the initial-final axis of these categories, history dependence can appear both literally and transformed into instantaneous state. The framework can be connected to philosophical and epistemological discourse on one side, and to algorithmic considerations for computational modeling on the other.

Osvald Demuth (1936–1988) studied constructive analysis from the viewpoint of the Russian school of constructive mathematics. In the course of his work he introduced various notions of effective null set which, when phrased in classical language, yield a number of major algorithmic randomness notions. In addition, he proved several results connecting constructive analysis and randomness that were rediscovered only much later.In this paper, we trace the path that took Demuth from his constructivist roots to his deep and innovative work on the interactions between constructive analysis, algorithmic randomness, and computability theory. We will focus specifically on (i) Demuth’s work on the differentiability of Markov computable functions and his study of constructive versions of the Denjoy alternative, (ii) Demuth’s independent discovery of the main notions of algorithmic randomness, as well as the development of Demuth randomness, and (iii) the interactions of truth-table reducibility, algorithmic randomness, and semigenericity in Demuth’s work.

Kapovich, Myasnikov, Schupp and Shpilrain in 2003 developed generic approach to algorithmic problems, which considers an algorithmic problem on “most” of the inputs (i.e., on a generic set) instead of the entire domain and ignores it on the rest of inputs (a negligible set). Jockusch and Schupp in 2012 began the study of generic computability in the context of classical computability theory. In particular, they defined a generic analog of Turing reducibility. In this paper we introduce a generic analog of m-reducibility as m-reducibility by computable functions, which preserve the non-negligibility of sets. We study generic m-reducibility of computable and c.e. sets. We prove the existence of generically m-complete c.e. sets, incomparable c.e. sets and m-degrees, which contain more than one generic m-degree.

We introduce a computational formalism that is deployable within an arbitrary logical system. This formalism is intended to capture computation on an arbitrary system, both physical and unphysical, including quantum computers, Blum-Shub-Smale machines, and infinite time Turing machines. We demonstrate that for finite problems, the computational power of any device describable via a finite first-order theory is equivalent to that of a Turing machine. Whereas for infinite problems, their computational power is equivalent to that of a type-2 machine.

Having explored the limits and the “negative” effects of the type of self-exploration and self-examination embedded observers are bound to we shall now examine the “positive” side of self-description. In particular, we shall prove that, at least for “nontrivial” deterministic systems (in the sense of recursion theory and, by the Church-Turing thesis, capable of universal computation), it is possible to represent a complete theory or “blueprint” of itself within these very systems.

We aim at providing a philosophical analysis of the notion of “proof by Church’s Thesis”, which is – in a nutshell – the conceptual device that permits to rely on informal methods when working in Computability Theory. This notion allows, in most cases, to not specify the background model of computation in which a given algorithm – or a construction – is framed. In pursuing such analysis, we carefully reconstruct the development of this notion (from Post to Rogers, to the present days), and we focus on some classical constructions of the field, such as the construction of a simple set. Then, we make use of this focus in order to support the following encompassing claim (which opposes to a somehow commonly received view): the informal side of Computability, consisting of the large class of methods typically employed in the proofs of the field, is not fully reducible to its formal counterpart.

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 nineteenth publication in the Lecture Notes in Logic series, collects the proceedings of the European Summer Meeting of the Association for Symbolic Logic, held in Paris, France in July 2000. This meeting marked the centennial anniversary of Hilbert's famous lecture and was held in the same hall at La Sorbonne where Hilbert presented his problems. Three long articles, based on tutorials given at the meeting, present accessible expositions of developing research in model theory, computability, and set theory. The eleven subsequent papers present work from the research frontier in all areas of mathematical logic.

This paper aims to interpret and formalize Herbert Simon’s cognitive notions of bounded rationality, satisficing and heuristics in terms of computability theory and computational complexity theory. Simon’s theory of human problem solving is analyzed in the light of Turing’s work on Solvable and Unsolvable Problems . It is suggested here that bounded rationality results from the fact that the deliberations required for searching computationally complex spaces exceed the actual complexity that human beings can handle. The immediate consequence is that satisficing becomes the general criterion of decision makers and heuristics are the procedures used for achieving their goals. In such decision problems, it is demonstrated that bounded rationality and satisficing are more general than orthodox, non-cognitive, Olympian rationality and optimization, respectively, and not the other way about.

What can and cannot be computed in a distributed system is a complex function of the system's communication model, timing model, and failure model. Considering a canonical distributed system model, where processes execute asynchronously, communicate by reading and writing shared memory, and fail by crashing, this paper surveys important results about computability, and explains the fundamental role that topology plays in the distributed computability theory. The paper also considers different types of additional assumptions that allow impossibility results to be circumvented. These assumptions are known under the names failure detectors and adversaries. Finally, it presents a powerful simulation technique (known under the name BG simulation), which allows to show that, from a computability point of view, t-resilience is not different from wait-freedom. When pieced together, the aim of all the concepts, notions, models, and algorithms presented in the paper, is to provide the reader with a synthetic view of important results on the distributed asynchronous read/write shared-memory model, its power and its limits.

This research is about operational- and complexity-oriented aspects of classical foundations of computability theory. The approach is to re-examine some classical theorems and constructions, but with new criteria for success that are natural from a programming language perspective. Three cornerstones of computability theory are the S-m-ntheorem; Turing's "universal machine"; and Kleene's second recursion theorem. In today's programming language parlance these are respectively partial evaluation, self-interpretation, and reflection. In retrospect it is fascinating that Kleene's 1938 proof is constructive; and in essence builds a self-reproducing program. Computability theory originated in the 1930s, long before the invention of computers and programs. Its emphasis was on delimiting the boundaries of computability. Some milestones include 1936 (Turing), 1938 (Kleene), 1967 (isomorphism of programming languages), 1985 (partial evaluation), 1989 (theory implementation), 1993 (efficient self-interpretation) and 2006 (term register machines). The "Swiss pocket knife" of the title is a programming language that allows efficient computer implementation of all three computability cornerstones, emphasising the third: Kleene's second recursion theorem. We describe experiments with a tree-based computational model aiming for both fast program generation and fast execution of the generated programs., In Proceedings Festschrift for Dave Schmidt, arXiv:1309.4557

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 twentieth publication in the Lecture Notes in Logic series, contains the proceedings of the 2001 European Summer Meeting of the Association for Symbolic Logic, held at the Vienna University of Technology. Two long articles present accessible expositions on resolution theorem proving and the determinacy of long games. The remaining articles cover separate research topics in many areas of mathematical logic, including applications in computer science, proof theory, set theory, model theory, computability theory, linguistics and aspects of philosophy. This collection will interest not only mathematical logicians but also philosophical logicians, historians of logic, computer scientists, formal linguists and mathematicians working in algebra, abstract analysis and topology.