Computer Science
Turing Machines
Turing Machines are theoretical models of computation that consist of a tape divided into cells, a read/write head, and a set of states and rules. They can simulate the logic of any computer algorithm and are used to study the limits of computation. Turing Machines are fundamental to the understanding of computability and complexity in computer science.
Written by Perlego with AI-assistance
Related key terms
1 of 5
12 Key excerpts on "Turing Machines"
eBook - ePubCybernetical Intelligence
Engineering Cybernetics with Machine Intelligence
- Kelvin K. L. Wong(Author)
- 2023(Publication Date)
- Wiley-IEEE Press(Publisher)
12 Turing MachineThe Turing machine is a theoretical model of computation that was first introduced by the British mathematician and computer scientist Alan Turing in the 1930s. A simple abstract machine is capable of performing any computation that can be carried out by any computer or algorithm.The Turing machine consists of an infinite tape divided into squares, each of which can contain a symbol from a finite set of possible symbols. The machine also has a read/write head that can move left or right along the tape and can read and write symbols on the tape. The machine has a set of states and a transition function that determines how the machine should behave based on the current symbol on the tape and the current state of the machine. The operation of the Turing machine proceeds as follows:- The machine starts in an initial state and the read/write head is positioned over a square on the tape.
- The machine reads the symbol on the tape at the current position.
- Based on the current state of the machine and the symbol on the tape, the machine consults its transition function to determine the next state of the machine and the symbol to write on the tape.
- The machine writes the symbol on the tape at the current position and moves the read/write head left or right as instructed by the transition function.
- The machine continues to perform steps 2–4 until it reaches a halting state, at which point the computation is complete.
The Turing machine is a powerful theoretical concept that has been used to prove fundamental results in computer science and mathematics. For example, Turing used the concept of the Turing machine to show that there are some problems that are fundamentally unsolvable by any algorithm, a concept known as the “halting problem.” Additionally, the Turing machine has been used to define the notion of computability, which is the ability to solve a problem using an algorithm. The parameters of a Turing machine are summarized in Table 12.1
eBook - PDF- Marcus Kracht(Author)
- 2011(Publication Date)
- De Gruyter Mouton(Publisher)
Turing Machines We owe to (Turing, 1936) and (Post, 1936) the concept of a machine which is very simple and nevertheless capable of computing all functions that are believed to be computable. Without going into the details of what makes a function computable, it is nowadays agreed that there is no loss if we define 'computable' to mean computable by a Turing machine. The essential idea was that computations on objects can be replaced by computations on strings. The number η can for example be represented by η 4- 1 successive strokes on a piece of paper. (So, the number 0 is represented by a single stroke. This is Turing Machines 81 really necessary.) In addition to the stroke we have a blank, which is used to separate different numbers. The Turing machine, however powerful, takes a lot of time to compute even the most basic functions. Hence we agree from the start that it has an arbitrary, finite stock of symbols that it can use in addition to the blank. A Turing machine is a physical device, consisting of a tape which is infinite in both directions. That is, it contains cells numbered by the set of integers (but the numbering is irrelevant for the computation). Each cell may carry a symbol from an alphabet Λ or a blank. The machine possesses a read and write head, which can move between the cells, one at a time. Finally, it has finitely many states, and can be programmed in the following way. We assign instructions for the machine that tell it what to do on condition that it is in state q and reads a symbol a from the tape. These instruction tell the machine whether it should write a symbol, then move the head one step or leave it at rest, and subsequently change to a state q'.
eBook - PDF- Armond Duwell(Author)
- 2021(Publication Date)
- Cambridge University Press(Publisher)
Turing’s mathematical representation of what is essential to human com- puting defines what a Turing machine is. A Turing machine is not an actual machine, but a mathematical construct like circles or triangles. A Turing machine consists, in part, of an endless tape partitioned into various cells that are capable of bearing symbols. A Turing machine is equipped with a read/write head that is capable of reading symbols from a finite set on the cell in the tape that it is currently positioned over, writing or erasing symbols, and shift- ing left or right one cell. A Turing machine also has a finite set of internal states. Particular Turing Machines are characterized by their machine table, which corresponds to what we would now call a program. The machine table determines the behavior of the machine. Given an internal state and scanned symbol, which we refer to jointly as the configuration of the machine, the program indicates whether the read/write tape head should erase or write a symbol, whether the head should move or not, and finally, what internal state to update to. Machine tables can be represented as sets of instructions of the form hq i ; s i ; q j ; s j ; di, where q i=j are the current/subsequent internal states, s i=j are the current/subsequent symbols on the tape, which include the blank symbol, and d 2 f1; 0; 1g indicates how the read/write tape head should move. 2 See Figure 1. Turing devotes Section 9 of his paper to arguing that Turing Machines cap- ture the essential properties of humans performing computations. He draws our attention to several important aspects of human computations. First, when humans perform computations, they typically utilize a spatial medium with distinguishable locations (e.g. a piece of paper with a grid on it). Turing views 2 This notation is not Turing’s, but it has the advantage of being more transparent than Turing’s.
No longer available |Learn more- (Author)
- 2014(Publication Date)
- Learning Press(Publisher)
However, the tape can be moved back and forth through the machine, this being one of the elementary operations of the machine. Any symbol on the tape may therefore eventually have an innings. (Turing 1948, p. 61) A Turing machine that is able to simulate any other Turing machine is called a universal Turing machine ( UTM , or simply a universal machine ). A more mathematically-oriented definition with a similar universal nature was introduced by Alonzo Church, whose work on lambda calculus intertwined with Turing's in a formal theory of computation known as the Church–Turing thesis. The thesis states that Turing Machines indeed capture the informal notion of effective method in logic and mathematics, and provide a precise definition of an algorithm or 'mechanical procedure'. Studying their abstract properties yields many insights into computer science and complexity theory. Informal description The Turing machine mathematically models a machine that mechanically operates on a tape on which symbols are written which it can read and write one at a time using a tape head. Operation is fully determined by a finite set of elementary instructions such as in state 42, if the symbol seen is 0, write a 1; if the symbol seen is 1, shift to the right, and change into state 17; in state 17, if the symbol seen is 0, write a 1 and change to state 6; etc. In the original article (On computable numbers, with an application to the Entscheidungsproblem), Turing imagines not a mechanism, but a person whom he calls the computer, who executes these deterministic mechanical rules slavishly (or as Turing puts it, in a desultory manner). The head is always over a particular square of the tape; only a finite stretch of squares is given. The instruction to be performed (q 4 ) is shown over the scanned square. (Drawing after Kleene (1952) p.375.)
No longer available |Learn more- (Author)
- 2014(Publication Date)
- Academic Studio(Publisher)
However, the tape can be moved back and forth through the machine, this being one of the elementary operations of the machine. Any symbol on the tape may therefore eventually have an innings. (Turing 1948, p. 61) A Turing machine that is able to simulate any other Turing machine is called a universal Turing machine ( UTM , or simply a universal machine ). A more mathematically-oriented definition with a similar universal nature was introduced by Alonzo Church, whose work on lambda calculus intertwined with Turing's in a formal theory of com-putation known as the Church–Turing thesis. The thesis states that Turing Machines indeed capture the informal notion of effective method in logic and mathematics, and provide a precise definition of an algorithm or 'mechanical procedure'. Studying their abstract properties yields many insights into computer science and complexity theory. Informal description The Turing machine mathematically models a machine that mechanically operates on a tape on which symbols are written which it can read and write one at a time using a tape head. Operation is fully determined by a finite set of elementary instructions such as in state 42, if the symbol seen is 0, write a 1; if the symbol seen is 1, shift to the right, and change into state 17; in state 17, if the symbol seen is 0, write a 1 and change to state 6; etc. In the original article (On computable numbers, with an application to the Entscheidungsproblem), Turing imagines not a mechanism, but a person whom he calls the computer, who executes these deterministic mechanical rules slavishly (or as Turing puts it, in a desultory manner). The head is always over a particular square of the tape; only a finite stretch of squares is given. The instruction to be performed (q 4 ) is shown over the scanned square. (Drawing after Kleene (1952) p.375.)
eBook - PDF- C. E. Shannon, J. McCarthy, C. E. Shannon, J. McCarthy, C. Shannon, J. McCarthy(Authors)
- 2016(Publication Date)
- Princeton University Press(Publisher)
Turing Machines A UNIVERSAL TURING MACHINE WITH TWO INTERNAL STATES Claude E. Shannon INTRODUCTION In a well-known paper1, A. M. Turing defined a class of computing machines now known as Turing Machines. We maythink of a Turing machine as composed of three parts — acontrol element, a reading and writing head, and an infinite tape. The tape is divided into a sequence of squares, each of which can carry any symbol from a finite alphabet. The reading head will at a given time scan one square of the tape. It can read the symbol written there and, under directions from the control element, can write a new symbol and also move one square to the right or left. The control ele- ment is a device with a finite number of internal "states." At a given time, the next operation of the machine is determined by the current state of the control element and the symbol that is being read by the reading head. This operation will consist of three parts; first the printing of a new symbol in the present square (which may, of course, be the same as the symbol just read); second, the passage of the control element to a new state (which may also be the same as the previous state); and third, movement of the reading head one square to the right or left. In operation, some finite portion ofthe tape is prepared with a starting sequence of symbols, the remainder ofthe tape being left blank (i.e., registering a particular "blank" symbol). The reading head is placed at a particular starting square and the machine proceeds to compute in ac- cordance with its rules of operation. In Turing1s original formulation Turing, A. M., "On Computable Numbers, with an Application to the Entscheidungsproblem," Proc. of the London Math. Soc. 2-^2 (1936), pp. 230 - 265. 157 SHANNON alternate squares were reserved for the final answer, the others being used for intermediate calculations. This and other details of the original defi- nition have been varied in later formulations of the theory.
eBook - PDFRethinking Cognitive Computation
Turing and the Science of the Mind
- Andy Wells(Author)
- 2017(Publication Date)
- Red Globe Press(Publisher)
6 Tu r i n g ’ s A n a l y s i s o f C o m p u t a t i o n Introduction Chapters 3–5 have introduced the techniques needed for a study of Turing’s work. A Turing machine is a mini-mind connected to an unlimited linear environment of squares. The purpose of this chapter is to explain why Turing developed such a machine, why it has strange characteristics like an infinite, one-dimensional tape and why, despite these strange characteristics, the Turing machine is important for psychological theory. The starting point for a proper appreciation of the Turing machine is an understanding of the analysis that led to it. Turing Machines were the result of his thinking about the processes that a human, calculating with paper and pencil, could carry out. The underlying issue to which his work was directed, as mentioned in Chapter 1, was the concept of effective calculability. The relevant sense of ‘effective’ is the everyday notion of success in producing a result. The ques-tion of what constitutes an effective calculation arose when mathematicians with an interest in the foundations of their subject began, systematically, to examine how mathematics works and what it is about. Among their reasons for doing this were the discovery in the late nineteenth century of some deep-seated and disturbing paradoxes arising from ideas and practices that had previously seemed innocuous. Russell’s paradox, which undermined Frege’s attempt to found mathematics on logic, is a famous example. Russell’s letter to Frege describing the paradox and Frege’s reply have been reprinted by van Heijenoort (1967). In the 1930s three different formal approaches offering precise models of the intuitive notion of effective calculability appeared. They were lambda definability, Church (1936), general recursiveness, Kleene (1936) and Turing computability, Turing (1936). Background material and discussions of the three approaches can be found in Gandy (1988) and Sieg (1994).
eBook - PDF- Adam Olszewski, Jan Wolenski, Robert Janusz, Adam Olszewski, Jan Wolenski, Robert Janusz(Authors)
- 2013(Publication Date)
- De Gruyter(Publisher)
148 B. Jack Copeland Turing prefaces his first description of a Turing machine with the words: ‘We may compare a man in the process of computing a [...] number to a machine’ [Turing 1936, p. 59]. The Turing ma-chine is a model, idealised in certain respects, of a human com-puter. Wittgenstein put this point in a striking way: ‘Turing’s “Ma-chines”. These machines are humans who calculate’ [Wittgenstein 1980, § 1096]. It is a point that Turing was to emphasise, in various forms, again and again. For example: ‘A man provided with pa-per, pencil, and rubber, and subject to strict discipline, is in effect a universal machine’ [1948, p. 416]. The electronic stored-program digital computers for which the universal Turing machine was a blueprint are, each of them, compu-tationally equivalent to a Turing machine with a finite tape, and so they too are, in a sense, models of human beings engaged in com-putation. Turing chose to emphasise this when explaining the new electronic machines in a manner suitable for an audience of uniniti-ates: ‘The idea behind digital computers may be explained by saying that these machines are intended to carry out any operations which could be done by a human computer’ [1950a, p. 444]. He makes the point a little more precisely in the technical document containing his design for the ACE: The class of problems capable of solution by the machine can be defined fairly specifically.
eBook - PDFTuring's Legacy
Developments from Turing's Ideas in Logic
- Rod Downey(Author)
- 2014(Publication Date)
- Cambridge University Press(Publisher)
This paper formulated definitions of time and space complexity on multitape Turing Machines and proved results demonstrating that with more time, more problems can be computed. It was a fundamental step to make complexity classes, defined by functions that bound the amount of resources use, the main subject of study. More abstract definitions of com- putability could not have offered natural guidance to an intuitively satisfying and practical formulation of computational complexity. 1 Some scholars question the correctness of the Church–Turing Thesis. For a discussion of these issues and relevant citations we refer the reader to Davis [Dav06a, Dav06b]. TURING AND THE DEVELOPMENT OF COMPUTATIONAL COMPLEXITY 301 The Turing machine beautifully captured the discrete step-by-step nature of computation. Furthermore, this machine enabled the definition and measure- ment of time and space complexity in a natural and precise manner amenable to quantifying the resources used by a computation. This natural precision of Turing Machines was crucial in guiding the originators of this field in their fundamental definitions and first results which set the tenor for this research area up to the present day. Other, more abstract definitions of computabil- ity, while having advantages of brevity and elegance, could not and did not offer the needed precision or guidance toward this intuitively satisfying and practical formulation of complexity theory. §2. Modes of computation. A computation of a Turing machine is a se- quence of moves, as determined by its transition function. Ordinarily, the transition function is single-valued. Such Turing Machines are called deter- ministic and their computations are sequential. A nondeterministic Turing machine is one that allows for a choice of next moves; in this case the transition function is multivalued. If M is a nonde- terministic Turing machine and x is an input word, then M and x specify a computation tree.
eBook - PDFThe Computing Universe
A Journey through a Revolution
- Tony Hey, Gyuri Pápay(Authors)
- 2014(Publication Date)
- Cambridge University Press(Publisher)
After reading the symbol in the box, she can overwrite the symbol in the box, change to a new state of mind, and move to consider the symbol in the next square – to the left or the right. It is her state of mind that tells her what to do with the symbol she has read – whether it should be used as part of the process of addition or of multiplication, for example. Turing envis- aged that a human computer would need only a finite number of states of mind to complete any given calculation. Having broken down how a human would actually go about performing the calculation into these simple steps, Turing then proposed a very simple machine that could mimic all the actions of the human computer and so work through the algorithmic steps to complete the same calculation (Fig. 6.3). Fig. 6.2. Turing designed his machine to mimic the behavior of a human computer. Fig. 6.3. This figure illustrates the con- cept of a Turing machine as “a human in a box.” The box has no bottom so the human can read the symbol under the box. 107 Mr. Turing’s amazing machines Fig. 6.4. The photograph shows a working model of a Turing machine. To summarize, Turing Machines were to be provided with paper in the form of a tape. The tape is marked off into boxes and each box can contain at most one symbol (Fig. 6.4). At each step of the algorithm, the head of this “super-typewriter” machine can move one space, to the adjacent box on the left or on the right. The paper tape is assumed to be unlimited in length so that although the machine has a finite number of symbols and states, it is allowed an unlimited space for its calculations. This is not to say that the amount of paper attached to such a machine actually is infinite. At any given stage in any calculation the length of tape will be finite but we have the option of adding more tape when we need to. Turing’s machine is therefore able to read and write, move left or right along the tape, as specified by its set of states.
eBook - PDF- Elliott Mendelson(Author)
- 2015(Publication Date)
- Chapman and Hall/CRC(Publisher)
311 5 Computability 5.1 Algorithms: Turing Machines An. algorithm .is.a.computational.method.for.solving.each.and.every.problem. from.a.large.class.of.problems . .The.computation.has.to.be.precisely.specified. so.that.it.requires.no.ingenuity.for.its.performance . .The.familiar.technique. for.adding.integers.is.an.algorithm,.as.are.the.techniques.for.computing.the. other.arithmetic.operations.of.subtraction,.multiplication.and.division . .The. truth.table.procedure.to.determine.whether.a.statement.form.is.a.tautology. is.an.algorithm.within.logic.itself . It.is.often.easy.to.see.that.a.specified.procedure.yields.a.desired.algorithm . . In.recent.years,.however,.many.classes.of.problems.have.been.proved.not.to. have.an.algorithmic.solution . .Examples.are: . 1 . .Is.a.given.wf.of.quantification.theory.logically.valid? . 2 . .Is. a. given. wf. of. formal. number. theory. S. true. (in. the. standard. interpretation)? . 3 . .Is.a.given.wf.of.S.provable.in.S? . 4 . .Does.a.given.polynomial. f ( x 1 ,.…,. x n ).with.integral.coefficients.have. integral.roots.(Hilbert’s.10th.problem)? In.order.to.prove.rigorously.that.there.does. not .exist.an.algorithm.for.answer-ing.such.questions,.it.is.necessary.to.supply.a.precise.definition.of.the.notion. of.algorithm . Various.proposals.for.such.a.definition.were.independently.offered.in.1936. by. Church. (1936b),. Turing. (1936–1937),. and. Post. (1936) . .All.of.these.defini-tions,. as. well. as. others. proposed. later,. have. been. shown. to. be. equivalent . . Moreover,.it.is.intuitively.clear.that.every.procedure.given.by.these.defini-tions.is.an.algorithm . .On.the.other.hand,.every.known.algorithm.falls.under. these.definitions . .Our.exposition.will.use.Turing’s.ideas . First.of.all,.the.objects.with.which.an.algorithm.deals.may.be.assumed.to. be.the.symbols.of.a.finite.alphabet.A.=.{a 0 ,.a 1 ,.…,.a n }. .Nonsymbolic.objects.can. 312 Introduction to Mathematical Logic be. represented.
eBook - PDFFormal Languages and Computation
Models and Their Applications
- Alexander Meduna(Author)
- 2014(Publication Date)
- Auerbach Publications(Publisher)
213 Chapter 10 Applications of Turing Machines: Theory of Computation In Chapter 9, we have considered Turing Machines (TMs) as language acceptors by analogy with other language acceptors, such as finite and pushdown automata, discussed earlier in this book� In this chapter, we make use of TMs to show the fundamentals of theory of computation , which is primarily oriented toward determining the theoretical limits of computation in general� This orientation comes as no surprise: by the Church–Turing thesis, which opened Section IV of this book, every procedure can be formalized by a TM, so any computation beyond the power of TMs is also beyond the computer power in general� This two-section chapter gives an introduction to two key areas of the theory of computation— computability and decidability� In Section 10�1, regarding computability, we view TMs as computers of functions over nonnegative integers and show the existence of functions whose computation cannot be specified by any procedure� Then, regarding decidability, we formalize algorithms that decide problems by using TMs that halt on every input in Section 10�2, which is divided into five subsections� In Section 10�2�1, we conceptualize this approach to decidability� In Section 10�2�2, we formulate several important problems concerning the language models discussed in Chapters 3 and 6, such as finite automata (FAs) and context-free grammars (CFGs), and construct algorithms that decide them� In Section 10�2�3, more surprisingly, we present prob-lems that are algorithmically undecidable, and in Section 10�2�4, we approach undecidability from a more general viewpoint� Finally, in Section 10�2�5, we reconsider algorithms that decide problems in terms of their computational complexity measured according to time and space requirements� Perhaps most importantly, we point out that although some problems are decidable
Index pages curate the most relevant extracts from our library of academic textbooks. They’ve been created using an in-house natural language model (NLM), each adding context and meaning to key research topics.
