What defines a calculation? The elusive search for the limits of computation

What defines a calculation? The elusive search for the limits of computation
Image: Intellect (generated)

In short: Computation is more than just arithmetic; it is a fundamental process of well-defined calculation. While we rely on digital devices to perform these tasks, the theoretical boundaries of what is computable remain a subject of intense philosophical and mathematical debate, challenging our understanding of both machines and the human mind.

The quest to define 'well-defined' mathematical statements gained momentum in the 1930s. Mathematicians sought a rigorous framework to distinguish computable processes from those that are not. Alan Turing famously provided the most influential solution by formalizing the Turing machine. Any calculation expressible through the initialisation parameters of such a machine is deemed computable. This definition encompasses modern programming languages like Python and Java, as well as calculations performed by abacuses or analytical engines.

However, this framework has distinct limits. Certain problems, such as the halting problem and the busy beaver game, remain outside the scope of computable functions. These are not merely ill-defined; they are problems for which it can be proven that no Turing machine exists to solve them. This has led to an open question in mathematics: does a more powerful definition exist that could capture these non-computable statements, or are they fundamentally beyond the reach of formal calculation?

Beyond the mathematical definition, philosophers and theorists have proposed alternative accounts of what constitutes computation. The 'simple mapping account' suggests that any physical system performs a computation if its microphysical states mirror computational state transitions. To avoid the extreme view that everything is computing everything—known as pancomputationalism—thinkers like Jerry Fodor argue that semantic content must be a necessary condition for computation. Meanwhile, Gualtiero Piccinini advocates for a mechanical philosophy, defining computing systems as mechanisms that manipulate medium-independent vehicles according to specific rules. This perspective is vital for understanding computation in diverse systems, from the human brain to quantum computers, where physical variables other than voltage may drive the process.

Opens the Intellect+ feed with this card first. Swipe up for the next one.

Sources

To cite this card, link to https://intellectplus.co.uk/app/science-computation.

How we source, check and correct cards: Editorial standards.

General information, not professional advice. Spotted an error? Flag the card or see corrections and complaints.

Intellect Plus is a visual educational discovery platform for exploring fascinating facts and ideas. Brain Food, Not Brain Rot. What is Intellect Plus?

Related

Finding something worth knowing…