The Turing machine is an An abstract machine, also called an abstract computer, is a theoretical model of a computer hardware or software system. Abstraction of computing processes is used in both the computer science and computer engineering disciplines. Abstract machines are often used in thought experiments regarding computability or to analyze the complexity of... abstract machine introduced in 1936 was a leap year starting on Wednesday (link will take you to calendar). Events January-February January 15 -- The first building to be completely covered in glass is completed in Toledo, Ohio, for the Owens-Illinois Glass Company. January 20 - Death of George V of the United Kingdom. His... 1936 by Alan Turing, on the steps of the bus, with members of the Walton Athletic Club, 1946. Alan Mathison Turing (June 23, 1912–June 7, 1954) was a British mathematician, logician, cryptographer, and war hero, and is widely considered to be the father of computer science. With the Turing Test... Alan Turing to give a mathematically precise definition of Flowcharts are often used to represent algorithms. An algorithm is a finite set of well-defined instructions for accomplishing some task which, given an initial state, will result in a corresponding recognisable end-state (contrast with heuristic). Algorithms can be implemented by computer programs, although often in restricted forms; an... algorithm or 'mechanical procedure'. As such it is still widely used in theoretical Computer science (informally: CS or compsci) is, in its most general sense, the study of computation and information processing, both in hardware and in software. Introduction Computer science encomposses a variety of topics relating to computation, ranging from abstract analysis of algorithms and formal grammars, to subjects like programming languages... computer science, especially in Complexity theory is part of the theory of computation dealing with the resources required during computation to solve a given problem. The most common resources are time (how many steps does it take to solve a problem) and space (how much memory does it take to solve a problem). Other... complexity theory and the theory of Computation can be defined as finding a solution to a problem from given inputs by means of an algorithm. This is what the theory of computation, a subfield of computer science and mathematics, deals with. For thousands of years, computing was done with pen and paper, or chalk and slate... computation. The thesis that states that Turing machines indeed capture the informal notion of effective or mechanical method in logic and mathematics is known as the In computability theory the Church-Turing thesis, Churchs thesis, Churchs conjecture or Turings thesis, named after Alonzo Church and Alan Turing, is a hypothesis about the nature of mechanical calculation devices, like computers, and what kind of algorithms they can perform. It is generally assumed that an... Church-Turing thesis.

The concept of the Turing machine is based on the idea of a person executing a well-defined procedure by changing the contents of an infinite number of ordered paper sheets that can contain one of a finite set of symbols. The person needs to remember one of a finite set of states and the procedure is formulated in very basic steps in the form of "If your state is 42 and the symbol you see is a '0' then replace this with a '1', remember the state 17, and go to the following sheet."

Turing machines shouldn't be confused with the The Turing test is a proposal for a test of a machines capability to perform human-like conversation. Described by Alan Turing in the 1950 paper Computing machinery and intelligence, it proceeds as follows: a human judge engages in a natural language conversation with two other parties, one a... Turing test, Turing's attempt to capture the notion of This article is about intelligence exhibited by manufactured systems, typically computers. For other uses of the term AI, see Ai. For the influential Warp Records series, see Artificial Intelligence (series). Artificial intelligence, also known as machine intelligence, is defined as intelligence exhibited by anything manufactured (i.e. artificial) by humans... artificial intelligence.

A Turing machine that is able to simulate any other Turing machine is called a universal Turing machine or simply a universal machine as Turing described it in 1947:

It can be shown that a single special machine of that type can be made to do the work of all. It could in fact be made to work as a model of any other machine. The special machine may be called the universal machine.

Definition

Informal description

A Turing machine is a In computer science, in particular automata theory, pushdown automata (PDA) are abstract devices that recognize context-free languages. Informally, a pushdown automaton is a finite automaton outfitted with access to a potentially unlimited amount of memory in the form of a single stack. The finite automaton in question is usually... pushdown automaton made more powerful by relaxing the last-in-first-out requirement of its stack. (Interestingly, a seemingly minor relaxation enables the Turing machine to perform such a wide variety of computations that it can serve as a model for the computational capabilities of all modern computer software.)

More precisely, a Turing machine consists of:

1. A tape which is divided into cells, one next to the other. Each cell contains a symbol from some finite alphabet. The alphabet contains a special blank symbol (here written as '0') and one or more other symbols. The tape is assumed to be arbitrarily extendible to the left and to the right, i.e., the Turing machine is always supplied with as much tape as it needs for its computation. Cells that have not been written to before are assumed to be filled with the blank symbol.
2. A head that can read and write symbols on the tape and move left and right.
3. A state register that stores the state of the Turing machine. The number of different states is always finite and there is one special start state with which the state register is initialized.
4. An action table (or transition function) that tells the machine what symbol to write, how to move the head ('L' for one step left, and 'R' for one step right) and what its new state will be, given the symbol it has just read on the tape and the state it is currently in. If there is no entry in the table for the current combination of symbol and state then the machine will halt.

Note that every part of the machine is finite, but it is the potentially unlimited amount of tape that gives it an unbounded amount of storage space.

Formal definition

One-tape Turing machine

More formally, a (one-tape) Turing machine is usually defined as a 6- See also tuple (music) as in duple and triple. In mathematics, a tuple is a finite sequence of objects (an ordered list of a limited number of objects). (An infinite sequence is a family.) Tuples are used by mathematicians to describe mathematical objects that consist of certain components. For example... tuple M = (Q,Γ,s,b,F,δ), where

• Q is a finite set of states
• Γ is a finite set of the tape alphabet
• is the initial state
• is the blank symbol (the only symbol allowed to occur on the tape infinitely often at any step during the computation)
• is the set of final or accepting states
• is a partial function called the transition function, where L is left shift, R is right shift.

Definitions in the literature sometimes differ slightly, to make arguments or proofs easier or clearer, but this is always done in such a way that the resulting machine has the same computational power. For example, changing the set {L,R} to {L,R,S}, where S would allow the machine to stay on the same tape cell instead of moving left or right, does not increase the machine's computational power.

k-tape Turing machine

A k-tape Turing machine can similarly be described as a 6-tuple M = (Q,Γ,s,b,F,δ), where

• Q is a finite set of states
• Γ is a finite set of the tape alphabet
• is the initial state
• is the blank symbol
• is the set of final or accepting states
• is a partial function called the transition function, where L is left shift, R is right shift, S is no shift.

Note that a k-tape Turing Machine is no more powerful than a standard Turing Machine.

Example

The following Turing machine has an alphabet {'0', '1'}, with 0 being the blank symbol. It expects a series of 1's on the tape, with the head initially on the leftmost 1, and doubles the 1's with a 0 in between, i.e., "111" becomes "1110111". The set of states is {s1, s2, s3, s4, s5} and the start state is s1. The action table is as follows.

 Old Read Wr. New Old Read Wr. New St. Sym. Sym. Mv. St. St. Sym. Sym. Mv. St. - - - - - - - - - - - - - - - - - - - - - - - - s1 1 -> 0 R s2 s4 1 -> 1 L s4 s2 1 -> 1 R s2 s4 0 -> 0 L s5 s2 0 -> 0 R s3 s5 1 -> 1 L s5 s3 0 -> 1 L s4 s5 0 -> 1 R s1 s3 1 -> 1 R s3 

A computation of this Turing machine might for example be: (the position of the head is indicated by displaying the cell in bold face)

 Step State Tape Step State Tape - - - - - - - - - - - - - - - - - 1 s1 11 9 s2 1001 2 s2 01 10 s3 1001 3 s2 010 11 s3 10010 4 s3 0100 12 s4 10011 5 s4 0101 13 s4 10011 6 s5 0101 14 s5 10011 7 s5 0101 15 s1 11011 8 s1 1101 -- halt -- 

The behavior of this machine can be described as a loop: it starts out in s1, replaces the first 1 with a 0, then uses s2 to move to the right, skipping over 1's and the first 0 encountered. S3 then skips over the next sequence of 1's (initially there are none) and replaces the first 0 it finds with a 1. S4 moves back to the left, skipping over 1's until it finds a 0 and switches to s5. s5 then moves to the left, skipping over 1's until it finds the 0 that was originally written by s1. It replaces that 0 with a 1, moves one position to the right and enters s1 again for another round of the loop. This continues until s1 finds a 0 (this is the 0 right in the middle between the two strings of 1's) at which time the machine halts.

Deterministic and non-deterministic Turing machines

If the action table has at most one entry for each combination of symbol and state then the machine is a deterministic Turing machine (DTM). If the action table contains multiple entries for a combination of symbol and state then the machine is a In theoretical computer science, an ordinary (deterministic) Turing machine has a transition rule that specifies for a given current state of the head and computer (s,q) a single instruction (s, q, d), where s is the symbol to be written by the head, q is the subsequent state of... non-deterministic Turing machine (NDTM or NTM).

Universal Turing machines

Every Turing machine computes a certain fixed In mathematics and computer science, a partial function from the domain X to the codomain Y is a binary relation over X and Y which associates with every element in the set X at most one element in the set Y. If a partial function associates with every element in... partial In computability theory computable functions or Turing computable functions are the basic objects of study. They make our intuitive notion of algorithm precise and according to the Church-Turing thesis they are exactly the functions that can be calculated using a mechanic calculation device. Before the precise definition of computable... computable function from the input strings over its alphabet. In that sense it behaves like a computer with a fixed program. However, as Alan Turing already described, we can encode the action table of any Turing machine in a string. Thus we might try to construct a Turing machine that expects on its tape a string describing an action table followed by a string describing the input tape, and then computes the tape that the encoded Turing machine would have computed. As Turing showed, such a Turing machine is indeed possible and since it is able to simulate any other Turing machine it is called a universal Turing machine.

With this encoding of action tables as strings, it becomes possible in principle for Turing machines to answer questions about the behavior of other Turing machines. Most of these questions, however, are undecidable, meaning that the function in question cannot be calculated by any Turing machine. For instance, the problem of determining whether a particular Turing machine will halt on a particular input, or on all inputs, known as the In computability theory the halting problem is a decision problem which can be informally stated as follows: Given a description of an algorithm and its initial input, determine whether the algorithm, when executed on this input, ever halts (completes). The alternative is that it runs forever without halting. Alan Turing... Halting problem, was shown to be undecidable in Turing's original paper. Rice's theorem shows that any nontrivial question about the behavior or output of a Turing machine is undecidable.

If we broaden the definition to include any Turing machine that simulates some Turing-complete computational model, not just Turing machines that directly simulate other Turing machines, a universal Turing machine can be fairly simple, using just a few states and a few symbols. For example, only 2 states are needed, since a 2×18 (meaning 2 states, 18 symbols) universal Turing machine is known. A complete list of the smallest known universal Turing machines is: 2×18, 3×10, 4×6, 5×5, 7×4, 10×3, 22×2. These simulate a computational model called A tag system is a certain turing-equivalent computational system. External link http://mathworld.wolfram.com/TagSystem.html Categories: Stub ... tag systems.

A universal Turing machine is In computability theory a programming language or any other logical system is called Turing-complete if it has a computational power equivalent to a universal Turing machine. In other words, the system and the universal Turing machine can emulate each other. (Under traditional hyphenation conventions, the adjective Turing-complete should... Turing-complete. It can calculate any In mathematical logic and computer science, the recursive functions are a class of functions from natural numbers to natural numbers which are computable in some intuitive sense. In fact, in computability theory it is shown that the recursive functions are precisely the functions that can be computed by Turing machines... recursive function, decide any In computer science a formal language is called recursive or decidable if there exists an algorithm to decide for any given string w over the alphabet of the language, if w belongs to the language or not. More formally, a formal language is called recursive if and only if it... recursive language, and accept any In mathematics, logic and computer science, a formal language is called recursively enumerable, partially decidable or Turing-recognizable if there exists an algorithm to enumerate all valid strings of the language. Alternatively we can define them as those languages for which an algorithm exists, that when given string w as... recursively enumerable language. According to the Church-Turing thesis, the problems solvable by a universal Turing machine are exactly those problems solvable by an algorithm or an effective method of computation, for any reasonable definition of those terms.

Comparison with real machines

It's often said that Turing machines, unlike simpler automata, are as powerful as real machines, and are able to execute any operation that a real program can. What is missed in this statement is that almost any particular program running on a particular machine and given a finite amount of input is in fact nothing but a In the theory of computation, a deterministic finite state machine or deterministic finite automaton (DFA) is a finite state machine where for each pair of state and input symbol there is a deterministic next state. Formal definition A DFA is a 5-tuple, (S, Σ, T, s, A), consisting of... deterministic finite automaton, since the machine it runs on can only be in finitely many configurations. Turing machines would actually only be equivalent to a machine that had an infinite amount of storage space. We might ask, then, why Turing machines are useful models of real computers. There are a number of ways to answer this:

1. The difference lies only with the ability of a Turing machine to manipulate unbounded amout of data. However, an actual running of a Turing machine that manipulates unbounded data, takes unbounded time to do so.
2. Real machines are much more complex than a Turing machine. For example, a Turing machine describing an algorithm may have a few hundred states, while the equivalent DFA on a given real machine has quadrillions.
3. Turing machines describe algorithms independent of how much memory they utilize. There is a maximum to the amount of memory that any machine which we know of has, but this limit can rise arbitrarily in time. Turing machines allow us to make statements about algorithms which will (theoretically) hold forever, regardless of advances in conventional computing machine architecture.
4. Turing machines simplify the statement of algorithms. Algorithms running on Turing-equivalent abstract machines are usually more general than their counterparts running on real machines, because they have arbitrary-precision datatypes available and never have to deal with unexpected conditions (including, but not limited to, running out of memory).

One way in which Turing machines are a poor model for programs is that many real programs, such as In computing, an operating system (OS) is the system software responsible for the direct control and management of hardware and basic system operations. Additionally, it provides a foundation upon which to run application software such as word processing programs and web browsers. In general, the operating system is the first... operating systems and A word processor (also more formally known as a document preparation system) is a computer application used for the production (including composition, editing, formatting, and possibly printing) of any sort of viewable or printed material. They are descended from early text formatting tools (sometimes called text justification tools, from their... word processors, are written to receive unbounded input over time, and therefore do not halt. Turing machines do not model such ongoing computation well (but can still model portions of it, such as individual procedures).

Another limitation of Turing Machines is that they do not model the strengths of a particular arrangement well. For instance, modern computers are actually instances of a more specific form of computing machine, known as the random access machine. The primary difference between this machine and the Turing Machine is that the Turing Machine uses an infinite tape, while the random access machine uses a numerically indexed sequence (typically an integer field). The upshot of this distinction is that there are computational optimizations that can be performed based on the memory indices, which are not possible in a general Turing Machine; thus when Turing Machines are used as the basis for bounding running times, a 'false lower bound' can be proven on certain algorithms' running times (due to the false simplifying assumption of a Turing Machine). An example of this is Counting sort (like bucket sort) is a sorting algorithm which takes advantage of knowing the maximum value within the array to be sorted. If the maximum value is not known, an initial pass of the data will be necessary to find the largest value (this pass will be O(n... counting sort, which seemingly violates the θ(nlogn) In mathematics, especially in order theory, an upper bound of a subset S of some partially ordered set is an element which is greater than or equal to every element of S. The term lower bound is defined dually. Formally, given a partially ordered set (P, ≤), an element u... lower bound on In computer science and mathematics, a sorting algorithm is an algorithm that puts elements of a list in a certain order. The most used orders are numerical order and lexicographical order. Efficient sorting is important to optimizing the use of other algorithms (such as search and merge algorithms) that require... sorting algorithms.

A physical Turing machine

It is not difficult to simulate a Turing machine on a modern computer (except for the limited memory of actually existing computers).

It is also possible to build a Turing machine on a purely mechanical basis. The mathematician Karl Scherer is a mathematician who built a mechanical Turing machine in 1986 using metal and plastic construction sets, and some wood. The 1.5-meter-high machine uses the pulling of strings to read, move and write the data (which is represented using ball bearing balls). The machine is... Karl Scherer has indeed built such a machine in 1986 is a common year starting on Wednesday of the Gregorian calendar. Events January January 1 - Spain and Portugal enter the European Community January 1 - Aruba gains increased autonomy from the Netherlands and is separated from the Netherlands Antilles. January 9 - After losing a patent battle with Polaroid, Kodak leaves... 1986 using metal and plastic construction sets, and some wood. The 1.5 meter high machine uses the pulling of strings to read, move and write the data (which is represented using ball A bearing is a component used to reduce friction in a machine. Bearings may be classified broadly according to the motions they allow and according to their principle of operation. Major Types Common motions include linear and rotary. A linear bearing allows motion along a straight line, for example a... bearings).

The machine is now exhibited in the entrance of the Department of Computer Science of the The Ruprecht Karl University of Heidelberg (German Ruprecht-Karls-Universität Heidelberg; also known as simply University of Heidelberg) was established in the town of Heidelberg in the Rhineland in 1386. The Latin name is Ruperto Carola Heidelbergensis. It is a member of the Coimbra Group and the LERU. The... University of Heidelberg, The Federal Republic of Germany ( German: Bundesrepublik Deutschland) is one of the worlds leading industrialised countries, located in the heart of Europe. Due to its central location, Germany has more neighbours than any other European country: these are Denmark in the north, Poland and the Czech Republic in the... Germany.

Also, using a few hundred mirrors, one can build an optical universal Turing machine in one's backyard, using the In dynamical systems theory, the horseshoe map was introduced by Stephen Smale as a simple model of complex behavior. It is given on the unit square by the formula: (1)     , where: (2)     This map serves as a model for general behavior at... Horseshoe map. This is based on a work by Stephen Smale (born July 15, 1930) is an American mathematician and winner of the Fields Medal in 1966. He made his reputation by a proof of the Poincare conjecture for all dimensions greater than 4; he later generalized the ideas in the proof to establish the h-cobordism theorem. Stephen... Stephen Smale.

The concept of a Turing machine was used as an educational tool in the Science fiction is a form of speculative fiction principally dealing with the impact of imagined science and technology, or both, upon society and persons as individuals. There are exceptions (or, at least, some unusual examples) to this general definition. Scope In defining the scope of the science fiction genre, we... science fiction novel The Diamond Age, or A Young Ladys Illustrated Primer is a 1995 cyberpunk or postcyberpunk novel by Neal Stephenson taking place in a world where nanotechnology is ubiquitous. Its primary themes include social class, cultural tribalism, and societal responses to technological change. The book won the 1996 Hugo Award... The Diamond Age (1995), by Neal Stephenson (b. October 31, 1959 in Fort Meade, Maryland) is known primarily as a science fiction writer in the postcyberpunk genre with a predisposition to divert into explorations of mathematics, currency, and the history of science. He also writes non-fiction articles about technology in publications such as Wired... Neal Stephenson. The main character, Nell, possesses an interactive book which teaches her creative thinking and logic by presenting puzzles in a story as Turing machines which become more and more complex as the story progresses. They begin as a simple chain-fed clockwork device and progresses to abstract economic processes, trades, and finally the interaction of entire fictional kingdoms.

See also

• Langton's ant, a simple two-dimensional Turing machine.
• Paterson's worms, a family of two-dimensional Turing machines
• In computability theory the Church-Turing thesis, Churchs thesis, Churchs conjecture or Turings thesis, named after Alonzo Church and Alan Turing, is a hypothesis about the nature of mechanical calculation devices, like computers, and what kind of algorithms they can perform. It is generally assumed that an... Church-Turing thesis, effective Turing machine can perform any computation in any language.
• In computability theory, a busy beaver (from the colloquial expression for industrious person) is a Turing machine that, when given an initially empty (binary) tape (a string of only 0s), does a lot of work, then halts. The functions defined below, called busy beaver functions, were introduced and their... Busy Beaver
• Computability logic is a formal theory of computability, introduced by Giorgi Japaridze in 2003. That is in the same sense as classical logic is a formal theory of truth. While the central semantic concept in classical logic is (Tarskian) truth, computability logic is based on a concept of computability. The... Computability logic
• A Turing tarpit is a programming language designed to be Turing-complete while minimizing the number of distinct instructions. Such a language gives up practicality (such as ease of coding, performance, etc.) but is often useful in theoretical computer science. Originally: 54. Beware of the Turing tar-pit in which... Turing tarpit, a term describing a minimalistic Turing-complete programming language
• In computability theory a programming language or any other logical system is called Turing-complete if it has a computational power equivalent to a universal Turing machine. In other words, the system and the universal Turing machine can emulate each other. (Under traditional hyphenation conventions, the adjective Turing-complete should... Turing completeness

References

• Rolf Herken: The Universal Turing Machine - A Half-Century Survey, Springer Verlag, ISBN 3-211-82637-8
• Paul Strathern: Turing and the Computer - The big idea, Anchor Books/Doubleday, ISBN 0-385-49243-X
• Turing, A., On Computable Numbers, With an Application to the Entscheidungsproblem (http://www.abelard.org/turpap2/tp2-ie.asp), Proceedings of the London Mathematical Society, Series 2, Volume 42, 1936; reprinted in M. David (ed.), The Undecidable, Hewlett, NY: Raven Press, 1965;
• Boolos, G. and Jeffrey, R., Computability and Logic, 2nd ed., Cambridge: Cambridge University Press, 1980.
• Rogozhin, Yurii, "A Universal Turing Machine with 22 States and 2 Symbols" (http://www.imt.ro/Romjist/Volum1/Vol1_3/turing.htm), Romanian Journal Of Information Science and Technology, 1(3), 259-265, 1998. (surveys known results about small universal Turing machines)

External links

• Turing Machine on Stanford Encyclopedia of Philosophy (http://plato.stanford.edu/entries/turing-machine/)
• Detailed info on the Church-Turing Hypothesis (http://plato.stanford.edu/entries/church-turing/) (Stanford Encyclopedia of Philosophy)
• Computing machinery and intelligence - A.M. Turing (http://www.abelard.org/turpap/turpap.htm) Original 1950 article by Alan Turing on machine intelligence, where he introduces the famous Turing test
• The Turing test and intelligencedocument (http://www.abelard.org/turing/tur-hi.htm) clarifying the meaning of the Turing test and suggests that meeting the Turing test is already in the process of being achieved
• Citations from CiteSeer (http://citeseer.org/cs?q=Turing+machine)

Simulators

• Visual Turing, a Turing machine interactive simulator/IDE (http://www.cheransoft.com/vturing/) (free software for Windows).
• Suzanne Brittons Turing Machine Simulator (http://ironphoenix.org/tril/tm/) (java applet).
• C++ Simulator of a Nondeterministic and Deterministic Multitape Turing Machine (http://semillon.wpi.edu/~aofa/AofA/msg00020.html) (free software).
• C++ Simulator of a Universal Turing Machine (which accepts Multitape Turing Machine) (http://semillon.wpi.edu/~aofa/AofA/msg00024.html) (free software).
• Turing Machine as an educational freeware board game for PCs (http://www.zillions-of-games.com/cgi-bin/zilligames/submissions.cgi/71230?do=show;id=9)
• Turing Machine II - an educational freeware board game for PCs (http://www.zillions-of-games.com/cgi-bin/zilligames/submissions.cgi/71230?do=show;id=10)
• Turing Train Teminal (http://www.monochrom.at/turingtrainterminal/) - A working Turing machine built out of scale trains.