Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Posting-Version: version B 2.10.2 9/18/84; site rochester.UUCP Path: utzoo!watmath!clyde!burl!ulysses!mhuxr!mhuxt!houxm!whuxl!whuxlm!akgua!gatech!ut-sally!seismo!rochester!miller From: miller@rochester.UUCP (Brad Miller) Newsgroups: net.ai,net.philosophy Subject: Re: A halting problem Message-ID: <14551@rochester.UUCP> Date: Tue, 14-Jan-86 14:24:19 EST Article-I.D.: rocheste.14551 Posted: Tue Jan 14 14:24:19 1986 Date-Received: Fri, 17-Jan-86 01:13:14 EST References: <2175@aecom.UUCP> Reply-To: lab@rochester.UUCP (Lab Manager(Brad Miller)) Distribution: net Organization: U. of Rochester, CS Dept. Lines: 42 Xref: watmath net.ai:3173 net.philosophy:3773 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