[FOM] Re: Recursive but not p.r. computable functions

[Hilly Levitz]

If K  and  L are programming languages whose programs compute the partial recursive functions and p.r. functions respectively, then an interpreter program for the language L in the language K  computes a function which is recursive but not p.r.  Moreover using the "macro" technique in Davis and Weyuker, such a program can be written "in macro" in under ten lines. 

For computer science students, at least, the sought after function  arises in a natural way . As to simple, that depend on where you're coming from. 

An execution of this strategy in in Levitz, Nichols, and Smith  ZML, Bd 37, pp121-124 (1991)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: /pipermail/fom/attachments/20030219/1b3d46f1/attachment.html