Are the brackets in formal box notation of recursive functions omittable?

224 Views Asked by At

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.

1

There are 1 best solutions below

2
On BEST ANSWER

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.