turing-machine

An idealized computing machine capable of simulating any other automaton by processing instructions on an infinite tape, foundational to the theory of computation.

Written by the Tronix Library

5 chapters across 2 books

Great Ideas in Information Theory, Language and Cybernetics (1966)Jagjit Singh

chapter XIII TURING MACHINES VON NEUMANN'S warning against identifying computing machines and neuron networks with the animal nervous system is quite oppor- tune in view of the present controversy concerning whether or not machines can think. Take first the digital computer we described in Chapter IX. As we saw, it merely works out what has already been thought of beforehand by the designer and supplied to it in the form of program instructions. In fact, it obeys these instructions as literally as the unfortunate Casabianca boy who remained on the burning deck because his father had told him to do so. For instance, if in the course of a computation the machine requires the quotient of two numbers of which the divisor happens to be zero, it will go on, Sisyphus-like, trying to divide by zero forever unless expressly for- bidden by prior instruction. A human computer would certainly not go on dividing by zero, whatever else he might do. The incapacity of the machine to deviate one whit from what the "moving finger" of prior instructions has already decreed make? it necessary to think out in advance every possible contingency that might arise in the course of the work and give the machine appropriate instructions for each case. Is the limitation imposed by this conservation law whereby the machine is incapable of originating a new instruction or idea destined to remain forever? Or will designers be able to construct in course of time automata able to do their own thinking like Rossum robots in Karel Capek's R.U.R. or the Great Brains in Olaf Stapledon's First and Last Men? There are no unequivocal answers to these questions. It all depends on the meaning we choose to assign to the verb "to think." If we adopt a behavioristic definition of the term as the English logician A. M. Turing and his followers suggest, we may consider a machine capable of "thinking" provided it can be made to imitate a human 184

This chapter discusses von Neumann's caution against equating computing machines and neuron networks with the animal nervous system, emphasizing the limitations of digital computers which strictly follow pre-programmed instructions without deviation. It explores the debate on whether machines can truly 'think,' highlighting Turing's behavioristic definition of thinking as imitation of human responses, while questioning if this suffices for genuine understanding. The chapter also introduces the concept of Turing machines as idealized computing devices capable of simulating any other automaton, addressing the complexity and reproduction of automata in relation to biological evolution and information theory.

Alan Turing: The Enigma (1983)Andrew Hodges

--- (≈20%)

This chapter details Alan Turing's foundational conceptualization of computation as a process involving a finite set of symbols and mental states, leading to the invention of the Turing machine as a universal computational model. It explores Turing's intellectual shift from spiritual beliefs to a mechanistic and materialist understanding of the mind, situating his work within the philosophical and scientific debates on determinism and free will, and highlighting the originality and historical significance of his invention amid the pre-war context.

--- (≈21%)

This chapter covers Alan Turing's independent formulation of the Turing machine as a solution to Hilbert's Entscheidungsproblem, highlighting the simultaneous but distinct work of Alonzo Church and the significance of Turing's conceptual breakthrough. It also details Turing's recognition through a university prize and his preparation for a research stay at Princeton, where he encounters a prestigious mathematical community and candidly shares his views on sexuality and religion, revealing his identity and cultural perceptions.

--- (≈25%)

This chapter chronicles Alan Turing's pioneering efforts to physically realize computational logic through his design and partial construction of an electromechanical multiplier using relay switches, embodying Boolean algebra and binary arithmetic. It further explores his advanced mathematical work on extending axiomatic systems via ordinal logics to address Gödel's incompleteness theorem, introducing the oracle Turing machine concept that opened new avenues in computability theory. Alongside these intellectual achievements, the chapter touches on Turing's cryptanalysis beginnings, his innovative use of analogue computation for complex functions, and glimpses of his personal life and academic travels.

Chapter 75

This chapter provides an extensive and detailed index of Alan Turing's multifaceted life and work, emphasizing his foundational contributions to theoretical computer science through the concept of the Turing machine and computable numbers, his pivotal role in wartime cryptanalysis of the Enigma cipher at Bletchley Park, and his pioneering efforts in early computer development such as the ACE project. It also addresses his groundbreaking ideas on machine intelligence, including the Turing Test, alongside his personal and social experiences, notably his sexuality and legal persecution, situating his scientific achievements within broader historical, cultural, and political contexts.

Opening the stacks