What is Turing complete?

Turing completeness (TC) answers: ‘Can this system, in principle, express any computable procedure?’

Much hinges on ‘in principle’, which effectively means ‘in the absence of physical limits to running the computations’. In other words, computation involves both abstract software and physical hardware.

Our computational age has placed its bets on software, but this means doubling down on increasing the capacity of hardware as the physical substrate for running the computations. Therefore, when we imagine computational power, we place all our hopes and fears in the abstraction layer; we tend not to notice, or we downplay, the physical layer as a mere means to the larger end.

Compute itself has become the motor of history—no longer politics, economy, or knowledge production.

This brings us to the physical problem of infrastructure.

What is infrastructure?

Infrastructure answers: ‘How much of that power can we actually realize, at what speed, scale, reliability, and cost?’

This question is the hidden substrate of TC. It is hidden in the often heard caveat: ‘given unbounded time and memory.’ This clause functions like a horizon line. It sees the physical world as a limit against computational power: Data centers, GPUs, networking, storage tiers, cooling, redundancy, orchestration—this is the material extension of the tape and the acceleration of steps. It doesn’t change what is computable (in the Turing sense), but it radically changes:

what is technically feasible
what is economically viable
what is institutionally adoptable

In other words, infrastructure is to our Computable World as shipping lanes and national railroads were to Modernity—the power to bring more and more of the world under our computational influence.

Faster than Nature

Only 300 years ago, as the Enlightenment was getting underway, the Western world thought that the events of Genesis—the authoritative guide to History—occurred around 4000 B.C., give or take a few years either way.

Over the course of the eighteenth century, a couple of things happened to weaken this consensus. First, geologists started making sense of the fossils that they were finding in the striated rocks around them, some of which were being discovered through mining operations and the digging of canals for ‘inland navigation’. That is, they were being discovered in the very infrastructural activities that humanity was using to expand its purpose—mining, road making, canal construction. To try to make sense of the amount of time necessary for these formations to occur naturally elongated time well beyond 4000 B.C. Second, it became clear that the promised Second Coming was not going to happen anytime soon.

The long delay started to look like a permanent condition.

Combining these two factors is not just ‘the discovery of time’ as Toulmin and Goodfield put it, but a profound change in human consciousness. That sounds underwhelming—like an arcane historical specialty. But when we put this change in consciousness in the context of our evolving and expanding capacity to assert purpose, this is a vitally imporant development in that capacity.

Our intelligence expands exponentially, not just because we recognize elongated time, but because our capacity to ‘compute’ is crucial to that recognition. James Hutton writes in 1788:

The Mosaic history [the Old Testament] places this beginning of man at no great distance…. But this is not the case with those inferior species of animals…. We find in natural history monuments [fossils] which prove that those animals had long existed; and we thus procure a method for the computation of a period of time extremely remote, though far from being precisely ascertained.

Here ‘computation’ itself is that which needs to grow in order to more precisely measure the extremely remote duration that the fossil records are suggesting. Computational power, in other words, is becoming central to human consciousness, especially with respect to situating ourselves in a world governed by natural processes that we barely understand.

Has the latest acceleration of our computational power caused a crisis of purpose? Possibly. We have yet to understand how to adjust to its speed.

If the Enlightenment stretched time, computation accelerates it. What geology did for the past, infrastructure now does for the future. The question is no longer merely what can be computed—but who we become as we build the substrate capable of computing it.

Read more from the Wednesdays series.

This essay is also part my series on Our Computational World.

For more on cultivating out power of purpose, see ‘Cultivating Purpose and Discernment in a Computational World’.

Read my Substack posts on Purpose and Discernment and Faster than Nature for deeper dives into these themes.

What Is Turing Complete? Infrastructure, Computation, and the New Motor of History