jfjr@mbunix.mitre.org (Jerome Freedman) (01/16/89)
I have seen the phrase "turing complete" applied to
languages (PostScript etc). I know what it means but
I'd like a formal definition.
Jerry Freedman, Jr
jfjr@mbunix.mitre.org
Jerry Freedman, Jr "Why did
jfjr@mitre-bedford.arpa Unix come from the east?"
(617)271-3191 piet@ruuinf (Piet van Oostrum) (01/18/89)
In article <43638@linus.UUCP>, jfjr@mbunix (Jerome Freedman) writes:
`
` I have seen the phrase "turing complete" applied to
`languages (PostScript etc). I know what it means but
`I'd like a formal definition.
`
The most formal you can get is:
For every function that is computable by a Turing machine, there is a
program in the (said) language that computes that function.
--
Piet van Oostrum, Dept of Computer Science, University of Utrecht
Padualaan 14, P.O. Box 80.089, 3508 TB Utrecht, The Netherlands
Telephone: +31-30-531806. piet@cs.ruu.nl (mcvax!hp4nl!ruuinf!piet)bradb@ai.toronto.edu (Brad Brown) (01/20/89)
In article <988@ruuinf.UUCP> piet@ruuinf (Piet van Oostrum) writes: >In article <43638@linus.UUCP>, jfjr@mbunix (Jerome Freedman) writes: > ` > ` I have seen the phrase "turing complete" applied to > `languages (PostScript etc). I know what it means but > `I'd like a formal definition. > ` >The most formal you can get is: > >For every function that is computable by a Turing machine, there is a >program in the (said) language that computes that function. Actually the question is not dumb at all. The idea of Turing compatability is kind of subtle, but here's a try at it: Sometime in the 1930s (I think) Allan Turing formalized the notion of what it means for a computer to 'compute' something. What he did was create an ultra-simple computer that could be studied theoretically. The theoretical results could be applied to real computers because he was able to show that the Turing Machine (TM)(as his 'computer' came to be known) was capable of computing anything that a 'real' computer was and vice-versa. The TM consists of a 'tape,' which is an infinitely long tape containing symbols. The symbols may be basically anything, but usually come from a fairly small alphabet that is made up for the problem to be solved. The TM also has a 'read-write head,' which is positioned over a particular element of the tape. The read-write head is controlled by a finite-state machine (FSM) whose state is defined by the current state and the symbol on the tape under the read-write head. Associated with each state is an action, like 'write such-and-such symbol' or 'move tape head left one' and a next state that the FSM goes into. A 'program' for a Turing Machine is written by defining the set of states in the FSM. An instance of a particular problem (IE the input to the program) is given to the TM by writing a sequence of symbols corresponding to the problem on the tape and positioning the tape head at the front of the string of symbols. The TM then executes the program, which produces output by writing (more) symbols on the tape. Abstract? You bet. But, this kind of machine can be analysed formally, which makes it very important for mathematics types. Noone would EVER write a program for a Turing Machine (except for fun or marks in a complexity theory course :-) ). Now here's the important part: It can be shown that a Turing Machine can compute anything that is 'computable' (in an intuitive sense.) (Actually I think the definition of 'computability' is usually taken to mean that a function is Turing-computable.) Second, there are some problems that you can pose that cannot be computed AT ALL. (For example, I can prove to you that it is impossible to write a program that will examine any given program and decide whether it will halt or run forever.) Thirdly, 'real' computers can compute the same things as Turing machines, so the theoretical limitations on Turing machines apply to real computers, all real computers are essentially capable of computing the same things, and so on. Now, this is not to say that real computers are equivalently good at computing things. Some are faster than others, real computers can't compute absolutely everything because they have finite memories, and so on. This brings us to another important topic, polynomial equivalence, which I will ignore for the sake of brevity. Essentially, then, saying a given language (like PostScript) is Turing- equivalent is the same thing as saying that you can write PostScript programs that are capable of computing anything that a traditional language, like C or Lisp or assembly, can compute. Whew... (-: Brad Brown :-) bradb@ai.toronto.edu