gudeman@cs.arizona.edu (David Gudeman) (05/09/91)
(I didn't want to go to this much work, but no one else has pointed
this out, so here goes.)
There seems to be a misconception floating around: that the reason the
halting problem is unsolvable is because there are an infinite number
of possible states in a TM. That is not the reason. There are
theoretical machines that can solve the halting problem for a TM --
machines that can do an infinite amount of work in finite time. The
_unsolvable_ halting problem is the problem of writing a TM that can
take the encoding of any other TM and tell whether that TM will halt.
The classic proof that this is unsolvable does not rely on the
infinite number of available states, it just generates a paradox based
on the assumption that the halting problem is solvable. The same
paradox can be generated for _any_ class of machines meeting certain
very innocuous criteria.
Let C be any class of machines. An input to C is a string over the
alphabet Sigma (that is, an element of Sigma*). An encoding of
C-machines is a total one-to-one function E:C->Sigma from C-machines
to inputs. If M is a C-machine and S is an input, then you can run C
on S: if the computation terminates then it ends in either an
accepting or a rejecting state.
If you have three C-machines M1, M2 and M3 you can form a compound
machine M1->M2;M3 with the behavior that if M1 terminates in an
accepting state then M2 is executed on the remainder of the input, and
if it terminates in a rejecting state then M3 is executed on the
remainder of the input. If you have a C-machine M and an input S,
then M::S is the machine that always behaves exactly as M would behave
if run on S. The machine CLoop is a C-machine that never halts,
CAccept is a C-machine that halts immediately and accepts.
Theorem: For any class of machines C over inputs Sigma* such that
(1) there exists an encoding E from Sigma* to C,
(2) M1->M2;M3 and M::S are defined,
and (3) CLoop and CAccept are defined,
it is impossible to construct a C-machine Halt that for all C-machines
M: (a) halts on E(M), (b) accepts E(M) if M terminates and (c) rejects
E(M) if M does not terminate.
Proof: Suppose that Halt exists. Then define
Paradox = (Halt::E(Paradox)) -> CLoop ; CAccept
what is the result of running Paradox?
Computer programs certainly meet the 3 criteria in the theorem, so it
is not possible to write a computer program that solves the halting
problem for computer programs.
However, this is a theoretical result much like the theory that you
can't go faster than light. The fact that there is a speed we can't
reach does not make it worthless to work on vehicles that go faster.
In the same way, just because it is impossible to solve the halting
problem with a program that always answers correctly, that does not
mean that we can't work on a program that always answers "yes", "no",
or "I can't tell". And a lot can be done in that area.
--
David Gudeman
gudeman@cs.arizona.edu
noao!arizona!gudemandbae@s1.msi.umn.edu (David Epstein) (05/09/91)
This is an interesting discussion, and I have learned a lot from it. There are quite a few subtle points that I had not realized before. gudeman@cs.arizona.edu (David Gudeman) writes: >If you have three C-machines M1, M2 and M3 you can form a compound >machine M1->M2;M3 with the behavior that if M1 terminates in an >accepting state then M2 is executed on the remainder of the input, and >if it terminates in a rejecting state then M3 is executed on the >remainder of the input. ....[ stuff deleted ] ..... >Computer programs certainly meet the 3 criteria in the theorem, so it >is not possible to write a computer program that solves the halting >problem for computer programs. The problem here is that if you are dealing with a specific machine, with one particular piece of hardware, then the description of M1 may fill up the machine, and likewise with M2 and M3. In that case you may very well have no room to store the description of M1->M2;M3. I think this is Victor Yodaiken's point, or at least one of them. It's no use saying you will put the description on tape because that can get too large as well. If the number of tapes is larger than the memory of the computer you will almost certainly be in trouble. The discussion is quite difficult, because on the one hand we are working with abstract constructs and mathematical proofs, and on the other hand with practical computers. To relate the two, we make a mathematical model of the computer. But mathematical models are never fully accurate descriptions. For example, I never have to call out an engineer to fix my finite state automaton :-). And I don't have to worry about the effect of gamma rays on it, nor about how the end of the universe may affect it. We have therefore to choose, from among various possible mathematical models, not the model which *IS* the computer, but the model which most faithfully follows the particular behaviour we are trying to investigate. This is a matter of judgement, not of irrefutable logic, and is likely to depend on which kind of behaviour of the practical computer one is interested in. If you are interested in error correction in hardware, your mathematical model is not going to be a finite state automaton, because that never makes errors. >Proof: Suppose that Halt exists. Then define > Paradox = (Halt::E(Paradox)) -> CLoop ; CAccept >what is the result of running Paradox? Is this a misprint, David? You can't define Paradox in terms of itself. If it is a misprint, can you please repost, as I would like to study this. David Epstein.
new@ee.udel.edu (Darren New) (05/10/91)
In article <1991May9.122526.13533@s1.msi.umn.edu> dbae@s1.msi.umn.edu (David Epstein) writes: >>Proof: Suppose that Halt exists. Then define >> Paradox = (Halt::E(Paradox)) -> CLoop ; CAccept >>what is the result of running Paradox? > >Is this a misprint, David? You can't define Paradox in terms of >itself. If it is a misprint, can you please repost, as I would like to >study this. Paradox is not really defined in terms of itself in a recursive-call sense. E(Paradox) is the "source code" for the program Paradox. If you know how Halt, CLoop, and CAccept are written, then you know how Paradox is written (see the >> lines :-). Feed the Paradox program to Halt, and if Halt says it halts then loop, otherwise halt. Paradox never explicity calls itself (altho Halt might "call" Paradox in some way, in which case Halt doesn't halt and thus gives a "wrong" answer). -- --- Darren New --- Grad Student --- CIS --- Univ. of Delaware --- ----- Network Protocols, Graphics, Programming Languages, FDTs ----- +=+ Nails work better than screws, when both are driven with hammers +=+
gudeman@cs.arizona.edu (David Gudeman) (05/10/91)
In article <1991May9.122526.13533@s1.msi.umn.edu> David Epstein writes:
]
]>Proof: Suppose that Halt exists. Then define
]> Paradox = (Halt::E(Paradox)) -> CLoop ; CAccept
]>what is the result of running Paradox?
]
]Is this a misprint, David? You can't define Paradox in terms of
]itself.
It was sort of a misprint, I guess I should have asked about the
behavior of Halt::E(Paradox). But the definition of Paradox is OK.
E(Paradox) is a representation of Paradox in the input language so I'm
defining Paradox in terms of a representation of itself. This is
certainly possible on a real computer, since you can have the program
Paradox open the file that contains its own source code and read it.
Incidentally, I'm not happy with the conditions I stated for the
theorem since some of them should be assumptions about all classes of
automata. The existence of an encoding E seems to apply for any
alphabet with two or more characters as long as C is a countable set.
It seems that the existence of 'CAccept' and 'M1->M2;M3' are immediate
consequences of the definition of an automaton (I obviously didn't
give a full definition), and I'm also inclined to believe that 'M::S'
is a consequence of the definition an automaton.
--
David Gudeman
gudeman@cs.arizona.edu
noao!arizona!gudemananw@maths.nott.ac.uk (Dr A. N. Walker) (05/10/91)
In article <2990@optima.cs.arizona.edu> gudeman@cs.arizona.edu (David Gudeman) writes: >(I didn't want to go to this much work, but no one else has pointed >this out, so here goes.) I was intending to, but news takes *ages* to get here, so I was too late .... Anyway, I think I still have something to say. As David says, the halting problem really isn't a problem of large machines. I like to think in more concrete terms than these abstract machines with inputs over Sigma and so on, so here is the same argument more concretely. Suppose you write a [purported] halting problem solver. I'll assume it's in C, so you have a program source called, say, "fred.c", which compiles into a binary program "fred", running under Unix. The idea is that you call $ fred jim.c and the computer clunks away for a while, and then prints out "Halts" if "jim.c" describes a program that eventually halts, and prints out "Loops" if the program would run for ever. Let us assume that the structure of "fred.c" is such that it computes away for a while, but eventually must run through a final chunk of code that looks like: if (halt) printf ("Halts\n"); else printf ("Loops\n"); exit (0); I now subvert "fred" by writing a new program whose source is "bert.c", identical with "fred.c" except that the above chunk is replaced by if (halt) while (1); /* ie, loop forever */ else exit (0); Now, whenever "fred" would print "Halts", "bert" will loop forever, and whenever it prints "Loops", "bert" stops. What does "bert bert.c" do? It stops if "fred bert.c" would print "Loops", and goes on forever if "fred bert.c" would print "Halts". So, "fred bert.c" cannot tell the truth. There are three ways out of this: (a) "fred" can lie [but then it's not much use]; (b) "fred" can go on for ever without printing anything [that's not much use either!]; (c) "fred" can admit, after a while, that it cannot tell, and give up. Note, however, that, in any sensible implementation, "bert" is, if anything, rather simpler than "fred". The conclusion is that the best we can hope for from a "halting problem program" is for it to be able to analyse simple programs, but that anything complicated will be beyond it. In particular, it cannot be powerful enough to introspect itself. [Finding and curing the bugs in the above argument is left as an exercise for the reader.] As David says, there is nothing particularly "large" in this sort of argument. The best source I know for all this material is *still* Minsky's "Computation: Finite and Infinite Machines", which is now terribly out of date, but is brilliantly written. A new edition would be a delight. -- Andy Walker, Maths Dept., Nott'm Univ., UK. anw@maths.nott.ac.uk
dhesi%cirrusl@oliveb.ATC.olivetti.com (Rahul Dhesi) (05/11/91)
In <1991May10.155454.2239@maths.nott.ac.uk> anw@maths.nott.ac.uk (Dr A. N. Walker) writes: >Suppose you write a [purported] halting problem solver. I'll >assume it's in C, so you have a program source called, say, "fred.c", >which compiles into a binary program "fred", running under Unix. The >idea is that you call > $ fred jim.c Suppose jim.c halts when given certain inputs and does not halt when given certain other inputs. The halting problem in this case has not been correctly defined, since the command line "fred jim.c" does not specify the inputs given to jim.c. We we really ought to be saying % fred jim.c fred.c where jim.c is the program whose halting characteristics are being tested, and fred.c is the input that jim.c will be assumed to read when it executes. -- Rahul Dhesi <dhesi@cirrus.COM> UUCP: oliveb!cirrusl!dhesi
kwalker@cs.arizona.edu (Kenneth Walker) (05/11/91)
For the moment, lets assume our analysis routine manages to place a bound
on the number of states (size of memory) that will exist in the compiled
program and that the analysis program must itself execute within the same
finite-state machine. Because the analysis routine must itself be coded
in some of the states, it does not have enough states to represent the
states of the program it is analysing. Is there any hope (in a theoretical
sense) of a finite state machine computing interesting properties of
an arbitrary finite state machine of its own size?
Ken Walker / Computer Science Dept / Univ of Arizona / Tucson, AZ 85721
+1 602 621-4252 kwalker@cs.arizona.edu {uunet|allegra|noao}!arizona!kwalkertruesdel@nas.nasa.gov (David A. Truesdell) (05/11/91)
dhesi%cirrusl@oliveb.ATC.olivetti.com (Rahul Dhesi) writes: >In <1991May10.155454.2239@maths.nott.ac.uk> anw@maths.nott.ac.uk (Dr A. >N. Walker) writes: >>Suppose you write a [purported] halting problem solver. I'll >>assume it's in C, so you have a program source called, say, "fred.c", >>which compiles into a binary program "fred", running under Unix. The >>idea is that you call >> $ fred jim.c >Suppose jim.c halts when given certain inputs and does not halt when >given certain other inputs. The halting problem in this case has not >been correctly defined, since the command line "fred jim.c" does not >specify the inputs given to jim.c. We we really ought to be saying > % fred jim.c fred.c >where jim.c is the program whose halting characteristics are being >tested, and fred.c is the input that jim.c will be assumed to read when >it executes. And therein lies the madness: The next step is: % fred jim.c fred.c jim.c Then: % fred jim.c fred.c jim.c fred.c Then: % fred jim.c fred.c jim.c fred.c jim.c ... And so on. Thus, the "run it, and see if it halts" suggestion falls flat on its face. There is at least one problem which would take an infinite amount of time and resources to set up, much less attempt to run. -- T.T.F.N., dave truesdell (truesdel@nas.nasa.gov) 'And Ritchie said, "Let there be portability!" And nothing happened, so Ritchie realized that he had his work cut out for him.'
rockwell@socrates.umd.edu (Raul Rockwell) (05/11/91)
Kenneth Walker: Is there any hope (in a theoretical sense) of a finite state machine computing interesting properties of an arbitrary finite state machine of its own size? I don't think this is an interesting question. :-) An interesting question would be: what properties should a computation device have such that most practical programs can be determined to halt. This is related to proving a program correct. I should note that functional languages seem to be rather promising in this regard. Raul Rockwell
anw@maths.nott.ac.uk (Dr A. N. Walker) (05/14/91)
In article <truesdel.673916303@sun418> truesdel@nas.nasa.gov (David A. Truesdell) writes: >dhesi%cirrusl@oliveb.ATC.olivetti.com (Rahul Dhesi) writes: >>Suppose jim.c halts when given certain inputs and does not halt when >>given certain other inputs. The halting problem in this case has not >>been correctly defined, since the command line "fred jim.c" does not >>specify the inputs given to jim.c. Quite right, but the distinction is uninteresting, because all interesting [:-)] variants of the halting problem are equally insoluble. E.g., it is generally undecidable whether "jim.c" halts when given *no* input, when given *specified* input, when given *some* input or when given *any* input. In my original submission, I carefully left all this to the reader! >> We we really ought to be saying >> % fred jim.c fred.c > >And therein lies the madness: >The next step is: > > % fred jim.c fred.c jim.c > >Then: > > % fred jim.c fred.c jim.c fred.c > >Then: Then you define "fred" to [attempt to] determine whether its parameter halts or loops *when given itself* as input, and the paradox comes back and bites you again without Rahul's objection. See Minsky, op previously cit, for a full discussion. -- Andy Walker, Maths Dept., Nott'm Univ., UK. anw@maths.nott.ac.uk
yodaiken@chelm.cs.umass.edu (victor yodaiken) (05/14/91)
In article <3069@optima.cs.arizona.edu> kwalker@cs.arizona.edu (Kenneth Walker) writes: > >For the moment, lets assume our analysis routine manages to place a bound >on the number of states (size of memory) that will exist in the compiled >program and that the analysis program must itself execute within the same >finite-state machine. Because the analysis routine must itself be coded >in some of the states, it does not have enough states to represent the >states of the program it is analysing. Is there any hope (in a theoretical >sense) of a finite state machine computing interesting properties of >an arbitrary finite state machine of its own size? > No. But, a finite machine of size X can solve the halting problem for finite machines of size Y, supposing that Y is sufficiently smaller than X. In practical terms, this means a cross-compiler on a CRAY might be able to detect failure to halt in programs being compiled for a small micro. But, the exact ratio between X and Y depends on your ingenuity,the programming language, and the class of programs you find interesting.
quale@saavik.cs.wisc.edu (Douglas E. Quale) (05/15/91)
An earlier poster said that thinking of computers as analog devices is not a very useful view of computation. This is true. The problem is that the operation of a real computer is not the same as our abstract notion of computation. When considering real machines at lower and lower levels of abstraction eventually statistics enters in and we lose determinacy. In arguing that an FSM is a more appropriate abstraction than a TM for modelling execution of a program on a real computer, three points come to mind: 1) Undoubtedly sometimes an FSM is more appropriate, but 2) The FSM view ties us to a particular machine. I don't think this is a very useful view of computation. :-) Generally we want our programs to behave similarly on different machines. I want to say "This program will terminate with result foo or with an error condition if not enough memory is available." I don't want to say "This program will terminate with result foo if run on a small enough machine but I don't know what it will do otherwise." 3) When considering termination, an FSM has only two posssible behaviors on any given input: termination or infinite loop. A TM can terminate or it can fail to terminate either by entering an infinite loop or by simply running forever never repeating any earlier state. Since most programming languages do not specify that they must be run on a finite machine we can consider these programs as FSMs on a finite machine or as TMs on an infinite machine. Now, the 64K question is: * What useful programs terminate as FSMs and fail to terminate as TMs? The most obvious example is a memory testing program, but I think that nearly all programs that terminate only on FSMs are bugged or useless. It would be very interesting, however, to have you folks think up a bunch of useful programs to prove me wrong. In general it seems to me that having to resort to finiteness of the machine to prove termination is a sign that something is wrong (unless we are considering the memory test). (In an earlier post I referred to the Goldbach Conjecture as the Goldbach hypothesis. My apology for the blunder.) If the halting problem were solvable, then it could be used to decide any mathematical problem involving only a countably infinite number of test cases. In addition to Fermat's Last Theorem, the Riemann Hypothesis and Goldbach's Conjecture, I'd like to know whether or not there are any odd perfect numbers.... -- Doug Quale quale@saavik.cs.wisc.edu
yodaiken@chelm.cs.umass.edu (victor yodaiken) (05/16/91)
In article <1991May15.145359.20719@daffy.cs.wisc.edu> quale@saavik.cs.wisc.edu (Douglas E. Quale) writes: >2) The FSM view ties us to a particular machine. I don't think this is a > very useful view of computation. :-) Generally we want our programs > to behave similarly on different machines. I want to say "This program > will terminate with result foo or with an error condition if not enough > memory is available." I don't want to say "This program will terminate > with result foo if run on a small enough machine but I don't know what > it will do otherwise." I don't understand your reasoning here. Knowing that the state machine has a bounded number of states does not commit us to exactly what that number is. >* What useful programs terminate as FSMs and fail to terminate as TMs? Here are some programs that differ in interesting ways on FSMs and TMs while(true){ print(i), i = i+1 } loops or dies on a FSM, runs without repeating state on a TM input i while(i is not prime) i = i+1; print (i) > finds the next prime greater than i on a TM, but has more complex behavior on a FSM n = m*m does the multiplication on a TM, may compute m*m MOD k on a FSM i = 1 while(i != 0) i = i+ 1 terminates with most definitions of FSM arithmetic, does not terminate on a TM. Correct programs on real machines must respect that inherent limitations of digital computing devices. While it is sometimes convenient to act as if we were writing programs within an unbounded domain, e.g. as if "i" could indeed range over the integers, this is only a convenience when it does not lead to errors.
quale@saavik.cs.wisc.edu (Douglas E. Quale) (05/16/91)
In article <30581@dime.cs.umass.edu> yodaiken@chelm.cs.umass.edu (victor yodaiken) writes: >In article <1991May15.145359.20719@daffy.cs.wisc.edu> quale@saavik.cs.wisc.edu (Douglas E. Quale) writes: >>2) The FSM view ties us to a particular machine. I don't think this is a >> very useful view of computation. :-) Generally we want our programs >> to behave similarly on different machines. I want to say "This program >> will terminate with result foo or with an error condition if not enough >> memory is available." I don't want to say "This program will terminate >> with result foo if run on a small enough machine but I don't know what >> it will do otherwise." > >I don't understand your reasoning here. Knowing that the state machine >has a bounded number of states does not commit us to exactly what that >number is. > Yes, but why do you want to write programs whose behavior depends on how large a machine they are run on? The behavior of your programs cannot be determined without knowing exactly what that number is. >>* What useful programs terminate as FSMs and fail to terminate as TMs? > >Here are some programs that differ in interesting ways on FSMs and TMs > >while(true){ print(i), i = i+1 } > > loops or dies on a FSM, runs without repeating state on a TM > > >i = 1 >while(i != 0) i = i+ 1 > > terminates with most definitions of FSM arithmetic, > does not terminate on a TM. > > > >Correct programs on real machines must respect that inherent limitations of >digital computing devices. While it is sometimes convenient to act as >if we were writing programs within an unbounded domain, e.g. as if >"i" could indeed range over the integers, this is only a convenience >when it does not lead to errors. These programs are excellent examples because neither one is in the slightest bit interesting. Explain to me what useful programs contain either of those fragments. They look like bugs to me, unless you really want an integer overflow or infinite loop with undefined results. The same remark applies to the other fragments you gave. The question remains: What program has an interesting result on an FSM and fails to halt on a TM. It's important to remember that an TM program and input that terminates will use only a finite amount of tape. If we restrict our attention to TMs that terminate, we will have a class that could be run on real machines, modulo space requirements. (A TM isn't meant to model resource usage, but an FSM is a pretty poor model for that purpose as well.) The problem is that we have no way to know whether a given TM halts. To be safe, I would limit myself to TMs that I could prove to halt, but we are forever undecided.... -- Doug Quale quale@cs.wisc.edu
quale@saavik.cs.wisc.edu (Douglas E. Quale) (05/16/91)
In article <30581@dime.cs.umass.edu> yodaiken@chelm.cs.umass.edu (victor yodaiken) writes: >In article <1991May15.145359.20719@daffy.cs.wisc.edu> quale@saavik.cs.wisc.edu (Douglas E. Quale) writes: >>2) The FSM view ties us to a particular machine. I don't think this is a >> very useful view of computation. :-) Generally we want our programs >> to behave similarly on different machines. I want to say "This program >> will terminate with result foo or with an error condition if not enough >> memory is available." I don't want to say "This program will terminate >> with result foo if run on a small enough machine but I don't know what >> it will do otherwise." > >I don't understand your reasoning here. Knowing that the state machine >has a bounded number of states does not commit us to exactly what that >number is. > Yes, but why do you want to write programs whose behavior depends on how large a machine they are run on? The behavior of your programs cannot be determined without knowing exactly what that number is. It is rather difficult to say much about a program when its behavior is different on nearly every machine. >>* What useful programs terminate as FSMs and fail to terminate as TMs? > >Here are some programs that differ in interesting ways on FSMs and TMs > >while(true){ print(i), i = i+1 } > > loops or dies on a FSM, runs without repeating state on a TM > > >i = 1 >while(i != 0) i = i+ 1 > > terminates with most definitions of FSM arithmetic, > does not terminate on a TM. > > > >Correct programs on real machines must respect that inherent limitations of >digital computing devices. While it is sometimes convenient to act as >if we were writing programs within an unbounded domain, e.g. as if >"i" could indeed range over the integers, this is only a convenience >when it does not lead to errors. These programs are excellent examples because neither one is in the slightest bit interesting. Explain to me what useful programs contain either of those fragments. They look like bugs to me, unless you really want an integer overflow or infinite loop with undefined results. The same remark applies to the other fragments you gave. The question remains: What program has an interesting result on an FSM and fails to halt on a TM. It's important to remember that an TM program and input that terminates will use only a finite amount of tape. If we restrict our attention to TMs that terminate, we will have a class that could be run on real machines, modulo space requirements. (A TM isn't meant to model resource usage, but an FSM is a pretty poor model for that purpose as well.) The problem is that we have no way to know whether a given TM halts. To be safe, I would limit myself to TMs that I could prove to halt, but we are forever undecided.... -- Doug Quale quale@saavik.cs.wisc.edu
sw@smds.UUCP (Stephen E. Witham) (05/17/91)
In article <1991May15.145359.20719@daffy.cs.wisc.edu>, quale@saavik.cs.wisc.edu (Douglas E. Quale) writes: > 2) The FSM [finite state machine] view ties us to a particular machine. > I don't think this is a very useful view of computation. :-) When people say (and they really do!), "This algorithm needs space O(n)," it seems to me they're working with a model of "arbitrarily large FSMs." You can map FSMs to each other, and arrange them by memory capacity. That's a class to which all real computers belong. You can prove things like... o This program will finish on an FSM of size X. (Maximum size needed). o This program may crash on an FSM of size < X. (Minimum size needed). o This program may run forever on any FSM. (No limit to size needed). (where you may relate X to some function of the input). Oh, also, you can do the same with time limits. So, the version of the halting problem you can definitely solve (given enough time on a big enough computer) is, given some ridiculously large amounts of memory and time, will this program halt? Sounds useful to me. But solving the halting problem for programs already written is silly. I forget--how did we all get on the subject? --Steve Witham, sw@smds.UUCP Not-the-fault-of: SMDS, Inc., Concord, MA
sw@smds.UUCP (Stephen E. Witham) (05/17/91)
In article <30581@dime.cs.umass.edu>, yodaiken@chelm.cs.umass.edu (victor yodaiken) writes: > [some reasonable stuff...] > > n = m*m > does the multiplication on a TM, may compute m*m MOD k > on a FSM If so, it's because of the compiler, not the machine itself. You can compile a program for a regular computer so that the program either computes to whatever precision is needed, or quits. So there are two issues you're mixing here: 1) What if the compiler in one machine thinks arithmetic is to be done modulo some word size? I.e., what if different compilers interpret the same program TEXT differently, resulting in DIFFERENT PROGRAMS, and 2) What if you know that all your compilers agree exactly on the meaning of the text, so all your computers are running the SAME PROGRAM, but some of them can't keep running it if it needs too much memory? As far as the halting problem per se, on FSMs per se, only question 2 makes much sense. > [...more examples, some reasonable...] > > Correct programs on real machines must respect that inherent limitations of > digital computing devices. While it is sometimes convenient to act as > if we were writing programs within an unbounded domain, e.g. as if > "i" could indeed range over the integers, this is only a convenience > when it does not lead to errors. Fixed-size representations of numbers are not an inherent limitation of computers! They are just a convenience, too. Thinking that integer variables behave like integers only leads to errors IF you're using a compiler (or a method of programming) that doesn't treat them that way. You are obviously aware of the limits of correctness in the programming context you're used to, but you seem almost unaware that there are other ways of doing things (and I do mean with real computers). Snap out of it, guy! Was it a momentary lapse, or are the limits of your thinking really so tied to convention? --Steve Witham, sw@smds.UUCP Not-the-fault-of: SMDS, Inc., Concord, MA
yodaiken@chelm.cs.umass.edu (victor yodaiken) (05/19/91)
In article <472@smds.UUCP> sw@smds.UUCP (Stephen E. Witham) writes: >In article <30581@dime.cs.umass.edu>, yodaiken@chelm.cs.umass.edu (victor yodaiken) writes: >> [some reasonable stuff...] >> >> n = m*m >> does the multiplication on a TM, may compute m*m MOD k >> on a FSM > >If so, it's because of the compiler, not the machine itself. >You can compile a program for a regular computer so that the program >either computes to whatever precision is needed, or quits. Of course, you are correct, but the point stands. If we have TM machine representable integers, m*n means something different than m*n does on an actual computer. [Fixed size representations are not necessarily the only reps] >computers! They are just a convenience, too. Thinking that integer >variables behave like integers only leads to errors IF you're using a >compiler (or a method of programming) that doesn't treat them that way. > Still, even variable sized representations of integers are not integers. I think that you are pointing out that the identification of "int" with "representable in one machine word" is often error causing. If so I agree. And, it is also true that compilers can generate "ints" that will cause the program to quit (or take an execption) if forced beyond machine representation bounds. But, integers != machine representation of integers. >Snap out of it, guy! Was it a momentary lapse, or are the limits of your >thinking really so tied to convention? > Probably.
anw@maths.nott.ac.uk (Dr A. N. Walker) (05/21/91)
In article <1991May15.145359.20719@daffy.cs.wisc.edu> quale@saavik.cs.wisc.edu (Douglas E. Quale) writes: >3) When considering termination, an FSM has only two posssible behaviors > on any given input: termination or infinite loop. Um. If by "infinite loop" you mean "non-termination", yes, but not very revealing. Otherwise, no. Consider, for example, an input consisting of the digits of pi, and consider the FSM that moves into state N on reading the digit "N". That will not terminate, and because pi is irrational it cannot "loop" either. For one that *may* terminate, consider an FSM that sits there looking for the sequence "12345678924680" [which I just made up]. I guess that will terminate, but I'm not sure; if it doesn't then it's quite possible that states will repeat in some perhaps regular pattern [depending on the program], but that's not quite what one really means by looping either. Of course, if the input is *generated* by an FSM, then you may be able to prove something; but once you link up two FSMs with each able to read the output of the other, you get TM capability. >* What useful programs terminate as FSMs and fail to terminate as TMs? The trouble is that few "useful" programs work on FSMs. FSMs cannot multiply arbitrary integers, cannot match brackets, etc. In real life they do these things quite well, purely because the real-life integers we want to multiply and the real-life programs whose brackets we want to match fit adequately into real-life computers. But do people want the theory or the practice? You can reasonably ask for either. We get into difficulties when trying to mix both together, especially when contributors assume that because a TM is not an FSM it *must* be infinite. It merely needs to be big enough. -- Andy Walker, Maths Dept., Nott'm Univ., UK. anw@maths.nott.ac.uk
rockwell@socrates.umd.edu (Raul Rockwell) (05/21/91)
Andy Walker: Consider, for example, an input consisting of the digits of pi, and consider the FSM that moves into state N on reading the digit "N". That will not terminate, and because pi is irrational it cannot "loop" either. It's not a finite state machine either, because it has too many states. ... but once you link up two FSMs with each able to read the output of the other, you get TM capability. No, a turing machine has the ability to "create" a new FSM on the fly (in state 0). In fact, it has the ability to create an infinite number of FSMs (given infinite time). The trouble is that few "useful" programs work on FSMs. FSMs cannot multiply arbitrary integers, cannot match brackets, etc. No, but they can multiply bounded integers, and they can match brackets in bounded strings. By placing the bounds conveniently high they can be considered transparent for most applications. In real life they do these things quite well, purely because the real-life integers we want to multiply and the real-life programs whose brackets we want to match fit adequately into real-life computers. Exactly. In real life, the integers (and string lengths) are not arbitrary. By the way, a classic example of the problems involved in a solution which takes infinite time is the following "algorithm" for a turing machine: Find the first non-zero cell on a tape by scanning left till you hit a non-zero cell. If this does not terminate, scan right till you hit a non-zero cell. The tape provided is arbitrary. But the turing machine doesn't have a method for determining if a given algorithm will terminate. You could set up the TM to scan both directions, and halt when it finds the first non-zero cell that's close to the starting point, but you can't even use that result to run the above algorithm (because you still wouldn't know if the tape on the left had a non-zero cell). *lecture off* Raul Rockwell
sw@smds.UUCP (Stephen E. Witham) (05/21/91)
In article <30739@dime.cs.umass.edu>, yodaiken@chelm.cs.umass.edu (victor yodaiken) writes: > > Of course, you are correct, but the point stands. If we have > TM machine representable integers, m*n means something different than > m*n does on an actual computer. > [...] > Still, even variable sized representations of integers are not integers. > I think that you are pointing out that the identification of "int" with > "representable in one machine word" is often error causing. If so I agree. Using either of the methods you and I mentioned, you can write a program, or compile it, so that your "ints" always act exactly like integers, but sometimes the program can't go on. Then the ONLY difference between m*n on two machines is that on some (imaginary, infinite) machines, you don't have to say "if possible." Knowing that a program will either do exactly the right thing, or quit, is a useful kind of property for a program to have when you want to prove things about it. In fact, you should insist on it. If you're trying to prove things about programs, then you're really starting off on the wrong foot if you let your compiler decide the meaning of your programs for you. You should decide what you want a program to do, THEN figure out how to write it for the machine(s) and compiler(s) you've got. Only then can you compare the behavior of (nearly) equivalent programs on different machines. A program that has ints falling off the ends of their ranges at machine-dependent places is probably just WRONG, and not worth proving much else about. The reason for the length of this post is that I'm trying to argue against a vague target: the attitude that computers doing almost but not quite what they are supposed to do is a fact of life that we should all accept and learn to live with. Don't think that way! Don't take compromise and approximation for granted! The way you spoke of "inherent limitations" of computers was getting close to cybercrud: pulling things over on people (or yourself) using conventional notions of computers. --Steve Witham, sw@smds.UUCP Not-the-fault-of: SMDS, Inc., Concord, MA