home *** CD-ROM | disk | FTP | other *** search
- Newsgroups: sci.math
- Path: sparky!uunet!pmafire!mica.inel.gov!guinness!opal.idbsu.edu!holmes
- From: holmes@opal.idbsu.edu (Randall Holmes)
- Subject: Re: help with recursive functions
- Message-ID: <1992Oct8.183408.5402@guinness.idbsu.edu>
- Sender: usenet@guinness.idbsu.edu (Usenet News mail)
- Nntp-Posting-Host: opal
- Organization: Boise State University
- References: <1b074cINN4fu@usenet.INS.CWRU.Edu>
- Date: Thu, 8 Oct 1992 18:34:08 GMT
- Lines: 23
-
- In article <1b074cINN4fu@usenet.INS.CWRU.Edu> cxm7@po.CWRU.Edu (Colin Mclarty) writes:
- >
- > I'd like some help with partial recursive functions which
- >do not extend to (total) recursive ones. I can prove there is no
- >effective routine for extending all partials to total recursive
- >functions, but I do not see how to prove there are particular
- >partial recursive functions that do not extend to recursive. Are
- >there typical methods from proving this in particular cases?
- >
- >Colin McLarty
-
- Easy example: the function which, given the code for a Turing
- machine, simulates its operation and outputs the number of steps it
- takes to halt if it does halt. If this function could be extended to
- a total recurisive function, it could be used immediately to solve the
- halting problem.
-
-
- --
- The opinions expressed | --Sincerely,
- above are not the "official" | M. Randall Holmes
- opinions of any person | Math. Dept., Boise State Univ.
- or institution. | holmes@opal.idbsu.edu
-