home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / sci / math / research / 615 < prev    next >
Encoding:
Internet Message Format  |  1992-12-21  |  3.8 KB
  1. Path: sparky!uunet!dtix!darwin.sura.net!zaphod.mps.ohio-state.edu!sdd.hp.com!ux1.cso.uiuc.edu!news.cso.uiuc.edu!dan
  2. From: cap@ifi.unizh.ch (Clemens Cap)
  3. Newsgroups: sci.math.research
  4. Subject: Higher recursion
  5. Message-ID: <1992Dec20.180042.1451@ifi.unizh.ch>
  6. Date: 20 Dec 92 18:00:42 GMT
  7. Sender: Daniel Grayson <dan@math.uiuc.edu>
  8. Followup-To: poster
  9. Organization: University of Zurich, Department of Computer Science
  10. Lines: 78
  11. Approved: Daniel Grayson <dan@math.uiuc.edu>
  12. Originator: dan@symcom.math.uiuc.edu
  13. X-Submissions-To: sci-math-research@uiuc.edu
  14. X-Administrivia-To: sci-math-research-request@uiuc.edu
  15.  
  16.  
  17.         Desperately seeking 
  18.         
  19.       ***************************************
  20.       *help (examples, references, pointers)*
  21.       ***************************************
  22.  
  23.       for higher order recursion theory.
  24.  
  25.  
  26. Introdution
  27. ************
  28.  
  29. In classical recursion theory one studies questions like the following:
  30.  
  31. A functional F is a function from partial recursive functions to partial 
  32. recursive functions.
  33.  
  34. A functional F is called effective, iff there exists an extensional, partial 
  35. recursive function h, such that the effect functional F has on a function g
  36. can be described by an action of this function h on an arbitrary program q
  37. of this function g.
  38.  
  39. A functional F is called monotonic, iff whenever for two functions f and g 
  40. there is f < g, then also F(f) < F(g).  ( < is the usual ordering of partial 
  41. functions).
  42.  
  43. A functional F is called compact, iff for every function f there exists 
  44. a function u with finite domain and u < f, such that F(f) = F(u).
  45.  
  46. Classical recursion theory now studies the following questions:
  47.  
  48. (0) A functional is continuous, iff it is monotonic and compact.
  49. (1) A functional is effective, iff it is continuous.
  50. (2) A functional having the properties of (1) (and (2) always has a least
  51. fixed point function m (so F(m) = m), which can effectively be calculated
  52. either by inductive techniques or by applying a suitable recursive function
  53. to a program of the extensional function belonging to the functional, thus
  54. leading to a program of the least fixed point m.
  55.  
  56. **********************
  57. Now comes my QUESTION:
  58. **********************
  59.  
  60. A) Is there an analogon to this for functionals of higher type?
  61.    For example, let us call a functional of type-2 an operation which takes
  62.    a number of ordinary functionals (as defined above) as argument 
  63.    and yields an ordinary functional as result.
  64.    What can be said about representations via programs, or extensional
  65.    functions, about continuity, monotonicity and compactness ?
  66.    Is there an analogon to above theorem from type-1 recursion theory ?
  67.    
  68. B) G. Plotkin writes in his lecture notes on domains on page 6 
  69.    "And indeed at higher types continuity is a real restriction."
  70.    I would like to understand the meaning of this sentence in the context of
  71.    above lines and I am looking for a concrete example.
  72.    
  73. C) I have studied Kechris and Moschovakis on "Recursion in Higher Types" in
  74.    the Handbook of Mathematical Logic by Barwise, and found some pointers.
  75.    However, I am interested essentially in "real computable and constructive"
  76.    stuff -- everything should have some consequences for a programmer sitting
  77.    in front of his Turing Machine. So also I am very happy for help along the
  78.    line of "fully-abstract-categoric-domain-theoretical-stuff" I would even be
  79.    more happy with help along the line of "apply-example-program-useful-recursive"
  80.    
  81.  
  82. **** Please mail to cap@ifi.unizh.ch
  83.      I will post a summary, in case I receive interesting pointers.
  84.  
  85. Thanx, and happy holidays (after having answered my questions, of coures (;-) )
  86.  
  87.  
  88.  
  89. -- 
  90. * Dr. Clemens H. CAP                        cap@ifi.unizh.ch (email)   
  91. * Ass. Professor for Formal Methods in CS   +(1) 257-4326    (office)
  92. * Dept. of Computer Science                 +(1) 322 02 19   (home)
  93. * University of Zurich                      +(1) 363 00 35   (fax) 
  94.