Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!batcomputer!cornell!oravax!ian From: ian@oravax.UUCP (Ian Sutherland) Newsgroups: comp.theory Subject: Re: Question on halting problem Message-ID: <2280@oravax.UUCP> Date: 27 Apr 91 06:59:43 GMT References: Reply-To: ian@oravax.odyssey.UUCP (Ian Sutherland) Organization: ORA Corporation, Ithaca, New York Lines: 17 Keywords: for 10 bonus points... In article masticol@athos.rutgers.edu (Steve Masticola) writes: > >This brings up my point: Is it >possible to define an algorithm s.t. its termination is undecidable? What do you mean by the termination of a single program being "undecidable"? The halting problem is recursively undecidable in the sense that there is no recursive function which, given a program (which takes no arguments), tells you whether the program halts or not. The termination of a single program P can't be undecidable in this sense, because there's definitely a recursive function of no arguments which tells you whether P halts or not. You may not know what it is, but it exists (no philosophical arguments please). -- Ian Sutherland ian@cambridge.oracorp.com Sans peur