Why turing machines are useful

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. A limitation of Turing machines is that they do not model the strengths of a particular arrangement well.

For instance, modern stored-program computers are actually instances of a more specific form of abstract machine known as the random access stored program machine or RASP machine model.

Like the Universal Turing machine the RASP stores its "program" in "memory" external to its finite-state machine's "instructions". Elgot and Robinson , Hartmanis , and in particular Cook-Rechow ; references at random access machine.

The RASP's finite-state machine is equipped with the capability for indirect addressing e. 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 binary search , an algorithm that can be shown to perform more quickly when using the RASP model of computation rather than the Turing machine model. Another limitation of Turing machines is that they do not model concurrency well.

For example, there is a bound on the size of integer that can be computed by an always-halting nondeterministic Turing machine starting on a blank tape. See article on unbounded nondeterminism. By contrast, there are always-halting concurrent systems with no inputs that can compute an integer of unbounded size.

A process can be created with local storage that is initialized with a count of 0 that concurrently sends itself both a stop and a go message. When it receives a go message, it increments its count by 1 and sends itself a go message.

When it receives a stop message, it stops with an unbounded number in its local storage. They were described in by Alan Turing. Gandy's analysis of Babbage's Analytical Engine describes the following five operations cf p. Gandy states that "the functions which can be calculated by 1 , 2 , and 4 are precisely those which are Turing computable.

With regards to Hilbert's problems posed by the famous mathematician David Hilbert in , an aspect of problem 10 had been floating about for almost 30 years before it was framed precisely. Hilbert's original expression for 10 is as follows:. By the international congress of mathematicians, Hilbert "made his questions quite precise.

First, was mathematics complete Second, was mathematics consistent And thirdly, was mathematics decidable? The problem was that an answer first required a precise definition of " definite general applicable prescription ", which Princeton professor Alonzo Church would come to call "effective calculability", and in no such definition existed. Church's paper published 15 April showed that the Entscheidungsproblem was indeed "undecidable" and beat Turing to the punch by almost a year Turing's paper submitted 28 May , published January In the meantime, Emil Post submitted a brief paper in the fall of , so Turing at least had priority over Post.

While Church refereed Turing's paper, Turing had time to study Church's paper and add an Appendix where he sketched a proof that Church's lambda-calculus and his machines would compute the same functions. And Post had only proposed a definition of calculability and criticized Church's "definition", but had proved nothing. In the spring of , Turing as a young Master's student at King's College Cambridge, UK , took on the challenge; he had been stimulated by the lectures of the logician M.

Newman used the word 'mechanical' In his obituary of Turing Newman writes:. While Gandy believed that Newman's statement above is "misleading", this opinion is not shared by all. Turing had a lifelong interest in machines: "Alan had dreamt of inventing typewriters as a boy; [his mother] Mrs. Turing had a typewriter; and he could well have begun by asking himself what was meant by calling a typewriter 'mechanical'" Hodges p. His PhD thesis, titled "Systems of Logic Based on Ordinals", contains the following definition of "a computable function":.

Arguments still continue concerning the origin and nature of what has been named by Kleene Turing's Thesis. But what Turing did prove with his computational-machine model appears in his paper On Computable Numbers, With an Application to the Entscheidungsproblem :. Turing's example his second proof : If one is to ask for a general procedure to tell us: "Does this machine ever print 0", the question is "undecidable".

In , while at Princeton working on his PhD thesis, Turing built a digital Boolean-logic multiplier from scratch, making his own electromechanical relays Hodges p. With the symbols "1 1 0" printed on the tape, let's attempt to convert the 1s to 0s and vice versa. This is called bit inversion, since 1s and 0s are bits in binary. This can be done by passing the following instructions to the Turing machine, utilising the machine's reading capabilities to decide its subsequent operations on its own.

These instructions make up a simple program. The machine will first read the symbol under the head, write a new symbol accordingly, then move the tape left or right as instructed, before repeating the read-write-move sequence again. Let's see what this program does to our tape from the previous end point of the instructions:. The current symbol under the head is 0, so we write a 1 and move the tape right by one square.

Finally, a 'blank' symbol is read, so the machine does nothing apart from read the blank symbol continuously since we have instructed it to repeat the read-write-move sequence without stopping. In fact, the program is incomplete. We will also have to make some assumptions about the configuration of the tape when the machine is started, and when it finishes, in order to interpret the computation.

Figure 3: Initial configuration for a computation over two numbers n and m. Here the supposed addition machine takes two arguments representing the numbers to be added, starting at the leftmost 1 of the first argument. A machine must finish in standard configuration too. There must be a single block of symbols a sequence of 1s representing some number or a symbol representing another kind of output and the machine must be scanning the leftmost symbol of that sequence.

If the machine correctly computes the function then this block must represent the correct answer. Adopting this convention for the terminating configuration of a Turing machine means that we can compose machines by identifying the final state of one machine with the initial state of the next. The idea of doing an addition with Turing machines when using unary representation is to shift the leftmost number n one square to the right.

A real number is Turing computable if there exists a Turing machine which computes an arbitrarily precise approximation to that number. Turing gave several examples of classes of numbers computable by Turing machines see section 10 Examples of large classes of numbers which are computable of Turing —7 as a heuristic argument showing that a wide diversity of classes of numbers can be computed by Turing machines.

One might wonder however in what sense computation with numbers, viz. Examples of such problems are:. An important challenge of both theoretical and concrete advances in computing often at the interface with other disciplines has become the problem of providing an interpretation of X such that it can be tackled computationally.

The universal Turing machine which was constructed to prove the uncomputability of certain problems, is, roughly speaking, a Turing machine that is able to compute what any other Turing machine computes. Conversely, any problem that is not computable by the universal machine is considered to be uncomputable.

This is the rhetorical and theoretical power of the universal machine concept, viz. It is also one of the main reasons why Turing has been retrospectively identified as one of the founding fathers of computer science see Section 5.

So how to construct a universal machine U out of the set of basic operations we have at our disposal? In other words, Turing develops a technique that allows to treat program and behavior on the same level. Turing —7: Thus, a first and perhaps most essential step, in the construction of U are the quintuple and complete configuration notation and the idea of putting them on the same tape. More particularly, the tape is divided into two regions which we will call the A and B region here.

To simplify the construction of U and in order to encode any Turing machine as a unique number, Turing develops a third notation which permits to express the quintuples and complete configurations with letters only. Of course, there is a broad variety of possible encodings, including binary encodings]:. This is the so-called Standard Description S. Thus, for instance, the S. Indeed, as Turing shows, one can easily get a numerical description representation or Description Number D.

This is achieved by Turing through the construction of a sequence of Turing computable problems such as:. Turing develops a notational technique, called skeleton tables , for these functions which serves as a kind of shorthand notation for a complete Turing machine table but can be easily used to construct more complicated machines from previous ones.

The technique is quite reminiscent of the recursive technique of composition see: recursive functions. To illustrate how such functions are Turing computable, we discuss one such function in more detail, viz. It is constructed on the basis of a number of other Turing computable functions which are built on top of each other. In order to understand how these functions work, remember that Turing used a system of alternating F and E -squares where the F -squares contain the actual quintuples and complete configurations and the E -squares are used as a way to mark off certain parts of the machine tape.

Turing defined nine different functions to show how the compare function can be computed with Turing machines:. Below is an outline of the universal Turing machine indicating how these basic functions indeed make possible universal computation.

It is assumed that upon initialization, U has on its tape the S. Remember that Turing uses the system of alternating F and E -squares and so, for instance, the S. The two configurations are compared. The printing and move L,R, N operations are marked with u and the next state with y. All marks z are erased. U prints the next complete configuration and erases all marks u, v, w, x, y. U first searches for the rightmost letter u , to check which move is needed R, L, N and erases the mark u for R, L, N.

The move operation L, R, N is accounted for by the particular combination of u, v, w, x, y :. This small defect was corrected by Post Post by including an additional instruction in the function used to mark the complete configuration in the next round. Since several modifications and simplifications have been implemented.

The removal of the difference between F and E -squares was already discussed in Section 1. These results are usually achieved by relying on other equivalent models of computability such as, for instance, tag systems. The same result was achieved independently by Church a, b using a different kind of formal device which is logically equivalent to a Turing machine see Sec.

The result went very much against what Hilbert had hoped to achieve with his finitary and formalist program. The true reason why Comte could not find an unsolvable problem, lies in my opinion in the assertion that there exists no unsolvable problem.

Instead of the stupid Ignorabimus, our solution should be: We must know. We shall know. Note that the solvability Hilbert is referring to here concerns solvability of mathematical problems in general and not just mechanically solvable.

It is shown however in Mancosu et al. There are two main methods:. The notion of reducibility has its origins in the work of Turing and Post who considered several variants of computability Post ; Turing The concept was later appropriated in the context of computational complexity theory and is today one of the basic concepts of both computability and computational complexity theory Odifreddi ; Sipser First of all, one needs a formalism which captures the notion of computability.

Turing proposed the Turing machine formalism to this end. A second step is to show that there are problems that are not computable within the formalism. To achieve this, a uniform process U needs to be set-up relative to the formalism which is able to compute every computable number. One can then use some form of diagonalization in combination with U to derive a contradiction. Such machines were identified by Turing as circle-free.

All other machines are called circular machines. A number n which is the D. The problem to decide for every number n whether or not it is satisfactory. The proof of the uncomputability of CIRC? Hence, it relies for its construction on the universal Turing machine and a hypothetical machine that is able to decide CIRC? Based on the uncomputability of CIRC? Turing shows that the Entscheidungsproblem is not decidable. This is achieved by showing:. Sign up to join this community.

The best answers are voted up and rise to the top. Stack Overflow for Teams — Collaborate and share knowledge with a private group. Create a free Team What is Teams? Learn more. Are Turing machines still useful as model of computation?

Ask Question. Asked 2 years, 7 months ago. Active 2 years, 7 months ago. Viewed times. Improve this question. Mark S. Mark S Mark S 5 5 silver badges 17 17 bronze badges. They're quite finite. But more generally, it sounds like your question is more akin to "do we really need set theory, to begin with? It's not necessary on a daily basis, and you can forget about them most of the time; but there needs to be a common, agreed-upon, sound foundation Of course the formalism of set theory is worth it!

Of course formalizing computation is worth it.