We show how Kreisel's representation theorem for sets in the analytical hierarchy can be generalized to sets defined by positive induction and use this to estimate the complexity of constructions in the theory of domains with totality.

In this note, we consider constraints on the physical possibility of transfinite Turing machines that arise from how one models the continuous structure of space and time in one's best physical theories. We conclude by suggesting a version of Church's thesis appropriate as an upper bound for physical computation given how space and time are modeled on our current physical theories.

We use the theory of domains with totality to construct some logics generalizing ω-logic and β-logic and we prove a completenes theorem for these logics. The key application is E-logic, the logic related to the functional 3E. We prove a compactness theorem for sets of sentences semicomputable in 3E.

Transfinite recursion is an essential component of set theory. In this paper, we seek intrinsically justified reasons for believing in recursion and the notions of higher computation that surround it. In doing this, we consider several kinds of recursion principles and prove results concerning their relation to one another. We then consider philosophical motivations for these formal principles coming from the idea that computational notions lie at the core of our conception of set. This is significant because, while (...) the iterative conception of set has been widely recognized as insufficient to establish replacement and recursion, its supplementation by considerations pertaining to algorithms suggests a new and philosophically well-motivated reason to believe in such principles. (shrink)

This book presents new results in computability theory, a branch of mathematical logic and computer science that has become increasingly relevant in recent years. The field's connections with disparate areas of mathematical logic and mathematics more generally have grown deeper, and now have a variety of applications in topology, group theory, and other subfields. This monograph establishes new directions in the field, blending classic results with modern research areas such as algorithmic randomness. The significance of the book lies not only (...) in the depth of the results contained therein, but also in the fact that the notions the authors introduce allow them to unify results from several subfields of computability theory. (shrink)

Ordinal Computability discusses models of computation obtained by generalizing classical models, such as Turing machines or register machines, to transfinite working time and space. In particular, recognizability, randomness, and applications to other areas of mathematics, including set theory and model theory, are covered.

Context: Consistency of mathematical constructions in numerical analysis and the application of computerized proofs in the light of the occurrence of numerical chaos in simple systems. Purpose: To show that a computer in general and a numerical analysis in particular can add its own peculiarities to the subject under study. Hence the need of thorough theoretical studies on chaos in numerical simulation. Hence, a questioning of what e.g. a numerical disproof of a theorem in physics or a prediction in numerical (...) economics could mean. Method: An algebraic simple model system is subjected to a deeper structure of underlying variables. With an algorithm simulating the steps in taking a limit of second order difference quotients the error terms are studied at the background of their algebraic expression. Results: With the algorithm that was applied to a simple quadratic polynomial system we found unstably amplified round-off errors. The possibility of numerical chaos is already known but not in such a simple system as used in our paper. The amplification of the errors implies that it is not possible with computer means to constructively show that the algebra and numerical analysis will ‘on the long run’ converge to each other and the error term will vanish. The algebraic vanishing of the error term cannot be demonstrated with the use of the computer because the round-off errors are amplified. In philosophical terms, the amplification of the round-off error is equivalent to the continuum hypothesis. This means that the requirement of (numerical) construction of mathematical objects is no safeguard against inference-only conclusions of qualities of (numerical) mathematical objects. Unstably amplified round-off errors are a same type of problem as the ordering in size of transfinite cardinal numbers. The difference is that the former problem is created within the requirements of constructive mathematics. This can be seen as the reward for working numerically constructive. (shrink)

This book constitutes the refereed proceedings of the 7th Conference on Computability in Europe, CiE 2011, held in Sofia, Bulgaria, in June/July 2011. The 22 revised papers presented together with 11 invited lectures were carefully reviewed and selected with an acceptance rate of under 40%. The papers cover the topics computability in analysis, algebra, and geometry; classical computability theory; natural computing; relations between the physical world and formal models of computability; theory of transfinite computations; and computational linguistics.

In [7], open questions are raised regarding the computational strengths of so-called ∞-α -Turing machines, a family of models of computation resembling the infinite-time Turing machine model of [2], except with α -length tape . Let TαTα denote the machine model of tape length α . Define that TαTα is computationally stronger than TβTβ precisely when TαTα can compute all TβTβ-computable functions ƒ: min2→min2 plus more. The following results are found: Tω1≻TωTω1≻Tω. There are countable ordinals α such that Tα≻TωTα≻Tω, (...) the smallest of which is precisely γ , the supremum of ordinals clockable by TωTω. In fact, there is a hierarchy of countable TαTαs of increasing strength corresponding to the transfinite Turing-jump operator ▼. There is a countable ordinal μ such that neither Tμ⪰Tω1Tμ⪰Tω1 nor Tμ⪯Tω1Tμ⪯Tω1—that is, the models TμTμ and Tω1Tω1 are computation-strength incommensurable . A similar fact holds for any larger uncountable device replacing Tω1Tω1. Further observations are made about countable TαTα. (shrink)

Hay and, then, Johnson extended the classic Rice and Rice-Shapiro Theorems for computably enumerable sets, to analogs for all the higher levels in the finite Ershov Hierarchy. The present paper extends their work to analogs in the transfinite Ershov Hierarchy. Some of the transfinite cases are done for all transfinite notations in Kleene's important system of notations, equation image. Other cases are done for all transfinite notations in a very natural, proper subsystem equation image of equation (...) image, where equation image has at least one notation for each constructive ordinal. In these latter cases it is open as to what happens for the entire set of transfinite notations in equation image. (shrink)

We study the computational content of various theorems with reverse mathematical strength around Arithmetical Transfinite Recursion (ATR_0) from the point of view of computability-theoretic reducibilities, in particular Weihrauch reducibility. Our main result states that it is equally hard to construct an embedding between two given well-orderings, as it is to construct a Turing jump hierarchy on a given well-ordering. This answers a question of Marcone. We obtain a similar result for Fraïssé's conjecture restricted to well-orderings.

Preface -- 1. Propositional logic : proofs from axioms and inference rules -- 2. First order logic : proofs with quantifiers -- 3. Set theory : proofs by detachment, contraposition, and contradiction -- 4. Mathematical induction : definitions and proofs by induction -- 5. Well-formed sets : proofs by transfinite induction with already well-ordered sets -- 6. The axiom of choice : proofs by transfinite induction -- 7. applications : Nobel-Prize winning applications of sets, functions, and relations -- (...) 8. Solutions to some odd-numbered exercises. (shrink)

We analyse Kreisel’s notion of human-effective computability. Like Kreisel, we relate this notion to a concept of informal provability, but we disagree with Kreisel about the precise way in which this is best done. The resulting two different ways of analysing human-effective computability give rise to two different variants of Church’s thesis. These are both investigated by relating them to transfinite progressions of formal theories in the sense of Feferman.

We study the complexity of (finitely-valued and transfinitely-valued) Euclidean functions for computable Euclidean domains. We examine both the complexity of the minimal Euclidean function and any Euclidean function. Additionally, we draw some conclusions about the proof-theoretical strength of minimal Euclidean functions in terms of reverse mathematics.

This article shows that Rabbi Pinchas Elijah Hurwitz, a major eighteenth-century kabbalist, Orthodox rabbi and Enlightenment thinker, who merged Lurianic Kabbalah with Kantian philosophy, attempted to describe God and the world in terms of formal grammars and abstract information processes. He resolves a number of Kant's dualistic views by introducing prophecy as a tool that allows a mystic's mind to perform transfinite hypercomputation and to obtain a priori knowledge about things usually known only a posteriori. According to Hurwitz, the (...) reality consists of Divine names, which generate an infinite network of recursive string rewriting systems, some of which are identical to what is known today as Lindenmayer systems. Hurwitz is also one of the first thinkers, who raised questions about non-human and artificial intelligence. (shrink)

Numbers. Natural numbers -- Integers -- Real numbers -- Irrational and transcendental numbers -- Funny numbers. Zero -- e : the unnatural natural number -- [Phi] : the golden ratio -- i : the imaginary number -- Writing numbers. Roman numerals -- Egyptian fractions -- Continued fractions -- Logic. Mr. Spock is not logical -- Proofs, truth, and trees : oh my! -- Programming with logic -- Temporal reasoning -- Sets. Cantor's diagonalization : infinity isn't just infinity -- Axiomatic set (...) theory : keep the good, dump the bad -- Models : using sets as the LEGOs of the math world -- Transfinite numbers : counting and ordering infinite sets -- Group theory : finding symmetries with sets -- Mechanical math. Finite state machines : simplicity goes far -- The turing machine -- Pathology and the heart of computing -- Calculus : no, not that calculus- [lambda] calculus -- Numbers, booleans, and recursion -- Types, types, types : modeling [lambda] calculus -- The halting problem. (shrink)

α-recursion lifts classical recursion theory from the first transfinite ordinal ω to an arbitrary admissible ordinal α [10]. Idealized computational models for α-recursion analogous to Turing machine models for classical recursion have been proposed and studied [4] and [5] and are applicable in computational approaches to the foundations of logic and mathematics [8]. They also provide a natural setting for modeling extensions of the algorithmic logic described in [1] and [2]. On such models, an α-Turing machine can complete a (...) θ-step computation for any ordinal θ < α. Here we consider constraints on the physical realization of α-Turing machines that arise from the structure of physical spacetime. In particular, we show that an α-Turing machine is realizable in a spacetime constructed from R only if α is countable. While there are spacetimes where uncountable computations are possible and while they may even be empirically distinguishable from a standard spacetime, there is good reason to suppose that such nonstandard spacetimes are nonphysical. We conclude with a suggestion for a revision of Church’s thesis appropriate as an upper bound for physical computation. (shrink)

Infinite time Turing machines represent a model of computability that extends the operations of Turing machines to transfinite ordinal time by defining the content of each cell at limit steps to be the lim sup of the sequences of previous contents of that cell. In this paper, we study a computational model obtained by replacing the lim sup rule with an ‘eventually constant’ rule: at each limit step, the value of each cell is defined if and only if the (...) content of that cell has stabilized before that limit step and is then equal to this constant value. We call these machines weak infinite time Turing machines. We study different variants of wITTMs adding multiple tapes, heads, or bidimensional tapes. We show that some of these models are equivalent to each other concerning their computational strength. We show that wITTMs decide exactly the arithmetic relations on natural numbers. (shrink)

We prove that the first-order logic of CZF is intuitionistic first-order logic. To do so, we introduce a new model of transfinite computation (Set Register Machines) and combine the resulting notion of realisability with Beth semantics. On the way, we also show that the propositional admissible rules of CZF are exactly those of intuitionistic propositional logic.

The prelims comprise: Introduction Programs and Theories Finite Digital Physics Transfinite Digital Physics The Physics of Computation Conclusion.

If the computational theory of mind is right, then minds are realized by machines. There is an ordered complexity hierarchy of machines. Some finite machines realize finitely complex minds; some Turing machines realize potentially infinitely complex minds. There are many logically possible machines whose powers exceed the Church–Turing limit (e.g. accelerating Turing machines). Some of these supermachines realize superminds. Superminds perform cognitive supertasks. Their thoughts are formed in infinitary languages. They perceive and manipulate the infinite detail of fractal objects. They (...) have infinitely complex bodies. Transfinite games anchor their social relations. (shrink)

Infinite time Turing machines extend the operation of ordinary Turing machines into transfinite ordinal time. By doing so, they provide a natural model of infinitary computability, a theoretical setting for the analysis of the power and limitations of supertask algorithms.

I use modal logic and transfinite set-theory to define metaphysical foundations for a general theory of computation. A possible universe is a certain kind of situation; a situation is a set of facts. An algorithm is a certain kind of inductively defined property. A machine is a series of situations that instantiates an algorithm in a certain way. There are finite as well as transfinite algorithms and machines of any degree of complexity (e.g., Turing and super-Turing machines (...) and more). There are physically and metaphysically possible machines. There is an iterative hierarchy of logically possible machines in the iterative hierarchy of sets. Some algorithms are such that machines that instantiate them are minds. So there is an iterative hierarchy of finitely and transfinitely complex minds. (shrink)

Infinite time Turing machines extend the operation of ordinary Turing machines into transfinite ordinal time. By doing so, they provide a natural model of infinitary computability, a theoretical setting for the analysis of the power and limitations of supertask algorithms.

In this paper Lucas comes back to Gödelian argument against Mecanism to clarify some points. First of all, he explains his use of Gödel’s theorem instead of Turing’s theorem, showing how Gödel’ theorem, but not Turing’s theorem, raises questions concerning truth and reasoning that bear on the nature of mind and how Turing’s theorem suggests that there is something that cannot be done by any computers but not that it can be done by human minds. He considers moreover how Gödel’s (...) theorem can be interpreted as a sophisticated form of the Cretan paradox, posed by Epimenides, able to escape the viciously self-referential nature of the Cretan paradox, and how it can be used against Mechanism as a schema of disproof. Finally, Lucas suggests some answers to the most recurrent criticisms against his argument: criticisms about the implicit idealisation in the way he set up the context between mind and machine; questions concerning modality and finitude, issues of transfinite arithmetic; questions concerning the need of formalizing rational inference and some questions about consistency. (shrink)

Infinite time Turing machines extend the operation of ordinary Turing machines into transfinite ordinal time. By doing so, they provide a natural model of infinitary computability, a theoretical setting for the analysis of the power and limitations of supertask algorithms.

We give a partial answer to an important open problem in descriptive set theory, the Decomposability Conjecture for Borel functions on an analytic subset of a Polish space to a separable metrizable space. Our techniques employ deep results from effective descriptive set theory and recursion theory. In fact it is essential to extend several prominent results in recursion theory (e.g. the Shore-Slaman Join Theorem) to the setting of Polish spaces. As a by-product we give both positive and negative results on (...) the Martin Conjecture on the degree preserving Borel functions between Polish spaces. Additionally we prove results about the transfinite version as well as the computable version of the Decomposability Conjecture. (shrink)

I present a hypothetical account of how the ancients might have come to introduce mathematical objects in order to describe patterns, and I explain how working with patterns can generate information about the mathematical realm. The ancients might have started using what I call templates, i.e. concrete devices, like blueprints or drawings, to represent how things are shaped or structured, and this could have evolved into representing the abstract patterns that concrete things might fit. In this way, they might have (...) come to believe that written constructions and computations could provide information about the mathematical realm, for by their very nature, patterns should be structurally analogous to their templates and in positing that they are, one simply projects onto structures and features already attributed to templates. By reflecting on systems of dots representing cardinalities, the ancients could generate a body of results that then evolved into a systematic theory of numbers, but the approach fails when there is no direct connection between the computations and the patterns they are supposed to concern, e.g. those concerning trigonometric functions or transfinite ordinal numbers. In these cases, we forge a connection between proofs and patterns by positing that the premises of the proofs state uncontroversial features of the patterns, i.e. the premises constitute implicit definitions of the patterns. I explain how this position does not entail that mathematics is analytic or a priori. (shrink)

Foundational questions in logic, mathematics, computer science and physics are constant sources of epistemological debate in contemporary philosophy. To what extent is the transfinite part of mathematics completely trustworthy? Why is there a general 'malaise' concerning the logical approach to the foundations of mathematics? What is the role of symmetry in physics? Is it possible to build a coherent worldview compatible with a macroobjectivistic position and based on the quantum picture of the world? What account can be given of (...) opinion change in the light of new evidence? These are some of the questions discussed in this volume, which collects 14 lectures on the foundations of science given at the School of Philosophy of Science, Trieste, October 1989. The volume will be of particular interest to any student or scholar engaged in interdisciplinary research into the foundations of science in the context of contemporary debates. (shrink)

Schmerl and Beklemishev’s work on iterated reflection achieves two aims: it introduces the important notion of \-ordinal, characterizing the \-theorems of a theory in terms of transfinite iterations of consistency; and it provides an innovative calculus to compute the \-ordinals for a range of theories. The present note demonstrates that these achievements are independent: we read off \-ordinals from a Schütte-style ordinal analysis via infinite proofs, in a direct and transparent way.

We gather the following miscellaneous results in proof theory from the attic.1. 1. A provably well-founded elementary ordering admits an elementary order preserving map.2. 2. A simple proof of an elementary bound for cut elimination in propositional calculus and its applications to separation problem in relativized bounded arithmetic below S21.3. 3. Equivalents for Bar Induction, e.g., reflection schema for ω logic.4. 4. Direct computations in an equational calculus PRE and a decidability problem for provable inequations in PRE.5. 5. Intuitionistic fixed (...) point theories which are conservative extensions of HA.6. 6. Proof theoretic strengths of classical fixed points theories.7. 7. An equivalence between transfinite induction rule and iterated reflection schema over IΣn.8. 8. Derivation lengths of finite rewrite rules reducing under lexicographic path orders and multiply recursive functions.Each section can be read separately in principle. (shrink)

Martin’s conjecture is an attempt to classify the behavior of all definable functions on the Turing degrees under strong set theoretic hypotheses. Very roughly it says that every such function is either eventually constant, eventually equal to the identity function or eventually equal to a transfinite iterate of the Turing jump. It is typically divided into two parts: the first part states that every function is either eventually constant or eventually above the identity function and the second part states (...) that every function which is above the identity is eventually equal to a transfinite iterate of the jump. If true, it would provide an explanation for the unique role of the Turing jump in computability theory and rule out many types of constructions on the Turing degrees.In this thesis, we will introduce a few tools which we use to prove several cases of Martin’s conjecture. It turns out that both these tools and these results on Martin’s conjecture have some interesting consequences both for Martin’s conjecture and for a few related topics.The main tool that we introduce is a basis theorem for perfect sets, improving a theorem due to Groszek and Slaman. We also introduce a general framework for proving certain special cases of Martin’s conjecture which unifies a few pre-existing proofs. We will use these tools to prove three main results about Martin’s conjecture: that it holds for regressive functions on the hyperarithmetic degrees, that part 1 holds for order preserving functions on the Turing degrees, and that part 1 holds for a class of functions that we introduce, called measure preserving functions.This last result has several interesting consequences for the study of Martin’s conjecture. In particular, it shows that part 1 of Martin’s conjecture is equivalent to a statement about the Rudin-Keisler order on ultrafilters on the Turing degrees. This suggests several possible strategies for working on part 1 of Martin’s conjecture, which we will discuss.The basis theorem that we use to prove these results also has some applications outside of Martin’s conjecture. We will use it to prove a few theorems related to Sacks’ question about whether it is provable in $\mathsf {ZFC}$ that every locally countable partial order of size continuum embeds into the Turing degrees. We will show that in a certain extension of $\mathsf {ZF}$, this holds for all partial orders of height two, but not for all partial orders of height three. Our proof also yields an analogous result for Borel partial orders and Borel embeddings in $\mathsf {ZF}$, which shows that the Borel version of Sacks’ question has a negative answer.We will end the thesis with a list of open questions related to Martin’s conjecture, which we hope will stimulate further research.prepared by Patrick Lutz.E-mail: [email protected]. (shrink)

It is shown that the classes of discrete parts, A ∩ ℕk, of approximately resp. weakly decidable subsets of Euclidean spaces, A ⊆ ℝk, coincide and are equal to the class of ω-r. e. sets which is well-known as the first transfinite level in Ershov's hierarchy exhausting Δ02.

Sections 1 through 4 define, in the usual inductive style, various classes of object including one which is called the “combinatory terms of polymorphic type”. Section 5 defines a reduction relation on these terms. Section 6 shows that the weak normalizability of the combinatory terms of polymorphic type entails the weak normalizability of the lambda terms of polymorphic type. The entailment is not vacuous, because the combinatory terms of polymorphic type are indeed weakly normalizable, as is proven in Sect. 7 (...) using Tait and Girard’s computability predicates. The remainder of the paper is devoted to arguing that interesting consequences would follow from the existence of an “ordinally informative” proof, i.e. one which uses transfinite induction over recursive ordinal numbers and otherwise finitary methods, of normalizability for as large a class of the terms as possible. (shrink)

We investigate a new paradigm in the context of learning in the limit, namely, learning correction grammars for classes of computably enumerable (c.e.) languages. Knowing a language may feature a representation of it in terms of two grammars. The second grammar is used to make corrections to the first grammar. Such a pair of grammars can be seen as a single description of (or grammar for) the language. We call such grammars correction grammars. Correction grammars capture the observable fact that (...) people do correct their linguistic utterances during their usual linguistic activities. We show that learning correction grammars for classes of c.e. languages in the TxtEx-model (i.e., converging to a single correct correction grammar in the limit) is sometimes more powerful than learning ordinary grammars even in the TxtBe-model (where the learner is allowed to converge to infinitely many syntactically distinct but correct conjectures in the limit). For each n ≥ 0, there is a similar learning advantage, again in learning correction grammars for classes of c.e. languages, but where we compare learning correction grammars that make n + 1 corrections to those that make n corrections. The concept of a correction grammar can be extended into the constructive transfinite, using the idea of counting-down from notations for transfinite constructive ordinals. This transfinite extension can also be conceptualized as being about learning Ershov-descriptions for c.e. languages. For u a notation in Kleene's general system $(O,\, < _o )$ of ordinal notations for constructive ordinals, we introduce the concept of an u-correction grammar, where u is used to bound the number of corrections that the grammar is allowed to make. We prove a general hierarchy result: if u and v are notations for constructive ordinals such that $u\, < _o \,v$ , then there are classes of c.e. languages that can be TxtEx-learned by conjecturing v-correction grammars but not by conjecturing u-correction grammars. Surprisingly, we show that— above "ω-many" corrections—it is not possible to strengthen the hierarchy: TxtEx-learning u-correction grammars of classes of c.e. languages, where u is a notation in O for any ordinal, can be simulated by TxtBe-learning ω-correction grammars, where ω is any notation for the smallest infinite ordinal ω. (shrink)

We present some characterizations of the members of Δta2, that class of the topological arithmetical hierarchy which is just large enough to include several fundamental types of sets of points in Euclidean spaces ℝk. The limit characterization serves as a basic tool in further investigations. The characterization by effective difference chains of effectively exhaustible sets yields only a hierarchy within a subfield of Δta2. Effective difference chains of transfinite (but constructive) order types, consisting of complements of effectively exhaustible sets, (...) as well as another closely related concept, yield a rich hierarchy within the whole class Δta2. The presentation always first reports analogies between Hausdorff's difference hierarchy within the Borel class ΔB2 and Ershov's hierarchy within the class Δ02 of the arithmetical hierarchy; after that the counterparts for Δta2 are developed. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim). (shrink)

We present some characterizations of the members of Δta2, that class of the topological arithmetical hierarchy which is just large enough to include several fundamental types of sets of points in Euclidean spaces ℝk. The limit characterization serves as a basic tool in further investigations. The characterization by effective difference chains of effectively exhaustible sets yields only a hierarchy within a subfield of Δta2. Effective difference chains of transfinite order types, consisting of complements of effectively exhaustible sets, as well (...) as another closely related concept, yield a rich hierarchy within the whole class Δta2. The presentation always first reports analogies between Hausdorff's difference hierarchy within the Borel class ΔB2 and Ershov's hierarchy within the class Δ02 of the arithmetical hierarchy; after that the counterparts for Δta2 are developed. (shrink)

Arthur Clark and Michael Kube–McDowell (“The Triger”, 2000) suggested the sci-fi idea about the direct transformation from a chemical substance to another by the action of a newly physical, “Trigger” field. Karl Brohier, a Nobel Prize winner, who is a dramatic persona in the novel, elaborates a new theory, re-reading and re-writing Pauling’s “The Nature of the Chemical Bond”; according to Brohier: “Information organizes and differentiates energy. It regularizes and stabilizes matter. Information propagates through matter-energy and mediates the interactions of (...) matter-energy.” Dr Horton, his collaborator in the novel replies: “If the universe consists of energy and information, then the Trigger somehow alters the information envelope of certain substances –“. “Alters it, scrambles it, overwhelms it, destabilizes it” Brohier adds. There is a scientific debate whether or how far chemistry is fundamentally reducible to quantum mechanics. Nevertheless, the fact that many essential chemical properties and reactions are at least partly representable in terms of quantum mechanics is doubtless. For the quantum mechanics itself has been reformulated as a theory of a special kind of information, quantum information, chemistry might be in turn interpreted in the same terms. Wave function, the fundamental concept of quantum mechanics, can be equivalently defined as a series of qubits, eventually infinite. A qubit, being defined as the normed superposition of the two orthogonal subspaces of the complex Hilbert space, can be interpreted as a generalization of the standard bit of information as to infinite sets or series. All “forces” in the Standard model, which are furthermore essential for chemical transformations, are groups [U(1),SU(2),SU(3)] of the transformations of the complex Hilbert space and thus, of series of qubits. One can suggest that any chemical substances and changes are fundamentally representable as quantum information and its transformations. If entanglement is interpreted as a physical field, though any group above seems to be unattachable to it, it might be identified as the “Triger field”. It might cause a direct transformation of any chemical substance by from a remote distance. Is this possible in principle? (shrink)

One recursively enumerable real α dominates another one β if there are nondecreasing recursive sequences of rational numbers (a[n] : n ∈ ω) approximating α and (b[n] : n ∈ ω) approximating β and a positive constant C such that for all n, C(α − a[n]) ≥ (β − b[n]). See [R. M. Solovay, Draft of a Paper (or Series of Papers) on Chaitin’s Work, manuscript, IBM Thomas J. Watson Research Center, Yorktown Heights, NY, 1974, p. 215] and [G. J. (...) Chaitin, IBM J. Res. Develop., 21 (1977), pp. 350–359]. We show that every recursively enumerable random real dominates all other recursively enumerable reals. We conclude that the recursively enumerable random reals are exactly the Ω-numbers [G. J. Chaitin, IBM J. Res. Develop., 21 (1977), pp. 350–359]. Second, we show that the sets in a universal Martin-Lof test for randomness have random measure, and every recursively enumerable random number is the sum of the measures represented in a universal Martin-Lof test. (shrink)

The contribution of the body to cognition and control in natural and artificial agents is increasingly described as “off-loading computation from the brain to the body”, where the body is said to perform “morphological computation”. Our investigation of four characteristic cases of morphological computation in animals and robots shows that the ‘off-loading’ perspective is misleading. Actually, the contribution of body morphology to cognition and control is rarely computational, in any useful sense of the word. We thus distinguish (...) (1) morphology that facilitates control, (2) morphology that facilitates perception and the rare cases of (3) morphological computation proper, such as ‘reservoir computing.’ where the body is actually used for computation. This result contributes to the understanding of the relation between embodiment and computation: The question for robot design and cognitive science is not whether computation is offloaded to the body, but to what extent the body facilitates cognition and control – how it contributes to the overall ‘orchestration’ of intelligent behaviour. (shrink)

A basic deep neural network (DNN) is trained to exhibit a large set of input–output dispositions. While being a good model of the way humans perform some tasks automatically, without deliberative reasoning, more is needed to approach human‐like artificial intelligence. Analysing recent additions brings to light a distinction between two fundamentally different styles of computation: content‐specific and non‐content‐specific computation (as first defined here). For example, deep episodic RL networks draw on both. So does human conceptual reasoning. Combining the (...) two takes advantage of the complementary costs and benefits of each. It also offers a better model of human cognitive competence. (shrink)

To compute is to execute an algorithm. More precisely, to say that a device or organ computes is to say that there exists a modelling relationship of a certain kind between it and a formal specification of an algorithm and supporting architecture. The key issue is to delimit the phrase of a certain kind. I call this the problem of distinguishing between standard and nonstandard models of computation. The successful drawing of this distinction guards Turing's 1936 analysis of (...) class='Hi'>computation against a difficulty that has persistently been raised against it, and undercuts various objections that have been made to the computational theory of mind. (shrink)

An influential view in cognitive science is that computation in cognitive systems is semantic, conceptually depending on representation: to compute is to manipulate representations. I argue that accepting the non-semantic teleomechanistic view of computation lays the ground for a promising alternative strategy, in which computation helps to explain and naturalise representation, rather than the other way around. I show that this computation-based approach to representation presents six decisive advantages over the semantic view. I claim that it (...) can improve the two most influential current theories of representation, teleosemantics and structural representation, by providing them with precious tools to tackle some of their main shortcomings. In addition, the computation-based approach opens up interesting new theoretical paths for the project of naturalising representation, in which teleology plays a role in individuating computations, but not representations. (shrink)

Turing computation over a non-linguistic domain presupposes a notation for the domain. Accordingly, computability theory studies notations for various non-linguistic domains. It illuminates how different ways of representing a domain support different finite mechanical procedures over that domain. Formal definitions and theorems yield a principled classification of notations based upon their computational properties. To understand computability theory, we must recognize that representation is a key target of mathematical inquiry. We must also recognize that computability theory is an intensional enterprise: (...) it studies entities as represented in certain ways, rather than entities detached from any means of representing them. (shrink)

Although computation and the science of physical systems would appear to be unrelated, there are a number of ways in which computational and physical concepts can be brought together in ways that illuminate both. This volume examines fundamental questions which connect scholars from both disciplines: is the universe a computer? Can a universal computing machine simulate every physical process? What is the source of the computational power of quantum computers? Are computational approaches to solving physical problems and paradoxes always (...) fruitful? Contributors from multiple perspectives reflecting the diversity of thought regarding these interconnections address many of the most important developments and debates within this exciting area of research. Both a reference to the state of the art and a valuable and accessible entry to interdisciplinary work, the volume will interest researchers and students working in physics, computer science, and philosophy of science and mathematics. (shrink)