quale@picard.cs.wisc.edu (Douglas E. Quale) (02/12/91)
In article <319@smds.UUCP> rh@smds.UUCP (Richard Harter) writes: >Programs which execute on real computers are not equivalent to Turing >machine programs in general. In real computers there is only a finite >amount of memory available (including memory of all types). As a direct >consequence there are only a finite number of programs that can be >executed on a real computer (the number is, however, very large) whereas >a universal Turing machine can execute an infinite number of distinct >programs. I don't think this is quite right. The original post refers to Turing equivalence of languages, not the machines that execute the programs. Any Turing program will use only a finite amount of memory (tape) at any particular time. It is easy to write a program to do this. It is true that due to the finite size of the machines on which these programs are executed some Turing programs won't run. But this is a limitation of the size of the computer on which the program is run, not the implementation language be it C, Pascal, Lisp or whatever. (Most languages definitions don't put limits on the size of programs, and neither do most formal semantics.) -- Doug Quale
rh@smds.UUCP (Richard Harter) (02/12/91)
In article <1991Feb11.164821.10486@spool.cs.wisc.edu>, quale@picard.cs.wisc.edu (Douglas E. Quale) writes: ] In article <319@smds.UUCP> rh@smds.UUCP (Richard Harter) writes: ] >Programs which execute on real computers are not equivalent to Turing ] >machine programs in general. In real computers there is only a finite ] >amount of memory available (including memory of all types).... ] I don't think this is quite right. The original post refers to Turing ] equivalence of languages, not the machines that execute the programs. The original post is based on a quote from Dan, to wit "most real languages are not equivalent to Turing machines". I would prefer to let Dan explicate what he meant by this statement. ] Any Turing program will use only a finite amount of memory (tape) at any ] particular time. It is easy to write a program to do this. ] It is true that due to the finite size of the machines on which these ] programs are executed some Turing programs won't run. But this is a ] limitation of the size of the computer on which the program is run, ] not the implementation language be it C, Pascal, Lisp or whatever. ] (Most languages definitions don't put limits on the size of programs, ] and neither do most formal semantics.) Now it quite true that one can write a universal Turing machine emulation program in most implementation languages. We all know this. However it is an intrinsic property of computers that they are not Turing machines. I.e. it is not just a matter of "a limitation of the size of the computer on which the program is run"; it is a common characteristic of all computers in the real universe that has been, that is, or that ever will be. Real computers can only run a finite number of Turing programs, a Turing machine can run an infinite number. What does this mean? Well, when we say that language X is a universal Turing machine language, what we are really saying is if a machine can be programmed in language X and if programs written in language X can access an unboundedly large amount of memory then that machine is a universal Turing machine. On the face of it, this doesn't mean much since there are no such machines. However we can go further and show that if language Y has the same property then any program written in language Y can be written in language X and vice versa. So we have established a criterion for determining the formal equivalence of languages. However there are some catches (and I hazard to guess this is what Dan had in mind). In most implementation languages there are explicit limitations in the language specifications that preclude their use as programming languages for Turing machines if you assume that the tape (i.e. memory) is addressed. The traditional Turing machine description obviates that issue by having I/O commands that reference the contents of the current position of the tape. If the memory is accessed via a pointer (or array index) and the pointer is contained in words of fixed length then the language is not universal Turing machine equivalent. On the other hand any given language may have an obscure work around, so it is not a trivial matter to say whether a particular language such as C is actually universal Turing machine equivalent. On the other hand, if we assume that the addressless commands to access the current memory cell are available then all issues of dynamic storage allocation are irrelevant -- a universal Turing machine can be written as a fixed size program with fixed memory usage. -- Richard Harter, Software Maintenance and Development Systems, Inc. Net address: jjmhome!smds!rh Phone: 508-369-7398 US Mail: SMDS Inc., PO Box 555, Concord MA 01742 This sentence no verb. This sentence short. This signature done.
lavinus@csgrad.cs.vt.edu (02/13/91)
Well, I guess I'll throw my two cents' worth into this whole Turing machine debate: A Turing machine, by definition, has an infinite tape. Therefore, no computer in existence can simulate a "real" Turing machine, dynamic allocation or not. What a real-life computer CAN simulate is a Linear Bounded Automata, i.e., a Turing machine with a finite tape. However, if one consults any Formal Languages textbook, one will find that these two machines are tremendously different in terms of computing power. For instance, only a Turing machine can run an acceptor for a recursively enumerable language (Level 0 on the Chomsky hierarchy), while the best one can to with an LBA is to parse a context-sensitive (level 1) grammar. BUT... whether or not a particular machine can implement a real-life programming language is not a function of the size of the programs that may be written in that language, but a function of the complexity of the grammer which describes that language. To date, there are no level 0 programming languages, because they're incredibly difficult to parse. So the point of all this is that any language for which a compiler can be written on a real computer can be accepted by an LBA (if you believe Church's thesis, anyway), and any language accepted by an LBA can be accepted by a Turing machine, so, assuming that Church's thesis is correct, every modern-day programming language is Turing-equivalent to every other one. Adios... Joe Lavinus -- =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= = Joseph W. Lavinus = \ / = = Virginia Tech, Blacksburg, Virginia = \/__V = = email: lavinus@csgrad.cs.vt.edu = /\ =
boyland@aspen.Berkeley.EDU (John B. Boyland) (02/14/91)
In article <926@creatures.cs.vt.edu>, lavinus@csgrad.cs.vt.edu writes: |> A Turing machine, by definition, has an infinite tape. Therefore, no computer |> in existence can simulate a "real" Turing machine, dynamic allocation or not. |> What a real-life computer CAN simulate is a Linear Bounded Automata, i.e., |> a Turing machine with a finite tape. [...] And, now, my two cents: A Turing machine during some time period t, never uses more than kt units of tape, where 'k' depends on the speed of the Turing machine. Thus in a finite time, a Turing machine always is limited within a finite section of tape. As long as the machine runs slow enough, one could splice on new reels of tape on the tape being used on a REAL machine (assuming this real machine had a bidirectional tape reader/writer). So, basically, one could run any Turing program. Of course, the operator may decide to interrupt computation (because funding is dropped, or whatever), but assuming the current model of Big Crunch, where the universe has a limited "lifetime", it is theoretically possible to build a Turing machine which never runs out of tape. John Boyland boyland@sequoia.Berkeley.EDU
smryan@garth.UUCP (Steven Ryan) (02/14/91)
>on which the program is run"; it is a common characteristic of all >computers in the real universe that has been, that is, or that ever >will be. Real computers can only run a finite number of Turing programs, >a Turing machine can run an infinite number. Wrong. I put a mirror on the back of spaceship and send off into the cosmos, bouncing a laser from my computer to ship and back again. The laser pulses to encode information. Can you deductively prove that this is not an arbitrary large but finite storage device? -- ...!uunet!ingr!apd!smryan Steven Ryan ...!{apple|pyramid}!garth!smryan 2400 Geng Road, Palo Alto, CA
norvell@csri.toronto.edu (Theo Norvell) (02/14/91)
In article <926@creatures.cs.vt.edu> lavinus@csgrad.cs.vt.edu () writes: >Well, I guess I'll throw my two cents' worth into this whole Turing machine >debate: > >A Turing machine, by definition, has an infinite tape. Therefore, no computer >in existence can simulate a "real" Turing machine, dynamic allocation or not. >What a real-life computer CAN simulate is a Linear Bounded Automata, i.e., >a Turing machine with a finite tape. What do you mean by "finite"? All tapes are always finite. It's just that Turing machine tapes grow as is needed. If you mean a constant size tape, you are talking about Finite State Automata, not LBAs.. A Linear Bounded Automaton is a Turing machine with a tape that is linear in the size of the input. I fail to see why this is any easier in principle to simulate than one that uses an amount of tape that is some other kind of finite function of the input size. In other words, why do you pick _Linear_ Bounded Automata, rather than, say, Quadratic Bounded Automata? The tricky kind of Turing machines are those that might run for ever using more and more tape. Of course this includes all universal Turing machines, but few other interesting functions. One can imagine a physical machine that just keeps asking for more and more tape (real machines do request tapes). Eventually the universe might run out of the raw materials to manufacture the tape, but by that time people will probably have lost interest in the problem. Theo Norvell
yodaiken@chelm.cs.umass.edu (victor yodaiken) (02/17/91)
In article <11077@pasteur.Berkeley.EDU> boyland@sequoia.Berkeley.EDU (John B. Boyland) writes: >In article <926@creatures.cs.vt.edu>, lavinus@csgrad.cs.vt.edu writes: >|> A Turing machine, by definition, has an infinite tape. Therefore, no >computer >|> in existence can simulate a "real" Turing machine, dynamic allocation >or not. >|> What a real-life computer CAN simulate is a Linear Bounded Automata, i.e., >|> a Turing machine with a finite tape. [...] > >And, now, my two cents: > >A Turing machine during some time period t, never uses more than kt units of >tape, where 'k' depends on the speed of the Turing machine. Thus in a finite >time, a Turing machine always is limited within a finite section of tape. >As long as the machine runs slow enough, one could splice on new reels of tape >on the tape being used on a REAL machine (assuming this real machine had a >bidirectional tape reader/writer). So, basically, one could run any Turing >program. Of course, the operator may decide to interrupt computation (because This is a time-honored argument, but requires radical redefinition of "computer". If the operation of your "computer" depends on actions of the operator, then the operator is part of the computer. I'm perfectly willing to admit that a human being combined with a finite mechanical computing device may not be a finite state machine. But, if we limit our attention to digital computing devices that occupy finite space, we are within the realm of finite state machines, not turing machines.
gessel@ilium.cs.swarthmore.edu (Daniel Mark Gessel) (02/20/91)
Many programming languages (some would say all) are "Turing Equivalent". That is, anything you can do with a Turing Machine, you can express with such a programming language. Many programs do not do all that they are cabable of on a real machine because they run out of memory, i.e. hit the limitations of the machine. REAL machines today, and probably ever, cannot run all possible programs written in a Turing Equivalent Language without restricting them in some way (i.e., a failed malloc call). One reason for using a turing equivalent language that may run out of memory on a given machine, is to have a large degree of machine independence, generally considered a valuable thing, which can use whatever resources that exist when it is running. Is the halting problem solvable then? Not for a program in such a language, but for a program in that language on a given machine. However, on a given machine, the program has "finite" power, and it is not "The Halting Problem" anymore. IMHO Dan -- Daniel Mark Gessel Internet: gessel@cs.swarthmore.edu I do not speak (nor type) representing Swarthmore College.
thornley@cs.umn.edu (David H. Thornley) (02/20/91)
In article <GESSEL.91Feb19111858@ilium.cs.swarthmore.edu> gessel@ilium.cs.swarthmore.edu (Daniel Mark Gessel) writes: >Many programming languages (some would say all) are "Turing >Equivalent". That is, anything you can do with a Turing Machine, you >can express with such a programming language. Many programs do not do all >that they are cabable of on a real machine because they run out of >memory, i.e. hit the limitations of the machine. > >REAL machines today, and probably ever, cannot run all possible programs >written in a Turing Equivalent Language without restricting them in >some way (i.e., a failed malloc call). > What "probably ever"? The Turing Machine has one or more infinite- length tapes. No real hardware has such, or will ever have such. Looked at one way, any real computer system is a deterministic finite automaton. >One reason for using a turing equivalent language that may run out of >memory on a given machine, is to have a large degree of machine >independence, generally considered a valuable thing, which can use >whatever resources that exist when it is running. > To be practical: If a language can emulate a Turing machine, it can probably handle most problems in a more efficient way than writing a Turing machine in the language. There are notable exceptions, particularly in older languages like COBOL. Treating computers as finite automata is not particularly useful. Consider the language recognized by a compiler. If you treat the computer as a finite automaton, the language recognized is a regular expression, which is, essentially, every legal program that will fit in the machine in alternation. It is far more useful to consider the computer as a Turing machine, write a suitable grammar, and to bail out if the system runs out of resources. Similarly, if you are analyzing computational complexity of an algorithm on a large DFA, all algorithms can be expressed as O(1). Machine portability is also important. The same computer with either 4MB or 8MB of RAM is (DFA) a much different machine with far more states, or (Turing) the same machine that will fail less often. >Is the halting problem solvable then? Not for a program in such a >language, but for a program in that language on a given machine. >However, on a given machine, the program has "finite" power, and it is >not "The Halting Problem" anymore. > The halting problem for a DFA is mathematically trivial: simply enumerate all possible states, and note whether they halt or not (they will either halt in the number of steps equal to all possible states, or they will loop forever). If you want something more practical, consider special hardware. Construct memory chips with two identical banks, and a readout pin indicating whether the two banks have identical contents. With a little ingenuity, you can do the same with disk banks. Construct a dual CPU that can tell if both sides have identical contents and status information. Then, load each half of the system identically, and start running with the left half running precisely half as fast as the right half. If the two are ever identical again, the program loops; if it is looping, there are strict bounds as to how far it can go before you catch it with this technique. IMHO, there is no use for these techniques. They have no theoretical importance, and I have never heard of a practical implementation. Stick with Turing equivalence. DHT
ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) (02/20/91)
In article <11077@pasteur.Berkeley.EDU>, boyland@aspen.Berkeley.EDU (John B. Boyland) writes: ... > funding is dropped, or whatever), but assuming the current model of Big Crunch, > where the universe has a limited "lifetime", it is theoretically possible to > build a Turing machine which never runs out of tape. What current model of "Big Crunch"? Unless there has been a breakthrough in the last couple of days, the Missing Matter is still missing, and the best guess is still an open universe. -- Professional programming is paranoid programming