Turing Machine

#REDIRECT Turing machine

Turing machine

The Turing machine is an abstract machine introduced in 1936 by Alan Turing to give a mathematically precise definition of algorithm or 'mechanical procedure'. The concept is still widely used in theoretical computer science, especially in computational complexity theory and the theory of 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 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 Turing test, Turing's attempt to capture the notion of 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 pushdown automaton made more powerful by relaxing the last-in-first-out requirement of its stack. (Interestingly, this 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: # 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. # A ''head'' that can read and write symbols on the tape and move left and right. # 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. # 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; 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-tuple $M=(Q,\; \backslash Gamma,\; s,\; b,\; F,\; \backslash delta)$, where *$Q$ is a finite set of states *$\backslash Gamma$ is a finite set of the tape alphabet *$s\; \backslash in\; Q$ is the initial state *$b\; \backslash in\; \backslash Gamma$ is the blank symbol (the only symbol allowed to occur on the tape infinitely often at any step during the computation) *$F\; \backslash subseteq\; Q$ is the set of final or accepting states *$\backslash delta:\; Q\; \backslash times\; \backslash Gamma\; \backslash rightarrow\; Q\; \backslash times\; \backslash Gamma\; \backslash times\; \backslash \{L,R\backslash \}$ 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 $\backslash \{L,R\backslash \}$ to $\backslash \{L,R,S\backslash \}$, 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,\; \backslash Gamma,\; s,\; b,\; F,\; \backslash delta)$, where *$Q$ is a finite set of states *$\backslash Gamma$ is a finite set of the tape alphabet *$s\; \backslash in\; Q$ is the initial state *$b\; \backslash in\; \backslash Gamma$ is the blank symbol *$F\; \backslash subseteq\; Q$ is the set of final or accepting states *$\backslash delta:\; Q\; \backslash times\; \backslash Gamma^k\; \backslash rightarrow\; Q\; \backslash times\; (\backslash Gamma\; \backslash times\; \backslash \{L,R,S\backslash \})^k$ 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 1s on the tape, with the head initially on the leftmost 1, and doubles the 1s 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 1s and the first 0 encountered. S3 then skips over the next sequence of 1s (initially there are none) and replaces the first 0 it finds with a 1. S4 moves back to the left, skipping over 1s until it finds a 0 and switches to s5. s5 then moves to the left, skipping over 1s 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 1s) 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 non-deterministic Turing machine (NDTM or NTM). == Universal Turing machines == Every Turing machine computes a certain fixed partial function 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 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 tag systems. A universal Turing machine is Turing completeness. It can calculate any recursive function, decide any recursive language, and accept any 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 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 unlimited 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: # The difference lies only with the ability of a Turing machine to manipulate an unbounded amount of data. However, given a finite amount of time, a Turing machine (like a real machine) can only manipulate a finite amount of data. # Like a Turing machine, a real machine can have its storage space enlarged as needed, by acquiring more disks or other storage media. If the supply of these runs short, the Turing machine may become less useful as a model. But the fact is that neither Turing machines nor real machines need astronomical amounts of storage space in order to do most of the computations people actually want done. The processing time required is usually much more of a problem. # 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. # 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. # 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 operating systems and 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, which seemingly violates the $\backslash theta(n\backslash log\{n\})$ lower bound on sorting algorithms. The concept of a Turing machine was used as an educational tool in the science fiction novel ''The Diamond Age'' (1995), by 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 analogue of the Turing machine. * Probabilistic Turing machine * Church-Turing thesis, which says Turing machines can perform any computation that can be performed. * Busy Beaver * Computability logic * Turing completeness * Turing tarpit, any computing system or language which, like the Turing machine, is not only Turing-complete but also useless for practical computing. * Neal Stephenson's Cryptonomicon == 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 * [http://www.abelard.org/turpap2/tp2-ie.asp Turing, A., ''On Computable Numbers, With an Application to the Entscheidungsproblem''], 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. * [http://www.imt.ro/Romjist/Volum1/Vol1_3/turing.htm Rogozhin, Yurii, "A Universal Turing Machine with 22 States and 2 Symbols"], ''Romanian Journal Of Information Science and Technology'', 1(3), 259-265, 1998. (surveys known results about small universal Turing machines) == External links == * [http://plato.stanford.edu/entries/turing-machine/ Turing Machine on Stanford Encyclopedia of Philosophy] * [http://plato.stanford.edu/entries/church-turing/ Detailed info on the Church-Turing Hypothesis] (Stanford Encyclopedia of Philosophy) * [http://citeseer.org/cs?q=Turing+machine Citations from CiteSeer] == Simulators == * [http://sourceforge.net/projects/visualturing/ Visual Turing Machine], a visual designer and simulator, (free software, platform independent). * [http://www.cheransoft.com/vturing/ Visual Turing, a Turing machine interactive simulator/IDE] (free software for Windows). * [http://ironphoenix.org/tril/tm/ Suzanne Britton's Turing Machine Simulator] (java applet). * [http://semillon.wpi.edu/~aofa/AofA/msg00020.html C++ Simulator of a Nondeterministic and Deterministic Multitape Turing Machine] (free software). * [http://semillon.wpi.edu/~aofa/AofA/msg00024.html C++ Simulator of a Universal Turing Machine (which accepts Multitape Turing Machine)] (free software). * [http://www.monochrom.at/turingtrainterminal/ Turing Train Terminal] - A working Turing machine built out of scale trains. Alan Turing Computational models th:เครื่องจักรทัวริง

Turing machine

==Old discussions with no heading== I added the formal definition of the Turing machine, because I felt it was missing. Such a definition exists for the pushdown automaton and I think it is important to have it for the Turing machine as well. However, I am not satisfied with the blank symbol, because the bar should strike through the upper part of the "b", and not sit on top of it. If anyone knows how to display this symbol between "math" markups, please correct it. --User:Gachet ---- I was thinking of adding a link to the general theorem which says that practically no non-trivial question about the behavior of Turing machines can be decided, but I forgot the name of it. Anybody knows? --AxelBoldt ---- Sure, it's Rice's Theorem. --:AV ---- Two things are missing from the article but I don't have time right now: * The functions that Turing machines define are only partial because TM's need not halt. * Link to recursive functions, recursive and recursively enumerable languages. --AxelBoldt ---- Someone got Minsky's 7x4 confused with Rogozhin's 4x6, and so states and symbols were tangled in the text...I've tried to unsnarl it but I have trusted the content of the table, except for swapping the order to be more intuitive. By the way, Rogozhin said Raphael Robinson spotted a defect in Minsky's table, which both Rogozhin and Robinson remedied in different ways, still using only 7x4, so maybe this isn't the best example. Also I thought it worth clarifying the different definitions of UTM, based on Turing-completeness vs. simulating other Turing machines. None of that list of smallest ones directly simulates a Turing machine, though they can simulate a tag-system that simulates a Turing machine, or indeed a tag-system that simulates a Pentium. -Daniel. :Personally, I don't think the table of the universal machine is useful at all without knowing precisely what tag-systems are and how they are supposed to be presented as input to the machine. Maybe we should start Universal Turing machine and discuss all these matters there. User:AxelBoldt 22:17 Nov 16, 2002 (UTC) ::A good idea. I've deleted the table, and will dig up the right references and make the new page soon, if I remember. -Daniel. :::Okay. If I haven't done it by now I probably never will. Sorry. -Daniel. ---- Moved from article, from section "References and external links" (link not working - 404): * A Turing machine implemented in the cellular automaton known as Conway's Game of Life: http://www.rendell.co.uk/gol/tm.htm (by User:Snoyes 22:16 Mar 30, 2003 (UTC)) ---- Something which may or may not deserve mentioning. A Turing machine as described in Turing's original paper actually never halts, so the halting problem for such machines is easily solvable. The problem shown to be unsolvable in that paper is thus not the halting problem but another, closely related problem. This point seems to be totally ignored in most web documentation on the issue, and I don't know whether or how to go about mentioning it here. Thoughts? -Daniel. : I don't understand Turing's paper sufficiently to check whether it halts or not... but in my compsci lectures the lecturer described a turing-like machine with a HALT instruction, and proceeded from there to show X Y and Z. An obvious equivalent in a machine with no HALT instruction is to set a flag READ-ONLY and modify all rules so that if the READ-ONLY flag is set then no modifications are made. Then you define the halting problem as asking - does the machine ever get the READ-ONLY flag set? User:MyRedDice ---- I hope I didn't break this article with my incomprehensible cloud-shovelling strict version of Turing machines. I'm also not completely certain I didn't make some sort of trivial error somewhere. There's a guy at the McGill math department who claims he had an alternate model of computation at the same time (or so) as Turing did, and for that reason they use it a bit there. His claim to fame is that it's less cumbersome and tricky to write down than this Turing machine business, even if the Turing machine approach is closer in spirit to actual hardware. User:Loisel 08:59 6 Jul 2003 (UTC) :Loisel, it is getting a little dense towards the end. We're trying to write for as general an audience as is realistic here. Do you think you could present it more accessibly? I'd like to have a dash at it, but it might be a while until I get round to it. By the way, there is already an article on complexity classes P and NP, so you might consider how much material on that subject should be in this article. --User:Robert Merkel 05:48, 7 Aug 2003 (UTC) :In fact, I have to say that earlier versions of the article are actually, to my way of thinking, more useful. I honestly am tempted to revert it. --User:Robert Merkel 05:55, 7 Aug 2003 (UTC) ---- I have decided to revert to an earlier version of the article, on the basis that this version is actually readable, unlike the present version. Have a look at the two versions and compare. Any useful information from later versions not captured in this version should of course be added back in, but let's try and remember our audience when we write please. --User:Robert Merkel 09:11, 10 Aug 2003 (UTC) :I put back the paragraph about undecidable UTM problems and Rice's theorem. I think the current version (un-reverted) is both clearer and more informative than the reverted version. I hope you agree. I do agree that the article is better without the giant mathematical gobbledygook section that you removed. -User:Dominus 12:52, 10 Aug 2003 (UTC) ::I completely agree. Good work. --User:Robert Merkel 00:16, 11 Aug 2003 (UTC) ---- My question is this. Must the turing machine move either left or right everytime? Can there be a state which does not move the head? 28th Aug 2003 : It's easy to prove that for every Turing machine that is allowed to leave its head stationary, there is an equivalent Turing machine, accepting the same language, which moves its head at every step. So it doesn't matter whether you require the head to move or not. -- User:Dominus 04:25, 28 Aug 2003 (UTC) ---- Old Read Wr. New St. Sym. Sym. Mv. St. Eh? Old State, ?, ?, Move, New State? -- User:R3m0t 23:45, 7 Dec 2003 (UTC) :I'd presume "Old State, Read Symbol, Write/Written Symbol, Move, New State", but I'm not 100% sure, and have only skim-read the article. I agree that it needs clarifying, though - and perhaps the tables ought to be properly marked up, too, rather than just laying out text ASCII-art style? :In fact, if I understand it correctly, it would probably best be labelled "Old State, Symbol Read, Symbol to Write, Move Direction, New State" - at least in some kind of key/legend. :- User:IMSoP 00:08, 9 Dec 2003 (UTC) :: I came here to make the same comment. This doesn't make any sense if you don't know what the abbreviations mean, and they're not obvious. Needs rewriting by someone who understands what it means! User:HappyDog 01:28, 17 Jan 2004 (UTC) ---- TEXT OF DELETED ARTICLE Turing Machine with faults, failures and recovery (in case anyone wants to merge anything in) User:Tannin 11:05, 3 Mar 2004 (UTC) ''This page has been listed on Wikipedia:Votes for deletion. Please see that page for justifications and discussion.''

== Turing Machine with faults, failures and recovery ==
In contrast to practical situation an ordinary Turing Machine never fails.
Turing Machine with faults, failures and recovery is (weakly) non-deterministic Turing Machine consisting of : * five semi-infinite (to the right) tapes
** Master Tape,
** Synchro Tape,
** Backup Tape,
** Backup Synchro Tape,
** User (Tester) Tape;
* four controlling components (sets of rules)
** Program,
** Daemon,
** Apparatus,
** User.
Only daemon has non-deterministic behavior.

==== Tapes, alphabets ==== Master Tape corresponds to the tape of ordinary deterministic Turing Machine.
Head of Synchro Tape is synchronized with head of Master Tape.
Backup Tape is used to back Master Tape data up.
Backup Synchro Tape is used to back Synchro Tape data up.
User Tape is used to perform pure/ideal computation (without faults and failures).

Master Tape, Backup Tape, User Tape are using the same (user-defined) alphabet.
Synchro Tape, Backup Synchro Tape are using the same special (embedded, user-independent) alphabet.

==== States ==== Program contains :
- user-defined states (initial, internal and halting states),
- user-required check-point states (indirectly defined by user),
- embedded (user-independent) shutting down state.
Note 1. Some of user-defined rules an user may mark as check-points.
Check-point states are derived from these rules.
Note 2. Shutting down state differs from user-defined halting state.

Daemon contains three embedded (user-independent) states :
- passive,
- active,
- aggressive.

Apparatus contains two embedded (user-independent) states :
- normal,
- emergency.

User contains two embedded (user-independent) states :
- tracking,
- stabilizing.

==== Rules ==== There are three sets of rules :
a) Daemon's set of non-deterministic rules.
The set includes only daemon states.
b) Common set of deterministic rules
The set includes states of all controlling components (program, daemon, apparatus, user).
In fact, this common set consists of two subsets :
- program rules including
* user-defined rules,
* user-required check-point rules;
- outside rules including
* deterministic daemon rules,
* apparatus rules,
* user rules.
c) Daemon-defined set of rules (fault rules).

==== Transitions ==== Each transition step consists of two half-steps (tacts) :
a) First tact. Daemon performs transition according to non-deterministic rule
from passive state to {passive, active, aggressive }
b) Second tact. One of three kinds of transitions is performed :
- normal transition, if daemon is in passive state,
- fault transition, if daemon is in active state,
- failure transition, if daemon is in aggressive state.
Note. On second tact daemon always goes into passive state.

==== Faults and failures ==== The difference between fault and failure is as follows.
- Fault transition : * apparatus stay in normal state.
* illegal (daemon-defined) program rule is applied,
and the program continues computation.
- Failure transition : * apparatus go into in emergency state.
* the program is unable to continue computation.

=== External links === http://alexvn.freeservers.com/s1/utm.html
http://sourceforge.net/project/showfiles.php?group_id=79519&package_id=80937
== Diagram == This page ''really'' needs a diagram. Even a simple one would do. I'll take care of this in a while if no one else gets to it. User:Dcoetzee 00:58, 2 Oct 2004 (UTC) :I have one at [http://perl.plover.com/yak/lambda/samples/tm.gif], although it's not particularly attractive. If you do want to use it, I hereby release the illustration under the terms of the GFDL. -- User:Dominus 14:10, 2 Nov 2004 (UTC) ::I like it, but I'd prefer something that shows that the tape is semi-infinite and evokes that finiteness of the control. I'm thinking of adding in the "toy train" metaphor somewhere, and a diagram to go with that. (The train metaphor is that the read/write head is represented by a toy train on a track that extends forever in one direction, and it decides without any outside control which way to go based on the character under it. Less clear, though, is how a train writes characters on the track.) User:Dcoetzee 23:52, 2 Nov 2004 (UTC) :::According to the wikipedia article, the tape is infinite in both directions. -- User:Dominus 14:08, 3 Nov 2004 (UTC) ::::You're right. I usually see it treated with a semi-infinite tape, as in Sipser, but admittedly this complicates the mechanics a bit (you need to say what happens when it moves left from the leftmost cell). On the other hand it helps sometimes to be able to speak of the "beginning" of the tape, but you might as well label them with integers and call the cell labelled zero the "origin" of the tape. I'm unsure which is better for education. User:Dcoetzee 18:17, 3 Nov 2004 (UTC) == Were the actual machines ever widely produced pre-computer era? == I know Turing machines were used a lot in military and industrial sector applications before computers made their way through as the mainly used calculating machines; but were Turing machines ever produced by any company on a wider market for small-business clients? : Turing machines are a purely theoretical concept, not real machines. There were different calculating machines before the computer used by military as well as by bigger businesses. -- User:Tillwe | User_talk:tillwe 08:55, 29 Nov 2004 (UTC) == The meaning of "state", and computers as DFAs == Im curious about the use of the term "state" in this document. It seems to me that two seperate concepts of state are referred to in the document without distinguishing them. Consider that in the "informal description" it keeps the concept of state and memory distinct: " 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. .... 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. " However later on in the section "Comparison with real machines" a different "state" is discussed (albeit implicitly): "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 deterministic finite automaton, since the machine it runs on can only be in finitely many states." The problem here is that in the first case "state" is held to be distinct from memory. In the second case memory and state are merged. The truth is that a "real computer" is much closer to a turing machine (with memory distinct from state) than it is to a DFA (with no memory outside of state). :I agree with you up to this last sentence. Two different senses of "state" have been used, both of which are common and established in their own areas, and this is potentially confusing. But "state" as the word is used in talking about real computers definitely includes the contents of memory; and "state" as the word is used in talking about Turing machines does not map neatly onto any feature of real computers. So I don't think it would be clear to say "The truth is that a 'real computer' has memory distinct from its state." :In a related issue, after mapping DFAs to Turing machines (where the "state" is not the main form of storage), and then mapping Turing machines to real computers, we are then asked to map real computers back onto DFAs. But this time, we're using "state" in the sense of the complete configuration of a computer's memory, registers, hard drives, and whatever...and mapping that back onto the DFA sense of "state". Meaning we end up with a DFA with two-to-the-trillionth-power different states or something, as you've mentioned below, and it seems like a technicality to call that "finite". However, this is indeed what people mean in saying a real computer is only as powerful as a DFA. It seems to me that this mixed use in the discussion of any form of finite state automata is extremely confusing. Either a turing machine has infinite states, :(in the sense of "state" used in talking about real computers, it does...) or a "real computer" is a turing machine with restricted memory. If we accept that a "real computer" is equivelent to a DFA then we shouldnt discuss Turing machines as though they were finite state machines. Also in todays market of mass storage devices and backup tapes IMO a modern computer has essentially infinte resources to work with. After all we could keep adding new harddrives ad nauseum. :This is true and I've added it to the article. I also think that the merging of state and memory is problematic as it implies that the state of the machine is a holistic one comprising of the combined state of every mass storage device and memory address that the computer can access. Since a single byte of RAM implies 256 distinct states a computer with a few terabytes of mass storage available and a few gigabytes of memory would have more states than there are atoms in the universe. Add a network connection and the number of states that the machine can be in just explodes. :Right. And that is what they mean. It's a huge number but it is still finite and that's their point. I've tried to address the distance between that and any practical limitations, in my addition to the article. Maybe this is just the ramblings of a confused man, but personally i feel that there is a problem here. Some areas where it gets confusing is that in other documents we see that one requires a turing machine to process a type 0 language and that DFA's and NFA's can only handle a type 3 language. However if a "real computer" is really a DFA then how can it process a type 0 language like C which requires handling recursive constructs (which we know a DFA cannot.) :A real computer can't necessarily process a fifty petabyte C program. Not that there is any such thing AFAIK. :User:DanielCristofani 10:04, 16 May 2005 (UTC) I think that however you slice it there is something misleading in calling a "real computer" a DFA. (an anonymous contributor) == Deleted links == The two papers on the Turing Test clearly shouldn't be here. Paterson's Worms are more of a judgement call, but the analogy is less close than in the case of Langton's Ant, and I don't know that anyone has suggested they might be Turing-complete.

---

See other meanings of words starting from letter:

T

TA | TB | TC | TD | TE | TF | TG | TH | TI | TJ | TK | TL | TŁ | TM | TN | TO | TP | TR | TS | TU | TW | TX | TY | TZ |

Words begining with Turing_machine:

Turing_Machine
Turing_machine
Turing_machine
Turing_machines
Turing_Machine_simulator

These materials are based on Wikipedia and licensed under the GNU FDL