The halting problem - Intuition Stories - Speculative Machines and Us

intuition
stories

Stories for teaching, learning, and research: From electric brains to generative AI, explore intuition in digital computing histories through 40 key concepts, initiatives, milestones, systems, and publications. Uncover how questions about sensing, thinking, and speculating animate current debates on machine intelligence.
The halting problem
Computability problem proving that no algorithm can decide if a program halts on all inputs
The halting problem

The halting problem

In his pivotal account of the Universal Machine in his 1936 paper ‘On Computable Numbers’, the mathematician Alan Turing pointed to “the incomputable” in mathematics, showing inherent limits to computation.

In doing so, he articulated ‘the halting problem’: that a general algorithm will never exist which can determine in advance whether an arbitrary computer programme will finish running or continue on forever. The halting problem is foundational to computer science, influencing AI models and algorithms.

Digital media scholars, in turn, explore the speculative promise of computational undecidability. The computer scientist and literary scholar N. Katherine Hayles argues that Turing’s vital legacy has been to illustrate the generative limits of pre-emptive control in algorithmic systems: ‘the more control is codified and extended through computational media, the more apparent it becomes that control can never be complete’ (Hayles, 2017: 203).

Recognising the extent to which unknowability and contingency characterise computational architectures is important for understanding how these systems could operate otherwise, for how recursivity could be opened ‘up to many different and thus transversal epistemologies’ (Parisi and Dixon-Romàn, 2020: np).

Also important to foreground – as cybernetics, STS, actor-network-theories, affect studies, and ecological media scholarship have long illustrated – is that beneath any technology presented as “artificial”, “automatic”, or “autonomous” are dense networks of affective and socio-technical relations (Wilson, 2010; Amoore, 2020).

Artificial intuition
AI concept proposing how machines might simulate intuition for rapid, creative, or uncertain decisions
Artificial intuition
Neural network
AI architecture inspired by brains, enabling learning from data through layered connections
Neural network
Post-cybernetic logic
Leveraging computational uncertainty to generate value
Post-cybernetic logic