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