Godel & Turing

Source: British Computer Society, Jun 2004/Nov 2007

His practical proposals for digital computing were streets ahead in their recognition of non-numerical structures.

Turing’s introduction stated that he hoped soon to base ‘the theory of
functions of a real variable’ on this concept, and this remark suggests that in 1936 he had every intention of redefining the relationship between Z and R in a constructivist way.

it is due to Turing’s quite inexplicable genius that he saw a connection, invisible to others, between Hilbert’s decision problem, the classical question of free will and physical determinism, and the computation of real numbers.3

G¨odel had shown how to encode as integers, statements about integers, and thereby showed the incompleteness of formal systems.

Turing showed how to encode operations on integers, by integers, and thereby showed the undecidability of formal systems. Thus Turing had the vital perception that operations and numerical data could be codified alike as a symbolic structure.

in a remarkable application of that perception, Turing showed that ‘it is possible to invent a single machine which can be used to compute any computable sequence’. This invention was his universal machine.

Turing’s mechanization of judgment through ‘weight of evidence’ (anticipating statistical methods very popular in Artificial Intelligence sixty years later) was perhaps a key step in persuading him of the boundless scope for the mechanization of human intelligence. In 1943, he discussed such ideas with Shannon, and in 1944 he was speaking of ‘building a brain’.

But Turing’s post-1945 views still marked a definite shift. In particular they implied a rejection of the view that uncomputable ‘intuitive’ steps were needed for the recognition of true but formally unprovable G¨odel statements.

Such uncomputable mental steps were implied by his 1938 analysis, and G¨odel himself certainly believed in them. One sentence in Turing’s proposal for the ACE computer (Turing 1946) is evidence of this shift: it is a claim that a computer could play ‘very good chess’ if ‘occasional serious mistakes’ were allowed. This cryptic reference to mistakes was clarified by the argument of (Turing 1947) that once the possibility of mistakes is allowed, G¨odel’s theorem becomes irrelevant.

(G¨odel, of course, rejected this post-war Turing vision of machine intelligence, although he had endorsed Turing’s original definition of computability.)

That a program is itself a form of data is the basis of modern computing. We can
now hardly imagine a world in which this idea was not familiar, and it is hard to read On computable numbers without translating Turing machines into programs and the universal machine into a computer running those programs. Turing’s 1936 construction of the universal machine, by treating programs as data to be read in just the same way as numerical or any other kind of symbolic data, defined a structure quite different from that of Babbage and his successors up to the ENIAC.

Turing certainly saw from the very start that programs were data and could be manipulated as such. On the first page of his 1946 report, Turing explained that the management of a calculation would be ‘looked after by the machine itself’

Turing also wrote in a most important passage that the future of software writing should be free from drudgery because ‘any processes that are quite mechanical may be turned over to the machine computer itself.’ This insight (going far beyond von Neumann) depended on his perception of programs being themselves data-structures. In (Turing 1947) he spoke of how a machine could be given instructions in ‘any symbolic logic’.

The thrust of these post-war papers, putting forward what he called a ‘heretical theory’ of the mind, was to put forward a wholly computable model. Penrose, summarizing Turing’s position in 1950, says that ‘It seems likely that he viewed physical action in general—which would include the action of a human brain—to be always reducible to some kind of Turing-machine action’ (Penrose 1994, p. 21). This goes a little further than what Turing explicitly wrote in 1950, but reflects what is implicit in the entire framework.

A late-1950s Turing might also, in the light of his work in morphogenesis, seeing discrete structures emerging out of non-linear equations, have taken more interest in exploring the relationship of computability with continuous dynamical systems

when computing is front-page news, physics has lost its 1950s status. But
computing requires both software and hardware, and the Church-Turing thesis, which underlies computing, relates both to logic and to physics

… from 1945 onwards he took the view that all mental processes fell within the scope of computable operations.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.