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.

We focus on total functions in the theory of reversible computational models. We define a class of recursive permutations, dubbed Reversible Primitive Permutations ( RPP ) which are computable invertible total endo-functions on integers, so a subset of total reversible computations. RPP is generated from five basic functions (identity, sign-change, successor, predecessor, swap), two notions of composition (sequential and parallel), one functional iteration and one functional selection. RPP is closed by inversion and it is expressive enough to encode Cantor pairing and the whole class of Primitive Recursive Functions.

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 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.

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.

The academic results that students of computer science degrees obtain in their learning of subjects of theoretical computer science are traditionally low, as a consequence of the difficulties students experience due to their little theoretical background. In order to reverse this problematic situation in theoretical computing education, it is essential that students acquire an intuitive and progressive knowledge of the main theoretical computing concepts and their associated skills and abilities, even before they finish secondary school. To achieve this goal, in this paper we offer a novel methodology to systematically introduce questions of computability and algorithmic complexity in the curriculum of the final years of high school education. We propose to start from those results of impossibility that are already included in the pre-university curriculum of mathematics courses, and around these theorems of impossibility, conveniently adapted and presented to students, identify motivating and interesting theoretical computing questions. To provide evidence of the applicability of the proposed methodology, we analyze the experimental results we have obtained to confirm that the introduction of theoretical computing questions from impossibility results increases secondary school students’ academic grades and motivation beyond traditional programming courses.

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.

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

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.

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.

Computable analysis has been part of computability theory since Turing's original paper on the subject (Turing, Proc. London Math. Sc. 42:230---265, 1936). Nevertheless, it is difficult to locate basic results in this area. A first goal of this paper is to give some new simple proofs of fundamental classical results (highlighting the role of ź10${{\Pi }_{1}^{0}}$ classes). Naturally this paper cannot cover all aspects of computable analysis, but we hope that this gives the reader a completely self-contained ingress into this area. A second goal is to use tools from effective topology to analyse the Darboux property, particularly a result by Sierpinski, and the Blaschke Selection Theorem.

International audience; In computability theory many results state the existence of objects that in many respects lack algorithmic structure but at the same time are effective in some sense. Friedberg and Muchnik's answer to Post problem is one of the most celebrated results in this form. The main goal of the paper is to develop a general result that embodies a large number of these particular constructions, capturing the essential idea that is common to all of them, and expressing it in topological terms.To do so, we introduce the effective topological notions of irreversible function and directional genericity and provide two main results that identify situations when such constructions are possible, clarifying the role of topology in many arguments from computability theory. We apply these abstract results to particular situations, illustrating their strength and deriving new results.This paper is an extended version of a conference paper with detailed proofs and new results.

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.

The present paper introduces a novel notion of `(effective) computability', called viability, of strategies in game semantics in an intrinsic (i.e., without recourse to the standard Church-Turing computability), non-inductive and non-axiomatic manner, and shows, as a main technical achievement, that viable strategies are Turing complete. Consequently, we have given a mathematical foundation of computation in the same sense as Turing machines but beyond computation on natural numbers, e.g., higher-order computation, in a more abstract fashion. As immediate corollaries, some of the well-known theorems in computability theory such as the smn-theorem and the first recursion theorem are generalized. Notably, our game-semantic framework distinguishes `high-level' computational processes that operate directly on mathematical objects such as natural numbers (not on their symbolic representations) and their `symbolic implementations' that define their `computability', which sheds new light on the very concept of computation. This work is intended to be a stepping stone towards a new mathematical foundation of computation, intuitionistic logic and constructive mathematics.

A generic computation of a subsetAof ℕ is a computation which correctly computes most of the bits ofA, but which potentially does not halt on all inputs. The motivation for this concept is derived from complexity theory, where it has been noticed that frequently, it is more important to know how difficult a type of problem is in the general case than how difficult it is in the worst case. When we study this concept from a recursion theoretic point of view, to create a transitive relationship, we are forced to consider oracles that sometimes fail to give answers when asked questions. Unfortunately, this makes working in the generic degrees quite difficult. Indeed, we show that generic reduction is$\Pi _1^1$―complete. To help avoid this difficulty, we work with the generic degrees of density-1 reals. We demonstrate how an understanding of these degrees leads to a greater understanding of the overall structure of the generic degrees, and we also use these density-1 sets to provide a new a characterization of the hyperartithmetical Turing degrees.

Algorithmic randomness.Martingales.Betting strategies.Turing degrees. Betting strategies are often expressed formally as martingales. A martingale is called integer-valued if each bet must be an integer value. Integer-valued strategies correspond to the fact that in most betting situations, there is a minimum amount that a player can bet. According to a well known paradigm, algorithmic randomness can be founded on the notion of betting strategies. A real X is called integer-valued random if no effective integer-valued martingale succeeds on X. It turns out that this notion of randomness has interesting interactions with genericity and the computably enumerable degrees. We investigate the computational power of the integer-valued random reals in terms of standard notions from computability theory.

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.

We study the computational power of randomized computations on infinite objects, such as real numbers. In particular, we introduce the concept of a Las Vegas computable multi-valued function, which is a function that can be computed on a probabilistic Turing machine that receives a random binary sequence as auxiliary input. The machine can take advantage of this random sequence, but it always has to produce a correct result or to stop the computation after finite time if the random advice is not successful. With positive probability the random advice has to be successful. We characterize the class of Las Vegas computable functions in the Weihrauch lattice with the help of probabilistic choice principles and Weak Weak K\H{o}nig's Lemma. Among other things we prove an Independent Choice Theorem that implies that Las Vegas computable functions are closed under composition. In a case study we show that Nash equilibria are Las Vegas computable, while zeros of continuous functions with sign changes cannot be computed on Las Vegas machines. However, we show that the latter problem admits randomized algorithms with weaker failure recognition mechanisms. The last mentioned results can be interpreted such that the Intermediate Value Theorem is reducible to the jump of Weak Weak K\H{o}nig's Lemma, but not to Weak Weak K\H{o}nig's Lemma itself. These examples also demonstrate that Las Vegas computable functions form a proper superclass of the class of computable functions and a proper subclass of the class of non-deterministically computable functions. We also study the impact of specific lower bounds on the success probabilities, which leads to a strict hierarchy of classes. In particular, the classical technique of probability amplification fails for computations on infinite objects. We also investigate the dependency on the underlying probability space., Comment: Information and Computation (accepted for publication)

Computational complexity theory is a branch of computer science dedicated to classifying computational problems in terms of their difficulty. While computability theory tells us what we can compute in principle, complexity theory informs us regarding what is feasible. In this chapter I argue that the science of quantum computing illuminates complexity theory by emphasising that its fundamental concepts are not model-independent, but that this does not, as some suggest, force us to radically revise the foundations of the theory. For model-independence never has been essential to those foundations. The fundamental aim of complexity theory is to describe what is achievable in practice under various models of computation for our various practical purposes. Reflecting on quantum computing illuminates complexity theory by reminding us of this, too often under-emphasised, fact.

In this paper, we highlight a new computational aspect of Nonstandard Analysis relating to higher-order computability theory. In particular, we prove that the Gandy-Hyland functional equals a primitive recursive functional involving nonstandard numbers inside Nelson's internal set theory. From this classical and ineffective proof in Nonstandard Analysis, a term from Godel's system T can be extracted which computes the Gandy-Hyland functional in terms of a modulus-of-continuity functional and the special fan functional. We obtain several similar relative computability results not involving Nonstandard Analysis from their associated nonstandard theorems. By way of reversal, we show that certain relative computability results, called Herbrandisations, also imply the nonstandard theorem from whence they were obtained. Thus, we establish a direct two-way connection between the field Computability (in particular theoretical computer science) and the field Nonstandard Analysis.

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.

We survey recent advances on the interface between computability theory and algorithmic randomness, with special attention on measures of relative complexity. We focus on (weak) reducibilities that measure (a) the initial segment complexity of reals and (b) the power of reals to compress strings, when they are used as oracles. The results are put into context and several connections are made with various central issues in modern algorithmic randomness and computability.

Emergence and development of recursion theory and computer science enable us to rigorously address the question of characterising the class of mathematical concepts that are cognitively accessible to computational devices such as human minds. The answer to this question would give reasons for which some concepts are epistemically easy (e.g. provable within first-order theories or possessing certain combinatorial properties) and the others are cognitively hard for the human mind.

Das Buch gibt eine kurze Einführung in die Theorie der Berechenbarkeit., Why do we need a formalization of the notion of algorithm or effective computation? In order to show that a specific problem is algorithmically solvable, it is sufficient to provide an algorithm that solves it in a sufficiently precise manner. However, in order to prove that a problem is in principle not solvable by an algorithm, a rigorous formalism is necessary that allows mathematical proofs. The need for such a formalism became apparent in the studies of David Hilbert (1900) on the foundations of mathematics and Kurt Gödel (1931) on the incompleteness of elementary arithmetic. The first investigations in the field were conducted by the logicians Alonzo Church, Stephen Kleene, Emil Post, and Alan Turing in the early 1930s. They have provided the foundation of computability theory as a branch of theoretical computer science. The fundamental results established Turing computability as the correct formalization of the informal idea of effective calculation. The results have led to Church’s thesis stating that ”everything computable is computable by a Turing machine”. The theory of computability has grown rapidly from its beginning. Its questions and methods are penetrating many other mathematical disciplines. Today, computability theory provides an important theoretical background for logicians, pure mathematicians, and computer scientists. Many mathematical problems are known to be undecidable such as the word problem for groups, the halting problem, and Hilbert’s tenth problem. This book is a development of class notes for a two-hour lecture including a one-hour lab held for second-year Bachelor students of Computer Science at the Hamburg University of Technology during the last two years. The course aims to present the basic results of computability theory, including mathematical models of computability, primitive recursive and partial recursive functions, Ackermann’s function, Gödel numbering, universal functions, smn theorem, Kleene’s normal form, undecidable sets, theorems of Rice, and word problems. The manuscript has partly grown out of notes taken by the author during his studies at the University of Erlangen-Nuremberg. I would like to thank again my teachers Martin Becker† and Volker Strehl for giving inspiring lectures in this field. The second edition contains minor changes. In particular, the section on Gödel numbering has been rewritten and a glossary of terms has been added.

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. This tutorial surveys some important results about computability in the canonical distributed system model, where processes execute asynchronously, they communicate by reading and writing shared memory, and they fail by crashing. It explains the fundamental role that topology plays in the distributed computability theory.

An infinite sequence X is said to have trivial (prefix-free) initial segment complexity if the prefix-free Kolmogorov complexity of each initial segment of X is the same as the complexity of the sequence of 0s of the same length, up to a constant. We study the gap between the minimum complexity K(0 n ) and the initial segment complexity of a nontrivial sequence, and in particular the nondecreasing unbounded functions f such that ? for a nontrivial sequence X, where K denotes the prefix-free complexity. Our first result is that there exists a $\varDelta^{0}_{3}$ unbounded nondecreasing function f which does not have this property. It is known that such functions cannot be $\varDelta^{0}_{2}$ hence this is an optimal bound on their arithmetical complexity. Moreover it improves the bound $\varDelta^{0}_{4}$ that was known from Csima and Montalban (Proc. Amer. Math. Soc. 134(5):1499---1502, 2006). Our second result is that if f is $\varDelta^{0}_{2}$ then there exists a non-empty $\varPi^{0}_{1}$ class of reals X with nontrivial prefix-free complexity which satisfy (?). This implies that in this case there uncountably many nontrivial reals X satisfying (?) in various well known classes from computability theory and algorithmic randomness; for example low for ?, non-low for ? and computably dominated reals. A special case of this result was independently obtained by Bienvenu, Merkle and Nies (STACS, pp. 452---463, 2011).

We examine an effective version of the standard fact from analysis which says that, for any @e>0 and any Lebesgue-measurable subset of Cantor space, X@?2^@w, there is an open set U"@e@?2^@w,U"@e@?X, such that @m(U"@e)@?@m(X)+@e, where @m(Z) denotes the Lebesgue measure of Z@?2^@w, that arises naturally in the context of algorithmic randomness. More specifically, our main result shows that for any given rational numbers 0@?@e

Instruction sequence is a key concept in practice, but it has as yet not come prominently into the picture in theoretical circles. This paper concerns instruction sequences, the behaviours produced by them under execution, the interaction between these behaviours and components of the execution environment, and two issues relating to computability theory. Positioning Turing's result regarding the undecidability of the halting problem as a result about programs rather than machines, and taking instruction sequences as programs, we analyse the autosolvability requirement that a program of a certain kind must solve the halting problem for all programs of that kind. We present novel results concerning this autosolvability requirement. The analysis is streamlined by using the notion of a functional unit, which is an abstract state-based model of a machine. In the case where the behaviours exhibited by a component of an execution environment can be viewed as the behaviours of a machine in its different states, the behaviours concerned are completely determined by a functional unit. The above-mentioned analysis involves functional units whose possible states represent the possible contents of the tapes of Turing machines with a particular tape alphabet. We also investigate functional units whose possible states are the natural numbers. This investigation yields a novel computability result, viz. the existence of a universal computable functional unit for natural numbers., Comment: 37 pages; missing equations in table 3 added; combined with arXiv:0911.1851 [cs.PL] and arXiv:0911.5018 [cs.LO]; introduction and concluding remarks rewritten; remarks and examples added; minor error in proof of theorem 4 corrected

This paper deals with the question: what are the key requirements for a physical system to perform digital computation? Time and again cognitive scientists are quick to employ the notion of computation simpliciter when asserting basically that cognitive activities are computational. They employ this notion as if there was or is a consensus on just what it takes for a physical system to perform computation, and in particular digital computation. Some cognitive scientists in referring to digital computation simply adhere to Turing’s notion of computability. Classical computability theory studies what functions on the natural numbers are computable and what mathematical problems are undecidable. Whilst a mathematical formalism of computability may perform a methodological function of evaluating computational theories of certain cognitive capacities, concrete computation in physical systems seems to be required for explaining cognition as an embodied phenomenon. There are many non-equivalent accounts of digital computation in physical systems. I examine only a handful of those in this paper: (1) Turing’s account; (2) The triviality “account”; (3) Reconstructing Smith’s account of participatory computation; (4) The Algorithm Execution account. My goal in this paper is twofold. First, it is to identify and clarify some of the underlying key requirements mandated by these accounts. I argue that these differing requirements justify a demand that one commits to a particular account when employing the notion of computation in regard to physical systems. Second, it is to argue that despite the informative role that mathematical formalisms of computability may play in cognitive science, they do not specify the relationship between abstract and concrete computation.

This paper studies the Turing degrees of various properties defined for universal numberings, that is, for numberings which list all partial-recursive functions. In particular properties relating to the domain of the corresponding functions are investigated like the set DEQ of all pairs of indices of functions with the same domain, the set DMIN of all minimal indices of sets and DMIN⁎ of all indices which are minimal with respect to equality of the domain modulo finitely many differences. A partial solution to a question of Schaefer is obtained by showing that for every universal numbering with the Kolmogorov property, the set DMIN⁎ is Turing equivalent to the double jump of the halting problem. Furthermore, it is shown that the join of DEQ and the halting problem is Turing equivalent to the jump of the halting problem and that there are numberings for which DEQ itself has 1-generic Turing degree.

The main topics of the present work are universal machines for plain and prefix-free description complexity and their domains. It is characterised when an r.e. set W is the domain of a universal plain machine in terms of the description complexity of the spectrum function sW mapping each non-negative integer n to the number of all strings of length n in W; furthermore, a characterisation of the same style is given for supersets of domains of universal plain machines. Similarly the prefix-free sets which are domains or supersets of domains of universal prefix-free machines are characterised. Furthermore, it is shown that the halting probability ΩV of an r.e. prefix-free set V containing the domain of a universal prefix-free machine is Martin-Löf random, while V may not be the domain of any universal prefix-free machine itself. Based on these investigations, the question whether every domain of a universal plain machine is the superset of the domain of some universal prefix-free machine is discussed. A negative answer to this question had been presented at CiE 2010 by Mikhail Andreev, Ilya Razenshteyn and Alexander Shen, while this paper was under review.

We reformulate the theory of ludics introduced by J.-Y. Girard from a computational point of view. We introduce a handy term syntax for designs, the main objects of ludics. Our syntax also incorporates explicit cuts for attaining computational expressivity. In addition, we consider design generators that allow for finite representation of some infinite designs. A normalization procedure in the style of Krivine’s abstract machine directly works on generators, giving rise to an effective means of computation over infinite designs.The acceptance relation between machines and words, a basic concept in computability theory, is well expressed in ludics by the orthogonality relation between designs. Fundamental properties of ludics are then discussed in this concrete context. We prove three characterization results that clarify the computational powers of three classes of designs. (i) Arbitrary designs may capture arbitrary sets of finite data. (ii) When restricted to finitely generated ones, designs exactly capture the recursively enumerable languages. (iii) When further restricted to cut-free ones as in Girard’s original definition, designs exactly capture the regular languages.We finally describe a way of defining data sets by means of logical connectives, where the internal completeness theorem plays an essential role.

In computability theory, program self-reference is formalized by the not-necessarily-constructive form of Kleene's Recursion Theorem (krt). In a programming system in which krt holds, for any preassigned, algorithmic task, there exists a program that, in a sense, creates a copy of itself, and then performs that task using the self-copy. Interpreted in this way, such self-copying programs have usable self-knowledge. Herein, properties complementary to krt are considered. Of particular interest are those properties involving the implementation of control structures. One main result is that no property involving the implementation of denotational control structures is complementary to krt. This is in contrast to a result of Royer, which showed that implementation of if-then-else — a denotational control structure — is complementary to the constructive form of Kleene's Recursion Theorem. Examples of non-denotational control structures whose implementation is complementary to krt are then given. Some such control structures so nearly resemble denotational control structures that they might be called quasi-denotational.

It is sometimes suggested that the history of computation in cognitive science is one in which the formal apparatus of Turing-equivalent computation, or effective computability, was exported from mathematical logic to ever wider areas of cognitive science and its environs. This paper, however, indicates some respects in which this suggestion is inaccurate. Computability theory has not been focused exclusively on Turing-equivalent computation. Many essential features of Turing-equivalent computation are not captured in definitions of computation as (digital) symbol manipulation. Turing-equivalent computation did not play the role in McCulloch and Pitts’s early cybernetic work that is sometimes attributed to it. Finally, various segments of the neuroscientific community invoke a notion of computation that differs from the Turing-equivalent notion.

For every real number β>1, the β-shift is a dynamical system describing iterations of the map x ↦ β x mod 1 and is studied intensively in number theory. Each β-shift has an associated language of finite strings of characters; properties of this language are studied for the additional insight they give into the dynamics of the underlying system. We prove that the language of the β-shift is recursive iff β is a computable real number. That fact yields a precise characterization of the reals: The real numbers β for which we can compute arbitrarily good approximations—hence in particular the numbers for which we can compute their expansion to some base—are precisely those for which there exists a program that decides for any finite sequence of digits whether the sequence occurs as a subword of some element of the β-shift. While the “only if” part of the proof of the above result is constructive, the “if” part is not. We show that no constructive proof of the “if” part exists. Hence, there exists no algorithm that transforms a program computing arbitrarily good approximations of a real number β into a program deciding the language of the β-shift.

In dealing with emergent phenomena, a common task is to identify useful descriptions of them in terms of the underlying atomic processes, and to extract enough computational content from these descriptions to enable predictions to be made. Generally, the underlying atomic processes are quite well understood, and (with important exceptions) captured by mathematics from which it is relatively easy to extract algorithmic content. A widespread view is that the difficulty in describing transitions from algorithmic activity to the emergence associated with chaotic situations is a simple case of complexity outstripping computational resources and human ingenuity. Or, on the other hand, that phenomena transcending the standard Turing model of computation, if they exist, must necessarily lie outside the domain of classical computability theory. In this talk we suggest that much of the current confusion arises from conceptual gaps and the lack of a suitably fundamental model within which to situate emergence. We examine the potential for placing emergent relations in a familiar context based on Turing's 1939 model for interactive computation over structures described in terms of reals. The explanatory power of this model is explored, formalising informal descriptions in terms of mathematical definability and invariance, and relating a range of basic scientific puzzles to results and intractable problems in computability theory.

Universality is one of the most important ideas in computability theory. There are various criteria of simplicity for universal Turing machines. Probably the most popular one is to count the number of states/symbols. This criterion is more complex than it may appear at a first glance. In this note we review recent results in Algorithmic Information Theory and propose three new criteria of simplicity for universal prefix-free Turing machines. These criteria refer to the possibility of proving various natural properties of such a machine (its universality, for example) in a formal theory, PA or ZFC. In all cases some, but not all, machines are simple.

The interest is in characterizing insightfully the power of program self-reference in effective programming systems ( $\mathsf{epses}$), the computability-theoretic analogs of programming languages (for the partial computable functions). In an $\mathsf{eps}$in which the constructive form of Kleene’s Recursion Theorem (KRT) holds, it is possible to construct, algorithmically, from an arbitrary algorithmic task, a self-referential program that, in a sense, creates a self-copy and then performs that task on the self-copy. In an $\mathsf{eps}$in which the not-necessarily-constructive form of Kleene’s Recursion Theorem (krt) holds, such self-referential programs exist, but cannot, in general, be found algorithmically. In an earlier effort, Royer proved that there is no collection of recursive denotational control structures whose implementability characterizes the $\mathsf{epses}$in which KRT holds. One main result herein, proven by a finite injury priority argument, is that the $\mathsf{epses}$in which krt holds are, similarly, not characterized by the implementability of some collection of recursive denotational control structures. On the positive side, however, a characterization of such $\mathsf{epses}$of a rather different sort is shown herein. Though, perhaps not the insightful characterization sought after, this surprising result reveals that a hidden and inherent constructivity is always present in krt.

The settling time reducibility ordering gives an ordering on computably enumerable sets based on their enumerations. The

A classic result known as the speed-up theorem in machine-independent complexity theory shows that there exist some computable functions that do not have best programs for them (Blum in J. ACM 14(2):322–336, 1967 and J. ACM 18(2):290–305, 1971). In this paper we lift this result into type-2 computations. Although the speed-up phenomenon is essentially inherited from type-1 computations, we observe that a direct application of the original proof to our type-2 speed-up theorem is problematic because the oracle queries can interfere with the speed of the programs and hence the cancellation strategy used in the original proof is no longer correct at type-2. We also argue that a type-2 analog of the operator speed-up theorem (Meyer and Fischer in J. Symb. Log. 37:55–68, 1972) does not hold, which suggests that this curious speed-up phenomenon disappears in higher-typed computations beyond type-2. The result of this paper adds one more piece of evidence to support the general type-2 complexity theory under the framework proposed in Li (Proceedings of the Third International Conference on Theoretical Computer Science, pp. 471–484, 2004 and Proceedings of Computability in Europe: Logical Approach to Computational Barriers, pp. 182–192, 2006) and Li and Royer (On type-2 complexity classes: Preliminary report, pp. 123–138, 2001) as a reasonable setup.

A consistent learner is required to correctly and completely reflect in its actual hypothesis all data received so far. Though this demand sounds quite plausible, it may lead to the unsolvability of the learning problem. Therefore, in the present paper several variations of consistent learning are introduced and studied. These variations allow a so-called @d-delay relaxing the consistency demand to all but the last @d data. Additionally, we introduce the notion of coherent learning (again with @d-delay) requiring the learner to correctly reflect only the last datum (only the [email protected] datum) seen. Our results are manyfold. First, we provide characterizations for consistent learning with @d-delay in terms of complexity and computable numberings. Second, we establish strict hierarchies for all consistent learning models with @d-delay in dependence on @d. Finally, it is shown that all models of coherent learning with @d-delay are exactly as powerful as their corresponding consistent learning models with @d-delay.