Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Path: utzoo!watmath!clyde!cbosgd!gatech!seismo!rochester!hari From: hari@rochester.UUCP (Narayanan Hari Narayanan) Newsgroups: net.ai,net.philosophy Subject: Re: A halting problem Message-ID: <14830@rochester.UUCP> Date: Sun, 26-Jan-86 11:31:57 EST Article-I.D.: rocheste.14830 Posted: Sun Jan 26 11:31:57 1986 Date-Received: Wed, 29-Jan-86 04:28:59 EST References: <2175@aecom.UUCP> <14551@rochester.UUCP> <3978@kestrel.ARPA> <436@faron.UUCP> <4024@kestrel.ARPA> <1063@mmintl.UUCP> Distribution: net Organization: U. of Rochester, CS Dept. Lines: 66 Xref: watmath net.ai:3227 net.philosophy:3971 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.