From the initial analysis of John Morris in 1976 about if computers can lie, I have presented my own treatment of the problem using what can be called a computational lying procedure. One that uses two Turing Machines. From there, I have argued that such a procedure cannot be implemented in a Turing Machine alone. A fundamental difficulty arises, concerning the computational representation of the self-knowledge a machine should have about the fact that it is lying. Contrary to Morris’ claim, (...) I have thus suggested that computers – as far as they are Turing Machines – cannot lie. Consequently, I have claimed that moral agency attribution to a robot or any other automated AI system, cannot be made, strictly grounded on imitating behaviors. Self-awareness as an ontological grounding for moral attribution must be evoked. This can pose a recognition problem from our part, should the sentient system be the only agent capable of acknowledging its own sentience. (shrink)

The counterfactual account of physical computation is simple and, for the most part, very attractive. However, it is usually thought to trivialize the notion of physical computation insofar as it implies ‘limited pancomputationalism’, this being the doctrine that every deterministic physical system computes some function. Should we bite the bullet and accept limited pancomputationalism, or reject the counterfactual account as untenable? Jack Copeland would have us do neither of the above. He attempts to thread a path between the two horns (...) of the dilemma by buttressing the counterfactual account with extra conditions intended to block certain classes of deterministic physical systems from qualifying as physical computers. His theory is called the ‘algorithm execution account’. Here we show that the algorithm execution account entails limited pancomputationalism, despite Copeland’s argument to the contrary. We suggest, partly on this basis, that the counterfactual account should be accepted as it stands, pancomputationalist warts and all. (shrink)

Gödel's Incompleteness Theorems have the same scientific status as Einstein's principle of relativity, Heisenberg's uncertainty principle, and Watson and Crick's double helix model of DNA. Our aim is to discuss some new faces of the incompleteness phenomenon unveiled by an information-theoretic approach to randomness and recent developments in quantum computing.

Recent work on hypercomputation has raised new objections against the Church–Turing Thesis. In this paper, I focus on the challenge posed by a particular kind of hypercomputer, namely, SAD computers. I first consider deterministic and probabilistic barriers to the physical possibility of SAD computation. These suggest several ways to defend a Physical version of the Church–Turing Thesis. I then argue against Hogarth's analogy between non-Turing computability and non-Euclidean geometry, showing that it is a non-sequitur. I conclude that the Effective version (...) of the Church–Turing Thesis is unaffected by SAD computation. (shrink)

The four authors present their speculations about the future developments of mathematical logic in the twenty-first century. The areas of recursion theory, proof theory and logic for computer science, model theory, and set theory are discussed independently.

In contrast to dominant approaches to human reason involving essentially a logical and instrumental conception of rationality easily modeled by artificial intelligence mechanisms, I argue that the specific capacities of the human mind are meta-analytic in nature, understood as irreducible to the analytic or the logical, or else the computational. Firstly, the assumption of a meta-analytical level of rationality is derived from key insights developed in various branches of the social sciences. This meta-analytical level is then inferred from Gödel’s incompleteness (...) theorem. On these bases, and with the help of psychological approaches to consciousness, I argue that human rationality may be characterized as the capacity to make meaningful use of signs. (shrink)

Kripke’s argument against functionalism extended to physical computers poses a deep philosophical problem for understanding the standard view of what computers are. The problem puts into jeopardy the definition in the standard view that computers are physical machines for performing physical computations. Indeed, it is entirely possible that, unless this philosophical problem is resolved, we will never have a good understanding of computers and may never know just what they are.

Though there is yet no consensus on the right way to understand ‘physicalism’, most philosophers agree that, regardless of whatever else is required, physicalism cannot be true if there exists fundamental mentality. I will follow Jessica Wilson (Philosophical Studies 131:61–99, 2006) in calling this the 'No Fundamental Mentality' (NFM) constraint on physicalism. Unfortunately for those who wish to constrain physicalism in this way, NFM admits of a counterexample: an artificially intelligent quantum computer which employs quantum properties as part of its (...) cognitive operations. If one of these quantum properties serves a proper functional role in the artificial intelligence, then that property counts as a mental under the physicalism-friendly theory of mentality called “realizer functionalism”, which says that a lower-order property is mental if it satisfies an appropriate higher-order functional description. Further, if this quantum property is both fundamental and mental, then NFM must rule that it is not physical. Yet the existence of such an artificially intelligent quantum computer, which possesses mental properties solely in virtue of the functional roles those properties play, is surely consistent with the truth of physicalism. This ought to motivate NFM proponents to reformulate their view. (shrink)

Computability theory is used to evaluate the complexity of classifying various kinds of Lebesgue spaces and associated isometric isomorphism problems.

How can the medium be addressed when it is always already saturated in religious over-determinations and ever marked by theological concerns (such as revelation and incarnation) while, at the same time, religion would not be practiced and theology not be done without using some such medium? We encourage methodological and conceptual shifts, first, from medium to mediality; second, from religion to its partial negation (or, perhaps, partial permeation); third, from theology to doing the theological differently. With these shifts we desire (...) to initiate, continue, and intensify debates, specifically between theologians and scholars of religious studies and media theory. (shrink)

Fetzer famously claims that program verification is not even a theoretical possibility, and offers a certain argument for this far-reaching claim. Unfortunately for Fetzer, and like-minded thinkers, this position-argument pair, while based on a seminal insight that program verification, despite its Platonic proof-theoretic airs, is plagued by the inevitable unreliability of messy, real-world causation, is demonstrably self-refuting. As I soon show, Fetzer is like the person who claims: ‘My sole claim is that every claim expressed by an English sentence and (...) starting with the phrase “My sole claim” is false’. Or, more accurately, such thinkers are like the person who claims that modus tollens is invalid, and supports this claim by giving an argument that itself employs this rule of inference. (shrink)

Steven Pinker's How the mind works (HTMW) marks in my opinion an historic point in the history of humankind's attempt to understand itself. Socrates delivered his "know thyself" imperative rather long ago, and now, finally, in this behemoth of a book, published at the dawn of a new millennium, Pinker steps up to have psychology tell us what we are: computers crafted by evolution - end of story; mystery solved; and the poor philosophers, having never managed to obey Socrates' command, (...) are left alone to wander in the labyrinth of their benighted speculation forever. Unfortunately, though HTMW is to this point the crowning attempt of psychology to make systematic sense of persons by integrating everything relevant science knows, the book fails - and it fails so fundamentally and irremediably that we would do well to wonder anew whether we should supplant the basic view it promotes with what I call the super-mind hypothesis: the view that though mere animals are evolved computers, persons are more. (shrink)

I articulate a novel modal argument for P=NP.

In this paper we discuss the views on the Turing test of four influential thinkers who belong to the tradition of analytic philosophy: Ludwig Wittgenstein, Noam Chomsky, Hilary Putnam and John Searle. Based on various beliefs about philosophical and/or linguistic matters, they arrive at different assessments of both the significance and suitability of the imitation game for the development of cognitive science and AI models. Nevertheless, they share a rejection of the idea that one can treat Turing test as a (...) test for “machine thinking.” This seems to stem from a concern for the proper use of language —one that is a fundamental methodological commitment of analytic philosophy. (shrink)

Which function is computed by a Turing machine will depend on how the symbols it manipulates are interpreted. Further, by invoking bizarre systems of notation it is easy to define Turing machines that compute textbook examples of uncomputable functions, such as the solution to the decision problem for first-order logic. Thus, the distinction between computable and uncomputable functions depends on the system of notation used. This raises the question: which systems of notation are the relevant ones for determining whether a (...) function is computable? These are the acceptable notations. I argue for a use criterion of acceptability: the acceptable notations for a domain of objects D\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {D}}$$\end{document} are the notations that we can use for the usual D\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {D}}$$\end{document}-activities. Acceptable notations for natural numbers are ones that we can count with. Acceptable notations for logical formulas are the ones that we can use in inference and logical analysis. And so on. This criterion makes computability a relative notion—whether a function is computable depends on which notations are acceptable, which is relative to our interests and abilities. I argue that this is not a problem, however, since there is independent reason for taking the extension of computable function to be relative to contingent facts. Similarly, the fact that the use criterion makes a mathematical distinction depend on practical concerns is also not a problem because it dovetails with similar phenomena in other areas of computability theory, namely the roles of notation in computation over real numbers and of Extended Church’s Thesis in complexity theory. (shrink)

The classical Hahn–Banach Theorem states that any linear bounded functional defined on a linear subspace of a normed space admits a norm-preserving linear bounded extension to the whole space. The constructive and computational content of this theorem has been studied by Bishop, Bridges, Metakides, Nerode, Shore, Kalantari Downey, Ishihara and others and it is known that the theorem does not admit a general computable version. We prove a new computable version of this theorem without unrolling the classical proof of the (...) theorem itself. More precisely, we study computability properties of the uniform extension operator which maps each functional and subspace to the set of corresponding extensions. It turns out that this operator is upper semi-computable in a well-defined sense. By applying a computable version of the Banach–Alaoglu Theorem we can show that computing a Hahn–Banach extension cannot be harder than finding a zero in a compact metric space. This allows us to conclude that the Hahn–Banach extension operator is ${\bf {\Sigma^{0}_{2}}}$ -computable while it is easy to see that it is not lower semi-computable in general. Moreover, we can derive computable versions of the Hahn–Banach Theorem for those functionals and subspaces which admit unique extensions. (shrink)

Given a program of a linear bounded and bijective operator T, does there exist a program for the inverse operator T−1? And if this is the case, does there exist a general algorithm to transfer a program of T into a program of T−1? This is the inversion problem for computable linear operators on Banach spaces in its non-uniform and uniform formulation, respectively. We study this problem from the point of view of computable analysis which is the Turing machine based (...) theory of computability on Euclidean space and other topological spaces. Using a computable version of Banach’s Inverse Mapping Theorem we can answer the first question positively. Hence, the non-uniform version of the inversion problem is solvable, while a topological argument shows that the uniform version is not. Thus, we are in the striking situation that any computable linear operator has a computable inverse while there exists no general algorithmic procedure to transfer a program of the operator into a program of its inverse. As a consequence, the computable version of Banach’s Inverse Mapping Theorem is a powerful tool which can be used to produce highly non-constructive existence proofs of algorithms. We apply this method to prove that a certain initial value problem admits a computable solution. As a preparation of Banach’s Inverse Mapping Theorem we also study the Open Mapping Theorem and we show that the uniform versions of both theorems are limit computable, which means that they are effectively -measurable with respect to the effective Borel hierarchy. (shrink)

This paper argues that the idea of a computer is unique. Calculators and analog computers are not different ideas about computers, and nature does not compute by itself. Computers, once clearly defined in all their terms and mechanisms, rather than enumerated by behavioral examples, can be more than instrumental tools in science, and more than source of analogies and taxonomies in philosophy. They can help us understand semantic content and its relation to form. This can be achieved because they have (...) the potential to do more than calculators, which are computers that are designed not to learn. Today’s computers are not designed to learn; rather, they are designed to support learning; therefore, any theory of content tested by computers that currently exist must be of an empirical, rather than a formal nature. If they are designed someday to learn, we will see a change in roles, requiring an empirical theory about the Turing architecture’s content, using the primitives of learning machines. This way of thinking, which I call the intensional view of computers, avoids the problems of analogies between minds and computers. It focuses on the constitutive properties of computers, such as showing clearly how they can help us avoid the infinite regress in interpretation, and how we can clarify the terms of the suggested mechanisms to facilitate a useful debate. Within the intensional view, syntax and content in the context of computers become two ends of physically realizing correspondence problems in various domains. (shrink)

Because it is time-dependent, parallel computation is fundamentally different from sequential computation. Parallel programs are non-deterministic and are not effective procedures. Given the brain operates in parallel, this casts doubt on AI's attempt to make sequential computers intelligent.

The history of laboratories may become controversial in social sciences. In this paper, the story of Sciences Po Médialab told by Venturini et al. is discussed and completed by demonstrating the incoherence in the choice of digital methods at the Médialab from the actor network theory perspective. As the Médialab mostly used web topologies as structural analysis of social positions, they were not able to account for the propagation of ideas, considered in actor network theory as non-humans that have their (...) own agency. The main arguments in favour of the ‘more continuous social’ developed at the Médialab proved to be as misleading as the network metaphor. The distribution of agency that actor network theory so successfully expands was paradoxicallty reduced to structures and individual preferences, to the detriment of the agency of replications that circulate entities in the form of messages, content or memes, and that should now become the next step for actor network theory-style digital methods. (shrink)

If the Trade Descriptions Act were applied to academic labels, cognitive scientists would be in trouble. For what they do is much wider than the name suggests—and wider, too, than most philosophers assume. They give you more for your money than you may have expected.

The choice construct (choose x: φ(x)) is useful in software specifications. We study extensions of first-order logic with the choice construct. We prove some results about Hilbert's ε operator, but in the main part of the paper we consider the case when all choices are independent.

In addition to his famous Chinese Room argument, John Searle has posed a more radical problem for views on which minds can be understood as programs. Even his wall, he claims, implements the WordStar program according to the standard definition of implementation because there is some ‘‘pattern of molecule movements’’ that is isomorphic to the formal structure of WordStar. Program implementation, Searle charges, is merely observer-relative and thus not an intrinsic feature of the world. I argue, first, that analogous charges (...) involving other concepts (motion and meaning) lead to consequences no one accepts. Second, I show that Searle’s treatment of computation is incoherent, yielding the consequence that nothing computes anything: even our standard personal computers fail to run any programs on this account. I propose an alternative account, one that accords with the way engineers, programmers, and cognitive scientists use the concept of computation in their empirical work. This alternative interpretation provides the basis of a philosophical analysis of program implementation, one that may yet be suitable for a computational theory of the mind. (shrink)

Arguments to the effect that Church's thesis is intrinsically unprovable because proof cannot relate an informal, intuitive concept to a mathematically defined one are unconvincing, since other 'theses' of this kind have indeed been proved, and Church's thesis has been proved in one direction. However, though evidence for the truth of the thesis in the other direction is overwhelming, it does not yet amount to proof.

Artificial Neural Networks have reached “grandmaster” and even “super-human” performance across a variety of games, from those involving perfect information, such as Go, to those involving imperfect information, such as “Starcraft”. Such technological developments from artificial intelligence (AI) labs have ushered concomitant applications across the world of business, where an “AI” brand-tag is quickly becoming ubiquitous. A corollary of such widespread commercial deployment is that when AI gets things wrong—an autonomous vehicle crashes, a chatbot exhibits “racist” behavior, automated credit-scoring processes (...) “discriminate” on gender, etc.—there are often significant financial, legal, and brand consequences, and the incident becomes major news. As Judea Pearl sees it, the underlying reason for such mistakes is that “... all the impressive achievements of deep learning amount to just curve fitting.” The key, as Pearl suggests, is to replace “reasoning by association” with “causal reasoning” —the ability to infer causes from observed phenomena. It is a point that was echoed by Gary Marcus and Ernest Davis in a recent piece for theNew York Times: “we need to stop building computer systems that merely get better and better at detecting statistical patterns in data sets—often using an approach known as ‘Deep Learning’—and start building computer systems that from the moment of their assembly innately grasp three basic concepts: time, space, and causality.” In this paper, foregrounding what in 1949 Gilbert Ryle termed “a category mistake”, I will offer an alternative explanation for AI errors; it is not so much that AI machinery cannot “grasp” causality, but that AI machinery (qua computation) cannot understand anything at all. (shrink)

The notion of a ‘symbol’ plays an important role in the disciplines of Philosophy, Psychology, Computer Science, and Cognitive Science. However, there is comparatively little agreement on how this notion is to be understood, either between disciplines, or even within particular disciplines. This paper does not attempt to defend some putatively ‘correct’ version of the concept of a ‘symbol.’ Rather, some terminological conventions are suggested, some constraints are proposed and a taxonomy of the kinds of issue that give rise to (...) disagreement is articulated. The goal here is to provide something like a ‘geography’ of the various notions of ‘symbol’ that have appeared in the various literatures, so as to highlight the key issues and to permit the focusing of attention upon the important dimensions. In particular, the relationship between ‘tokens’ and ‘symbols’ is addressed. The issue of designation is discussed in some detail. The distinction between simple and complex symbols is clarified and an apparently necessary condition for a system to be potentially symbol, or token bearing, is introduced. (shrink)

Digital physics claims that the entire universe is, at the very bottom, made out of bits; as a result, all physical processes are intrinsically computational. For that reason, many digital physicists go further and affirm that the universe is indeed a giant computer. The aim of this article is to make explicit the ontological assumptions underlying such a view. Our main concern is to clarify what kind of properties the universe must instantiate in order to perform computations. We analyse the (...) logical form of the two models of computation traditionally adopted in digital physics, namely, cellular automata and Turing machines. These models are computationally equivalent, but we show that they support different ontological commitments about the fundamental properties of the universe. In fact, cellular automata are compatible with a rather traditional form of physicalism, whereas Turing machines support a dualistic ontology, which could be understood as a realism about the laws of nature or, alternatively, as a kind of panpsychism. (shrink)

This introduction begins by posing the question that this Special Issue addresses and briefly considers historical precedents and why the issue is important. The discussion then moves on to the consideration of important milestones in the history of computing, up until the present time. A brief specification of the essential components of computational systems is then offered. The final section introduces the papers that are included in this volume.

Dual Process Theory is currently a popular theory for explaining why we show bounded rationality in reasoning and decision-making tasks. This theory proposes there must be a sharp distinction in thinking to explain two clusters of correlational features. One cluster describes a fast and intuitive process, while the other describes a slow and reflective one. A problem for this theory is identifying a common principle that binds these features together, explaining why they form a unity, the unity problem. To solve (...) it, a hypothesis is developed combining embodied predictive processing with symbolic classical approaches. The hypothesis, simplified, states that Type 1 processes are bound together because they rely on embodied predictive processing whereas Type 2 processes form a unity because they are accomplished by symbolic classical cognition. To show that this is likely the case, the features of Dual Process Theory are discussed in relation to these frameworks. (shrink)

Computer simulations and experiments share many important features. One way of explaining the similarities is to say that computer simulations just are experiments. This claim is quite popular in the literature. The aim of this paper is to argue against the claim and to develop an alternative explanation of why computer simulations resemble experiments. To this purpose, experiment is characterized in terms of an intervention on a system and of the observation of the reaction. Thus, if computer simulations are experiments, (...) either the computer hardware or the target system must be intervened on and observed. I argue against the first option using the non-observation argument, among others. The second option is excluded by e.g. the over-control argument, which stresses epistemological differences between experiments and simulations. To account for the similarities between experiments and computer simulations, I propose to say that computer simulations can model possible experiments and do in fact often do so. (shrink)

We have begun a theory of measurement in which an experimenter and his or her experimental procedure are modeled by algorithms that interact with physical equipment through a simple abstract interface. The theory is based upon using models of physical equipment as oracles to Turing machines. This allows us to investigate the computability and computational complexity of measurement processes. We examine eight different experiments that make measurements and, by introducing the idea of an observable indicator, we identify three distinct forms (...) of measurement process and three types of measurement algorithm. We give axiomatic specifications of three forms of interfaces that enable the three types of experiment to be used as oracles to Turing machines, and lemmas that help certify an experiment satisfies the axiomatic specifications. For experiments that satisfy our axiomatic specifications, we give lower bounds on the computational power of Turing machines in polynomial time using nonuniform complexity classes. These lower bounds break the barrier defined by the Church-Turing Thesis. (shrink)

Cognitive psychologists, like biologists, frequently describe mechanisms when explaining phenomena. Unlike biologists, who can often trace material transformations to identify operations, psychologists face a more daunting task in identifying operations that transform information. Behavior provides little guidance as to the nature of the operations involved. While not itself revealing the operations, identification of brain areas involved in psychological mechanisms can help constrain attempts to characterize the operations. In current memory research, evidence that the same brain areas are involved in what (...) are often taken to be different memory phenomena or in other cognitive phenomena is playing such a heuristic function. †To contact the author, please write to: Department of Philosophy, 0119, University of California, San Diego, La Jolla, CA 92093‐0119; e‐mail: [email protected]. (shrink)

Philosophy of science is positioned to make distinctive contributions to cognitive science by providing perspective on its conceptual foundations and by advancing normative recommendations. The philosophy of science I embrace is naturalistic in that it is grounded in the study of actual science. Focusing on explanation, I describe the recent development of a mechanistic philosophy of science from which I draw three normative consequences for cognitive science. First, insofar as cognitive mechanisms are information-processing mechanisms, cognitive science needs an account of (...) how the representations invoked in cognitive mechanisms carry information about contents, and I suggest that control theory offers the needed perspective on the relation of representations to contents. Second, I argue that cognitive science requires, but is still in search of, a catalog of cognitive operations that researchers can draw upon in explaining cognitive mechanisms. Last, I provide a new perspective on the relation of cognitive science to brain sciences, one which embraces both reductive research on neural components that figure in cognitive mechanisms and a concern with recomposing higher-level mechanisms from their components and situating them in their environments. (shrink)

Chaos-related obstructions to predictability have been used to challenge accounts of theory validation based on the agreement between theoretical predictions and experimental data. These challenges are incomplete in two respects: they do not show that chaotic regimes are unpredictable in principle and, as a result, that there is something conceptually wrong with idealized expectations of correct predictions from acceptable theories, and they do not explore whether chaos-induced predictive failures of deterministic models can be remedied by stochastic modeling. In this paper (...) we appeal to an asymptotic analysis of state space trajectories and their numerical approximations to show that chaotic regimes are deterministically unpredictable even with unbounded resources. Additionally, we explain why stochastic models of chaotic systems, while predictively successful in some cases, are in general predictively as limited as deterministic ones. We conclude by suggesting that the way in which scientists deal with such principled obstructions to predictability calls for a more comprehensive approach to theory validation, on which experimental testing is augmented by a multifaceted mathematical analysis of theoretical models, capable of identifying chaos-related predictive failures as due to principled limitations which the world itself imposes on any less-than-omniscient epistemic access to some natural systems. (shrink)

One of the most important contributions of A. Church to logic is his invention of the lambda calculus. We present the genesis of this theory and its two major areas of application: the representation of computations and the resulting functional programming languages on the one hand and the representation of reasoning and the resulting systems of computer mathematics on the other hand.

This paper reviews Benjamin Noys’ recent attempt in Malign Velocities: Accelerationism and Capitalism to mount a critique of accelerationism. The book, persuasive in certain respects, bypasses the institutional dynamics of accelerationism’s theoretical progenitors, viz. Nick Land and the Cybernetic Culture Research Unit of Warwick University, and instead portrays it as a “defeatist strategy” of the post-’68 conjuncture of “Deleuzian Thatcherism.” Such portrayal is debatable to the extent that it exhibits a questionable appropriation of “theory” in the strict sense of the (...) term; a term the paper attempts to define with reference to Matthew Arnold, Louis Althusser and Gilles Grelet. (shrink)

Given two infinite binary sequences A,B we say that B can compress at least as well as A if the prefix-free Kolmogorov complexity relative to B of any binary string is at most as much as the prefix-free Kolmogorov complexity relative to A, modulo a constant. This relation, introduced in Nies [14] and denoted by A≤LKB, is a measure of relative compressing power of oracles, in the same way that Turing reducibility is a measure of relative information. The equivalence classes (...) induced by ≤LK are called LK degrees and there is a least degree containing the oracles which can only compress as much as a computable oracle, also called the ‘low for K’ sets. A well-known result from Nies [14] states that these coincide with the K-trivial sets, which are the ones whose initial segments have minimal prefix-free Kolmogorov complexity. We show that with respect to ≤LK, given any non-trivial sets X,Y there is a computably enumerable set A which is not K-trivial and it is below X,Y. This shows that the local structures of and Turing degrees are not elementarily equivalent to the corresponding local structures in the LK degrees. It also shows that there is no pair of sets computable from the halting problem which forms a minimal pair in the LK degrees; this is sharp in terms of the jump, as it is known that there are sets computable from which form a minimal pair in the LK degrees. We also show that the structure of LK degrees below the LK degree of the halting problem is not elementarily equivalent to the or structures of LK degrees. The proofs introduce a new technique of permitting below a set that is not K-trivial, which is likely to have wider applications. (shrink)

Computability theory concerns information with a causal–typically algorithmic–structure. As such, it provides a schematic analysis of many naturally occurring situations. Emil Post was the first to focus on the close relationship between information, coded as real numbers, and its algorithmic infrastructure. Having characterised the close connection between the quantifier type of a real and the Turing jump operation, he looked for more subtle ways in which information entails a particular causal context. Specifically, he wanted to find simple relations on reals (...) which produced richness of local computability-theoretic structure. To this extent, he was not just interested in causal structure as an abstraction, but in the way in which this structure emerges in natural contexts. Post’s programme was the genesis of a more far reaching research project. In this article we will firstly review the history of Post’s programme, and look at two interesting developments of Post’s approach. The first of these developments concerns the extension of the core programme, initially restricted to the Turing structure of the computably enumerable sets of natural numbers, to the Ershov hierarchy of sets. The second looks at how new types of information coming from the recent growth of research into randomness, and the revealing of unexpected new computability-theoretic infrastructure. We will conclude by viewing Post’s programme from a more general perspective. We will look at how algorithmic structure does not just emerge mathematically from information, but how that emergent structure can model the emergence of very basic aspects of the real world. (shrink)

Whole brain emulation aims to re-implement functions of a mind in another computational substrate with the precision needed to predict the natural development of active states in as much as the influence of random processes allows. Furthermore, brain emulation does not present a possible model of a function, but rather presents the actual implementation of that function, based on the details of the circuitry of a specific brain. We introduce a notation for the representations of mind state, mind transition functions (...) and transition update functions, for which elements and their relations must be quantified in accordance with measurements in the biological substrate. To discover the limits of significance in terms of the temporal and spatial resolution of measurements, we point out the importance of brain region and task specific constraints, as well as the importance of in-vivo measurements. We summarize further problems that need to be addressed. (shrink)

Whole brain emulation aims to re-implement functions of a mind in another computational substrate with the precision needed to predict the natural development of active states in as much as the influence of random processes allows. Furthermore, brain emulation does not present a possible model of a function, but rather presents the actual implementation of that function, based on the details of the circuitry of a specific brain. We introduce a notation for the representations of mind state, mind transition functions (...) and transition update functions, for which elements and their relations must be quantified in accordance with measurements in the biological substrate. To discover the limits of significance in terms of the temporal and spatial resolution of measurements, we point out the importance of brain region and task specific constraints, as well as the importance of in-vivo measurements. We summarize further problems that need to be addressed. (shrink)

Several papers (e.g. [7, 23, 42]) have recently sought to give general frameworks for online structures and algorithms ([4]), and seeking to connect, if only by analogy, online and computable structure theory. These initiatives build on earlier work on online colouring and other combinatorial algorithms by Bean [10], Kierstead, Trotter et al. [48, 54, 57] and others, as we discuss below. In this paper we will look at such frameworks and illustrate them with examples from the first author’s MSc Thesis (...) ([58]). In this thesis, Askes looks at online, adversarial online and strongly online algorithms and structures. Additionally, we prove some new theorems about online algorithms on graphs of bounded pathwidth as well as some new results on punctually 1-decidable structures. (shrink)

Gottfried Wilhelm Leibniz is the self-proclaimed inventor of the binary system and is considered as such by most historians of mathematics and/or mathematicians. Really though, we owe the groundwork of today’s computing not to Leibniz but to the Englishman Thomas Harriot and the Spaniard Juan Caramuel de Lobkowitz, whom Leibniz plagiarized. This plagiarism has been identified on the basis of several facts: Caramuel’s work on the binary system is earlier than Leibniz’s, Leibniz was acquainted—both directly and indirectly—with Caramuel’s work and (...) Leibniz had a natural tendency to plagiarize scientific works. (shrink)