[I started this thread as a place to pre-discuss this meetup topic]

Two names come up first and foremost when discussing the historical roots of the concept of "limits on intelligence": Kurt Godel and Alan Turing.

Godel exposed the limits of descriptions and Turing exposed the limits on the comprehensibility of those descriptions.

May I suggest everyone find and read the short book, "Godel's Proof" by Ernest Nagel and James R. Newman (with introduction by Douglas R. Hofstadter).

Otherwise called "Godel's incompleteness theorems" (google this). The Wikipedia article by the same name is reasonable. Godel is how Hofstadter defeats Penrose.

On the Alan Turing side of this issue there is the problem of the limits of "computability" (Wikipedia article of this title is a good starting point). Where Godel defined the limits of the completeness of formalisms (descriptions), Turing came along to show that among Godel-allowable descriptions, there is a subset that can never be interpreted (computed). Not only that, this subset is the vast majority of programs that can be written.

Wow, "description" and "interpretation"… these domains map uncannily to "signal" and "cypher" in the domain of information theory. This is where the whole issue of intelligence is anchored deep into the causal framework of physics. The laws of the transfer of bits, communication (information theory) and the transfer of energy (thermodynamics) are equivalent. Energy = information! This realization allows theorists to bring the full power of physics to the issue of computation and intelligence. And, increasingly, physicists and cosmologists apply the "laws" of computation and information to their understandings of the universe as system.

Attempts to circumvent Turing's computability limits usually involve re-definitions of computation as system… most turn out to be logically absurd.

The work of both Godel and Turing acted as control rods in the runaway reaction that was the success of engineering (reductionist science) that informed the industrial revolution at the turn of the 20th century. Specifically, Godel wrote his proof as cautionary responce to the seeming impenetrability of the logical formalism introduced by Alfred North Whitehead and Bertrand Russell in their "Principia Mathematica".

Interestingly, Douglas Hofstadter, in his book "Godel, Escher, Bach: An Eternal Golden Braid" leans heavily upon Godel and Turing's laws of limits to weave together a solid base for his argument that intelligence is logically independent of specific substrate, opening the doors to the possibility (the inevitability) of non-biological, intentional intelligence as a matter of standard evolutionary course.

At the extreams, there are the diehard optimists, those who don't believe in any limits, who either wager their hopes on tighter granularity (simpler more atomic definitions of computation as in cellular automata) or on dimension-free "hyper-computation" (as suggested by some readings of quantum, string, and multi-verse theory, etc.)…

… and the pessimists, who fall into several groups and are most famously represented by Roger Penrose who wrote eloquently (if illogically) as apologist for the group that believes that biological minds contain some sort of special sauce that is not reproducible in turing machine logic ("The Emperor's New Mind").

For a really great introduction to the whole gambit of information, computation, complexity, entropy, physics (both relativistic and quantum, mathematics, set theory, compression, logic, probability, evolution, number theory, knowledge, signal processing, compression, redundancy, filtering, patterns and pattern detection, phase transitions, thermodynamics, the measurement of complexity… that together lead to an understanding of the universe and everything in it as a giant data set/computation/energy degradation system you should read "Programming the Universe" by Seth Lloyd (of MIT). Among other seemingly impossible feats, Lloyd goes about calculating the total quantum information in the universe. His goal is to quantify the computational and informational content and potential of the universe; a perspective he labels "it from bit". To do this, Lloyd relies heavily upon a means of measuring the total information in any configuration, a metric called "algorithmic information" that is defined as the minimum quantity of information required to construct a given configuration.

Lost (as has become intellectual tradition) in the morass of meme space and hubris that shapes the debate on the limits of intelligence is this little thing called evolution… a process that has, at least once, produced intelligence from non-intelligent parts… despite the limits of description and computability!

Randall

Another reading of Godel's work on the limits of descriptive systems is that description is by nature abstraction – a copy – a necessarily smaller copy of system being described. From this perspective, Godel's work falls nicely into the "Of course!" category. A description would be no better (or possibly worse) than its subject unless it was abbreviated or in some way compressed. What matters then is what makes it into an abstraction and what is left out. There are active and passive methods of building a description.

Anything that exists interacts with its environment through the passive descriptive filters that are part and parcel to causal reality. Locality, presence at one place in time and space is perhaps the most ruthless of the filters that passively reduce subject (the universe) to description (sensation). Access to knowledge of the source (environment) is further reduced – this time actively – by the limits of sensory access. The pupal aperture of our eyes effectively reject photons that are not aligned to the perpendicular of the plain of the retina. The corneal lens rejects photons too energetic to be aligned. Further subtract the photons that vibrate at a frequency not resonant with the rods and cones that convert electromagnetic environmental energy into nervous system signals (description). By the time the nervous system has access to a version of its environment, the description has become but a thin shadow of the system it abstracts.

Once this description has been formatted for nervous system processing, it meets with yet more reduction filters. Optical nerve ganglions enhance gross features like sharp objects and rapidly approaching objects and hold frame memory so that they pass only that part of the visual sensory stream that differs from the imediate past.

Once in the brain, the description is further reduced and compressed through a (parallel) series of pattern matching filters specialized to ignore all information that do not match pre-stored and constantly refined survival enhancing patterns.

At each stage or level in this description reduction cascade, Godel's completeness insights dictate what subset of the pattern they receive as input that can ever be used to describe the totality of the grammar that describes that level of the abstraction process. Obviously, the further you move away from the source pattern you are describing, the more Godel's limits get additively compounded.

And this is where Monica Andersen's concept of "salience" must be addressed. The only way to counter the debilitating effects of compounded abstraction layering (compression), is to make damn sure your filters are selecting for the parts of the system that are causally important.

Randall

On now to the computation side of the message/cypher equation. In the last post I tried to dissect the message, the description, the abstraction. But things aren't so binary in the causal world computation, intelligence, and cypher must share with data, description, abstraction, message.

All the world is message and we are but cyphers. Could Shakespeare have understand exactly how profound and universal was this one short and dismissively simple statment?

Message vs. cypher… how does one tell the difference? As I pointed out in the previous post, actual causal physical reality is never accessible in its entirety, locality alone acts as harsh and unrelenting filter, so on the data side of the message/cypher equation, all processes already reside exclusively the world that is computation.

Gone too is the sticky logic that is the embodiment argument, as there is no escape from locality… all computation assumes embodiment!

What this means is that everything is a graph and that interaction of any form is cypher, is computation – which is by virtue of the inability to escape reduction and compression – intelligence.

When we say that every configuration is data and every interaction between configurations is computation, we are putting a new spin on physics, on the causal world of gravity and chemistry and subatomic interactions, on physical cosmology at every scale.

But, more topical to this discussion we are also applying the same understanding (with all of its incumbent restrictions), to the rarified world of software and hardware that the word "computation" more usually applies. Self reference was a driving obsession of both Godel and Turing. The more abstracted a system becomes – the more layers of filtering that separate description from described – the more the distinction between message and cypher is blurred.

This is especially true of self-evolving systems. Is the code that writes over itself, in response to writing-over-itself instructions in that same code, code as message, or is it code as cypher? It would seem that it is both and that the distinction is contextual or use-determined.

Remember that structure and information are equivalent in every way. Likewise, processing is an unavoidable side effect of causality. Everything is processing everything else at all times, and nothing ever stands in the way of all of this processing. It should be obvious that these two facts, when taken together result in a hopelessly noisy information and processing environment. What evolution does is build lossy abstraction as structure. Once built, these abstractions allow more efficient self-processing. An abstraction is fit if it captures the salient aspects of a system (and dumps the rest), and if it is situated into causal reality such that it effects control over the system it extracts.

And, of course, the existence of an abstraction forever changes the environment in which it is situated… becomes ground for further abstractions. And as I have suggested earlier, no ground can ever be said not to be both ground and abstraction.

So the question of the limits of computation (intelligence) are inseparable from the limits of the interaction between message and cypher, and therefore become questions about limits of evolution as a process that builds towards systems in which message and cypher become harder and harder to distinguish.

These are deeply causal and theoretical ideas. They form the base, like it or not, of reality and are as such not to be confused with domain specific discussions. Computing in its most general form includes all that is and will ever be. Computing, in the common Silicon Valley context, involves issues unique to contemporary hardware and software and to the way culture speaks of and deals with computers, computation, and the work and commerce that is the computer industry. But ultimately, cultural issues regarding computation are restricted by the universal base that is computation… and not the other way around. It is important to vigilantly keep this natural hierarchy in mind every time we work towards effective solutions in complexity handling machinery and AI.

Randall

Lacking any credible evidence that intelligence is different from computation we move on…

So lets start by listing ways we already know computation is limited:

1. Incompleteness (a description can never fully describe itself).
2. Halting and Looping (the vast majority of descriptions are topologically un-processable).
3. n-Hard (processing procedure length grows with respect to size of data-set).
4. Expanding Domain (the act of processing data results in an ever expanding data set).

And postulate about other obvious computational and intelligence limitations:

5. The Trees (proximity to local data occludes access to other less proximal data).
6. The Forest (data acquired through processing obstruct access to source data).
7. Overwhelm (shear scale of integration outruns compression and over-runs processing scratchboard).
8. Cost of Graph Building (abstraction setup is impractical).
9. Cost of Graph Optimization (graph must be updated at speed and scale that outruns its fidelity to source).
10. Blurring (demands on compression exceed fidelity necessary for processing).
11. Parallel-itis (node-based machinery becomes as complex as the subject it is meant to abstract).
12. Linear-itis (parallel abstraction does not map to turing machine linearity).
13. To Many Answers (quantum or molecular computing space is statistically vast enough to insure the answer, the problem is finding it among all of the other almost-answers).
14. Complexity is Intractable (there is no free lunch, complexity must be evolved and evolution is expensive).
15. Minimum Required Bits (data + computer = more resources than can be made available).
16. Toxicity (processing produces reactive substructures that interact noisily with surroundings).
17. Foreground / Background Confusion (impossible to keep data and processing separate).
18. Measurement Perturbance (checking the state of attribute changes that attribute's state).
19…

And then there are the purely physical limitations…

a. energy availability (every flipped bit costs some energy, its the law!).
b. heat buildup (every flipped bit leaks heat, heat transfer is time limited, its the law!).
c. bit density (density and heat are directly related, gravity sucks).
d. speed of light (communication means distance, distance means latency).
e. optimizing structure (edits to its [bits] are more costly as number and depth increase).
f. bit decay (bits are its and its decay – especially true as the its holding bits get really small)
g…

Note: An interesting pattern emerges. Much late 20th century cosmology drifted towards the conclusion that physical reality is self-similar to information and computing. But in the context of this discussion, coming as it does from within the computing domain, the opposite needs to be said – computing is and always will be a physical system and as such, subject to the same parameters and limits one finds in any physical system.

Before Godel and Turing, one could be excused of wondering if abstraction systems were different in any real and causal way, from the systems they abstracted. Today, we aren't allowed that naivete. Instead, we are forced to identify the layered control grammars in physical systems and the causal influence (thermodynamic) topologies in the rarified worlds we call "information" and "computation".

Randall

Hi Randall,

Thanks for the topic and for your (as usual) very thoughtful posting. Unfortunately, I will not be at the AI Meetup due to a previous commitment. Therefore, I’m posting here some of my thoughts on this subject:

I agree that there are limits on intelligence - either artificial intelligence or "natural" intelligence. The reason why there are limits on intelligence is that I believe that intelligence has to do with predicting the future and there are definite limits to how well the future can be predicted. For example the bizarre systems that Monica has described will have very limited predictability.

I have read your posting and I know that I do not completely follow your discussion, but nevertheless, I will go out on a limb and say that, to me, Godel's Theorem and Turing's Computability Theorems are not really directly relevant to the question of the limits on intelligence. To me both Godel's and Turing's theorems are mostly about deciding if various reductionist procedures are either finite or infinite. I know that to a mathematician there is a big difference between a finite number and an infinite number (joke intended), but to a practical intelligence trying to predict the future, a really really big number versus infinity is not that different. Or in the reciprocal space, a really really small number versus exactly 0 is really not that different. Since futures are almost never exactly predictable, the business of intelligence needs to be more about probabilities instead of exactness and a probability of 10^-100 is effectively the same as a probability of exactly 0.

The quintessential non-computable Turing problem is the halting problem - the question of deciding whether a given Turning machine on a given input tape will run forever or will halt in a finite time. I don't think this really matters to intelligence - for example a Turing machine that only halts after 10^100 steps is equivalent to a machine that never halts for all intents and purposes to any practically intelligence - at least in our universe.

Godel's theorem states that there are true statements that cannot be proven within a given mathematical system. Now a mathematical proof is defined to be a finite set of symbols that prove the proposed theorem. One possible candidate for a true statement that may not have a (finite) proof is Goldbach's conjecture. Goldbach’s conjecture is that all even numbers can be written as the sum of two prime numbers. Goldbach’s conjecture has been verified for all even numbers up to 1.6*10^18 so I would say that for all practically purposes, Goldbach’s conjecture has been proven. Yes, it entirely possible that someone could find a counter example – such as a 20 digit even number that cannot be written as the sum of two primes but I think it is very unlikely. In fact, there are mathematical arguments that say that larger even numbers are more likely to be written as the sum of two primes than smaller numbers – so a counter example would probably have already been found if Goldbach’s conjecture was false. So the fact that it has been verified up to 1.6*10^18 is enough of a proof for me that Goldbach’s conjecture is true – for all practical purposes.

So basically, what I am saying is that likelihoods or probabilities are what predicting the future is about whereas Godel’s and Turing’s theorems are all about absolutes – and therefore, they are not directly relevant to the limits on intelligence.

Thanks Frank, your statements are valid. But the conclusion you draw seems to lie outside of what I would call the breakthrough of the Godel/Turing revolution. It is of course true that some problems are complex in ways that either hinder or prevent linear computational solutions. But the larger reading of Godel/Turing is that abstractions are no different from causal physical reality – have the same limitations. Likewise, the physical world is no different from information and computing. You can't make a computer that isn't physical and you can't find or build a physical configuration that doesn't behave as a computer (information undergoing transforms). The limits of computation are the limits of physical causality and vice versa.

From this grounding in the "universal transitive property of computation" (made that up), we accept that complex and terminally complex problems are both complex and terminal because of the nature of configuration and transformation and not because of any imaginary properties intrinsic to and novel to either side of the (imaginary) computation / physical causality split. Computation doesn't make a problem difficult or impossible. The problem itself is responsible for its computability. This is an important distinction.

To move forward, we accept these limits and attempt to distinguish the difference between problems that will benefit from better algorithms and problems that are inherited form the topology of their own demands on information and transformations on that information.

When faced with intrinsically incomputable problems, better engineering only helps us reach the intrinsic limits faster and be more aware of why.

How does nature deal with intrinsic causal limitations? Well, to the extent that Godel and Turing have forced us to accept that we humans, and everything we think, are part of nature, than we have to accept that evolution is the means by which we learn to take maximum advantage of available resources in the pursuit of the grand computation. Part of this grand computation is figuring out which of the almost infinitely possible computations we can and must ignore – computations that won't result in compression or will compress down to answers that don't matter.

This discussion, this topic, is the front line filter in this process.

I think the frustration people feel about the idea of computational limits says a lot about the fact that we just plain don't like limits. That we accept them (begrudgingly) in our physical environment doesn't transfer without a tantrum to the seemingly limit-free world of software and computation. We accept that we can't have free energy and anti-gravity hover cars, but become sanctimonious children when faced with the self-same limits with regard to access to the information and answers that would better our position. It matters little that this information is just as impossible as perpetual motion. We simply can not accept that information, like travel, requires energy and the right vehicle, and is limited by access routs, by traversable topologies, by the same limits that exist in our more pedestrian and familiar physical world.

What is it about the our experience of the physical and our experience of the informational that sets the two so apart? I think the answer lies in the fact that we have sensors throughout our body maintain constant awareness of much of our physical self and physical world. On the other hand, it seems for all the world that we have very little access to information about the physical reality that is the basis and environment of the information we take in, store, and perform transforms upon. Sure, we have this grand edifice of "consciousness, but it arrives at an extremely high level, stripped completely of the bit by bit goings on upon which it is built. As a result, we tend to form "understandings" about information that are much more etherial, open ended, ungrounded, and non-causal. From the limited vantage consciousness affords Turing and Godel are just big fat buzz-kills.

Randall

So much of our experience and compression of the physical world is taken for granted. We didn't build it. So how would we know much about all of the reasons it isn't some other way and is the way it is? When we create computers and software, we are forced to accept, square and sober, the wild and wooly indirection that is the difference between what we want and what can be. In the process we acquire a long list of the ways that things can go wrong and theories that attempt to make these ragged lists elegant and hierarchical. Along the way, the rift that appears to separate information from physicality grows into a chasm.

But what we learn when we play god is more than just practical. I suggest we will learn a lot about the quote un-quote "physical world" as we superimpose, the "what could be, isn't, and why" that we have learned in our explorations of abstraction and computation on top of our empirically and experientially acquired knowledge of "what is".

From this new vantage, something so mundane as a mountain, instead becomes the probabilistic sum of a cascade of causal interactions (a graph?). As such the category "mountain" is recast as a meta-concept that can be mapped across domains for ever greater meta-knowledge. Mountain becomes concept, becomes data configured towards computation.

If there is a definition of the future of computation, maybe it is as integration with and inseparable from what we have to this time called "physical reality".

Randall