Turing’s Titanic Machine?

It is in the nature of things that 1912 is generally more remembered for the sinking of the “unsinkable” Titanic than it is for the far more world-changing event: the birth of Alan Mathison Turing in a London nursing home on a Sunday in June of that year. The Turing Centenary presents a timely opportunity for us to remember the startling depth of impact of Turing’s universal machine over the last 75 years.

Back to Top

In this brief review I examine challenges to its continued primacy as a model for computation in daily practice and in the wider universe. In doing this, the Titanic analogy is surprisingly useful, even apt from some points of view. It reminds us of the achievements of science and engineering, and its precarious coexistence with the often surprising unpredictability of events in nature. Of course, this is a controversial area, and the arguments are too finely balanced for definitive conclusions. In the end we might decide that, at a basic level, things have not gone that far beyond Turing’s own clarifying constructs and his persistent uncertainties about their adequacy.

So why are questions about the adequacy of the Turing model of computation³⁴ so difficult to resolve, so avoided by “normal science,” and so controversial among those who debate the issues?

There are both theoretical and modeling uncertainties at work here. On the mathematical side, we have a well-developed theory of classical comput-ability—and incomputability—based on the Turing machine model and its oracle-enhanced incarnation. On the other side we have the Internet, artificial intelligence, and nature, with closely related models sometimes termed new computational paradigms.

Turing’s universal machine famously “computes” an incomputable object—the halting set of inputs on which its computations terminate—appearing over the years in many different guises. But in what sense is such an object computed? Why does it matter? A short answer is that it is computed much as the Mandelbrot set appears on a computer screen. It is computably enumerable. A great deal of research activity is directed at discovering incomputable objects that are not just notational variants of the halting set, and making the incomputable objects we have more accessible and more at home in the real world. Back in the 1950s, John Myhill²² elegantly brought all known naturally arising incomputable objects within the immediate orbit of the halting set.

In 1970, the negative solution to Hilbert’s Tenth Problem,²⁰ when combined with results from classical computability arising from contrived priority constructions, circumstantially pointed to a very rich infrastructure of incomputable objects. All of the artificially derived examples of computably enumerable sets are computably equivalent (according to Turing’s definition) to a set of natural number solutions for a Diophantine equation. But no mathematically natural example has been found. Given a particular description of a set of numbers, there are no techniques for identifying its level of incomputability—unless we get lucky and describe it in terms of the halting set, or its iterated relativizations. So mathematics provides nothing but the most schematic of examples of incomputability and a strictly limited toolbox to take into the real world.

There is a reasonable conjecture that mathematical failures are in some way essential; if there is something new to learn from nature and contemporary computing practices, the theoretical ramifications may be more complicated. There are classical results from the 1960s that tell us the problem of recognizing whether a given Turing machine has incomputable halting set or not is very far from being computable. In fact, it involves no less than three iterations of Turing’s halting problem. C.E.M. Yates³⁹ tells us that even problems computably equivalent to the halting set of a universal Turing machine may not be recognizably so. Odifreddi²⁴ quotes the eminent recursion theorist John Myhill as saying “recursion theory is a subject full of ingenuity, but not of intelligence.” However, one can often discover interesting conclusions out of the arcane technicalities of classical computability theory.

What do I mean by more complicated? I briefly review the territory (ignoring important topics, in particular the complexity theorist’s refinements) with the Turing model remaining a key element, though observed in new ways.

Back to Top

Computation Disembodied

What was clearly new about the Turing model of computation was its successful disembodiment of the machine. For practical purposes, this was not as complete as the post-Turing theoretician likes to pretend: the reembodied computer that is now a familiar feature of the modern world was hard won by pioneering engineers. But, for the purposes of the stored program computer, and for the proof of incomputability of the halting set, the essential disembodiment was that delivering program-data duality. This playing down of distinction between information and process has been taken further, and become a familiar feature of programming and theory. As Samson Abramsky puts it (private communication, 2011):

“Turing took traditional mathematical objects, real numbers, functions, etc. as the things to be computed. In subsequent work in computer science, the view of computation has broadened enormously. In the work on concurrent processes, the behavior is the object of interest. There is indeed a lack of a clear-cut Church-Turing thesis in this wider sphere of computation—computation as interaction, as Robin Milner put it.”

In the quantum world there is a parallel duality between matter and energy. All this has given rise to a standard computational paradigm vulnerable to surprises from the natural world. Physical processes not subject to data-process duality will not be assuredly different. But beneath the “normal science,” theoretical inadequacies may be brewing—or not—according to the viewpoint. The challenges to the standard model are varied, but most seem to have an impact on universality.

Among those who care about such things, there are different responses to the situation:

1. Confident of the unsinkability of the standard model, one can apply it ever more widely to what we observe in nature, and let it mold our expectations of what computing machines can achieve.
2. Distrustful of the science, one can open one’s mind to observation and surprises, speculate about inconsistencies with the standard model, and seek to philosophically clarify one’s perceptions.
3. Renewing Turing, one can use one’s observations and ingenuity to design new models of computation, directly inspired by real-world processes or arising from abstract theoretical considerations, or both.
4. Consistent with a genuine paradigm-change being in process, one can aim to develop the analysis of computability and incomputability, to the point where the theoretical context successfully hosts a convincing new view of what one observes, that is, a classical computability theoretic response.

As it turns out, each of these directions has been pursued with some success.

The first is probably still the most generally respected among theoretical computer scientists, although it has lost some of the dominance it had even 15 years ago. The second becomes more common the further one gets from the certainties of mathematics, while at the more scientific end can tip into direction three. The third direction has had modest success, despite attracting the attention of a determined rearguard from the first school of thought, most notably that of distinguished elder-statesman of computability, Martin Davis. Here is what Davis¹³ has to say about the so-called hypercomputationalists:

“The great success of modern computers as all-purpose algorithm-executing engines embodying Turing’s universal computer in physical form, makes it extremely plausible that the abstract theory of computability gives the correct answer to the question ‘What is a computation?’ and, by itself, makes the existence of any more general form of computation extremely doubtful.”

Of course, direction three intersects with mainstream areas looking for mere efficiency gains from natural computing, connectionist models, and quantum computing, among others. Adherents of approach four are quietly working away, often with no strong sense of doing anything related to actual computing. Let’s call the proponents of direction one: reductionists, of two: impressionists, of three: remodelers, and four: incomputability theorists (otherwise known as recursion theorists). There are overlaps between all four groups. The first three groups are very large. The incomputability theorists form more of an isolated sect, peripheral, tiny in numbers, and as a group (with notable exceptions) not visibly concerned with real-world relevance—inheritors of a proud pure-mathematical tradition, a tradition within which they are too busy proving theorems to tell us, emerged the stored program computer. Like Turing, the incomputability theorists inhabit the interface between computer science and mathematics, not wholly at home in either community.

The role of the reductionists is largely reactive, and in the end, driven by an agenda as speculative as anyone else’s. Kurt Gödel famously took some convincing of the Church-Turing thesis just for functions over the natural numbers. Areas needing special attention from the reductionists include quantum physics, theory of mind, the emergence of form in nature, and the various novel proposals from the remodelers. The notable successes of the reductionists include David Deutsch’s¹⁵ placing of the standard model of quantum computing firmly within the scope of the Turing model—though the model does not make full use of wave function collapse. Indeed, Calude and Svozil⁷ have shown that under reasonable assumptions, quantum randomness entails incomputability. The mind is very hard to pin down theoretically, but Deutsch is following a well-established reductive tradition when he argues (in “Question and Answers with David Deutsch,” Newscientist.com, Dec. 2006):

“I am sure we will have [conscious computers], I expect they will be purely classical, and I expect that it will be a long time in the future. Significant advances in our philosophical understanding of what consciousness is will be needed.”

---

What was clearly new about the Turing model of computation was its successful disembodiment of the machine.

---

Within the philosophy of mind there is a strong tendency toward physicalism and functionalism, both of which open the door to some version of the Turing model. The functionalist (see Hilary Putnam, 1960) stresses what a computer does as something realizable within diverse hardware. And there are successful mathematical reductions of particular emergent phenomena to computable solutions of differential equations, such as those in Turing’s 1952 morphogenesis paper.³⁵ An important expression of the functionalist view in computer science is provided by the notion of a virtual machine, whereby one achieves software implementation of a given programmable machine. Aaron Sloman³¹ and others have usefully applied the concept to AI.

Back to Top

Messages from the Real World

There are a number of features of real-world “computation,” that is, how nature and people in real interactive situations compute, worth spotlighting before addressing particular phenomena and models. Here the impressionists abound, sometimes viewed as infiltrators from the anti-science reaction in the humanities that has given us epistemological relativism, deconstruction, and the so-called “science wars” associated with Alan Sokal. Dissent from the pervasiveness of a mechanical causality can be traced back to the “occasionalism” of the influential Islamic philosopher al-Ghazali. This is often interpreted as reconciling a level of law-like causality with the possibility of miraculous and surprising infringements of it. One can see echoes of this in the latter-day links between theology and emergentism. Of course, if one sees truth as being computed somewhere (by God?), a change in our conception of what is computable does impact on our understanding of what we can know about the world.

The Mathematician’s Bias. A clear sign of a paradigm under unaccustomed examination is the October 2010 ACM Ubiquity Symposium on “What is Computation?” with a number of thought-provoking contributions. Part of the Editor’s Introduction by Peter J. Denning reads:

“By the late 1940s, the answer was that computation was steps carried out by automated computers to produce definite outputs. That definition did very well: it remained the standard for nearly 50 years. But it is now being challenged. People in many fields have accepted that computational thinking is a way of approaching science and engineering. The Internet is full of servers that provide nonstop computation endlessly. Researchers in biology and physics have claimed the discovery of natural computational processes that have nothing to do with computers. How must our definition evolve to answer the challenges of brains computing, algorithms never terminating by design, computation as a natural occurrence, and computation without computers?”

In another contribution to the Ubiquity symposium, Lance Fortnow asks: “So why are we having a series now asking a question that was settled in the 1930s?” He continues:

“A few computer scientists nevertheless try to argue that the [Church-Turing] thesis fails to capture some aspects of computation. Some of these have been published in prestigious venues such as Science, Communications of the ACM, and now as a whole series of papers in ACM Ubiquity. Some people outside of computer science might think that there is a serious debate about the nature of computation. There isn’t.”

Undeterred, Dennis J. Frailey thinks it is the mathematicians who have got it wrong:

“The concept of computation is arguably the most dramatic advance in mathematical thinking of the past century…Church, Gödel, and Turing defined it in terms of mathematical functions…They were inclined to the view that only the algorithmic functions constituted computation. I’ll call this the “mathematician’s bias” because I believe it limits our thinking and prevent us from fully appreciating the power of computation.”

Clearly, we do not have much of a grip on the issue. It is the old story of the blind men and the elephant again. On the one hand computation is seen as an essentially open, contextual, activity with the nature of data in question. Others bring out a formidable armory of theoretical weapons in service of the reductive project—for them there is nothing in concurrency or interaction or continuous data or mental recursions to stretch the basic capabilities of the Turing machine.

It is true that, in the pre-computer age, it has been the mathematically aware that have clarified difficult problems and vague intuitions. We look very selectively in the space available at how people have tried to isolate and clarify what is difficult about the reduction of computation, particularly in nature, to the basic Turing model.

Fuzziness, Continuous Data, Mistakes. Incomputability in the natural world may be difficult to pin down definitively, but there are many people—our impressionists—who think they know it when they see it. This, of course, is a problem. We may have a Turing test for intelligent machinery that seems to tell us something useful: though how useful is open to question. But why would a human observer-based test for in-computability inspire confidence?

Let us look at an example from another of the Ubiquity symposium contributors, Peter Wegner writing with Dina Goldin:³⁷

“One example of a problem that is not algorithmic is the following instruction from a recipe [quote Knuth, 1968]: ‘toss lightly until the mixture is crumbly.’ This problem is not algorithmic because it is impossible for a computer to know how long to mix: this may depend on conditions such as humidity that cannot be predicted with certainty ahead of time. In the function-based mathematical world-view, all inputs must be specified at the start of the computation, preventing the kind of feedback that would be necessary to determine when it’s time to stop mixing.”

The main problem here, according to the authors, is the fuzziness of the context, which the Turing machine, dealing with discrete data, exactly presented, cannot handle. There are interesting things going on here, though the logically literate reductionist will not be worried for a second. She knows all about approximations to infinitary data. She knows that if the real data is computable enough to get hold of and compute with, then implicit in that is a computable sequence of finitary approximations. That is how we compute using π, which needs an infinitary description, a series or an infinite decimal, say, on our laptop, which is, as we know, an embodied universal Turing machine.

But what about the fuzziness and unpredictability of the environment in this example? There are two approaches here. You can play God, and close up the environment. Take hold of the whole universe, if necessary, like Laplace’s predictive demon; the aim being to give the incomputability nowhere to hide. The whole point of the example is that it is something happening in the kitchen that is the challenge to the Turing model. If the challenge is created somewhere else, other than in our kitchen, then why are we bothering cooking? But assuming we know the boundary conditions, within which we have proper definitions of the terms we use in the recipe, complete with the underlying approximations, our universal Turing machine is well equipped to carry out the procedure.

Alternatively, you can work relative to what you observe, and not bother about where the context arose. In 1939, Turing provided us with the oracle Turing machine, which is just a Turing machine made to carry out our cooking task in the unsourced environment. It grabs the environmental data fuzzily presented using real numbers, and computes algorithmically using the approximations we are presented. We know we get the approximations—that is how we observe, do our science, and largely survive in the world.

And the recipe is executed by perfectly standard, suitably chosen, Turing functionals.

There is a lot of logical and computational fuzziness around nowadays, fuzzy sets, fuzzy logic, fuzzy Turing machines, among others. Of course, what it comes down to is using real numbers as data instead of natural numbers (or similar), and doing something recognizably algorithmic with them. There is a lot of interest in the “something” from the semantic point of view, but not so much from the computability theoretic one. In short, there is nothing that presents much of a challenge to the reductionists here. For some it will be seen as moving the deck chairs around on the standard model Titanic, a useful job, but not contributing much to the traversing of icebergs. Others will see the fuzziness as an indication of something happening which the reductionists did not look at closely enough. Something that is brought out more clearly when looking at, say, reductions of mentality to brain function; or biology to quantum mechanics.

On the other hand, remodelers have devised interesting proposals for machines with fuzzy aspects and more sophisticated characteristics than those seen in the above example. For example, Wiedermann and Leeuwen³⁸ build creatively on Turing’s own variations on the Turing machine model.

Another aspect of real-world computation (or reasoning) is its frequent non-monotonic nature: that is, the incidence of mistakes and adjustments, whereby information is adjusted over time with increasingly useful outcomes. In his talk to the London Mathematical Society on Feb. 20, 1947 (quoted in Hodges¹⁷), Turing says:

“…if a machine is expected to be infallible, it cannot also be intelligent. There are several theorems which say almost exactly that.”

According to Leavitt,¹⁹ Turing seems to have identified with machines. And he was rather prone to mistakes (even his famous 1936 paper needed a correction after publishing), so may have had a visceral understanding of what we now call Δ⁰₂ sets! One can certainly solve the halting problem this way. That is not the same as actually computing it, but in a world in which mistakes are learned from, not far off.

Parallelism and Interaction. So far, the reductionists are winning hands down against the impressionists. One needs the help of some remodelers.

In 1970, Georg Kreisel was ahead of his time in speculating on the possibility of a collision problem related to the three-body problem that might give “an analog computation of a non-recursive function (by repeating collision experiments sufficiently often).”¹⁸ This ties in with problems in applied mathematics with classical causality applied in complex environments. What makes the situation different is the infinitary mathematics involved in extending the computable causality to more than two bodies. It opens the door to the possibility of incomputability. Such a possibility is brought out even more dramatically by Xia’s solution to the Painlevé problem³⁰ of finding singularities, without collisions in small Newtonian systems.

Actually, the impressionist does not need to know much about mathematics to convince herself of the novelty of outcomes from natural processes involving a high degree of connectivity, such as the weather, turbulent flow, social movements, the Internet. The relevance of the computational mathematics of randomness, chaos theory, orphogenesis, game theory, computational complexity, as dictated by the particular situation is just an extra indicator of the problems we have theoretically capturing what is happening. What is convincing is the surprisingly unexpected character of some observed phenomena. The most shocking is the unpredictability of events affecting a framework we are part of: the mind the weather war the events of September 11.

The reductionist has a problem linearizing this. The mathematician’s bias is still valid in that useable data must be extracted from even an interactive process; that is how we work. But there are situations in which there is no obvious computable function capturing what is happening.

Infinitary Computation and Reality. A common criticism of real-world in-computability comes from those whose focus is practical computation. The apparent prevalence of discreteness at the basic quantum level breeds unease about the scientific role of real numbers Richard Feynman once remarked.

And if one can successfully put a bound on the number of subatomic particles in the universe, and can get by with a calculably finite number of rational numbers in practical scientific work, then surely this makes the classical mathematics of real numbers a mere convenience—one which with a little extra thought can be dispensed with? The finitist is invariably an impressionist. Finitism may be dressed in the language of philosophy, but its origin is very basic observation with little in the way of theoretical underpinnings.

However, most of us who are not committed occasionalists tend to accept a level of algorithmic structure to the universe. This is how we survive, benefitting from a level of computability of nature brought out by Newton’s use of the calculus. Algorithms may be finitely describable. But even simpler mathematics than that which gave us incomputability gives us transcendental real numbers, such as π, e, and 2 ². The finitary universe is just the tip of an iceberg full of hierarchically generated mathematics, much of it clearly relevant to our scientific and computational enterprise.

Some of this theory gives us descriptions of natural phenomena sensitive to small variations in initial conditions. This sensitivity can outstrip any level of approximation with which physicists say we can get by. So we end up with a tension between the mathematics that constrains observed reality, and scaling factors, which make things very complicated and potentially incomputable—and that potentially undermines expected symmetries in the physics.

Back to Top

Modeling Makes Sense

The models we encounter may simply be designed to capture some computational aspect of nature, or more specifically, of mentality; later to be worked on by the theorist, extending, generalizing, or particularizing the extracted archetypes. And then, as a by-product, these may deliver some more general perspective on computation itself. Examples include neural nets, Alife, or quantum computers (see Springer’s Handbook of Natural Computing.²⁹)

Preliminary to these may be models not directly intended as computational models at all, having been devised as routes to more precise descriptions of reality. Just as in mathematics the computational infrastructure of descriptions are not always easy to characterize, so in the real world. The models themselves may be “under construction” in some way, as is the standard model of particle physics. As well as leading on to more explicitly computational models, their properties are a rich source of impressions, and can be subjected to more technical analysis by computer scientists and mathematicians.

Of course, the mathematics of science is continuous rather than discrete. Some of the most interesting work here comes from the computable analysis community. Marian Pour-El, best known for her classic book with Ian Richards on Computability in Analysis and Physics, wrote (with Ning Zhong) the intriguingly titled The Wave Equation with Computable Initial Data Whose Unique Solution Is Nowhere Computable.²⁶ But today the physical relevance is not so clear.

One should also include here the scrutiny of emergence and its fractal analogues, of chaos, turbulence, and (especially important) the analyses of self-organization of Prigogine et al. An indication that something interesting is going on comes out of the discussion of irreversibility and the challenge to simple determinism. See Prigogine’s The End of Certainty,²⁸ or From Being To Becoming:²⁷

“…our confidence in the deterministic description of nature has been shaken both at the microscopic level and at the macroscopic one.”

We should mention the importance of the mathematics for researchers such as Vela Vellupillai³⁶ in economics. And the widespread interest in the computational characteristics of the Mandelbrot and Julia sets, both from high-profile figures such as Roger Penrose and Steve Smale, and from complexity-theorists and others. The computability of the Mandelbrot set is still a hotly debated question (see Peter Hertling’s nice overview¹⁶). See Cooper and Odifreddi¹⁰ for more background to the computational modeling.

Hypercomputational packages. So what about the consciously explicit modeling of incomputability? There is a common perception (sometimes very superficial) that the proposals under this heading are all wrong, even among people who are inclined to question the Turing model impressionistically. This is particularly true among those familiar with Martin Davis’ series of papers on hypercomputation. A highly respected researcher, author, and co-solver of Hilbert’s tenth problem, he is adept at spotting where a thought experiment is invalidated by contamination with possibly incomputable reals.

The case of Copeland is an interesting one. Davis is not impressed by possibly incomputable oracles computably delivering incomputability, while Copeland clearly is. How to explain this? There seems more to it than just Davis’s superior grasp of the technicalities. It seems that Copeland the philosopher has a less schematic conception of his proposal in mind, with his oracles based on an underlying impression of what the real world provides. There is a dichotomy between the mathematician’s god-like overview of the computing universe, and the computing in context of the impressionist, or for that matter, the practical computer scientist. So does Copeland belong here at all, annoying Martin Davis and others with his mathematically cloaked impressionism?

Here is a clear statement of his position:¹¹

“Naturally, the crucial question is: Are there real physical processes that can be harnessed to do the work of Turing’s ‘oracles?’ If so, computing machines that are forbidden by the thesis improperly known as the “Church-Turing thesis” can in principle be constructed. Leaving the issue of harness-ability to one side, I think it would be profoundly surprising if the physics of our world can fully be given without departing from the set of Turing-machine-computable functions.”

So the interest of “hypercomputation” as narrowly defined by Copeland depends on something else. Of course, Copeland has done important and perceptive work in regard to the history of the computer and the role of Turing. But the grip of the mathematics is less sure, and delivers nothing new. In contrast, the hypercomputationalist, Hava Siegelman does seem to belong here. Her “something else” is neural nets with real weights attached: ingenious, solid research, but still having problems delivering incomputability uncontaminated by incomputable reals from elsewhere, as observed by Davis. Tien Kieu’s proposed use of the Adiabatic Theorem from quantum mechanics is given sharply critical attention. (See Martin Ziegler⁴⁰ for a different take on recent controversies.)

Commendably passing the Davis test is Istvan Németi and his collaborators. Having both a firm grip on the logic and its history, and of the physics, the computational properties of his rotating black holes provide a delightful demonstration of incomputability in nature in action, although there is the inevitable manipulation of the specific instantiation of the physical conditions. One needs to see a Németi presentation to feel the full power of the thinking underlying this work. His paper²³ with Gy Dávid shows hypercomputing (computation beyond the Turing barrier) to be consistent with general relativity, and also discusses why hypercomputing seems to be consistent even with the addition of quantum mechanics. More recently, Andreka, Németi, and Németi² contains new ideas relative to earlier papers, such as a discussion of new kinds of solutions for the so-called blue shift problem.

Examples of incomputability arising from quite simple classical models can be found in a series of articles by Beggs, Costa, and Tucker and other collaborators. Of course, the manipulation of the physical conditions is key, and even the authors describe their work as a ‘thought experiment’. But the work is convincing enough for Martin Ziegler (private communication) to offer the opinion that although “experience seems in favor of [the] so-called (Physical) Church-Turing hypothesis [which] roughly claims that anything computable in physics can also be computed on a Turing machine,” it is true that “in the sense that the hypothesis’ reference to ‘physics’ should be made precise as ‘physical theory T,’ and for some such theories T, the claim is indeed true while false for others.” Beggs, Costa, and Tucker³ introduced the concept of measurable number of an oracle Turing machine. (See Costa et al.¹² for Turing machine simulation by differential equations. The main criticism here is not the soundness of the technicalities, but the relevance of the thought experiment to physical reality.)

---

Most of us who are not committed occasionalists tend to accept a level of algorithmic structure to this universe. This is how we survive, benefitting from a level of computability of nature brought out by newton’s use of the calculus.

---

On the whole, the feeling is that proofs and theorems are being used to disguise the fact there is something we do not fully understand about physical computation. Though the ingenious manipulations of basic science by Németi and Andreka, Beggs, Costa and Tucker, and others, may turn out to have been highly prescient in the course of time.

Back to Top

Embodying the Halting Set

So what is going on here? We quote Peter J. Denning introducing the ACM Ubiquity Symposium on “What is Computation?” as saying:

“Researchers in biology and physics have claimed the discovery of natural computational processes that have nothing to do with computers.”

With Lance Fortnow distinctly underwhelmed: “Some people outside of computer science might think that there is a serious debate about the nature of computation. There isn’t.”

As often happens when experts disagree, the truth lies somewhere in between.

Mathematically, there is essentially only one basic procedure for getting incomputability: take a computable context, and add a quantifier or more to move beyond locality. However you dress it up (via randomness, say), this schematic perspective prevails. For any halting set, it is just one existential quantifier added.

For those of us (like Turing) looking for mathematical descriptions underlying all real-world phenomena, there is a sneaking suspicion: All the fuss and descriptive variety associated with incomputability in nature and its models merely cloak avatars of halting sets for different machines. And all the connectivity and interactivity we observe in nature, and require in new computational paradigms, is what provides the underpinnings that move the quantificational glove puppet. For the derivation of a halting set, the connectivity is provided by how we observe the Turing machine. By examining a globality of instants in time, we structurally focus on a component of an emergent incomputable object. The Mandelbrot set is a more graphic example of an emergent process, involving, for the purposes of the discrete data feeding into the computer simulation, just one universal quantifier.

Morphogenesis, Definability. Back in the early 1950s, Alan Turing became interested in how certain patterns in nature arise. His seminal importation³⁵ of mathematical techniques into this area were to bring a new level of computability to natural phenomena, while improving our understanding of some of the problems pointed to by the impressionists. We are now in an area where impressionism and modeling go hand-in-hand.

Turing’s equations link up with the relationship between emergence and descriptions pointed to by the fractal example. Of course, some halting problems are solvable, as are some Julia sets.⁴ See Cooper⁹ for a more detailed argument for the two-way correspondence between emergence and appropriate descriptions, opening the door to incomputability in nature, and for the grounding of the observed robustness of emergent phenomena in a framing of the descriptions as mathematical definability.

So Turing’s approach is seminal, illuminating the connection between in-computability, mathematics, and natural phenomena. It has been carried forward by James D. Murray²¹ and others, and though things get a lot more complex than the examples tackled by Turing, it is enough to make something more coherent from the confusion of impressions and models. All that the hypercomputability theorists are getting excited about is embodiment and reframing of the standard model, with or without oracles. But the embodiment does extend to the emergent halting set and possibly hierarchically beyond, taking us into a world beyond basic algorithms (see Chaitin’s recent take on creativity and biology.⁸)

There is some elementary but not widely understood theory that glues the whole thing together. As more and more people are coming to see, going back to Turing with the eyes of a Turing will do wonders.

Back to Top

Definability in the Real World

One may theoretically tame the models of the modelers. But back in the real world, the impressionists will not be so impressed, and will see a lot missing in both models and explanation, as well as some puzzles regarding computability in some very challenging environments. Regarding the various models, there are too many examples to quote. For instance, as Rodney Brooks⁵ says:

“…neither AI nor Alife has produced artifacts that could be confused with a living organism for more than an instant. AI just does not seem as present or aware as even a simple animal and Alife cannot match the complexities of the simplest forms of life.”

Two particularly challenging natural environments are provided by the brain, and the standard model of particle physics.

For the brain we have very interesting connectionist models (see Teuscher³³ for Turing’s contribution), and we are not surprised to read a leading researcher like Paul Smolensky³² saying:

“There is a reasonable chance that connectionist models will lead to the development of new somewhat-general-purpose self-programming, massively parallel analog computers, and a new theory of analog parallel computation: they may possibly even challenge the strong construal of Church’s thesis as the claim that the class of well-defined computations is exhausted by those of Turing machines.”

But, as Steven Pinker puts it: “…neural networks alone cannot do the job,” and we too expect a bit more than the emergence of embodied incomputability, occupying a different level of data to that used for further computation. That is no real advance on the familiar Turing machine. It is not very promising for trans-Turing computing machines. Pinker²⁵ does not talk about incomputability, but does describe human thinking as exhibiting “a kind of mental fecundity called recursion,” giving us a good impression of real-life emergent phenomena reentering the system or the computational process as we would see it.

Is there really something different happening here? If so, how do we model it? Does this finally sink the standard Turing machine model? Neuroscience gives us an impressively detailed picture of brain functionality. Antonio Damasio, in his 1999 book The Feeling of What Happens, vividly fills out the picture we get from Pinker:

“As the brain forms images of an object—such as a face, a melody, a toothache, the memory of an event—and as the images of the object affect the state of the organism, yet another level of brain structure creates a swift nonverbal account of the events that are taking place in the varied brain regions activated as a consequence of the object-organism interaction. The mapping of the object-related consequences occurs in first-order neural maps representing the proto-self and object; the account of the causal relationship between object and organism can only be captured in second-order neural maps….one might say that the swift, second-order nonverbal account narrates a story: that of the organism caught in the act of representing its own changing state as it goes about representing something else.”

The book gives a modern picture of how the human body distributes its “second-order” representations across the impressive connectivity of the human organism, and enables representations to play a role in further thought processes.

Remarkably, once again, we find clues to what is happening theoretically in the 1930s work of Kleene and Turing. In his 1939 paper from Princeton, “Systems of Logic Based on Ordinals,” Turing is in no doubt he is saying something about human mentality:

“Mathematical reasoning may be regarded…as the exercise of a combination of…intuition and ingenuity…. In pre-Gödel times it was thought by some that all the intuitive judgments of mathematics could be replaced by a finite number of…rules. The necessity for intuition would then be entirely eliminated. In our discussions, however, we have gone to the opposite extreme and eliminated not intuition but ingenuity, and this in spite of the fact that our aim has been in much the same direction.”

To cut things short, Turing’s analysis depends on Kleene’s trick of building the constructive ordinals by computably sampling infinitary data needed to compute higher ordinals. The sampling is not canonical, there are lots of ways of doing it computably. This means we have an iterative process analogous to that described by Pinker and Damasio, which exhibits the irreversibility we expect from Prigogine. It is a picture of definable data represented using constructive ordinals. Turing’s representation of data is scientifically standard, in terms of reals. The basic computational structure of the connectivity is captured by functionals modeled by oracle Turing machines. The abstraction delivers a complex structure with a rich overlay of definable relations, corresponding to real-world ubiquity of emergent form impacting nontrivially on the development of the organism.

Back to Top

Embodiment Restored

The difference between this extended Turing model of computation, and what the modelers deliver is that there is a proper balance between process and information. The embodiment was a key problem for the early development of the computer, insufficiently recognized since the early days by the theorists, fixated on the universality paradigm.

Rodney Brooks⁶ tells how embodiment in the form of stored information has reemerged in AI:

“Modern researchers are now seriously investigating the embodied approach to intelligence and have rediscovered the importance of interaction with people as the basis for intelligence. My own work for the last 25 years has been based on these two ideas.”

I summarize some features of the framework, and refer the reader to sources^9,10 for further detail:

• Embodiment invalidating the ‘machine as data’ and universality paradigm.
• The organic linking of mechanics and emergent outcomes delivering a clearer model of supervenience of mentality on brain functionality, and a reconciliation of different levels of effectivity.
• A reaffirmation of the importance of experiment and evolving hardware, for both AI and extended computing generally.
• The validating of a route to creation of new information through interaction and emergence.
• The significance of definability and its breakdown for the physical universe giving a route to the determination of previously unexplained constants in the standard model of physics, and of quantum ambiguity in terms of a breakdown of definability, so making the multiverse redundant as an explanatory tool, and…
• Work by Slaman and Woodin and others on establishing partial rigidity of the Turing universe¹ promising an explanation of the existence of our “quasiclassical” universe.

As for building intelligent machines, we give the last word to Danny Hillis, quoted by Mark Williams in Red Herring magazine (Apr. 3, 2001):

“I used to think we’d do it by engineering. Now I believe we’ll evolve them. We’re likely to make thinking machines before we understand how the mind works, which is kind of backwards.”

So, Turing’s Titanic machine is showing good signs of unsinkability, but within a turbulent natural environment, embodied, full of emergent wonders, and a computational structure reaching far into the hazy distance. Turing, as we know, anticipated much of this, and, we hope, is smiling down on us, at the centenary of his birth in a Little Venice nursing home, now known as the Colonnade Hotel.

Back to Top

Back to Top

Back to Top

Back to top