9
$\begingroup$

E-recursion is a notion of generalized computability theory which seeks to extend computations to allow arbitrary sets as inputs. In contrast with e.g. $\alpha$-recursion, it disallows unbounded search: halting computations are witnessed by well-foundedness of related trees, while for many values of $\alpha$ well-foundedness of a given computable tree is $\Pi^0_1$ over $L_\alpha$. This leads to a really interesting behavior, with a number of odd properties.

I'm interested in the foundations. The standard definition of E-recursion is in terms of a set of schemes. Normann's original article on the subject is quite good, and presents this definition with solid motivation (another good source is the last part of Sacks' book, which certainly has much more material, but I've found it to be quite terse and not as good motivation-wise). However, definitions via schemes often (for me at least) leave some doubt as to whether they define the "right" notion of computability: how do we know we aren't "missing" more schemes?

Normann mentions, excitingly to me, that Moschovakis independently discovered essentially the same thing but via an inductive definability approach. This seems really interesting to me; unfortunately, as far as I can tell Moschovakis' paper never appeared (possibly because it was subsumed, modulo the definition, by Normann's).

My question is:

Does anyone have Moschovakis' text on the subject, or know what his definition was?

Improve this question
$\endgroup$
10
  • $\begingroup$ Moschovakis has a book called "Elementary Induction on Abstract Structures" which is about inductive definability. Did you find anything in there? $\endgroup$
    – William
    Dec 26, 2017 at 23:04
  • $\begingroup$ @William I did briefly, but I might have missed it - I'll look again. $\endgroup$
    – Noah Schweber
    Dec 26, 2017 at 23:12
  • 1
    $\begingroup$ Larry Moss was a student of Moschovakis and wrote his thesis on power-set recursion, which is (modulo possibly some details that I don't remember) E-recursion with the power set operation added as an initial function. This was over 30 years ago, so I don't remember much about his thesis, but it's reasonable to suppose that it included a Moschovakis-style approach to the subject. $\endgroup$
    – Andreas Blass
    Dec 26, 2017 at 23:58
  • $\begingroup$ @NoahSchweber: Did Normann's "Set Recursion" paper's bibliography list any of Moschovakis' papers as references? $\endgroup$
    – Thomas Benjamin
    Jan 8, 2018 at 12:16
  • $\begingroup$ @AndreasBlass: Do you know of any survey articles on power-set recursion? Considering how the cumulative hierarchy is formed, it might be of some small interest to study E-recursion with the power set operation added as an initial function. I wonder what came of Moss' thesis? $\endgroup$
    – Thomas Benjamin
    Jan 10, 2018 at 17:55

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.