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.
7 Key excerpts on "Turing Machines"
eBook - ePubLogic from A to Z
The Routledge Encyclopedia of Philosophy Glossary of Logical and Mathematical Terms
- John B. Bacon(Author)
- 2013(Publication Date)
- Routledge(Publisher)
...Devised by Turing as a characterization of the notion of computable function or mechanical calculation, a Turing machine is an abstract automaton or idealized computing device which consists of a program – a finite set of simple instructions – to be carried out on a one-dimensional recording tape by a reading-writing device with a memory restricted in capacity. A numerical function f is said to be computed by a Turing machine or to be Turing computable just in case there is a program which, when implemented, mimics on its tape the input-output behaviour of f Turing computability can be proved to be equivalent to register computability and to a function’s being recursive. See Computable function; Recursion theorem; Recursive function; Register machine; Turing computable function. Types, theory of A foundational theory devised by Russell and Whitehead to provide a way around the paradoxes of set theory. Russell believed the paradoxes to arise from the use of assumptions to the effect that classes and their members do not need to be distinguished in such a way as to prohibit reference to a set containing an object in the definition of that object. His simple theory of types stratified the universe of objects into levels or types. The lowest type contains only individuals. The next level is comprised of collections of individuals, the next collections of collections of individuals, and so on. In general, collections are formed exclusively of elements taken from the immediately preceding type. Russell provided a more complex stratification scheme in his ramified theory of types....
eBook - ePubArtificial Intelligence
An Introduction
- Alan Garnham(Author)
- 2017(Publication Date)
- Routledge(Publisher)
...The theory specifies what computers can and cannot do and how much time and memory they need for the computations that they can perform. It therefore indicates the limitations of computational theories of the mind. The theory had its origins in several branches of mathematics. A number of mathematicians were independently searching for the smallest set of primitive operations needed to carry out any possible computation. When their proposals were worked out in detail, it was shown that they were equivalent. One approach to the problem of computability was Turing's (1936). Turing formulated his ideas in terms of an abstract computing device called a Turing machine. A Turing machine performs its calculations with the help of a tape divided into squares, each of which can have one symbol on it. The Turing machine's primitive operations are reading and writing symbols on the tape and shifting and tape one square to the left or right. It uses a finite vocabulary of symbols, but its tape can be infinitely long. A Turing machine has only a finite number of internal states. When it reads the symbol on a square its state may change, depending on what state it is currently in and what the symbol is. The structure of a Turing machine is very simple and so are the operations it performs. However, additional bits of 'machinery' - more tapes for example - do not increase the range of computations that a Turing machine can perform. They only increase its speed. Furthermore, these gains in efficiency are of no theoretical interest, since they speed up the machine's operation by only a constant factor. It is possible to describe a Universal Turing Machine, constructed on the same principles as other Turing Machines. The Universal Turing Machine can mimic the operation of any other Turing machine. To simulate another machine it must be given a description of how that machine works. This description can be written on to its tape in standard Turing machine format...
eBook - ePubThis is Philosophy of Mind
An Introduction
- Pete Mandik(Author)
- 2013(Publication Date)
- Wiley-Blackwell(Publisher)
...In Turing's mathematical work his machine was more of a thought experiment than an actual machine. At the heart of a Turing machine is a finite-state machine, a machine that can only be in one of a finite number of states at a time. The transitions from state to state are controlled by a finite look-up table—a finite program that specifies what, for any given state the machine is in, its next state should be. The finite-state machine controls a read/write head that can move back and forth along an infinite tape and read, write, and erase symbols on that tape. Different Turing Machines have different look-up tables. A universal Turing machine can emulate the behavior of any other Turing machine. 7.13 Using his notion of a computing machine, Turing was able to prove that there is no general method for deciding, for any selected mathematical proposition, whether it is provable. Along the way Turing was able to prove that anything that can be computed can be computed by a universal Turing machine. 7.14 One important aspect of the idea of a Turing machine is the way that it can do something that a person can do. It can follow rules to read and write symbols and thus arrive at the solution to a problem. It is perhaps unsurprising, then, that in his later work Turing thought explicitly about what it might take for a machine to exhibit human-level intelligence. One question that arises in considering the possibility of artificial intelligence is the question of how one would know whether a machine did indeed have human-level intelligence. (Such a question should remind you of the problem of other minds that we discussed in chapter 5.) In response to such a concern, Turing proposed what has now come to be known as the “Turing test.” The Turing t est 7.15 Turing's test is designed to bypass irrelevant factors in deciding whether a being is intelligent. Such irrelevant factors include whether the being looks like a human...
eBook - ePubAlan Turing Decoded
The Man They Called Prof
- Dermot Turing(Author)
- 2021(Publication Date)
- The History Press(Publisher)
...By running one program to test another, Alan was able to find some mathematical equivalents to the Epimenides paradox (‘Epimenides the Cretan says that all Cretans are liars’). By producing contradictions, certain machines can be shown to be impossible: one example is a program to decide whether any particular program would ever lead to the machine printing the symbol ‘0’. The ‘halting problem’ – a program to see if any other program would run forever or halt at some stage – is a similar, more modern example; again, it can be proved by contradiction that such a program cannot be written. Turing Machines - what you need to know A model ‘Turing machine’ created in the 1950s by Professor Gisbert Hasenjäger. Without their knowledge, they were to become opponents in the cryptographic war. (Courtesy of Rainer Glaschick and the Heinz Nixdorf Foundation (Paderborn)) Most people have got through life happily and successfully without knowing the first thing about Turing Machines, and that’s fine. So you probably need to know nothing about them. But it might help a little to have some notion, in order to put the rest of Alan Turing’s life – much of which was founded on his greatest mathematical achievement, the paper on Computable Numbers – into context. The machine which Alan Turing conceptualised has a read-write head and a long tape. It also has a set of instructions which tell it what to do when it finds itself in a particular ‘state’, or as he put it, ‘ m -configuration’. So, for example, in State 1, it might view the tape, and if it is blank, print an asterisk, and then go to State 2. In State 2 it might just move the tape one place to the right, and then go to State 1. In State 1, if the tape is not blank, it might just go to State 2. (This might not be a very exciting set of instructions, but no matter.) The point here is that the instructions can all be coded into language or numerical form...
eBook - ePubReckoning with Matter
Calculating Machines, Innovation, and Thinking about Thinking from Pascal to Babbage
- Matthew L. Jones(Author)
- 2016(Publication Date)
- University of Chicago Press(Publisher)
...Machines need not be exclusively tied to predefined algorithmic behaviors: “It is certainly true, that ‘acting like a machine’ has become synonymous with lack of adaptability. But the reason for this is not obvious.” Memory—not processing ability—was the problem. So long as we demand a machine be infallible, Turing argued, “it cannot also be intelligent.” Rather than failing to give an answer, “we could arrange that it gives occasional wrong answers.” 108 If we want a computer to develop intelligence, we need not to treat it like a mere imitator. It must undergo the practical training of building skills and knowledge that cannot be reduced merely to procedure. A machine might know how : it need not exclusively follow encoded patterns of knowing that. In his earlier paper introducing his famous abstract machine, Turing had coupled Romantic unconscious influence and Gödel’s incompleteness theorem. He wrote in 1940, “In pre-Gödel times it was thought by some that it would be possible to carry” the program of formal logic “to such a point that all the intuitive judgements of mathematics could be replaced by a finite number of these rules. The necessity for intuition would then be entirely eliminated.” 109 With his constructive proof of propositions that are formally undecidable, Gödel had explored the dream of reducing mathematical inquiry to formal logic. “The activity of the intuition,” Turing explained, “consists in making spontaneous judgements which are not the result of conscious trains of reasoning.” 110 Mathematics could never be reduced to mechanism. In describing the possibility of a machine capable of thinking, Turing insisted on the collective and social nature of knowledge production, and of originality, even in mathematics: “A human mathematician has always undergone an extensive training. . ....
eBook - ePubLanguage and Meaning in Cognitive Science
Cognitive Issues and Semantic theory
- Andy Clark, Josefa Toribio, Andy Clark, Josefa Toribio(Authors)
- 2012(Publication Date)
- Routledge(Publisher)
...Can Machines Think? DANIEL C. DENNETT Can machines think? This has been a conundrum for philosophers for years, but in their fascination with the pure conceptual issues they have for the most part overlooked the real social importance of the answer. It is of more than academic importance that we learn to think clearly about the actual cognitive powers of computers, for they are now being introduced into a variety of sensitive social roles, where their powers will be put to the ultimate test: In a wide variety of areas, we are on the verge of making ourselves dependent upon their cognitive powers. The cost of overestimating them could be enormous. One of the principal inventors of the computer was the great British mathematician Alan Turing. It was he who first figured out, in highly abstract terms, how to design a programmable computing device—what we now call a universal Turing machine. All programmable computers in use today are in essence Turing Machines. Over thirty years ago, at the dawn of the computer age, Turing began a classic article, “Computing Machinery and Intelligence” with the words: “I propose to consider the question, ‘Can machines think?’”—but then went on to say that this was a bad question, a question that leads only to sterile debate and haggling over definitions, a question, as he put it, “too meaningless to deserve discussion.” 1 In its place he substituted what he took to be a much better question, a question that would be crisply answerable and intuitively satisfying—in every way an acceptable substitute for the philosophic puzzler with which he began. First he described a parlor game of sorts, the “imitation game,” to be played by a man, a woman, and a judge (of either gender). The man and woman are hidden from the judge's view but able to communicate with the judge by teletype; the judge's task is to guess, after a period of questioning each contestant, which interlocutor is the man and which the woman...
eBook - ePub30-Second AI & Robotics
50 key notions, fields, and events in the rise of intelligent machines, each explained in half a minute
- Luis de Miranda(Author)
- 2019(Publication Date)
- Ivy Press(Publisher)
...Born in 1912 in London, he was the son of a civil servant working in British India. In school he already showed signs of his later genius, reading Einstein’s work when he was only 16 years old. In a short life of 41 years, he worked in mathematics, logic, cryptography and theoretical biology. He was also a passionate runner, who almost ended up on the 1948 British Olympic team. Although not a philosopher, two of his ideas have strongly influenced the philosophy of artificial intelligence: the Turing Machine and the Turing Test. The Turing Machine is a hypothetical simple computer that can read from and write onto an endless storage tape. With the help of this thought experiment, Turing analysed which types of problems can in principle be solved by a computer program. His analysis, in the form of the Church-Turing thesis, remains valid to this day. The Turing Test is a test for computer intelligence (see here), in which a computer is considered ‘intelligent’ if it can be mistaken for a human in a typed conversation. During the Second World War, Turing worked at the Government Code and Cypher School at Bletchley Park, attempting to decrypt German military communications. The German military at this time used an encryption system based on a machine called Enigma, which encrypted messages through a series of rotating wheels. Turing helped to work out how Enigma worked, and together with his collaborators he built a machine to decrypt German messages. Due to various administrative hurdles, his group could not access enough resources to build more of these machines. In 1941, Turing wrote a letter directly to Prime Minister Winston Churchill, asking for more support, and Churchill gave a direct order that Turing’s group should receive all the help that it required. In this way, Turing’s group contributed significantly to the Allied victory in the war. After the war, Turing worked on computers, but also on chemistry and biology at the University of Manchester...
