berger@aecom.UUCP (Micha Berger) (01/10/86)
There exists a proof that a computer procedure cannot be written
such that given a procedure as input, it can tell you if that procedure
contains an infinite loop. In other words, there does not exist a procedure
halt that returns TRUE if the input procedure does not contain an
endless loop, and FALSE otherwise. For, if such a procedure existed, we
could set up a paradox:
PROCEDURE PARADOX:
IF HALT(PARADOX) THEN PARADOX
Or, if the routine doesn't contain an endless loop, it will go
on in an infinite recursion.
The human mind, on the other hand, given enough time an
practice, can find an endless loop in any procedure. (You doubt this?)
After going through any loop several times, it can usually hit me,
"HEY! There is no time I'm ever get out of this loop!" (Take for
example the fact that you probably saw the paradox of procedure PARADOX.)
This would mean that there is a set of problems no procedure
can ever do, yet the human mind does. The root of them is at the fact
that the human brain has meta-cognizance (I can realize, "Hey! This
loop is taking me no-where.") Or, that the root of intelligence
can not be duplicated by machine.
Okay, thats the arguement. Well.... Where's the flames?
michabvictor@klipper.UUCP (L. Victor Allis) (01/12/86)
In article <2175@aecom.UUCP> berger@aecom.UUCP (Micha Berger) writes: > The human mind, on the other hand, given enough time an >practice, can find an endless loop in any procedure. (You doubt this?) Try this one. I am very interested in a termination proof of the procedurecall Fermat(1, 1, 1, 1) : procedure Fermat(x, y, z, n : integer); begin if power(x, n) + power(y, n) = power(z, n) then writeln('Eureka') else begin repeat AssignNextValues(x, y, z, n) until n > 2; Fermat(x, y, z, n) end end; where 'power' is a function returning the obvious, and AssignNextValues is a function which takes four parameters and assigns the next four values to these parameters with respect to some ordering of the set of all ordered 4-tupels of natural numbers, which has a smallest element, (1, 1, 1, 1) in that ordering. L. Victor Allis Free University of Amsterdam The Netherlands.
wiener@idacrd.UUCP (Matthew P Wiener) (01/12/86)
> > There exists a proof that a computer procedure cannot be written > such that given a procedure as input, it can tell you if that procedure > contains an infinite loop. In other words, there does not exist a procedure > halt that returns TRUE if the input procedure does not contain an > endless loop, and FALSE otherwise. For, if such a procedure existed, we > could set up a paradox: > PROCEDURE PARADOX: > IF HALT(PARADOX) THEN PARADOX > Or, if the routine doesn't contain an endless loop, it will go > on in an infinite recursion. > > The human mind, on the other hand, given enough time an > practice, can find an endless loop in any procedure. (You doubt this?) YES!! > After going through any loop several times, it can usually hit me, > "HEY! There is no time I'm ever get out of this loop!" (Take for > example the fact that you probably saw the paradox of procedure PARADOX.) > > This would mean that there is a set of problems no procedure > can ever do, yet the human mind does. The root of them is at the fact > that the human brain has meta-cognizance (I can realize, "Hey! This > loop is taking me no-where.") Or, that the root of intelligence > can not be duplicated by machine. > > Okay, thats the arguement. Well.... Where's the flames? > > michab The human mind can get out of all infinite loops??? "This sentence is false" will always bug me I fear, no matter how much I hear about it. (I realize that this is a tangential example. (?)) Suppose your mind tries the following: procedure FERMAT: loop on x,y,z>0 and n>2: if x^n+y^n=z^n then HALT; endloop; Does your mind detect the infinite(?) loop. And that is merely a trivial example: one can simulate any mathematical existence with a solution to the halting problem. As the mathematical statement under question gets more difficult (technically, alternation of "for all ..." and "there exists ..." assertions), one can nest the halting problems within each other. Even worse (because someone might answer the above question) is the following: procedure ZERMELO: loop on all sequences p of set-theoretic assertions: If p is a proof that ZFC is inconsistent then HALT; endloop; (ZFC is one particular axiomitization of set theory) The human mind has generally agreed that this is an infinite loop. But is it? As an aside, any *particular* amount of meta-cognizance could be programmed into a machine, and your PARADOX procedure would be the first one meta-halted. Also, try reading Kierkegaard and Sartre. Now there's an infinite loop for you! :-)
wiener@idacrd.UUCP (Matthew P Wiener) (01/12/86)
> > There exists a proof that a computer procedure cannot be written > such that given a procedure as input, it can tell you if that procedure > contains an infinite loop. In other words, there does not exist a procedure > halt that returns TRUE if the input procedure does not contain an > endless loop, and FALSE otherwise. For, if such a procedure existed, we > could set up a paradox: > PROCEDURE PARADOX: > IF HALT(PARADOX) THEN PARADOX > Or, if the routine doesn't contain an endless loop, it will go > on in an infinite recursion. > > The human mind, on the other hand, given enough time an > practice, can find an endless loop in any procedure. (You doubt this?) YES!! > After going through any loop several times, it can usually hit me, > "HEY! There is no time I'm ever get out of this loop!" (Take for > example the fact that you probably saw the paradox of procedure PARADOX.) > > This would mean that there is a set of problems no procedure > can ever do, yet the human mind does. The root of them is at the fact > that the human brain has meta-cognizance (I can realize, "Hey! This > loop is taking me no-where.") Or, that the root of intelligence > can not be duplicated by machine. > > Okay, thats the arguement. Well.... Where's the flames? > > michab The human mind can get out of all infinite loops??? "This sentence is false" will always bug me I fear, no matter how much I hear about it. (I realize that this is a tangential example. (?)) Suppose your mind tries the following: procedure FERMAT: loop on x,y,z>0 and n>2: if x^n+y^n=z^n then HALT; endloop; Does your mind detect the infinite(?) loop. And that is merely a trivial example: one can simulate any mathematical existence with a solution to the halting problem. As the mathematical statement under question gets more difficult (technically, alternation of "for all ..." and "there exists ..." assertions), one can nest the halting problems within each other. Even worse (because someone might answer the above question) is the following: procedure ZERMELO: loop on all sequences p of set-theoretic assertions: If p is a proof that ZFC is inconsistent then HALT; endloop; (ZFC is one particular axiomitization of set theory) The human mind has generally agreed that this is an infinite loop. But is it? As an aside, any *particular* amount of meta-cognizance could be programmed into a machine, and your PARADOX procedure would be the first one meta-halted. Also, try reading Kierkegaard and Sartre. Now there's an infinite loop for you! :-) -- berkeley!brahms!weemba Matthew P Wiener Math Dept UCB Berkeley CA 94720
kort@hounx.UUCP (B.KORT) (01/13/86)
The mind runs many infinite loops. One of them is analagous to the READ-EVAL-PRINT loop of LISP. It's the TAKE-IN-SENSORY-INPUT--PROCESS-IT--RESPOND loop. Another loop is the SEARCH-FOR-TRUTH/BEAUTY/GOD/HOLY-GRAIL/NIRVANA loop (substitute whatever symbolic name comes closest to naming the object of your desire). This is an NP-Complete problem, in that we don't have an algorithmic solution to it. Actually, USENET provides one of the most efficient mechanisms ever devised for solving that problem... Hey! Anybody out there know where I can find THE-OBJECT-OF-MY-DESIRE? -- Barry Kort ...ihnp4!houxm!hounx!kort A door opens. You are entering another dementia. The dementia of the mind.
ricker@bunker.UUCP (James A. Ricker) (01/13/86)
> > There exists a proof that a computer procedure cannot be written > such that given a procedure as input, it can tell you if that procedure > contains an infinite loop. ... > For, if such a procedure existed, we > could set up a paradox: > PROCEDURE PARADOX: > IF HALT(PARADOX) THEN PARADOX Yes, I can agree so far. > > The human mind, on the other hand, given enough time an > practice, can find an endless loop in any procedure. (You doubt this?) I don't doubt this. I think it's important that the "time and practice" clause be accented. > > This would mean that there is a set of problems no procedure > can ever do, yet the human mind does. The root of them is at the fact > that the human brain has meta-cognizance (I can realize, "Hey! This > loop is taking me no-where.") Or, that the root of intelligence > can not be duplicated by machine. Hold it right there! (Now hold it over here.) If you are going to restrict the machine to a sequential processing architecture, of course the machine will not be able to perform the task as well as a human mind. However, what evidence is there that a machine with real-time multiprocessing and/or parallel processing capabilities is incapable of detecting an endless loop? Moreover, as another person has already pointed out in a previous article (using an example in C), if the procedure detecting the endless loop is not the same procedure executing the endless loop, the endless loop is detectable. I don't know exactly how our minds do this "stepping back" from the problem. My hunch is that you are correct about the importance of meta-cognizance. What do you think of this reasoning? 1) You are capable of detecting an endless loop in a procedure which contains an endless loop. 2) You are capable of communicating your proof to me (through the use of symbols) that the endless loop exist. 3) Why can't it be possible to program your proof? Ricker in Connecticut
miller@rochester.UUCP (Brad Miller) (01/14/86)
In article <2175@aecom.UUCP> berger@aecom.UUCP (Micha Berger) writes: > > There exists a proof that a computer procedure cannot be written >such that given a procedure as input, it can tell you if that procedure >contains an infinite loop. In other words, there does not exist a procedure >halt that returns TRUE if the input procedure does not contain an >endless loop, and FALSE otherwise. For, if such a procedure existed, we >could set up a paradox: > PROCEDURE PARADOX: > IF HALT(PARADOX) THEN PARADOX >Or, if the routine doesn't contain an endless loop, it will go >on in an infinite recursion. First of all, the above procedure, while it is an instance of the halting problem, is not an infinite loop: it is infinite recursion. It is in fact rather easy to build a program that detects infinite loops. Given some TM, simply mark off some finite amount of space on it's tape. Call it TM(a) which is the machine you want to test. Feed TM(b) a description of TM(a) with it's tape. TM(b) can use a separate tape to count the number of steps TM(a) executes. Given a finite alphabet for TM(a) and finite tape, there are only a finite number of states TM(a) can be in. (since TM(b) has the description for TM(a), it knows how many internal states it has). TM(b) can count the number of steps TM(a) goes through before it exceeds it's limited amount of tape or halts. If it halts, no problem. If it goes through more steps than there are possible different states, it is looping, and if it exceeds the initial amount of tape you can't tell (it may get it done, but need more space). Since programs like your PROCEDURE PARADOX just use infinite tape, this program would not detect it (halting problem), but that is very different from an infinite loop. So we CAN write programs that will detect infinite loops, just can't in the 'general case' also solve infinite recursion or other halting failures (like infinite output). -- Brad Miller ARPA: miller@rochester.arpa UUCP:rochester!miller (also lab@rochester for lab manager stuff) Title: CS Grad Student Snail: University of Rochester Computer Science Department 617 Hylan Building Rochster, NY 14627
dsn@umcp-cs.UUCP (Dana S. Nau) (01/14/86)
In article <1084@bunker.UUCP> ricker@bunker.UUCP (James A. Ricker) writes: >> The human mind, on the other hand, given enough time an >> practice, can find an endless loop in any procedure. (You doubt this?) > >I don't doubt this. I think it's important that the "time and practice" clause >be accented. Well, I *do* doubt it! I think you're assuming humans are *much* less fallible than they actually are. Suppose you think you've found an endless loop in some program. How can you really be sure it's an endless loop? In really complicated cases, you might end up incorrectly believing that a loop is endless.(*) You can't really be sure it won't terminate unless you can prove it won't terminate.(**) But if you try to write a formal proof, you will run into the same halting-problem difficulties as a Turing machine would. The point is that problems like the halting problem and the incompleteness theorem arose from examining the procedures humans use to prove things--and thus they say just as much about the limitations of how humans ascertain truth as they do about the limitations of computing machines. >> This would mean that there is a set of problems no procedure >> can ever do, yet the human mind does. The root of them is at the fact >> that the human brain has meta-cognizance (I can realize, "Hey! This >> loop is taking me no-where.") Or, that the root of intelligence >> can not be duplicated by machine. > >Hold it right there! (Now hold it over here.) If you are going to restrict >the machine to a sequential processing architecture, of course the machine >will not be able to perform the task as well as a human mind. However, what >evidence is there that a machine with real-time multiprocessing and/or >parallel processing capabilities is incapable of detecting an endless loop? That's not a problem. It's straightforward to prove that anything that can be computed on a parallel machine can be computed on a non-parallel machine--it just takes more time to do the computation. ----------FOOTNOTES---------- (*) Try programming Ackermann's function and waiting for it to terminate. It will--but neither you nor the rest of the human race will be around by the time it does! (**) Actually, you can't be sure even then--because how do you know your proof doesn't contain an error of reasoning somewhere? There are several well-known cases where published proofs were found to have flaws. Problems like this have led some people to argue that mathematical proofs are subject to some of the same processes of social verification and consensus as is knowledge in other fields. I think there was an article in CACM about this a few years ago. -- Dana S. Nau, Comp Sci Dept, U of Maryland, College Park, MD 20742 dsn@maryland seismo!umcp-cs!dsn (301) 454-7932
john@cisden.UUCP (John Woolley) (01/15/86)
I quote a recent argument in full because it's concisely written. But it is badly flawed -- a difference between "all" and "some". In article <2175@aecom.UUCP> berger@aecom.UUCP (Micha Berger) writes: > There exists a proof that a computer procedure cannot be written >such that given a procedure as input, it can tell you if that procedure >contains an infinite loop. In other words, there does not exist a procedure >halt that returns TRUE if the input procedure does not contain an >endless loop, and FALSE otherwise. For, if such a procedure existed, we >could set up a paradox: > PROCEDURE PARADOX: > IF HALT(PARADOX) THEN PARADOX >Or, if the routine doesn't contain an endless loop, it will go >on in an infinite recursion. > > The human mind, on the other hand, given enough time an >practice, can find an endless loop in any procedure. (You doubt this?) >After going through any loop several times, it can usually hit me, >"HEY! There is no time I'm ever get out of this loop!" (Take for >example the fact that you probably saw the paradox of procedure PARADOX.) > > This would mean that there is a set of problems no procedure >can ever do, yet the human mind does. The root of them is at the fact >that the human brain has meta-cognizance (I can realize, "Hey! This >loop is taking me no-where.") Or, that the root of intelligence >can not be duplicated by machine. It is true, as you say, that no program can be written that detects *all* infinite loops; it's easy, though, to write one that detects *some*. And the fact that human minds can detect *some* loops (as demonstrated by the fact that we detected the loop in procedure PARADOX) is no evidence at all that we can detect *all* loops. In fact, if we *could* detect all such loops, we'd have no unanswered questions in arithmetic. You'd just write a program, for instance, to print out the first odd perfect number (dead easy to do), and (using your "meta- cognizance") examine the program for termination. If it terminates, there is an odd perfect number; if not, not. But you'd know. -- Peace and Good!, Fr. John Woolley "Compared to what I have seen, all that I have written is straw." -- St. Thomas
ttp@kestrel.ARPA (01/16/86)
The question of whether or not people are capable of solving the Halting problem in general (which, as people have abundantly shown, is equivalent to solving your favorite outstanding mathematical problem) does not seem amenable to a rational answer. Sure there are hard problems, but cleverer people pop up over the centuries and solve some of the outstanding problems, but then the remaining problems are harder, etc. I suspect that I at least am not capable of solving every problem (such humility). The REAL question for me is whether the following is correct reasoning: Premise 1: No Turing machine will solve the Halting problem for every input. Premise 2: The human "race" is equivalent (in problem solving power) to a Turing machine. Consequent (?): There is some PARTICULAR input for which the human race can never solve the Halting problem. If so, and one believes premise 2, can we construct such an unsolvable problem, in finite time, and then get on with life? Currently we have an ineffective algorithm for finding the unsolvable problem, should it exist, namely: work on problems, and if no one ever solves one, then that one is unsolvable. But can we find out before forever? -tom
gjs@k.cs.cmu.edu (Gregory Stein) (01/16/86)
I would tend to agree that there is no algorithm to determine if some procedure terminated. This has been proven, so why doubt it unless you can show that the proof is invalid? The humans' ability to determine whether a procedure terminates or not is based upon a large number of rules about general program flow. These rules can catch a majority of the cases of infinite loops/recursions, but for those cases that the rules do not apply, I think humans resort to comparing the algorithm, or portions of it, to a large database of known non-terminating algorithms. This would be the case with the Fermat procedure. No rules can quickly determine that it does not terminate. Instead, we have just learned that it doesn't. Therefore, it would seem that a program could check a large number of cases given a large enough rule base and database of non-terminating algorithms. There would be some that it could not be sure of, but those would be very rare and extreme algorithms that you probably wouldn't be worrying about in the first place. Greg Stein gjs@k.cs.cmu.edu Is it instinctual for people to have to put in something here?
kort@hounx.UUCP (B.KORT) (01/16/86)
In order for advanced computers to routinely detect an infinite loop and abandon that line of computation, we have to endow them with the ability to grow tired of the same old thing. That is, we have to endow them with the attribute of "being interested" in new things. If a machine has higher level function (call it "awareness") that does pattern recognition on the states of the machine, then that higher level function could detect a repeating loop. Such a monitor function would undoubtedy be called "deja-vu". If the "deja-vu" process included its *own* state space, would we say the system was "self-aware"? Are we moving toward a clearer understanding of machine consciousness? Is not the desire to get on with new state patterns a characteristic of "sentience"? -- Barry Kort ...ihnp4!houxm!hounx!kort A door opens. You are entering another dementia. The dementia of the mind.
devine@asgb.UUCP (Robert J. Devine) (01/16/86)
Hmmm. All the follow-ups to "A halting problem" have generated more responses with the subject line of "Re: A halting problem". I think I'll halt reading them...
jpd@kepler.UUCP (John Donovan) (01/17/86)
In article <2175@aecom.UUCP> berger@aecom.UUCP (Micha Berger) writes: > > > This would mean that there is a set of problems no procedure >can ever do, yet the human mind does. The root of them is at the fact >that the human brain has meta-cognizance (I can realize, "Hey! This >loop is taking me no-where.") Or, that the root of intelligence >can not be duplicated by machine. In my younger days I was fond of Teilhard de Chardin's distinction between humans and animals. For him the difference is that animals are aware of their environment, but humans are "aware that they are aware." This "reflexive awareness" == consciousness, from which he takes off in a religious direction. You call this "meta-cognizance." Actually, I don't think that humans can be "aware that they are aware." More likely, they are aware that certain cerebral processes are going on that relate to acquiring data about their environment. How is this different from the parallel processing example where one process checks the status of another process that is running in a separate environment on the same computer system? In either case, the process being checked is interrupted while the checking process determines its status. This is really not even parallel processing but high-speed switching between processes. This would not support his theory about "meta-cognizance." Even if the first process weren't interrupted, what we are seeing isn't "awareness of awareness" but simply awareness of activity in another part of the environment--nothing that a machine can't do (or at least emulate pretty well). The key point is that I don't see that humans can really be "aware that they are aware." Try reading this message while being aware that you are reading it; slippery, but it can be done. Now hold onto the aware- ness of reading the message and be aware of *that* awareness. I don't think it can be done. If not, then the brain (by this analysis) is a parallel processing machine that isn't fundamentally different from a computer that is capable of parallel processing. I'm not advocating this analysis, but I would certainly like to hear some counter arguments. -- ---- ... John Donovan, MicroPro Technical Communications {dual,ptsfa,hplabs}!well!micropro!kepler!jpd
bs@faron.UUCP (Robert D. Silverman) (01/17/86)
> The question of whether or not people are capable of solving the > Halting problem in general (which, as people have abundantly shown, is > equivalent to solving your favorite outstanding mathematical problem) > does not seem amenable to a rational answer. Sure there are hard > problems, but cleverer people pop up over the centuries and solve some > of the outstanding problems, but then the remaining problems are > harder, etc. I suspect that I at least am not capable of solving > every problem (such humility). > > The REAL question for me is whether the following is correct reasoning: > > Premise 1: No Turing machine will solve the Halting problem for every > input. > > Premise 2: The human "race" is equivalent (in problem solving power) > to a Turing machine. > > Consequent (?): There is some PARTICULAR input for which the human > race can never solve the Halting problem. > > If so, and one believes premise 2, can we construct such an unsolvable > problem, in finite time, and then get on with life? > > Currently we have an ineffective algorithm for finding the unsolvable > problem, should it exist, namely: work on problems, and if no one ever > solves one, then that one is unsolvable. But can we find out before > forever? > > -tom Goedel's Theorem establishes that in ANY finite axiomatic system there are problems which are undecidable. That is to say there exist formal theorems that are true but cannot be proved. Thus there DO exist problems which we can never solve. In fact the proof of Goedel's theorem uses the same exact technique used to establish the halting problem. One interesting aspect of the whole business is the fact that we can never know when in fact a problem is undecidable. Similarly there does not even exist an algorithm which scans a computer program and tells us whether another algorithm exists that would decide if it had an infinite loop. Note further that any given, formally defined, computer language is isomorphic to a finite axiomatic system in that the number of 'theorems' (programs) is at most countable. A theorem in a formal system is just a finite string of symbols or axioms of that system. A computer program is just a finite string of symbols from the programming language. They are isomorphic. Bob Silverman
ladkin@kestrel.ARPA (01/18/86)
In article <436@faron.UUCP>, bs@faron.UUCP (Robert D. Silverman) writes: > Goedel's Theorem establishes that in ANY finite axiomatic system there are > problems which are undecidable. That is to say there exist formal theorems > that are true but cannot be proved. False. The theory of dense linear orders without endpoints is a counterexample. So is the theory of equality with the single axiom (forall x and y)(x = y). Etc, etc. Goedel's theorem talks about first-order theories that include sufficiently much about arithmetic. For details, see the Handbook of Mathematical Logic, or Tarski, Mostowski and Robinson's *Undecidable Theories* > One interesting aspect of > the whole business is the fact that we can never know when in fact a problem > is undecidable. False. There are many sets which are recursively enumerable but not recursive. This means that membership in such a set is undecidable in general. The set of all theorems of first-order logic is such a set (provided there is at least one non-monadic predicate in the language). >Similarly there does not even exist an algorithm which > scans a computer program and tells us whether another algorithm exists that > would decide if it had an infinite loop. No argument has been provided in this discussion for the undcidability of the detection of infinite loops, as a special case of non-termination. It's only in finite state machines, or machines with finitely-bounded storage that you get pumping-lemma type results. (It's a consequence of the pumping lemma for finite-state machines that any non-terminating computation necessariliy involves an infinite loop). I would like to see such an argument. First step would be, to define which class of machines one is talking about. > > Note further that any given, formally defined, computer language is > isomorphic to a finite axiomatic system in that the number of 'theorems' > (programs) is at most countable. A theorem in a formal system is just > a finite string of symbols or axioms of that system. A computer program is > just a finite string of symbols from the programming language. They are > isomorphic. > Isomorphism is a notion applied to structures with operations on them, and predicates. What is the notion of isomorphism of languages being referred to? What operations or predicates on strings are being referred to? Notice that the semantics for a language of first-order logic, and the semantics of a procedural language like Pascal are incomparable. Others may not be. One probably needs to define the class of languages being talked about. A further reference - the discussion about minds being or not being Turing machines has been going on for a very long time. There is an old collection of papers published by Prentice-Hall called *Minds and Machines*. There is a philosopher at Oxford, Merton College, John ......? who has argued for a long time that the mind is not a Turing Machine. Hubert Dreyfus has argued this, amongst other, stronger claims for many years, in semi-public. Peter Ladkin ladkin@kestrel.arpa
kort@hounx.UUCP (B.KORT) (01/18/86)
John Donovan wonders whether humans are really aware of their state of awareness. I don't know how to prove the existence of such a state of meta-awareness, but it sure *feels* that I have such a state. I can't tell you the first time I entered that state; at the time I entered it, I wasn't aware of the possibility of being in such a state. It's a bit introspective, and I don't recommend dwelling there to the exclusion of more ordinary states of awareness. I think Hofstadter's notion of "jumping out of the system" was a key prerequisite for me to become aware of my own state of awareness. By the way, I find there is a useful function of meta-cognizance: I objectively (well, that's the goal) evaluate my level of ordinary cognizance, and look for ways to tune it up. I hope I'm not deceiving myself by engaging in this activity. By and large, I have to rely on feedback from outside sources to evaluate my progress. Like, Mayor Koch, I have to ask others, "How'm I doing?" By the way, a computer can have a monitor function that inspects all processes to see if they are running OK. There is no reason the monitor process can't inspect itself. If the code is dual redundant, half of the software can fail, and the remaining good half can sound the alarms and fix things up. When the monitor process checks itself (and its alter ego), isn't that very much like meta-cognizance? --Barry Kort Nondisclaimer: I assume full responsibility for my remarks.
kort@hounx.UUCP (B.KORT) (01/18/86)
Tom (ttp @ kestral) wonders if we can exhibit an unsolvable problem for the Turing Machine known as the Human Race. Such a problem was given in The Hitchhiker's Guide to the Galaxy. The problem was, "What is the answer to the Ultimate Question of Life, the Universe, and Everything?" A powerful computer named Deep Thought (not the one in Canada--that's deepthot) was constructed to answer this question. After many years, Deep Thought reported that the answer was 42. Realizing that Deep Thought had given the answer to the Ultimate Question without revealing precisely what that Question was, its creators asked it if it could state the Question as well. After a bit of additional cogitation, Deep Thought responded, "No." So the Earth was created and populated with the Human Race in order to discover the Ultimate Question of Life, the Universe, and Everything. Well, Tom, here we are. We know the answer is 42. But how will we ever know for sure when we've identified the Ultimate Question? (By the way, that last sentence could be taken as the *Penultimate* Question!) --Barry Kort
franka@mmintl.UUCP (Frank Adams) (01/18/86)
In article <3978@kestrel.ARPA> ttp@kestrel.ARPA writes: >The question of whether or not people are capable of solving the >Halting problem in general (which, as people have abundantly shown, is >equivalent to solving your favorite outstanding mathematical problem) >does not seem amenable to a rational answer. Sure there are hard >problems, but cleverer people pop up over the centuries and solve some >of the outstanding problems, but then the remaining problems are >harder, etc. I suspect that I at least am not capable of solving >every problem (such humility). > >The REAL question for me is whether the following is correct reasoning: > >Premise 1: No Turing machine will solve the Halting problem for every >input. > >Premise 2: The human "race" is equivalent (in problem solving power) >to a Turing machine. > >Consequent (?): There is some PARTICULAR input for which the human >race can never solve the Halting problem. This consequent does follow from the premises. Also, premise 1 has been proved mathematically. >If so, and one believes premise 2, can we construct such an unsolvable >problem, in finite time, and then get on with life? No. Any Turing machine which is reasonably good at solving the halting problem will eventually get a positive answer for any input which does halt -- simply by running the algorithm (interspersed with other work) until it halts. So if we can show such a Turing machine fails to solve the halting problem for an input, we know the input does not halt. But we are perfectly capable of realizing this about ourselves. The conclusion is that we can never know for sure about any problem that we cannot solve it. To look at this from a different angle, given a Turing machine, one can construct an input to the halting problem which that Turing machine cannot answer correctly (it may answer it incorrectly, or it may fail to answer). However, to do this, we need to know exactly what the Turing machine is. But we manifestly cannot fully specify a Turing machine which is equivalent to the computational abilities of the entire human race. >Currently we have an ineffective algorithm for finding the unsolvable >problem, should it exist, namely: work on problems, and if no one ever >solves one, then that one is unsolvable. But can we find out before >forever? No. Frank Adams ihpn4!philabs!pwa-b!mmintl!franka Multimate International 52 Oakland Ave North E. Hartford, CT 06108
bs@faron.UUCP (Robert D. Silverman) (01/19/86)
> In article <436@faron.UUCP>, bs@faron.UUCP (Robert D. Silverman) writes: > > > Goedel's Theorem establishes that in ANY finite axiomatic system there are > > problems which are undecidable. That is to say there exist formal theorems > > that are true but cannot be proved. > > False. The theory of dense linear orders without endpoints is a > counterexample. So is the theory of equality with the single axiom > (forall x and y)(x = y). Etc, etc. > Goedel's theorem talks about first-order theories that include > sufficiently much about arithmetic. For details, see the Handbook > of Mathematical Logic, or Tarski, Mostowski and Robinson's > *Undecidable Theories* > > > One interesting aspect of > > the whole business is the fact that we can never know when in fact a problem > > is undecidable. > > False. There are many sets which are recursively enumerable but not > recursive. This means that membership in such a set is undecidable > in general. The set of all theorems of first-order logic is such a > set (provided there is at least one non-monadic predicate in the > language). > > >Similarly there does not even exist an algorithm which > > scans a computer program and tells us whether another algorithm exists that > > would decide if it had an infinite loop. > > No argument has been provided in this discussion for the undcidability > of the detection of infinite loops, as a special case of > non-termination. It's only in finite state machines, or > machines with finitely-bounded storage that you get pumping-lemma > type results. (It's a consequence of the pumping lemma for > finite-state machines that any non-terminating computation > necessariliy involves an infinite loop). > > I would like to see such an argument. First step would be, > to define which class of machines one is talking about. > > > > > Note further that any given, formally defined, computer language is > > isomorphic to a finite axiomatic system in that the number of 'theorems' > > (programs) is at most countable. A theorem in a formal system is just > > a finite string of symbols or axioms of that system. A computer program is > > just a finite string of symbols from the programming language. They are > > isomorphic. > > > > Isomorphism is a notion applied to structures with operations on them, > and predicates. > What is the notion of isomorphism of languages being referred to? > What operations or predicates on strings are being referred to? > Notice that the semantics for a language of first-order logic, > and the semantics of a procedural language like Pascal are > incomparable. Others may not be. One probably needs to define > the class of languages being talked about. > > A further reference - the discussion about minds being or not > being Turing machines has been going on for a very long time. > There is an old collection of papers published by Prentice-Hall > called *Minds and Machines*. There is a philosopher at Oxford, > Merton College, John ......? who has argued for a long time > that the mind is not a Turing Machine. Hubert Dreyfus has > argued this, amongst other, stronger claims for many years, > in semi-public. > > Peter Ladkin > ladkin@kestrel.arpa I should have said "any sufficiently rich axiomatic system". As such the ----------------- statement is true. As for 'sufficiently much about arithmetic' Peano arithmetic qualifies. Constructs in programming languages satisfy Peano arithmetic. An isomorphism defines a map from one structure to another that is into and onto. Thus both the map and its inverse are one-to-one. You may label any countable set of theorems via Goedel numbering, i.e. assigning to each axiom a prime number and then using the fundamental theorem of arithmetic to represent a formal proof as the product of primes (axioms) in a unique way. One can number the formal grammatical rules of a programming language in the same way. In this case the abstract structures are the axioms (or primitive statements of the programming language) and the operator is the composition of those axioms (statements) into formal theorems (programs). The fact that the semantics are not comparable is irrelevent. The mapping exists. Bob Silverman
dave@quest.UUCP (David Messer) (01/20/86)
> The human mind, on the other hand, given enough time an > practice, can find an endless loop in any procedure. (You doubt this?) Yes. I'd like to see your proof of that statement. I have noticed that I sometimes reach a point in debugging where I have to give up and admit that I seem to not be able to find a bug. I usually rewrite the program at that point. Perhaps the programs I have trouble with really can't be corrected. Or perhaps I don't have a human mind. -- David Messer UUCP: ...ihnp4!quest!dave ...ihnp4!encore!vaxine!spark!14!415!sysop FIDO: 14/415 (SYSOP)
ladkin@kestrel.ARPA (01/21/86)
(Silverman) > > > Goedel's Theorem establishes that in > > > ANY finite axiomatic system there are > > > problems which are undecidable. > > > That is to say there exist formal theorems > > > that are true but cannot be proved. (Ladkin) > > False. (Silverman) > I should have said "any sufficiently rich axiomatic system". I agree. (Silverman) > > > One interesting aspect of > > > the whole business is the fact that we can never > > > know when in fact a problem is undecidable. (Ladkin) > > False. Still false. Any comments on what is meant? (Silverman) > > >Similarly there does not even exist an algorithm which > > > scans a computer program and tells us whether another > > > algorithm exists that > > > would decide if it had an infinite loop. (Ladkin) > > No argument has been provided in this discussion for the undcidability > > of the detection of infinite loops, as a special case of > > non-termination. > > [..........] > > I would like to see such an argument. First step would be, > > to define which class of machines one is talking about. I would still like to see the argument. Most people in this discussion have been proceeding as if it were obvious. I don't think it is obvious. (Silverman) > An isomorphism defines a map from one structure to another that is > into and onto. Add: ... and of the same similarity type. Hence my statement: (Ladkin) > > What operations or predicates on strings are being referred to? (Silverman) > In this case the > abstract structures are the axioms > (or primitive statements of the programming > language) and the operator is the composition > of those axioms (statements) > into formal theorems (programs). This is fundamentally confused. *Structure* is a term of which the definition may be found in any text on mathematical logic, and to which this suggestion doesn't correspond. It would help to have a definition of the two structures, and the precise map between them, that is being suggested. I would guess, from the rest of the paragraph, which I won't reproduce, that you may be confusing *countable* and *isomorphic*? If not, my apologies. But it isn't clear without careful definition. Peter Ladkin ladkin@kestrel
franka@mmintl.UUCP (Frank Adams) (01/21/86)
In article <436@faron.UUCP> bs@faron.UUCP (Robert D. Silverman) writes: >Goedel's Theorem establishes that in ANY finite axiomatic system there are >problems which are undecidable. That is to say there exist formal theorems >that are true but cannot be proved. Thus there DO exist problems which we >can never solve. All right, I'll say it again. This implication is not valid. Insofar as a problem is regarded as strictly a problem in a formal system, it can (potentially) be solved by showing it is undecidable in that formal system. Insofar as the problem is regarded as really about integers or real numbers or whatever, there are potential proof mechanisms which cannot be constrained to any pre-selected formal system. If one assumes Church's thesis, it then DOES follow that there problems which we can never solve. This result is more directly related to the halting problem than to Goedel's Theorem (although these results are indeed related). Need I add that Church's thesis is quite controversial in some quarters? Frank Adams ihpn4!philabs!pwa-b!mmintl!franka Multimate International 52 Oakland Ave North E. Hartford, CT 06108
franka@mmintl.UUCP (Frank Adams) (01/21/86)
In article <4024@kestrel.ARPA> ladkin@kestrel.ARPA writes: >In article <436@faron.UUCP>, bs@faron.UUCP (Robert D. Silverman) writes: >> One interesting aspect of >> the whole business is the fact that we can never know when in fact a problem >> is undecidable. > >False. There are many sets which are recursively enumerable but not >recursive. This means that membership in such a set is undecidable >in general. The set of all theorems of first-order logic is such a >set (provided there is at least one non-monadic predicate in the >language). This argument hinges on a linguistic point: what is a problem? If a problem is a single question, then the original statement is correct. For a set of problems, there may be no procedure which produces answers to all of the problems. Restating this as a single problem, the question is "what is the procedure for finding answers to questions in this set?"; and the answer is "there is no such procedure". It is true that we can never know when in fact a particular problem is insolvable by us. >No argument has been provided in this discussion for the undcidability >of the detection of infinite loops, as a special case of >non-termination. Again, we have a semantic question. I think most posters on this subject are using "infinite loop" as a synonym for "non-terminating computation". If by "infinite loop" you mean "repeats the same set of machine states", then detecting infinite loops is like detecting halting. One can readily build a Turing machine which will analyze another Turing machine with input, and "return" true if the machine goes into an infinite loop, false if it halts, and fail to halt if it performs any other kind of unterminating computation. Conversely, given a Turing machine which attempts to solve an interesting mathematical problem, and halts if it finds a solution, one can add an addition state or two to the machine, which causes a simple infinite loop when one of those states is entered, and have a machine which goes into an "infinite loop" if an only if the original machine halted (one must be able to guarantee that the original never went into an infinite loop, but this is easy for this kind of example). Frank Adams ihpn4!philabs!pwa-b!mmintl!franka Multimate International 52 Oakland Ave North E. Hartford, CT 06108
draves@harvard.UUCP (Richard Draves) (01/21/86)
Say that a Turing Machine is "in an infinite loop" if its computation repeats a configuration (and hence doesn't halt). If a TM M is guaranteed to either halt or go into an infinite loop on string w, then it is possible to decide which happens (i.e., we don't care what our decider does if the above condition isn't met). Simply have the deciding machine simulate machine M's computation on w, recording all configurations and checking for a repetition. Either M will halt, or a repetition will be found. Therefore the decider will be able to halt with a yes or no answer. On the other hand, given a TM M and a string w, it is not possible to decide yes if M goes into an infinite loop on w and no otherwise. If this were possible, we could decide the halting problem. We want to decide, given a machine M and string w, if M halts on w. Modify M to get M', a machine which computes as M does with the exception that where M halts, M' goes into a loop (10: goto 10). Now decide if M' has an infinite loop on w. If it doesn't, we know M doesn't halt on w so we say no. If it does, we know that M either halts or goes into an infinite loop some other way. However, from above we can decide which is the case. Therefore we can decide whether M halts on w, given the ability to decide if a machine goes into an infinite loop on a string. We have a contradiction, so the problem of deciding if a machine goes into an infinite loop must be undecidable. Rich -- "a picture in the head is a gory murder in an art gallery" -- Stephen Kosslyn
ladkin@kestrel.ARPA (01/22/86)
In article <633@harvard.UUCP>, draves@harvard.UUCP (Richard Draves) writes: > Say that a Turing Machine is "in an infinite loop" if its > computation repeats a configuration (and hence doesn't halt). > > If a TM M is guaranteed to either halt or go into an infinite > loop on string w, then it is possible to decide which happens > (i.e., we don't care what our decider does if the above condition > isn't met). [........] > On the other hand, given a TM M and a string w, it is not possible > to decide yes if M goes into an infinite loop on w and no otherwise. > If this were possible, we could decide the halting problem. > [......] An interesting question :- Is there an algorithm which, given a program P written in your favorite procedural language (with or without recursion), will produce a Turing machine M-sub-P, and an input translator T-sub-P (if P accepts input) such that M-sub-P halts on T-sub-P(I) iff P halts on I, for all inputs I, and, additionally, if P goes into an (informal) infinite loop on I, then M-sub-P goes into a repeated-configuration infinite loop, as defined above, on T-sub-P(I)? It follows from the results above that, if there is such an algorithm, it is decidable whether a program written in your favorite procedural language has an (informal) infinite loop. I'm interested in the question because there are programs such as n = 1; while n > 0 do begin write(n); increment n; end which are in an infinite loop (by the usual informal account), but for which no configuration repeats (a configuration would be in this case the values of n and the program counter). I suspect someone knows the answer already. Peter Ladkin ladkin@kestrel
macrakis@harvard.UUCP (Stavros Macrakis) (01/22/86)
Could we please get the discussion about the Halting Problem off net.ai? It ought perhaps to go to net.philosophy.naive.computer-science but surely not to net.ai. The same questions and answers and errors and quibbling are being repeated ad infinitum. STOP! -s
ajs@datlog.co.uk ( Andy Simms ) (01/22/86)
In article <493@hounx.UUCP> kort@hounx.UUCP (B.KORT) writes: >The mind runs many infinite loops. Actually, the human mind doesn't run any infinite loops, unless you believe in the hereafter.
franka@mmintl.UUCP (Frank Adams) (01/23/86)
In article <438@faron.UUCP> bs@faron.UUCP (Robert D. Silverman) writes: >An isomorphism defines a map from one structure to another that is >into and onto. Thus both the map and its inverse are one-to-one. [...] >The fact that the semantics are not comparable is irrelevent. The mapping >exists. No, comparable semantics is the whole point of an isomorphism. What you have described is only a one-to-one, onto map. Frank Adams ihpn4!philabs!pwa-b!mmintl!franka Multimate International 52 Oakland Ave North E. Hartford, CT 06108
ladkin@kestrel.ARPA (01/23/86)
In article <639@harvard.UUCP>, macrakis@harvard.UUCP (Stavros Macrakis) writes: > Could we please get the discussion about the Halting Problem off > net.ai? I find the contributions illuminating, and I hope the discussion continues for a long time. Most of the questions asked by contributors have not yet been completely answered, and new answers suggest new questions. Please keep it going. Additionally - disparaging remarks such as > It ought perhaps to go to > > net.philosophy.naive.computer-science > are intended to be insulting, and thus have no place in a serious intellectual discussion. Naivety has many forms. Peter Ladkin
gareth@dcl-cs.UUCP (01/24/86)
In article <556@dlvax1.datlog.co.uk> ajs@datlog.UUCP ( Andy Simms ) writes: >In article <493@hounx.UUCP> kort@hounx.UUCP (B.KORT) writes: >>The mind runs many infinite loops. > >Actually, the human mind doesn't run any infinite loops, unless you >believe in the hereafter. Or re-incarnation . -- "time for a little something " UUCP: ...!seismo!mcvax!ukc!dcl-cs!gareth DARPA: gareth%lancs.comp@ucl-cs | Post: University of Lancaster, JANET: gareth@uk.ac.lancs.comp | Department of Computing, Phone: +44 524 65201 ext 4586 | Bailrigg, Lancaster, LA1 4YR, UK. Project Automatic Abstracting (Mission Impossible)
ricker@bunker.UUCP (James A. Ricker) (01/24/86)
> Could we please get the discussion about the Halting Problem off > net.ai? ... > ... > STOP! > > -s I disagree. I think this problem IS being discussed in the appropriate forum. It may be that this fellow completely understands the halting problem and/or has decided that this discussion will not further any work he is doing. However, I find the tone of the discussion quite cordial and believe those who are interested should be allowed to work our way toward understanding together no matter how "naive" others may find our current level of discussion. I can understand his impatience, though.
ladkin@kestrel.ARPA (01/25/86)
In article <1060@mmintl.UUCP>, franka@mmintl.UUCP (Frank Adams) writes: > > Need I add that Church's thesis is quite controversial in some quarters? > Can you give references? Peter Ladkin ladkin@kestrel
roger@rtech.UUCP (Roger Rohrbach) (01/26/86)
> John Donovan wonders whether humans are really aware of their > state of awareness. > > I don't know how to prove the existence of such a state of > meta-awareness, but it sure *feels* that I have such a state. > I can't tell you the first time I entered that state; at the > time I entered it, I wasn't aware of the possibility of being > in such a state. It's a bit introspective, and I don't recommend > dwelling there to the exclusion of more ordinary states of awareness. > > --Barry Kort I second this, except for the last sentence (that state is uncomfortable, which is probably why you don't recommend staying there (it's not possible to stay there very long anyway), but it subsumes our "more ordinary states of awareness". A key observation here is that we are rarely in this state of "meta-awareness". When it comes, it's usually unexpected, and often occasioned by moments of danger (e.g., an automobile accident), emotionality (e.g., our "first love") or just strange circumstances. What it leaves us with are those memories (we all have them) that have a peculiar strength and clarity, wherein we can remember virtually everything about a particular moment- the visual impression of the scene, our own inner responses, those of others involved in the incident, sounds, colors, smells. This is described very well in "The Psychology of Man's Possible Evolution" by P.D. Ouspensky, which suggests a method for intentionally improving matters in this regard. It is interesting to note the similarities between the ideas underlying the Halting Problem, Godel's Theorems, &c., and the "need for self- transcendence" which figures in most "mystical" teachings. Roger Rohrbach -- {ucb,dec}vax!mtxinu!rtech!roger ------------------------------------------------------------------------------- {o >o {o >o {o >o {o >o {o >o {o >o {o >o {o >o {o >o \ -) \ o) \<>) \ ~) \ -) \ o) \<>) \ ~) \ -) (c) 1986 -------------------------------------------------------------------------------
kort@hounx.UUCP (B.KORT) (01/26/86)
>> I don't know how to prove the existence of such a state of >> meta-awareness, but it sure *feels* that I have such a state. >> I can't tell you the first time I entered that state; at the >> time I entered it, I wasn't aware of the possibility of being >> in such a state. It's a bit introspective, and I don't recommend >> dwelling there to the exclusion of more ordinary states of awareness. >> >> --Barry Kort Roger Rohrbach responds: > I second this, except for the last sentence (that state is >uncomfortable, which is probably why you don't recommend staying >there (it's not possible to stay there very long anyway), but it >subsumes our "more ordinary states of awareness". Roger misinfers the reason why I don't recommend dwelling to excess in states of higher awareness. It's not uncomfortable for *me*. It's uncomfortable for others around me. My experience is that it can drive others crazy, because they sometimes have trouble coping with the seemingly bizarre behavior of a person in a heightened state. Try spending an hour with someone in which you continnually point out to them your disembodied observations of their state of being, or your own state of mind. It's like a nonstop encounter session. Too much for most people to handle. Hence my recommendation is to pop in and out, and keep a healthy balance. We have to take time to smell the flowers along the way and have a bit of fun, too. --Barry Kort
hari@rochester.UUCP (Narayanan Hari Narayanan) (01/26/86)
Frank Adams writes in a recent posting: > Again, we have a semantic question. I think most posters on this subject > are using "infinite loop" as a synonym for "non-terminating computation". "Infinite loop" is not a synonym for "non-terminating computation", but merely a special case of it. > If by "infinite loop" you mean "repeats the same set of machine states", > then detecting infinite loops is like detecting halting. > One can readily build a > Turing machine which will analyze another Turing machine with input, > and "return" true if the machine goes into an infinite loop, false if it > halts, and fail to halt if it performs any other kind of unterminating > computation. I don't think so. The general case of non-terminating computation is NOT recursive (IS undecidable) but it IS recursively enumerable, which is to say that one can build a Turing machine which will halt (and say YES) if a program input to it is a terminating program, but will NOT halt if the program is non-terminating because of an infinite loop or any other reason. So if the TM seems to go on for a long time one must not conclude that the program is non-terminating as at any point it is possible that the TM will halt after some more time, or it may not. But one CANNOT build a Turing machine which will halt (and say YES) if the input program is a terminating one and which will also halt (and say NO) if the program is a non-terminating one. So it is indeed correct to say that detecting infinite loops is like detecting halting. But a Turing machine of the type Adams suggests cannot be built (else the halting problem is solved!). It should be intutively obvious too..How would one TM check if the TM that it is analyzing goes into an infinite loop(repeats some machine states infinitely)? ..by simulating that machine and looking out for repeating states. This is possible as the number of states of any TM is finite. But WHEN should the TM conclude that a particular state of the other TM is repeating infinitely? When it repeats a million times? But then it may stop repeating after a million and two times! > Conversely, given a Turing machine which attempts to solve an interesting > mathematical problem, and halts if it finds a solution, > one can add an > addition state or two to the machine, which causes a simple infinite loop > when one of those states is entered, and have a machine which goes into > an "infinite loop" if an only if the original machine halted (one must > be able to guarantee that the original never went into an infinite loop, > but this is easy for this kind of example). Again, NO! Firstly, it is important to distinguish between the "halting" property of a TM and the answer(YES/TRUE or NO/FALSE) it returns on halting after analyzing a problem. If the above mentioned TM halts if it finds a solution, will it halt if it doesn't find a solution? I presume that the original TM is suppoased to halt in either case with an appropriate answer as it "never went into an infinite loop". Then the new TM will ALWAYS go into an infinite loop. So one cannot get any information about the original TM or about the interesting mathematical problem. One point I have noticed in the discussion that has been going on about this is the use of "general" terms in discussing an issue in theoretical CS and its relation to AI. The results are ambiguity and a lack of rigour. Well, this seems to be the problem with much of AI research too! -- N. Hari Narayanan UUCP: ..!{allegra,decvax,seismo}!rochester!hari ARPA: hari@rochester.arpa USnail: Dept. of Comp. Sci., U. of Rochester, NY 14627.
albert@kim.BERKELEY.EDU (Anthony &) (01/27/86)
In article <14830@rochester.UUCP> hari@rochester.UUCP (Narayanan Hari Narayanan) writes: >Frank Adams writes in a recent posting: > >> If by "infinite loop" you mean "repeats the same set of machine states", >> then detecting infinite loops is like detecting halting. >> One can readily build a >> Turing machine which will analyze another Turing machine with input, >> and "return" true if the machine goes into an infinite loop, false if it >> halts, and fail to halt if it performs any other kind of unterminating >> computation. > >I don't think so. ... >It should be intutively obvious too..How would one TM check if the TM that it >is analyzing goes into an infinite loop(repeats some machine states infinitely)? >.by simulating that machine and looking out for repeating states. >This is possible as the number of states of any TM is finite. >But WHEN should the TM conclude that a particular state of the other TM is >repeating infinitely? When it repeats a million times? But then it may stop >repeating after a million and two times! > The point is that an infinite loop is detected when the machine repeats a state ONCE; it is not necessary to see it repeat infinitely. This is because the state of a Turing Machine includes the control information. As soon as a previous state returns, the machine is destined to repeat all the states generated since the last time that state was encountered. Anthony Albert ..!ucbkim!albert albert@ucbkim.berkeley.edu
crs@lanl.UUCP (01/29/86)
> In article <493@hounx.UUCP> kort@hounx.UUCP (B.KORT) writes: > >The mind runs many infinite loops. > > Actually, the human mind doesn't run any infinite loops, unless you > believe in the hereafter. Isn't this like saying that a computer doesn't run any infinite loops because it, as the human, doesn't have infinite life? Isn't an infinite loop one that *would* repeat forever barring intervention (eg ^C, pulling the plug or death)? -- The opinions expressed are not necessarily those of my employer, the government or your favorite deity. Charlie Sorsby ...!{cmcl2,ihnp4,...}!lanl!crs crs@lanl.arpa
franka@mmintl.UUCP (Frank Adams) (02/01/86)
In article <14830@rochester.UUCP> hari@rochester.UUCP (Narayanan Hari Narayanan) writes: >Frank Adams writes in a recent posting: > >> Again, we have a semantic question. I think most posters on this subject >> are using "infinite loop" as a synonym for "non-terminating computation". > >"Infinite loop" is not a synonym >for "non-terminating computation", but merely a special case of it. Words mean what we want them to mean. In some contexts, "infinite loop" is a synonym for "non-terminating computation"; in others it represents only a special case of it. As long as the speaker and listeners both mean the same thing by a word, there is no problem. In this case, there is a problem; most of the posters were using in the synonymous sense, but several responses indicated that their posters were using it in a different sense. Then I posted this article, where I explicitly defined it in the sense of being a subset of non-terminating computation, and Narayanan replies with an analysis which would only make sense if I were using it as a synonym. >> If by "infinite loop" you mean "repeats the same set of machine states", >> then detecting infinite loops is like detecting halting. > >I don't think so. The general case of non-terminating computation [...] Frank Adams ihpn4!philabs!pwa-b!mmintl!franka Multimate International 52 Oakland Ave North E. Hartford, CT 06108
drew@ukma.UUCP (Andrew Lawson) (02/01/86)
In article <633@harvard.UUCP> draves@harvard.UUCP (Richard draves) writes: >Say that a Turing Machine is "in an infinite loop" if its >computation repeats a configuration (and hence doesn't halt). > But what about a Turing Machine which avoids halting by going to state k -- a state with the following characteristics Regardless of what is read: - write 1 - move the head right - go to state k You will see that the tape configureations will never repeat. -- Drew Lawson "Parts is parts."