Machines, Turing

Turing Formalized concept of computability universal turing machine... 

Finite automata such as these are the simplest kind of computational model, and are not very powerful. For example, no finite automaton can accept the set of all palindromes over some specified alphabet. They certainly do not wield, in abstract terms, the full computational power of a conventional computer. For that we need a suitable generalization of the these primitive computational models. Despite the literally hundreds of computing models that have been proposed at one time or another since the beginning of computer science, it has been found that each has been essentially equivalent to just one of four fundamental models finite automata, pushdown automata, linear bounded automata and Turing machines. 

A universal Turing machine uses an arbitrarily long tape as a potentially infinite memory storage device. Instead, for his proof, Conway used Minsky s idea that a potentially infinite memory can also be obtained by storing arbitrarily large numbers in memory registers. The idea is sketched in figure 3.85. 

Unrestricted Languages no restrictions all arbitrary productions of the form d —> 02 are allowed. Recognized by Turing Machines. 

Notice that only the last class of unrestricted languages requires a full universal computer (i.e. Turing Machine)-, the other classes require progressively simpler kinds of computers. Each one of these four automata act as a kind of black-box into which is fed a tape of symbols, sequentially, one cell at a time. During each cycle, the black-box reads the symbol at the appropriate cell, responds to that... 

A somewhat more robust measure may be defined by invoking the universal Turing machine. Let be the initial state of a computation that is designed to solve a size-N problem. If the problem is to find a solution to the Traveling-Salesman problem, for example, N would correspond to the number of cities that the salesman must visit. 

Margolus (margfiOb] generalizes Feynman s formalism - which applies to strictly serial computation - to describe deterministic parallel quantum computation in one dimension. Each row in Margolus model is a tape of a Turing Machine, and adjacent Turing Machines can communicate when their tapes arc located at the same coordinate. Extension of the formalism to more than one dimension remains an open problem. 

The Turing machine is one of the key abstractions used in modern computability theory. It is a mathematical model of a device that changes its internal state and reads from, writes on, and moves a potentially infinite tape, all in accordance with its present state. The model of the Turing machine played an important role in the conception of the modern digital computer. 

A curious mixture of Turing machines and Hermetic philosophy (especially Lull)... 

More specifically, the basic notions of a Turing Machine, of computable functions and of undecidable properties are needed for Chapter VI (Decision Problems) the definitions of recursive, primitive recursive and partial recursive functions are helpful for Section F of Chapter IV and two of the proofs in Chapter VI. The basic facts regarding regular sets, context-free languages and pushdown store automata are helpful in Chapter VIII (Monadic Recursion Schemes) and in the proof of Theorem 3.14. For Chapter V (Correctness and Program Verification) it is useful to know the basic notation and ideas of the first order predicate calculus a highly abbreviated version of this material appears as Appendix A. 

We shall see that there are several senses in which WHILE programs and WHILE schemes are universal. We first examine the "weakest" sense - the fact that WHILE programs can do everything that Turing machines can do. 

DEFINITION A set is recursively enumerable (r.e.) if and only if there is a Turing machine which when given as input a member of the set will eventually halt and give a YES answer but when given an input not in the set will either give a NO answer or fail to halt. 

A property P is partially decidable if the set a e A P holds for cal is recursively enumerable. That is, P is partially decidable if there is a Turing machine which halts and gives answer YES on input a if c has property P and... 

THEOREM 6.1 It is not partially decidable whether a Turing machine diverges on the blank initial tape. 

An infinite tape w is ultimately periodic if w = uvw. .. for finite tapes u,v with v e, i.e. if w can be written as a finite (possibly enpty) initial string u followed by arbitrarily many repetitions of a nonempty finite string v. We need the next result which relates Turing machines and two-tape acceptors with special attention to behavior on ultimately periodic input tapes. 

THEOREM 6.2 For each Turing machine T, one can construct a two-tape one-way deterministic finite state accepter Mp such that if D = (w,w) w input tape, finite or infinite ... 

This was because in our construction of Mj, from Turing machine T, we forced Hp to halt on (t,t) unless t encoded an infinite computation of T on the blank initial tape and by placing extra s in the encodement we made sure that such a tape t could never be ultimately periodic. Hence we can assume that M halts on (t,t) for t ultimately periodic. 

Statements (1), (2) and (3) declare that partial recursive function val(P,I,n) is nowhere defined it is known that it is not partially decidable whether a partial recursive function is everywhere undefined. Statement (4) says that partial recursive function val(P,I,n) is not total recursive while statements (5) and (6) say that it is total recursive neither property is partially decidable for partial recursive functions as defined by, e.g., Turing machines. 

For every Turing machine T one can construct a total recursive function g such that g(n) = n if T started on the initially balnk tape does not stop within n steps and g(n) = n + 1 if T started on the initially blank tape stops within n steps. This function is the identity if and only if T diverges on the initially blank tape. Hence it is not partially decidable whether a total recursive function computes the identity this settles (10). ... 

Just as we showed that for every Turing machine T there is a two-tape one-way deterministic finite state acceptor Mj such that T halts on the initially blank tape if and only if La(M, ) O D = , so it can be shown that far any recursively enumerable language L Q and a marker not in E, there is a deterministic two-tape one-way finite state acceptor M with input vocabulary E U, 0,1 such that ... 

---