Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 4 down vote accepted

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.

share|cite|improve this answer
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. – Phdetermined Feb 4 '13 at 23:55
Yes, that is exactly the issue -- that each function symbol has a fixed number of arguments. – Carl Mummert Feb 5 '13 at 0:44

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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