Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!wuarchive!uunet!stanford.edu!unix!clipper!smryan From: smryan@clipper.ingr.com (Steven Ryan) Newsgroups: comp.lang.misc Subject: Re: Will this *thread* ever halt? Message-ID: <1991Jun12.194212.21395@clipper.ingr.com> Date: 12 Jun 91 19:42:12 GMT References: <1991May28.204434.16396@netcom.COM> <22012:Jun1205:25:0491@kramden.acf.nyu.edu> Organization: Intergraph Advanced Processor Division - Palo Alto, CA Lines: 31 In article <22012:Jun1205:25:0491@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: >However, for any given *size* (including program size and memory use) of >self-contained C program, there exists a self-contained C program which >will determine the halting status of every self-contained C program >under that size. Therefore ``determining halting for self-contained C >programs'' is quite possible. Not all programs have an a priori space/time bounds. Your conclusion therefore only applies to bounded programs. You have no proof that unbounded programs do not exist. Even if you wish to assume that the universe has only finite space and time, therefore any 'practical' program must be bounded, your argument is not proved. If the universe is bounded and if there exists a program which requires exactly all the space of the universe, the program to analyze it requires double the size of universe and is thus 'practically' impossible. >In fact, it's rather easy. Perhaps you should spend a little time study the math you so easily dismiss. >Now, Doug, would you like to explain on what basis in fact or fiction >you decided to call this ``impossible''? Not that you'd pay attention to this. -- |-In compliance with DoC,-----------------------Steven Ryan--------------------| | this posting is devoid | 2400 Geng Road, Palo Alto, CA | | of all information. | [clipper![wyrmham!]] smryan@ingr.com | |-And Oliver North married William Secord/and gave birth to a little Teheran.--|