14 - Turing Transcendent: Beyond the Event Horizon

Summary

The beginning

Turing's seminal 1936 paper ‘On computable numbers, with an application to the Entscheidungsproblem’ is remarkable in several ways: firstly he had set out to solve Hilbert's decision problem of the title, with the definitive discussion of what a ‘human computer’ could do, and what would constitute an ‘effective process’, but secondly because it, well one cannot say ‘almost in passing’ because Turing was keen to put his observations on mechanical processes to work, but it was a second product of the paper that it lay also the foundations for the not yet even nascent theory of ‘computer science’. The main point as Turing saw, was the ‘universality’ of his machine: there is a universal program or machine that can simulate any other. The story of the development of that science from Turing's work is retold elsewhere, and is not the aim or direction of this article. Nor are we going to trace the remarkable history of the theory of ‘recursive functions’ (now reclaimed as ‘computable functions’) thence until the present day. That story would involve not just the study of the Turing complexity of sets of numbers, and the computably enumerable sets, but later generalisations in ‘generalised recursion theory’ or ‘higher type computability theory’ where deep theoretical analyses of notions of induction and logical definability theory came into being in the late 1960s and 1970s. Such theories abstracted away from any machine model to notions of recursion or induction on abstract structures. These results are beautiful and very deep, and turn out to have intimate connections with mathematical logic and set theory.

Whilst this high road of increasing abstraction is very appealing intellectually, we have recently seen a flurry of research work drawing its inspiration from the original conception of Turing's machine model, and which tries to work with that, generalising what it could, in theory, compute when released from spatial and tem- poral boundaries. This article seeks to give some flavour of those ideas. Whilst it has to be said that a stretch of the imagination is required to send a computer off into a black hole, or to transcend ordinary time with its clock ticks of 0,1,2, … into some transfinite stage ‘ ω ’ or even further beyond, thus ‘ transcending ’ the finite, […]