Introduction

The introductory quotation by Ray Kurzweil evokes an idea of certain ordered “intelligence levels”, one of which corresponds to human intelligence, with still some levels of “superhuman”, non-biological intelligence above it. The point in time when the “power” of non-biological intelligence will reach and trespass the level of human intelligence has obtained a popular label: the Singularity (cf. [17]). According to the leading thinkers in the field of artificial intelligence this point is near, lying merely a few decades in the future, with profound consequences for mankind, cf. [5, 10, 17]. Nevertheless, it seems that the AI literature has not paid much explicit attention to the formal investigation of the “power” of artificial intelligent systems, and hence, to the question whether there are some limits to this power. Yet, there is one notable exception to this state of affairs: this is the recurring idea that the human mind might perhaps possess the ability to go beyond the level of classical computability as defined, for example, by the classical Turing machines [24]. Penrose [22] seems to be the best-known defender of this idea. If this conjecture is right then, undoubtedly, any level of artificial intelligence reached after the Singularity will obey super-Turing computing power. Could the latter statements concerning the alleged super-Turing power of the human mind and the levels of intelligence beyond it be also supported in theory? It is the goal of this paper to give one possible answer to this question. In order to answer this question we will use a similar approach as Penrose did, when seeking the answer to his problem concerning the power of human thoughts, or, more generally, of cognition. Namely, we will identify a computational “machine” model of cognitive systems and investigate its computational power. However, unlike Penrose who attempted to show the superiority of the human mind by comparing it with the model of the classical Turing machine, we will make use of a different, demonstrably more computationally powerful model that captures the main features of cognitive systems. These features cannot be modelled by the classical Turing machine.

Usually, the term “cognition” denotes the activities by which living organisms collect, process, store and utilize information. These activities especially include perception, learning, memorization and decision making [23]. With respect to this definition intelligence can be seen as a part of cognition which is less interested in perception and focuses mainly on the quality of cognitive processes. Both cognition and intelligence are related to information processing. The belief that human or biological cognition and intelligence present a specific kind of computations (cf. [4]) is the basis of computationalism. The proponents of this school of thought believe that the computational modelling of cognitive abilities of living organisms, inclusively that of humans, is at least in principle possible and that in this way one can achieve if not a genuine than at least an approximative capturing and understanding of all mental faculties attributed to intelligence. This also includes thinking, consciousness and explanation of the underlying algorithmic principles.

Obviously, any computational model of cognitive systems must capture three crucial properties of cognitive systems. Namely, any cognitive system must clearly be

  1. 1.

    interactive—in order to be able to communicate with their environment, to reflect its changes, to get the feedback, etc.;

  2. 2.

    evolutionary—in order to develop over generations, and

  3. 3.

    potentially not time-bounded—in order to allow for their open-ended development.

Therefore, a classical Turing machine cannot model any full-fledged cognitive system—simply because such machines do not possess the above-mentioned properties. This also confirms Penrose’s conclusion that classical Turing machines do not adequately capture human intelligence, albeit by a different reasoning. Cognitive systems, therefore, must be modelled by theoretical computational models capturing interactivity, evolvability and time-unbounded operation of the underlying systems.

Surprisingly, early computational models of cognitive systems did not reflect any of the three above-mentioned properties. It was the paradigm of classical Turing machines [24] that has traditionally served as a framework for thinking about computing and, more generally, about intelligence (and, for example, for Penrose also about thinking [22]). However, with the recent progress of information technologies and in the sciences where many natural systems are now viewed as information processing systems, our perception of what is computing has substantially broadened. Contrary to the traditional view of computing nowadays, we are witnessing a shift from finite to potentially non-terminating interactive computations, a shift from rigid computing systems towards systems whose hardware and/or software can change over time, and a shift from once-for-all-times given architecture of computing systems to computing systems with their architecture and software evolving in an unpredictable, non-uniform way. The latter systems are known as non-uniform interactive evolutionary systems.

The efficiency of our models will be measured by the standard methods used in computational complexity theory, that is, by comparing their efficiency and computational power to that of the standard basic models known within this theory. We will look for the computational limits and hierarchies of our models. We will be mainly interested in their efficiency in processing data in order to solve cognitive problems and, last but not least, whether there are cognitive problems which, in principle, cannot be solved by these models. In the rest of this paper, we will be simply speaking only about cognition which, in the framework of its previous informal definition, also seems to be a key notion for the definition of intelligence.

The goal of this paper is to apply the recent theory of non-uniform interactive evolutionary systems in the domain of cognitive systems. This will be done in two steps. Firstly, by showing that non-uniform interactive evolutionary systems capture in a natural way the computational properties of cognitive systems. Secondly, by interpreting the results from the theory of non-uniform interactive evolutionary systems within the framework of cognitive systems. Within this framework lines we show four results that might be of interest from the viewpoint of the general theory of cognitive systems.

First, we show that in general cognitive systems may possess a super-Turing computational power. This means that in principle such systems can solve more problems than the classical Turing machines.

Second, based on our modelling, we offer a plausible explanation why human thought appears to be uncomputable (cf. [22]).

Third, we show that there exists an infinite number of infinite proper hierarchies of cognitive systems each of which can solve strictly more problems than all its predecessors in the hierarchy at hand. Within some hierarchies there are classes of problems that correspond to the level of intelligence reached at singularity point. Thus, if the ability to solve the problems is taken as a measure of cognitive systems then theoretically there is no upper limit to this measure.

Last but not least, we also try to estimate at what level of Arithmetical HierarchyFootnote 1 the cognitive systems corresponding to the human-level intelligence are to be sought. We give arguments pointing strongly towards the \(\Upsigma_2\) level of this hierarchy (cf. [6]).

The last four claims represent the original contributions to the theory of cognitive systems.

The structure of the paper is as follows. In "Extending the Notion of Cognitive Systems", we will generalize the notion of cognitive systems also to include “hybrid” systems consisting of a combination of natural (living) and artificial systems. In "Modelling Cognitive Systems by Finite Systems", we will argue that any finite cognitive system can be modelled by interactive finite transducers. Next, in "Non-uniform Evolutionary Interactive Systems", we show that the main essence of information processing by cognitive systems is captured by the models of non-uniform interactive evolutionary systems, and we introduce two representatives of such systems: evolutionary automata and interactive Turing machines with advice. In "The Super-Turing Computational Power of Cognitive Systems", a super-Turing computational power of cognitive system is shown and an explanation of apparent uncomputability of human thought (cf. [22]) is offered, too. An infinite proper hierarchy of cognitive systems is presented in "Hierarchies of Cognitive Systems". In "Discussion", we speculate on the computational power of human intelligence and present reasons why this power appears to be upper-bounded by the class \(\Upsigma_2\) of the arithmetical hierarchy. "Conclusions" contains the conclusions.

It is interesting to note that there is a clear link between our modelling and the recent work of Cooper [7], which comes from a more schematic direction, building its persuasiveness on broad structural rather than computational considerations.

Methods

Extending the Notion of Cognitive Systems

By the end of the past century computationalism has obtained an unexpected support both from computer science and the theoretical physics. In 1985 a paper by the theoretical physicist D. Deutsch appeared [8], showing that any real (dissipative) finite physical system can be efficiently simulated by a quantum computer. Since a quantum computer can be simulated by a Turing machine (albeit, as it seems, quite inefficiently) we have a proof of the computationalistic claim that, for example, man can be genuinely simulated, at least in principle, by a quantum computer. Another result from computational complexity theory asserts that this simulation will be efficient (indeed it will be of polynomial time complexity w.r.t. the size of the simulated physical system [2]).

In our approach we will further generalize the scope of computationalism by proceeding beyond the cognitive abilities of living organisms per se: our considerations will include any organisms (such as humans) equipped by whatever device which will “strengthen” their cognitive capabilities, or allow their new quality. The Hubble telescope mounted on a satellite encircling the Earth may serve as an example of such a device of which the control and computing centre on the Earth is also a part. No doubts that such a machine will strengthen the cognitive abilities of an observer using this device. Clearly, using this device, an observer gets an access to data inaccessible to him by his own senses. Moreover, these data are processed in a way which, without computers, is also beyond men’s abilities. We will call the resulting system, that is, an observer as well as his or her apparatus, the cognitive system. The resulting “hybrid” cognitive system is clearly endowed by a new quality of cognition which is unattainable for a man without the respective devices. Let us be broad-minded by not insisting on the cognitive device being really constructed. We will be happy just with the gedanken experiments, that is, with the situation when the assumed existence of a “cognitive amplifier” does not violate any natural law. Standing firmly on the ground of computationalism, any kind of devices just mentioned can eventually be thought of as a data processing system. In fact, the only way cognitive systems could fail to be simulated by computations would be if they were not governed by physical laws at all. Henceforth, in the end, using this rather general approach, everything reduces to the question about the limits of all “thinkable” cognitive (read: computational) systems based on whatever principles obeying natural laws.

Therefore, as our starting point we accept computationalism and in order to get insight into human-level artificial or non-biological intelligence we will model cognitive systems by suitable computational models and investigate their computational properties.

Modelling Cognitive Systems by Finite Systems

The basic notion we will be using for a while is the notion of a configuration of some finite artefact, organism, or of a matter in a fixed space volume. All these categories will be termed devices. A configuration of a device results from a particular observable or measurable arrangement of parts or components of the device at hand. We will say that in two successive times a device is in the same configuration if in the respective times the arrangements defining the configurations are the same. The contemporary quantum physics sets a theoretical upper bound on the number of configurations a device of a given mass and volume can enter. S. Lloyd has shown [19, 20] that the number of bits which can be represented by 1 kg of a matter in a volume of one litre can be of the order at most 1031. That is, such a volume can enter approximately \(2^{10^{31}}\) configurations. The former number is a huge, but finite number which can be seen as an upper limit on the memory capacity of conceivably the most efficient memory of a given size. It follows that within the framework of the previous consideration any finite device can serve as a memory of a capacity given by observable or measurable physical parameters of this device.

A finite device can be seen as a computing device that computes in accordance with a set of transition rules (i.e., with a programme) if and only if it fulfils the following rather general conditions:

  1. 1.

    it must be possible to set the device into a distinguished initial configuration;

  2. 2.

    the device in a given configuration, possibly interacting with its input data, will enter the next configuration; the dynamics of such a transition must correspond to the transition rules, that is, the device must “all by itself” cause the transition from one configuration into the other in accordance with its programme;

  3. 3.

    the input data need not all be present at the beginning of a computation; rather, the data can appear at unpredictable times.

We claim that the previous idea of a computing device is general enough also to cover any realizations of finite non-evolvable cognitive systems. The adjective “finite” is important, and in this particular case it means a system that can enter but a finite number of configurations.

The property ensuring that the device causes something to happen “all by itself” means that there is a mechanism in the device working in the desired way: the device is “made” in this way. The transition rules need not be explicitly known—it is enough if they exist and are finitely describable. The classical real computer can serve as the prime example of such a device; here the transition rules are known, similarly as in the case of automatic teller machines, mobile phones, etc. The brain presents another example of a computing device with unknown set of transitions, but the computationalists believe that it does exist. A rock, a picture, a memory card, a mathematical model of a Turing machine are examples of devices which do not compute in the sense defined above.

Note that we defined neither the result of the computation nor its termination. This has been done intentionally—our computing device should realize potentially never ending computations. Stated differently, the device transforms a potentially infinite stream of input data (which are called stimuli in the case of cognitive systems) into a potentially infinite stream of output data called actions in the case of living organisms; the sequence of actions corresponds to the behaviour. In this case it is possible, and the definition admits that some input data can represent reaction of the environment to some actions. Hence, we can speak about interactive computations. Obviously, with the device just described we can also realize finite computations—simply by artificially restricting the input stream. For example, from a certain position the input stream will consist but of empty symbols, and we will be interested only in terminating computations.

In the sequel, we will only deal with the classical (i.e., with discrete, non-quantum) computational devices of a finite size. Formally, computations of such devices are equivalent to computations of so-called interactive finite-state automata with output, which are also called interactive finite-state transducers [27]. Though other equivalent formalisms capturing interaction and non-termination are known, we prefer the framework of transducers which, as we will later see, can be seen as evolutionary forerunners of Turing machines.

There is no need to define interactive finite transducers formally here. We only note that each interactive finite transducer defines a relation between the input and output (data) stream. In general, a cognitive system can have several input and output ports through which the data stream into the systems or out of it. However, in our modelling we see all entering data as encoded into a single input stream (by increasing the input alphabet of the corresponding interactive finite transducer) and similarly we also treat the output streams. Then we speak about the translation of the input stream to an output stream.

Thus, comparing the notion of an interactive finite transducer with that of the commonly known finite-state automaton with output (the so-called Mealy automaton) we see that the input data for an interactive finite transducer are not given on an input tape before the start of a computation and there need not be a finite number of them. That is why the output of an interactive finite transducer can also be an infinite stream.

Thesis 1

From a computational viewpoint, any finite cognitive system is equivalent to an interactive finite transducer.

We have intentionally defined the previous claim as a thesis—since a finite cognitive system is not a formally defined notion, the previous equivalence cannot be formally proved. However, it can be rejected if someone will come with a design of a finite cognitive system that, from a computational viewpoint, would not be equivalent to an interactive finite transducer.

We conclude this section with a few words on the proper choice of a suitable model of a cognitive system (or of an organism, for that matter). If we want to model a system imitating the functions of a cognitive system, then we can use a model that is in some aspects “more powerful” than the modelled system. If this is the case, the additional power of the modelling device may simplify modelling of certain properties. For instance, for modelling a bacterium we can make use of a classical Turing machine (or, in the sense of the Church-Turing thesis, whatever equivalent computational device). Quite understandably, in such a case we cannot exploit the computational resources of the Turing machine on a wide scale (e.g., we cannot make use of a Turing machine’s potentially infinite memory). On the other hand, should a computational model be used for estimating the true computational power of a modelled system, a more powerful computation device cannot be used for such a purpose. That is, for example, for the aforementioned case of a bacterium modelled by a Turing machine one cannot claim that a bacterium has the same computational power as the modelling Turing machine. This seems to be obvious, but in the artificial intelligence literature we can often read that, for example, the human brain can in principle be modelled by a Turing machine and hence, they possess the same computational power. It follows that when it comes to capturing the true computational power of a cognitive system one must take care that the modelling system has no computational abilities other than those available to the modelled system. Considering once more our example of a Turing machine versus a human brain, then the brain cannot compensate for the potentially unlimited capacity of the Turing machine’s tape (unless we assume that brain can grow ad libitum when necessary).

Non-uniform Evolutionary Interactive Systems

Returning to the problem of modelling general cognitive systems, we should stress that so far our modelling by interactive finite transducers has been restricted to the case of finite cognitive systems. Obviously, for finite cognitive systems there is no way to exceed a certain finite number of configurations due to their finite size. To put it differently, the evolution (or learning) of such systems can only happen within a bounded space of all reachable configurations. However, as we have stressed in the Introduction, in a general case of a cognitive system we would also like to allow an evolution of such a system beyond the limits imposed by the number of achievable configurations. Moreover, we would also like to include a possibility of deep “structural” changes of such systems that can happen over time, induced, for example, by changes of their transition rules (this also covers the ability to work with a larger set of symbols). In “real” world, such changes may correspond to the (Darwinian) evolution of some species along a certain evolutionary path.

In order to model the evolution of a computational system over time we have in mind we consider the idea of (ordered) sequences of interactive finite transducers. The notion of sequence of finite computational devices has usually been used in computational complexity theory in different contexts, for example, to capture the computational power of non-uniform families of circuits (cf. [1]). In the sequence of interactive finite transducers, each interactive finite transducer corresponds to a “stable evolutionary period” in which evolution (if any) can be realized within the respective space of achievable configurations. Should this space be exhausted or should there be an evolutionary change that cannot be captured by the current design of the interactive finite transducer at hand (increasing the number of internal states, increasing the input or working alphabet, change of the transition rules), then a new interactive finite transducer must be considered. This gives rise to a potentially infinite sequence of interactive finite transducers in which the ith automaton corresponds to the contents and computations of a cognitive system during its ith stable period. In the course of this time only the ith automaton receives input and produces output.

We have arrived at the computational model called the evolving automaton, introduced in [27].

Definition 1

The evolving automaton with a schedule is an infinite sequence of interactive finite transducers sharing the following property: each transducer in the sequence contains some subset of states of the previous transducer in that sequence. The schedule determines when each transducer has to stop processing its inputs and thus, when is the turn of the next transducer.

The condition that a given interactive finite transducer has among its states a subset of states of a previous interactive finite transducer captures one important aspect: it is the persistence of data in the evolving automaton over time (cf. [11]). In the language of finite automata, this condition ensures that some information available to the current automaton is also available to its successor. This models passing of information over generations.

On an on-line delivered potentially infinite sequence of the input symbols the schedule of an evolving automaton determines the switching times when the inputs to an automaton must be redirected to the next automaton. This feature models the (hardware) evolution.

An evolving automaton is an infinite object given by an explicit enumeration of all its elements. There may not exist an algorithm enumerating the individual automata. Similarly, the schedule may also be non-computable. Note that at each time a computation of an evolving automaton is performed by exactly one of its elements (one automaton), that is, by a finite object.

It follows that the evolving automata are non-uniform, interactive evolutionary systems just like families of circuits: their development over time cannot be described by an algorithm. The cognitive systems are also a case in point: For example, the decision to change the architecture of a cognitive system may be the result of evolutionary pressure that has nothing to do with computability. Thus, a cognitive system may take its own action in order to get information that will update its knowledge base (e.g., by connecting to the Internet, or by “making a conversation” with another cognitive system), and this may happen at unpredictable times and in an unpredictable way. By the way, the Internet itself can be seen as an evolutionary automaton as shown in [34].

General computing devices (and as a special case, finite cognitive systems) modelled via interactive finite transducers were restricted by the finiteness condition that prevented any memory growth in such gadgets. However, some computing devices can have a specific ability to increase their memory capacity. This can be achieved either by an additional mechanism or by connecting several computing mechanisms together. This additional memory capacity enables these devices to create and exploit a potentially unbounded set of configurations. A so-called interactive Turing machine introduced in [27] can serve as an example of such a device.

An interactive Turing machine is basically a standard Turing machine which has no input tape. Instead, it reads the input symbols via the input port and sends the output symbols to its output port. An interactive Turing machine can be seen as an interactive finite transducer which in order to increase its memory capacity (depending on the cardinality of its set of states) makes use of a potentially infinite tape. This tape can only be used for a computational purpose in a symbiosis with an interactive finite transducer. This transducer is endowed by the ability to move along the tape while reading and rewriting the symbols on the tape. As a result we obtain a more powerful computational device than was the interactive finite transducer alone. An interactive Turing machine computes all that was computed by an interactive finite transducer, but also more than that. This is because it can enter more than a finite number of configurations.

From the viewpoint of its construction, an interactive Turing machine is the extension of a classical Turing machine for the case of infinite input streams; this is what enables an interactive Turing machine to compute “more” than the classical Turing machine. For instance, an interactive Turing machine can process an infinite sequence of finite data segments. Of course, each such segment can also be processed by a classical Turing machine. However, the latter machine has no means for “transferring” information obtained from processing a finite segment in one run into the next run. This is simply because the classical Turing machine, after terminating its computation, cannot be restarted from the configuration in which it has terminated its previous computation: According to its definition the classical Turing machine must start a new computation from its initial state, with all its tapes empty. For instance, the classical Turing machine cannot realize the following translation: If a segment of a stream gets accepted (the machine produces 1) then the following segment will always be rejected (the machine produces 0). The computational abilities of interactive Turing machines are studied in [28].

Obviously, interactive Turing machines capture the ability of computing devices to cope with the growing demand on the memory size. In order to further increase the computational power of interactive Turing machines we will proceed to a yet more powerful model of Turing machines: the so-called interactive Turing machine with advice. The model extends the well-known and well-studied model of (ordinary) Turing machines with advice in computational complexity theory (cf. [15]) to the case of interactive computations:

Definition 2

An interactive Turing machine with advice is a Turing machine whose architecture is changed in two ways:

  • instead of an input and output tape it has an input port and an output port allowing for reading or writing potentially infinite streams of symbols;

  • the machine is enhanced by a special, so-called advice tape that, upon request, allows for the insertion of a possibly non-computable external information that takes a form of a finite string of symbols. This string must not depend on the concrete stream of symbols read by the machine until that time; it can only depend on the number of those symbols.

An advice is different from an oracle as known in computability theory: An oracle value can depend on the current input (cf. [25]). The interactive Turing machines with advice also represent a non-uniform model of interactive, evolving, and time-unbounded computation. Such machines capture an interactive and time-unbounded software evolution of cognitive systems.

The mechanism of advice functions is very powerful and in fact it can provide an interactive Turing machine with any non-computable “assistance”. For theoretical and practical reasons it is useful to restrict the size of advice growth in interactive Turing machines with advice to polynomial functions. With advice functions that grow exponentially one could encode arbitrary oracles in advice. Van Leeuwen and Wiedermann proved a perhaps surprising result showing the computational equivalence of interactive Turing machines with advice with the evolving automata.

Proposition 1

Evolving automata can simulate interactive Turing machines with advice and vice versa.

Based on the previous two models, van Leeuwen and Wiedermann [26] have formulated the following thesis:

Thesis 2

Extended Turing machine paradigm: A computational process is any process whose evolution over time can be captured by evolving automata or, equivalently, by interactive Turing machines with advice.

Interestingly, the paradigm also expresses the equivalence of software and hardware evolution.

In [34] the authors have shown that the paradigm captures well the contemporary ideas on computing. The fact that it also covers cognitive systems adds a further support to this paradigm. For contemporary computing the extended Turing machine paradigm appears to play a role that is similar to that played for “classical” computing by the classical Turing machines (cf. [26, 34]).

Thesis 3

From a computational point of view, cognitive systems are equivalent to either evolving automata or, equivalently, interactive Turing machines with advice.

Results

The Super-Turing Computational Power of Cognitive Systems

Recall that we will measure the power of cognitive systems is measured in terms of sizes of sets of different reactions (or behaviours) that those systems can produce in potentially infinite interactions with their environment.

The super-Turing power of cognitive systems is shown by referring to super-Turing computing power of interactive Turing machines with advice.

Namely, in [26] it was shown that such machines can solve the halting problem. In order to do so they need a so-called halting advice that for each input of size n allows to stop their computation once it runs beyond a certain maximum time. This time bound is defined as the maximum, over computations over all inputs of size n and over all machines of size n that halt on such inputs. In order to make the advice representation smaller (in fact, of length n), instead of the running time, we may take the description of that particular Turing machine achieving the maximal running time.

Proposition 2

Cognitive systems have super-Turing computational power.

Roger Penrose [22] asked about the power of human thoughts: how to explain the fact that mathematicians are able to find proofs of some theorems in spite of the fact that in general (by virtue of Gödel’s or Turing’s results) there is no algorithm that would always lead to a proof or refutation of any theorem. In our setting the explanation could be that the mathematicians discover a “non-uniform proof”, that is, a way of proving a particular theorem at hand and probably nothing else. This proof is found using a kind of heuristic search over known results in mathematics. All these results form a certain kind of “blocks” or modules from which sometimes, after their proper adaptation, proofs of new theorems can be constructed. The whole procedure is not unlike the process of creating a complex programme (in accordance with its specification) from simpler modules with known properties. In computability theory a process of systematic enumeration of an infinite number of candidates in order to find a candidate satisfying the required conditions (a solution) is known as Levin’s search [18]. The above described heuristic search can be seen as an informal realization of Levin’s search adapted to a restricted domain of mathematical proofs over building blocks of known partial related results. The final solution then emerges in the mind of a mathematician (i.e., in a cognitive system) who happens to be knowledgeable of the required facts. For this to happen mathematicians in general perform “searches” for related results, take part in generating such results and interact unpredictably among themselves in order to spread the required knowledge, to stimulate its development and speed-up the search process. In particular cases, such a “search” can last over generations of mathematicians. When the respective “knowledge blocks” are ready then it is only matter of time and chance, when and where the final solution will emerge. This also explains why solutions of certain problems appear independently, at about the same time, at several places. Similar ideas on how mathematicians “create” their proofs have been recently presented by Blum [3].

Hierarchies of Cognitive Systems

For interactive Turing machines with advice or for evolving automata one can prove that there exist infinite proper hierarchies of computational problems that can be solved on some level of the hierarchy but not on any of the lower levels (cf. [30, 31]). Roughly speaking, the bigger the advice, the more problems can be solved by the underlying machine.

Proposition 3

There exists an infinity of infinite proper hierarchies of cognitive systems of increasing computational power.

Among the levels of the respective hierarchies there are many cognitive systems corresponding formally (and approximately) to the level of human intelligence (the Singularity level), and also infinitely many levels surpassing it in various ways.

The interpretation of the last results within the theory of cognitive systems is the following one. There exist infinite hierarchies of computations of cognitive systems dependent on the amount of non-computable information injected into such computations either via advice or via the design of the members of the respective evolving automaton. The bigger this amount, the more translations can be realized. Among the levels of those hierarchies there are many levels corresponding formally (and approximately) to the level of human intelligence (the Singularity level—cf. [17]) and also infinitely more levels surpassing it in various ways. The complexity classes defining individual levels in these hierarchies are partially ordered by the containment relation.

Discussion

Characterizing the Computational Power of Human Intelligence

The previous hierarchy result was good enough for proving the existence of a level in the complexity hierarchy of cognitive systems corresponding to the level of human intelligence. Can we characterize this level more precisely? There is increased theoretical evidence that the computational power of human intelligence (aided by computers or not) is upper-bounded by the \(\Upsigma_2\) level of the arithmetical hierarchy. This level contains computations which are recursive in the halting problem of the classical Turing machines. For instance, Penrose [22] argues that human mind might be able to decide predicates of form ∃ x ∀ y P(x, y), i.e., the \(\Upsigma_2\) level. The computations within this class can answer the following question related to the halting of the arbitrary (classical) Turing machines for any input: (“Does there exist a Turing machine which for all Turing machines and for all inputs decides whether they halt?”). Similar conclusions have been reached during the last few decades by a number of logicians, philosophers and computer scientists looking at the computations as potentially unbounded processes (cf. [29]).

A more detailed structural insight into the nature of computations in the \(\Upsigma_2\) level of the Arithmetical Hierarchy offers a recent model of van Leeuwen and Wiedermann [29]—so-called red-green Turing machines. This model characterizes the second level of Arithmetical Hierarchy in terms of a machine model. We also show how this model relates to Turing machines with advice.

A red-green Turing machine is formally almost identical to the classical model of Turing machines. The only difference is that in red-green Turing machines the set of states is decomposed into two disjoint subsets: the set of green states and the set of red states, respectively. There are no halting states. A computation of a red-green Turing machine proceeds as in the classical case, changing between green and red states in accordance with the transition function. The moment of state colour changing is called mind change. A formal language is said to be recognized if and only if on the inputs from that language the machine computations “stabilize” in green states, that is, from a certain time on, the machine keeps entering only green states. Similarly, a language is said to be accepted if and only if the inputs from that language are recognized, and the computations on the inputs outside that language eventually stabilize in red states.

The model captures informal ideas of how human mind alternates between two states (accept and reject) when looking for a solution of a difficult decision problem. In a neat way red-green Turing machines also mirror the main features of the current thinking of computing: namely, viewing computations as potentially infinite processes. The non-uniform evolution is not included—the model concentrates merely on uniform models of unbounded computations.

As an example of the computational power of red-green Turing machines we show how such machines can solve the classical halting problem: we take the classical Turing machine with the input for which the halting problem is to be solved. We colour the original halting state as green and add a loop in this state. All the other states are coloured red. Now we run the machine on the given input. Obviously, the computation converges to green states just in case when the original machine halts. Otherwise, it will compute forever in red states. In fact, it is almost obvious that red-green Turing machines are equivalent to Turing machines with the halting advice mentioned before Proposition 2. This observation gives the link between the computations of the red-green Turing machines and the Turing machines with advice.

In [29] it is shown that the computational power of red-green Turing machines increases with the number of mind changes allowed along the levels of the so-called Ershov hierarchy, cf. [6] and for any finite number of mind changes red-green Turing machines recognize languages in \(\Upsigma_2\) and accept languages from \(\Updelta_2.\) In fact, computations of red-green Turing machines exactly characterize \(\Upsigma_2\) (or \(\Updelta_2\) in case of acceptance).

The previous results, together with the similar results achieved with the help of other machine or logical models of unbounded computation (cf. the references in [29]), along with the expected exponential increase in computational power leading to the Singularity point, suggests the following thesis.

Thesis 4

The computational power of cognitive systems corresponding to human-level intelligence is upper-bounded by the class \(\Upsigma_2\) of the Arithmetical Hierarchy.

Note that the previous thesis does not claim that the cognitive systems can solve all problems from \(\Upsigma_2.\) Nevertheless, the example of the halting problem theorem shows that occasionally human mind can solve specific problems that in general belong to \(\Upsigma_2.\)

Last but not least, let us consider the following question whose answer also supports the claim of Thesis 4. Could an exponential increase in the computing power, to be expected in the future, help in solving at least some undecidable problems from the class \(\Upsigma_2\) by using a “brute force” method? Using such a method, we would simply run the computation at hand in hoping that it will eventually stop. Of course, the problem is that we never know whether and when an arbitrary computation will stop. Such questions can only be answered for very simple machines and even for them they lead to astronomical estimates of their running times.

The so-called busy beaver problem asks, for the classical Turing machines with k-states working in binary alphabet, without any input, what is the largest number of steps that such a machine can do before halting. The respective numbers are known only for k < 5. It is known that machines with k = 5 have the running time of 47, 176, 870 steps and for k = 6 more than 102879 steps [21]. Even from these figures one can see that with the increased number of states, the running times tend to grow incredibly fast. In fact, no recursive function can express the growth of the respective values as a function of k. What is known is the lower bound on that growth. Green [12] has recursively constructed machines for any number of states and derived a recursive function that provides a lower bound for their running time. He has shown that the running time of busy beaver machines with 2k states grows faster than \(3\uparrow^{k-2}3,\) using Knuth’s up-arrows notation [16]. For k = 10 one gets \(3\uparrow\uparrow\uparrow 3=3\uparrow\uparrow 3^{3^{3}}=3^{3^{3^{.{.{.{3}}}}}}\) with \(3^{27} = 7,625,597,484,987\) terms in the exponential tower. Thus, not even an exponential (or, for that matter, any computable) increase in the computing power of non-biological intelligence, as Kurzweil expects, can match the complexity increase in a busy beaver problem. This seems to be a good argument for claiming that although it is conceivable that artificial general intelligence will soon or later reach the level of human intelligence, any substantial progress towards higher “interesting” levels (let us say in the Arithmetical Hierarchy) cannot be expected since not even a “super-intelligence” can cope with computationally infeasible tasks.

Conclusions

We have investigated cognitive systems in the framework of the extended Turing machine Thesis and presented the results concerning computational power and hierarchies of such systems. The good news is that the cognitive systems may possess a super-Turing computational power and that, theoretically, there is no upper limit as far as the computational power of such systems is concerned. The bad news is that this power cannot be purposefully harnessed for solution of concrete uncomputable problems. This is because the proof of super-Turing power of such systems is existential (non-constructive). That is, it only makes use of the fact that non-computable information needed for such systems to solve any concrete undecidable problem for sure exists. The proof does not care of how such information can be gained. Unfortunately, there is currently no known realistic way of systematically retrieving such information. Occasionally a properly tuned heuristic might help, as shown at the end of "The Super-Turing Computational Power of Cognitive Systems". On the other hand, the case of busy beaver machines shows that there is no hope for solving certain problems related to the large instances of the halting problem of the classical Turing machines, not even for the future powerful computations invented by non-biological intelligence, as Ray Kurzweil hopes.

As far as superintelligence is concerned, putting it on par with the ability to solve the problems that human mind cannot deal with, not even in principle, we have come to a negative conclusion. The same computability limits hold irrespectively whether a human or computational (or artificial) intelligence is considered. Artificial cognitive systems possessing artificial intelligence cannot solve problems that are qualitatively different from those solvable by natural cognitive systems. There are no “miraculous”, so far unknown principles enabling future artificial intelligence to trespass the computability limits of the existing (models of) computational systems. Nevertheless, thanks to the different underlying technology and to potentially unbounded knowledge base, the future cognitive systems will be able to solve the problems amenable, in principle, also to human mind, substantially faster and more reliably than humans.

At present, perhaps the only theoretically promising way of computing information that is not computable classically and thus, to move the intelligence beyond that corresponding to the Singularity, is offered by so-called relativistic (or “black-hole”) computing (cf. [9] and [33]), but any progress along these lines seems to depend on the progress of relativistic physics.