So we know all recursive functions can be expressed as a finite sequence of symbols for the basic functions and processes composition, primitive recursion, and minimization. What I'm wondering is if it's important to include the brackets in this sequence of symbols?

I haven't been able to produce an example where the recursive function is underdetermined without the brackets, but that certainly doesn't mean there isn't one.


This is really an issue with parsing. If you have three functions, $f$, $g$, and "$fg$", the latter having a name with two letters, there is no clear way to parse the expression "fg1" - should it be $fg(1)$ or $f(g(1))$?

However, if the function names are chosen so that no function name is ever a proper substring of another function name, then it is possible to uniquely recover any correct expression with brackets from the corresponding expression in which the brackets have been removed.

| cite | improve this answer | |
  • $\begingroup$ That was my intuition, but I want to make sure I understand why the correct expression can be uniquely recovered. Does it have to do with the fact that the number of arguments of a particular function are clear without brackets? For example, the identity (or projection function) id^4_1 clearly has four arguments, so we're only going to associate the following four symbols as entries. And if one of those four symbols represents another n-place function, we consider the subsequent n arguments, etc. And likewise for Cn, Pr, and Mn, it will be clear how many argument places they will be taking. $\endgroup$ – Phdetermined Feb 4 '13 at 23:55
  • $\begingroup$ Yes, that is exactly the issue -- that each function symbol has a fixed number of arguments. $\endgroup$ – Carl Mummert Feb 5 '13 at 0:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.