Current conceptions of the integration of computers into society often depend on the view that the human mind, as well as the computer, is a computational system. This view is widely taken to have broad implications for educational policy. We present a critique of the premise and some of the conclusions of the above argument. It is here shown that the thesis that the human mind is a computational system is, in principle, not scientifically supportable. It is also shown that, (...) even if the computational theory of mind were held for non-scientific reasons, the educational implications often derived from it do not follow. (shrink)

We focus on a particular class of computably enumerable degrees, the array noncomputable degrees defined by Downey, Jockusch, and Stob, to answer questions related to lattice embeddings and definability in the partial ordering of c. e. degrees under Turing reducibility. We demonstrate that the latticeM5 cannot be embedded into the c. e. degrees below every array noncomputable degree, or even below every nonlow array noncomputable degree. As Downey and Shore have proved that M5 can be embedded below every nonlow2 degree, (...) our result is the best possible in terms of array noncomputable degrees and jump classes. Further, this result shows that the array noncomputable degrees are definably different from the nonlow2 degrees. We note also that there are embeddings of M5 in which all five degrees are array noncomputable, and in which the bottom degree is the computable degree 0 but the other four are array noncomputable. (shrink)

We use a method suggested by Kolmogorov complexity to examine some relations between Kolmogorov complexity and noncomputability. In particular we show that the method consistently gives us more information than conventional ways of demonstrating noncomputability . Also, many sets which are awkward to embed into the halting problem are easily shown noncomputable. We also prove a gap-theorem for outputting consecutive integers and find, for a given length n, a statement of length n with maximal proof length.

I explain why, within the nonclassical framework for cognitive science we describe in the book, cognitive-state transitions can fail to be tractably computable even if they are subserved by a discrete dynamical system whose mathematical-state transitions are tractably computable. I distinguish two ways that cognitive processing might conform to programmable rules in which all operations that apply to representation-level structure are primitive, and two corresponding constraints on models of cognition. Although Litch is correct in maintaining that classical cognitive science is (...) not committed to the first constraint, it is committed to the second. This fact constitutes an illuminating gloss on our claim that one foundational assumption of classicism is that human cognition conforms to programmable, representation-level, rules. (shrink)

We examine notions of genericity intermediate between 1-genericity and 2-genericity, especially in relation to the Δ20 degrees. We define a new kind of genericity, dynamic genericity, and prove that it is stronger than pb-genericity. Specifically, we show there is a Δ20 pb-generic degree below which the pb-generic degrees fail to be downward dense and that pb-generic degrees are downward dense below every dynamically generic degree. To do so, we examine the relation between genericity and array noncomputability, deriving some structural (...) information about the Δ20 degrees in the process. (shrink)

John Searle and Roger Penrose are two staunch critics of computationalism who nonetheIess believe that with the right framework the mind can be naturalized. while they may be successful in showing the shortcomings of computationalism, I argue that their alternative noncomputational frameworks equally fail to carry out the project to naturalize the mind. The main reason is their failure to resolve some fundamental incompatibilities between mind and science. Searle tries to resolve the incompatibility between the subjectivity of consciousness and the (...) objectivity of silence by means of conceptual clarification. He, howeve4 fails to deal with the concepts crucial to this incompatibility, namely, the publicness of scientific knowledge and the privacy of psychological knowledge. Penrose tries to resolve the incompatibility between the non-computationality of psychological process and the computationality of scientific process by expanding the scope of science through some radical changes in quantum physics. His strategy, howeve4 has the danger of trivializing the distinction between science and non-science thereby putting into question the very value of the project to naturalize the mind. In addition, the feasibility of this strategy remains dubious in light of the mysteries that still surround quantum physics. (shrink)

Algebraic/topological descriptions of living processes are indispensable to the understanding of both biological and cognitive functions. This paper presents a fundamental algebraic description of living/cognitive processes and exposes its inherent ambiguity. Since ambiguity is forbidden to computation, no computational description can lend insight to inherently ambiguous processes. The impredicativity of these models is not a flaw, but is, rather, their strength. It enables us to reason with ambiguous mathematical representations of ambiguous natural processes. The noncomputability of these structures means (...) computerized simulacra of them are uninformative of their key properties. This leads to the question of how we should reason about them. That question is answered in this paper by presenting an example of such reasoning, the demonstration of a topological strategy for understanding how the fundamental structure can form itself from within itself. (shrink)

We show: for every noncomputable c.e. incomplete c-degree, there exists a nonspeedable c-degree incomparable with it; The c-degree of a hypersimple set includes an infinite collection of \-degrees linearly ordered under \ with order type of the integers and consisting entirely of hypersimple sets; there exist two c.e. sets having no c.e. least upper bound in the \-reducibility ordering; the c.e. \-degrees are not dense.

In _Reconstructing the Cognitive World_, Michael Wheeler argues that we should turn away from the generically Cartesian philosophical foundations of much contemporary cognitive science research and proposes instead a Heideggerian approach. Wheeler begins with an interpretation of Descartes. He defines Cartesian psychology as a conceptual framework of explanatory principles and shows how each of these principles is part of the deep assumptions of orthodox cognitive science. Wheeler then turns to Heidegger's radically non-Cartesian account of everyday cognition, which, he argues, can (...) be used to articulate the philosophical foundations of a genuinely non-Cartesian cognitive science. Finding that Heidegger's critique of Cartesian thinking falls short, even when supported by Hubert Dreyfus's influential critique of orthodox artificial intelligence, Wheeler suggests a new Heideggerian approach. He points to recent research in "embodied-embedded" cognitive science and proposes a Heideggerian framework to identify, amplify, and clarify the underlying philosophical foundations of this new work. He focuses much of his investigation on recent work in artificial intelligence-oriented robotics, discussing, among other topics, the nature and status of representational explanation, and whether cognition is computation rather than a noncomputational phenomenon best described in the language of dynamical systems theory. Wheeler's argument draws on analytic philosophy, continental philosophy, and empirical work to "reconstruct" the philosophical foundations of cognitive science in a time of a fundamental shift away from a generically Cartesian approach. His analysis demonstrates that Heideggerian continental philosophy and naturalistic cognitive science need not be mutually exclusive and shows further that a Heideggerian framework can act as the "conceptual glue" for new work in cognitive science. (shrink)

A computable structure $\mathcal {A}$ is $\mathbf {x}$-computably categorical for some Turing degree $\mathbf {x}$ if for every computable structure $\mathcal {B}\cong\mathcal {A}$ there is an isomorphism $f:\mathcal {B}\to\mathcal {A}$ with $f\leq_{T}\mathbf {x}$. A degree $\mathbf {x}$ is a degree of categoricity if there is a computable structure $\mathcal {A}$ such that $\mathcal {A}$ is $\mathbf {x}$-computably categorical, and for all $\mathbf {y}$, if $\mathcal {A}$ is $\mathbf {y}$-computably categorical, then $\mathbf {x}\leq_{T}\mathbf {y}$. We construct a $\Sigma^{0}_{2}$ set whose degree (...) is not a degree of categoricity. We also demonstrate a large class of degrees that are not degrees of categoricity by showing that every degree of a set which is 2-generic relative to some perfect tree is not a degree of categoricity. Finally, we prove that every noncomputable hyperimmune-free degree is not a degree of categoricity. (shrink)

Ramsey’s theorem asserts that every k-coloring of $[\omega ]^n$ admits an infinite monochromatic set. Whenever $n \geq 3$, there exists a computable k-coloring of $[\omega ]^n$ whose solutions compute the halting set. On the other hand, for every computable k-coloring of $[\omega ]^2$ and every noncomputable set C, there is an infinite monochromatic set H such that $C \not \leq _T H$. The latter property is known as cone avoidance.In this article, we design a natural class of Ramsey-like theorems encompassing (...) many statements studied in reverse mathematics. We prove that this class admits a maximal statement satisfying cone avoidance and use it as a criterion to re-obtain many existing proofs of cone avoidance. This maximal statement asserts the existence, for every k-coloring of $[\omega ]^n$, of an infinite subdomain $H \subseteq \omega $ over which the coloring depends only on the sparsity of its elements. This confirms the intuition that Ramsey-like theorems compute Turing degrees only through the sparsity of its solutions. (shrink)

We prove that there exists a noncomputable c.e. real which is low for weak 2-randomness, a definition of randomness due to Kurtz, and that all reals which are low for weak 2-randomness are low for Martin-Löf randomness.

Gödel appears to have believed strongly that the human mind cannot be explained in terms of any kind of computational physics, but he remained cautious in formulating this belief as a rigorous consequence of his incompleteness theorems. In this chapter, I discuss a modification of standard Gödel-type logical arguments, these appearing to strengthen Gödel’s conclusions, and attempt to provide a persuasive case in support of his standpoint that the actions of the mind must transcend computation. It appears that Gödel did (...) not consider the possibility that the laws of physics might themselves involve noncomputational procedures; accordingly, he found himself driven to the conclusion that mentality must lie beyond the actions of the physical brain. My own arguments, on the other hand, are from the scientific standpoint that the mind is a product of the brain’s physical activity. Accordingly, there must be something in the physical actions of the world that itself transcends computation. We do not appear to find such noncomputational action in the known laws of physics, however, so we must seek it in currently undiscovered laws going beyond presently accepted physical theory. I argue that the only plausibly relevant gap in current understanding lies in a fundamental incompleteness in quantum theory, which reveals itself only with significant mass displacements between quantum states (“Schrödinger’s cats”). I contend that the need for new physics enters when gravitational effects just begin to play a role. In a scheme developed jointly with Stuart Hameroff, this has direct relevance within neuronal microtubules, and I describe this (still speculative) scheme in the following. (shrink)

It was shown by Cholak, Jockusch, and Slaman that every computable 2-coloring of pairs admits an infinite low₂ homogeneous set H. We answer a question of the same authors by showing that H may be chosen to satisfy in addition $C\,\not \leqslant _T \,H$, where C is a given noncomputable set. This is shown by analyzing a new and simplified proof of Seetapun's cone avoidance theorem for Ramsey's theorem. We then extend the result to show that every computable 2-coloring of (...) pairs admits a pair of low₂ infinite homogeneous sets whose degrees form a minimal pair. (shrink)

Answering a question in the reverse mathematics of combinatorial principles, we prove that the thin set theorem for pairs ) implies the diagonally noncomputable set principle over the base axiom system $\mathrm{RCA}_{0}$.

We show the existence of noncomputable oracles which are low for Demuth randomness, answering a question in [15]. We fully characterize lowness for Demuth randomness using an appropriate notion of traceability. Central to this characterization is a partial relativization of Demuth randomness, which may be more natural than the fully relativized version. We also show that an oracle is low for weak Demuth randomness if and only if it is computable.

This dissertation is an investigation into the degree to which the mathematics used in physical theories can be constructivized. The techniques of recursive function theory and classical logic are used to separate out the algorithmic content of mathematical theories rather than attempting to reformulate them in terms of "intuitionistic" logic. The guiding question is: are there experimentally testable predictions in physics which are not computable from the data? ;The nature of Church's thesis, that the class of effectively calculable functions on (...) the natural numbers is identical to the class of general recursive functions, is discussed. It is argued that this thesis is an example of an explication of the very notion of an effectively calculable function. This is contrary to a view of the thesis as a hypothesis about the limitations of the human mind. ;The extension to functions of a real variable of the notion of effective calculability is discussed, and it is argued that a function of a real variable must be continuous in order to be considered effectively calculable . The relation between continuity and computability is significant for the problem at hand. The results of a well-designed experiment do not depend critically upon the precise values of the relevant parameters. Accordingly, if the solution to a problem in mathematical physics depends discontinuously upon the data, it cannot be regarded as an experimentally testable prediction of the theory. The principle that the testable predictions of a physical theory cannot be singular is known as the principle of regularity. This principle is significant, because discontinuities generate non-computability, but they also disqualify a prediction from being experimentally testable. ;A mathematical framework is set up for discussing computability in physical theories. This framework is then applied to the case of quantum mechanics. It is found that, due to the use of unbounded operators in the theory, noncomputable objects appear, but predictions which satisfy the principle of regularity are nevertheless computable functions of the data. (shrink)

Let M be a smooth, compact manifold of dimension n ≥ 5 and sectional curvature | K | ≤ 1. Let Met (M) = Riem(M)/Diff(M) be the space of Riemannian metrics on M modulo isometries. Nabutovsky and Weinberger studied the connected components of sublevel sets (and local minima) for certain functions on Met (M) such as the diameter. They showed that for every Turing machine T e , e ∈ ω, there is a sequence (uniformly effective in e) of homology (...) n-spheres {P k e } k ∈ ω which are also hypersurfaces, such that P k e is diffeomorphic to the standard n-sphere S n (denoted P k e ≈ diff S n ) iff T e halts on input k, and in this case the connected sum N k e =M ♯ P k e ≈ diff M , so N k e ∈ Met(M), and N k e is associated with a local minimum of the diameter function on Met(M) whose depth is roughly equal to the settling time σ e (k) of T e on inputs y i } ∈ ω of c.e. sets so that for all i the settling time of the associated Turing machine for A i dominates that for A i + 1 , even when the latter is composed with an arbitrary computable function. From this, Nabutovsky and Weinberger showed that the basins exhibit a "fractal" like behavior with extremely big basins, and very much smaller basins coming off them, and so on. This reveals what Nabutovsky and Weinberger describe in their paper on fractals as "the astonishing richness of the space of Riemannian metrics on a smooth manifold, up to reparametrization." From the point of view of logic and computability, the Nabutovsky-Weinberger results are especially interesting because: (1) they use c.e. sets to prove structural complexity of the geometry and topology, not merely undecidability results as in the word problem for groups, Hilbert's Tenth Problem, or most other applications; (2) they use nontrivial information about c.e. sets, the Soare sequence {A i } i ∈ ω above, not merely G öodel's c.e. noncomputable set K of the 1930's; and (3) without using computability theory there is no known proof that local minima exist even for simple manifolds like the torus T 5 (see §). (shrink)

We work with weakly precomplete equivalence relations introduced by Badaev. The weak precompleteness is a natural notion inspired by various fixed point theorems in computability theory. Let E be an equivalence relation on the set of natural numbers $$\omega $$, having at least two classes. A total function f is a diagonal function for E if for every x, the numbers x and f(x) are not E-equivalent. It is known that in the case of c.e. relations E, the weak precompleteness (...) of E is equivalent to the lack of computable diagonal functions for E. Here we prove that this result fails already for $$\Delta ^0_2$$ equivalence relations, starting with the $$\Pi ^{-1}_2$$ level. We focus on the Turing degrees of possible diagonal functions. We prove that for any noncomputable c.e. degree $${\textbf{d}}$$, there exists a weakly precomplete c.e. equivalence E admitting a $${\textbf{d}}$$ -computable diagonal function. We observe that a Turing degree $${\textbf{d}}$$ can compute a diagonal function for every $$\Delta ^0_2$$ equivalence relation E if and only if $${\textbf{d}}$$ computes $${\textbf{0}}'$$. On the other hand, every PA degree can compute a diagonal function for an arbitrary c.e. equivalence E. In addition, if $${\textbf{d}}$$ computes diagonal functions for all c.e. E, then $${\textbf{d}}$$ must be a DNC degree. (shrink)

We give a rough statement of the main result. Let D be a compact subset of ℝ3× ℝ. The propagation u of a wave can be noncomputable in any neighborhood of any point of D even though the initial conditions which determine the wave propagation uniquely are computable. A precise statement of the result appears below.

Although there is a substantial philosophical literature on dynamical systems theory in the cognitive sciences, the same is not the case for neuroscience. This paper attempts to motivate increased discussion via a set of overlapping issues. The first aim is primarily historical and is to demonstrate that dynamical systems theory is currently experiencing a renaissance in neuroscience. Although dynamical concepts and methods are becoming increasingly popular in contemporary neuroscience, the general approach should not be viewed as something entirely new to (...) neuroscience. Instead, it is more appropriate to view the current developments as making central again approaches that facilitated some of neuroscience’s most significant early achievements, namely, the Hodgkin–Huxley and FitzHugh–Nagumo models. The second aim is primarily critical and defends a version of the “dynamical hypothesis” in neuroscience. Whereas the original version centered on defending a noncomputational and nonrepresentational account of cognition, the version I have in mind is broader and includes both cognition and the neural systems that realize it as well. In view of that, I discuss research on motor control as a paradigmatic example demonstrating that the concepts and methods of dynamical systems theory are increasingly and successfully being applied to neural systems in contemporary neuroscience. More significantly, such applications are motivating a stronger metaphysical claim, that is, understanding neural systems as being dynamical systems, which includes not requiring appeal to representations to explain or understand those phenomena. Taken together, the historical claim and the critical claim demonstrate that the dynamical hypothesis is undergoing a renaissance in contemporary neuroscience. (shrink)

In this article the linguistic processes of consciousness are discussed at the informational and semantic levels. The key question is devoted to the distinction between the information, meaning and sense in the physical, logico-semantic and historic levels of brain and consciousness. The principal point runs that the human linguistic process of sense producing takes the variety and indistinctness in the cultural presupposition. The modern theories of philosophy of mind relying on the theories of Soviet psychological school propose some new solutions (...) in the pragmatic questions of the semantic noncomputability. In this review we will try to justify the dualistic correlation between the cultural base and the communicative semantic process. (shrink)

The tower number ${\mathfrak t}$ and the ultrafilter number $\mathfrak {u}$ are cardinal characteristics from set theory. They are based on combinatorial properties of classes of subsets of $\omega $ and the almost inclusion relation $\subseteq ^*$ between such subsets. We consider analogs of these cardinal characteristics in computability theory.We say that a sequence $(G_n)_{n \in {\mathbb N}}$ of computable sets is a tower if $G_0 = {\mathbb N}$, $G_{n+1} \subseteq ^* G_n$, and $G_n\smallsetminus G_{n+1}$ is infinite for each n. (...) A tower is maximal if there is no infinite computable set contained in all $G_n$. A tower ${\left \langle {G_n}\right \rangle }_{n\in \omega }$ is an ultrafilter base if for each computable R, there is n such that $G_n \subseteq ^* R$ or $G_n \subseteq ^* \overline R$ ; this property implies maximality of the tower. A sequence $(G_n)_{n \in {\mathbb N}}$ of sets can be encoded as the “columns” of a set $G\subseteq \mathbb N$. Our analogs of ${\mathfrak t}$ and ${\mathfrak u}$ are the mass problems of sets encoding maximal towers, and of sets encoding towers that are ultrafilter bases, respectively. The relative position of a cardinal characteristic broadly corresponds to the relative computational complexity of the mass problem. We use Medvedev reducibility to formalize relative computational complexity, and thus to compare such mass problems to known ones.We show that the mass problem of ultrafilter bases is equivalent to the mass problem of computing a function that dominates all computable functions, and hence, by Martin’s characterization, it captures highness. On the other hand, the mass problem for maximal towers is below the mass problem of computing a non-low set. We also show that some, but not all, noncomputable low sets compute maximal towers: Every noncomputable (low) c.e. set computes a maximal tower but no 1-generic $\Delta ^0_2$ -set does so.We finally consider the mass problems of maximal almost disjoint, and of maximal independent families. We show that they are Medvedev equivalent to maximal towers, and to ultrafilter bases, respectively. (shrink)

Although there is a substantial philosophical literature on dynamical systems theory in the cognitive sciences, the same is not the case for neuroscience. This paper attempts to motivate increased discussion via a set of overlapping issues. The first aim is primarily historical and is to demonstrate that dynamical systems theory is currently experiencing a renaissance in neuroscience. Although dynamical concepts and methods are becoming increasingly popular in contemporary neuroscience, the general approach should not be viewed as something entirely new to (...) neuroscience. Instead, it is more appropriate to view the current developments as making central again approaches that facilitated some of neuroscience’s most significant early achievements, namely, the Hodgkin–Huxley and FitzHugh–Nagumo models. The second aim is primarily critical and defends a version of the “dynamical hypothesis” in neuroscience. Whereas the original version centered on defending a noncomputational and nonrepresentational account of cognition, the version I have in mind is broader and includes both cognition and the neural systems that realize it as well. In view of that, I discuss research on motor control as a paradigmatic example demonstrating that the concepts and methods of dynamical systems theory are increasingly and successfully being applied to neural systems in contemporary neuroscience. More significantly, such applications are motivating a stronger metaphysical claim, that is, understanding neural systems as being dynamical systems, which includes not requiring appeal to representations to explain or understand those phenomena. Taken together, the historical claim and the critical claim demonstrate that the dynamical hypothesis is undergoing a renaissance in contemporary neuroscience. (shrink)

Certain enterprises at the fringes of science, such as intelligent design creationism, claim to identify phenomena that go beyond not just our present physics but any possible physical explanation. Asking what it would take for such a claim to succeed, we introduce a version of physicalism that formulates the proposition that all available data sets are best explained by combinations of “chance and necessity”—algorithmic rules and randomness. Physicalism would then be violated by the existence of oracles that produce certain kinds (...) of noncomputable functions. Examining how a candidate for such an oracle would be evaluated leads to questions that do not admit an easy resolution. Since we lack any plausible candidate for any such oracle, however, chance-and-necessity physicalism appears very likely to be correct. (shrink)

A recent attempt to compute a (recursion‐theoretic) noncomputable function using the quantum adiabatic algorithm is criticized and found wanting. Quantum algorithms may outperform classical algorithms in some cases, but so far they retain the classical (recursion‐theoretic) notion of computability. A speculation is then offered as to where the putative power of quantum computers may come from.

Between Calculability and Non-Calculability. Issues of Calculability and Predictability in the Physics of Complex Systems. The ability to predict has been a very important qualifier of what constitutes scientific knowledge, ever since the successes of Babylonian and Greek astronomy. More recent is the general appreciation of the fact that in the presence of deterministic chaos, predictability is severely limited (the so-called ‘butterfly effect’): Nearby trajectories diverge during time evolution; small errors typically grow exponentially with time. The system obeys deterministic laws (...) and still is unpredictable, seemingly a paradox for the traditional viewpoint of Laplacian determinisms. With the concept of deterministic chaos the epistemological issue about an adequate understanding of predictability is no longer just a mere philosophical topic. Physicists on the one hand recognize the limits of (long term) predictability, computability and even of scientific knowledge, on the other hand they work on concepts for extending the horizon of predictability. It is shown in this paper that physics of complex systems is useful to clarify the jungle of different meanings of the terms ‘predictability’ and ‘computability’ — also with philosophical implications for understanding science and nature. Today, from the physical point of view, the relevance of the concepts of predictability seems to be underestimated by philosophers as a mere methodological topic. In the paper I analyse the importance of predictability and computability in physics of complex systems. I show a way how to cope with problems of unpredictability and noncomputability. Nine different concepts of predictability and computability (i.e. open solution, sensitivity/chaos, redundancy/chance) are presented, compared and evaluated. (shrink)

Levin and Schnorr (independently) introduced the monotone complexity, Km(α), of a binary string α. We use monotone complexity to define the relative complexity (or relative randomness) of reals. We define a partial ordering ≤Km on 2ω by α ≤Km β iff there is a constant c such that Km(α ↾ n) ≤ Km(β ↾ n) + c for all n. The monotone degree of α is the set of all β such that α ≤Km β and β ≤Km α. We (...) show the monotone degrees contain an antichain of size 2N0, a countable dense linear ordering (of degrees of cardinality 2N0), and a minimal pair. Downey, Hirschfeldt, LaForte, Nies and others have studied a similar structure, the K -degrees, where K is the prefix-free Kolmogorov complexity. A minimal pair of K -degrees was constructed by Csima and Montalbán. Of particular interest are the noncomputable trivial reals, first constructed by Solovay. We define a real to be (Km, K)-trivial if for some constant c, Km(α ↾ n) ≤ K(n)+c for all n. It is not known whether there is a Km-minimal real, but we show that any such real must be (Km, K)-trivial. Finally, we consider the monotone degrees of the computably enumerable (c.e.) and strongly computably enumerable (s.c.e.) reals. We show there is no minimal c.e. monotone degree and that Solovay reducibility does not imply monotone reducibility on the c.e. reals. We also show the s.c.e. monotone degrees contain an infinite antichain and a countable dense linear ordering. (shrink)

We explore the possibility of using quantum mechanical principles for hypercomputation through the consideration of a quantum algorithm for computing the Turing halting problem. The mathematical noncomputability is compensated by the measurability of the values of quantum observables and of the probability distributions for these values. Some previous no-go claims against quantum hypercomputation are then reviewed in the light of this new positive proposal.

While practical efforts in the field of artificial intelligence grow exponentially, the truly scientific and mathematically exact understanding of the underlying phenomena of intelligence and consciousness is still missing in the conventional science framework. The inevitably dominating empirical, trial-and-error approach has vanishing efficiency for those extremely complicated phenomena, ending up in fundamentally limited imitations of intelligent behaviour. We provide the first-principle analysis of unreduced many-body interaction process in the brain revealing its qualitatively new features, which give rise to rigorously defined (...) chaotic, noncomputable, intelligent and conscious behaviour. Based on the obtained universal concepts of unreduced dynamic complexity, intelligence and consciousness, we derive the universal laws of intelligence applicable to any kind of intelligent system interacting with the environment. We finally show why and how these fundamentally substantiated and therefore practically efficient laws of intelligent system dynamics are indispensable for correct AI design and training, which is urgently needed in this time of critical global change towards the truly sustainable development. (shrink)

We prove that if $A$, $B$ are noncomputable c.e. sets, $A<_{sQ_{1}}B$ and [($B$ is not simple and $A\oplus B\leq _{sQ_{1}}B$) or $B\equiv _{sQ_{1}}B\times \omega $], then there exist infinitely many pairwise $sQ_{1}$-incomparable c.e. sets $\{C_{i}\}_{i\in \omega }$ such that $A<_{sQ_{1}}C_{i}<_{sQ_{1}}B$, for all $i\in \omega $. We also show that there exist infinite collections of $sQ_{1}$-degrees $\{\boldsymbol {a_{i}}\}_{i\in \omega }$ and $\{\boldsymbol {b_{i}}\}_{i\in \omega }$ such that for every $i, j,$ (1) $\boldsymbol {a_{i}}<_{sQ_{1}}\boldsymbol {a_{i+1}}$, $\boldsymbol {b_{j+1}}<_{sQ_{1}}\boldsymbol {b_{j}}$ and $\boldsymbol {a_{i}}<_{sQ_{1}}\boldsymbol {b_{j}}$; (...) (2) every c.e set in $\boldsymbol {a_{i}}$ is a maximal set; and (3) every c.e. set in $\boldsymbol {b_{j}}$ is a non-maximal hyperhypersimple set. We prove that a noncomputable c.e. $sQ$-degree contains either only one or infinitely many c.e. $sQ_{1}$-degrees. The $sQ_{1}$-degrees of c.e. cylinders are dense upper semilattice. (shrink)

A set X of nonnegative integers is computably enumerable (c.e.), also called recursively enumerable (r.e.), if there is a computable method to list its elements. Let ε denote the structure of the computably enumerable sets under inclusion, $\varepsilon = (\{W_e\}_{e\in \omega}, \subseteq)$ . We previously exhibited a first order ε-definable property Q(X) such that Q(X) guarantees that X is not Turing complete (i.e., does not code complete information about c.e. sets). Here we show first that Q(X) implies that X has (...) a certain "slowness" property whereby the elements must enter X slowly (under a certain precise complexity measure of speed of computation) even though X may have high information content. Second we prove that every X with this slowness property is computable in some member of any nontrivial orbit, namely for any noncomputable A ∈ ε there exists B in the orbit of A such that X ≤ T B under relative Turing computability (≤ T ). We produce B using the Δ 0 3 -automorphism method we introduced earlier. (shrink)

We introduce a new hierarchy of computably enumerable degrees. This hierarchy is based on computable ordinal notations measuring complexity of approximation of${\rm{\Delta }}_2^0$functions. The hierarchy unifies and classifies the combinatorics of a number of diverse constructions in computability theory. It does so along the lines of the high degrees (Martin) and the array noncomputable degrees (Downey, Jockusch, and Stob). The hierarchy also gives a number of natural definability results in the c.e. degrees, including a definable antichain.

A problem is a multivalued function from a set of instances to a set of solutions. We consider only instances and solutions coded by sets of integers. A problem admits preservation of some computability-theoretic weakness property if every computable instance of the problem admits a solution relative to which the property holds. For example, cone avoidance is the ability, given a noncomputable set A and a computable instance of a problem ${\mathsf {P}}$, to find a solution relative to which A (...) is still noncomputable.In this article, we compare relativized versions of computability-theoretic notions of preservation which have been studied in reverse mathematics, and prove that the ones which were not already separated by natural statements in the literature actually coincide. In particular, we prove that it is equivalent to admit avoidance of one cone, of $\omega $ cones, of one hyperimmunity or of one non- $\Sigma ^{0}_1$ definition. We also prove that the hierarchies of preservation of hyperimmunity and non- $\Sigma ^{0}_1$ definitions coincide. On the other hand, none of these notions coincide in a nonrelativized setting. (shrink)

The main question of this article is whether there is a family closed under finite differences (i.e., if A belongs to the family and B=∗A, then B also belongs to the family) that can be enumerated by any noncomputable c.e. degree, but which cannot be enumerated computably. This question was formulated by Greenberg et al. (2020) in their recent work in which families that are closed under finite differences, close to the Slaman–Wehner families, are deeply studied.

We are sympathetic with the broad aims of Perruchet & Vinter's “mentalistic” framework. But it is implausible to claim, as they do, that human cognition can be understood without recourse to unconsciously represented information. In our view, this strategy forsakes the only available mechanistic understanding of intelligent behaviour. Our purpose here is to plot a course midway between the classical unconscious and Perruchet &Vinter's own noncomputational associationism.

Post in 1944 began studying properties of a computably enumerable set A such as simple, h-simple, and hh-simple, with the intent of finding a property guaranteeing incompleteness of A . From the observations of Post and Myhill , attention focused by the 1950s on properties definable in the inclusion ordering of c.e. subsets of ω, namely E = . In the 1950s and 1960s Tennenbaum, Martin, Yates, Sacks, Lachlan, Shoenfield and others produced a number of elegant results relating ∄-definable properties (...) of A , like maximal, hh-simple, atomless, to the information content of A . Harrington and Soare gave an answer to Post's program for definable properties by producing an ∄-definable property Q which guarantees that A is incomplete and noncomputable, but developed a new Δ 3 0 -automorphism method to prove certain other properties are not ∄-definable. In this paper we introduce new ∄-definable properties relating the ∄-structure of A to deg, which answer some open questions. In contrast to Q we exhibit here an ∄-definable property T which allows such a rapid flow of elements into A that A must be complete even though A may possess many other properties such as being promptly simple. We also present a related property NL which has a slower flow but fast enough to guarantee that A is not low, even though A may possess virtually all other related lowness properties and A may simultaneously be promptly simple. (shrink)

We prove that superhigh sets can be jump traceable, answering a question of Cole and Simpson. On the other hand, we show that such sets cannot be weakly 2-random. We also study the class $superhigh^\diamond$ and show that it contains some, but not all, of the noncomputable K-trivial sets.

Slaman and Wehner have constructed structures which distinguish the computable Turing degree 0 from the noncomputable degrees, in the sense that the spectrum of each structure consists precisely of the noncomputable degrees. Downey has asked if this can be done for an ordinary type of structure such as a linear order. We show that there exists a linear order whose spectrum includes every noncomputable Δ 0 2 degree, but not 0. Since our argument requires the technique of permitting below a (...) Δ 0 2 set, we include a detailed explanation of the mechanics and intuition behind this type of permitting. (shrink)

We examine the reverse mathematical strength of a variation of Hindman’s Theorem (HT) constructed by essentially combining HT with the Thin Set Theorem to obtain a principle that we call thin-HT. This principle states that every coloring c:N→N has an infinite set S⊆N whose finite sums are thin for c, meaning that there is an i with c(s)≠i for all nonempty sums s of finitely many distinct elements of S. We show that there is a computable instance of thin-HT such (...) that every solution computes ∅′, as is the case with HT, as shown by Blass, Hirst, and Simpson (1987). In analyzing this proof, we deduce that thin-HT implies ACA0 over RCA0+IΣ20. On the other hand, using Rumyantsev and Shen’s computable version of the Lovász Local Lemma, we show that there is a computable instance of the restriction of thin-HT to sums of exactly 2 elements such that any solution has diagonally noncomputable degree relative to ∅′. Hence there is a computable instance of this restriction of thin-HT with no Σ20 solution. (shrink)

In this paper I discuss the topics of mechanism and algorithmicity. I emphasise that a characterisation of algorithmicity such as the Turing machine is iterative; and I argue that if the human mind can solve problems that no Turing machine can, the mind must depend on some non-iterative principle — in fact, Cantor's second principle of generation, a principle of the actual infinite rather than the potential infinite of Turing machines. But as there has been theorisation that all physical systems (...) can be represented by Turing machines, I investigate claims that seem to contradict this: specifically, claims that there are noncomputable phenomena. One conclusion I reach is that if it is believed that the human mind is more than a Turing machine, a belief in a kind of Cartesian dualist gulf between the mental and the physical is concomitant. (shrink)

Good sciences have good metaphors. Indeed, good sciences are good because they have good metaphors. AI could use more good metaphors. In this editorial, I would like to propose a new metaphor to help us understand intelligence. Of course, whether the metaphor is any good or not depends on whether it actually does help us. (What I am going to propose is not something opposed to computationalism -- the hypothesis that cognition is computation. Noncomputational metaphors are in vogue these days, (...) and to date they have all been equally plausible and equally successful. And, just to be explicit, I do not mean “IQ” by “intelligence.” I am using “intelligence” in the way AI uses it: as a semi-techical term referring to a general property of all intelligent systems, animal (including humans), or machine, alike.). (shrink)

Although algorithmic information theory provides a measure of the information content of string of characters, problems of noise and noncomputability emerge. However, if pattern in a noisy string is recognized by reference to a set of similar strings, this article shows that a compressed algorithmic description of a noisy string is possible and illustrates this with some simple examples. The article also shows that algorithmic information theory can quantify the information in complex organized systems where pattern is nested within (...) pattern. (shrink)

We introduce a natural strengthening of prompt simplicity which we call strong promptness, and study its relationship with existing lowness classes. This notion provides a ≤ wtt version of superlow cuppability. We show that every strongly prompt c.e. set is superlow cuppable. Unfortunately, strong promptness is not a Turing degree notion, and so cannot characterize the sets which are superlow cuppable. However, it is a wtt-degree notion, and we show that it characterizes the degrees which satisfy a wtt-degree notion very (...) close to the definition of superlow cuppability. Further, we study the strongly prompt c.e. sets in the context of other notions related promptness, superlowness, and cupping. In particular, we show that every benign cost function has a strongly prompt set which obeys it, providing an analogue to the known result that every cost function with the limit condition has a prompt set which obeys it. We also study the effect that lowness properties have on the behaviour of a set under the join operator. In particular we construct an array noncomputable c.e. set whose join with every low c.e. set is low. (shrink)

We define a property R(A 0 , A 1 ) in the partial order E of computably enumerable sets under inclusion, and prove that R implies that A 0 is noncomputable and incomplete. Moreover, the property is nonvacuous, and the A 0 and A 1 which we build satisfying R form a Friedberg splitting of their union A, with A 1 prompt and A promptly simple. We conclude that A 0 and A 1 lie in distinct orbits under automorphisms of (...) E, yielding a strong answer to a question previously explored by Downey, Stob, and Soare about whether halves of Friedberg splittings must lie in the same orbit. (shrink)