2
$\begingroup$

In the developments I've seen of primitive recursive and computable functions, the functions always have codomain $\mathbb{N}$, but are allowed to have domain $\mathbb{N}^{m}$ for any natural number $m$. This seems odd to me---treating the domains and codomains as fundamentally different.

One solution would be to allow functions $f\colon \mathbb{N}^m\to \mathbb{N}^n$ for any natural numbers $m,n$. Of course, such a function is really just an $n$-tuple of functions $(f_1,f_2,\ldots, f_n)$ where $f_i$ is just the $i$th coordinate of $f$, and computability for $f$ would amount to computability for each $f_i$.

However, I'm more interested in the opposite direction: limiting the domain to always be $\mathbb{N}$. This seems to match, more naturally, what an idealized machine is doing by taking in a single natural number and spitting out a single natural number (or not halting). Of course, a fortiori, one could develop the recursive functions as usual, look at the subclass of functions whose domains are $\mathbb{N}$, and called these the limited domain computable functions, and then show that from these we can reconstruct the non-limited functions in a simple way.

My question is if there is a more natural approach. Just as the recursive functions are built up from some starting functions, using very limited and natural operators, I wonder if there are ways to build up the "limited domain computable functions" similarly, in a non-"ad hoc" way. (For instance, it would be nice if we could do it without the need to develop a universal Turing machine first.)

In other words: Does the extra generality in the domain necessarily simplify the development of computable functions?

Improve this question
$\endgroup$
5
  • $\begingroup$ There are nice recursive bijections between ${\mathbb N}^n$ and $\mathbb N$. If you just pre- and postcompose those, the number of arguments/results doesn't matter. $\endgroup$
    – user130903
    Commented Aug 3, 2020 at 19:44
  • $\begingroup$ You might look-up abstract recursion theory. (I think Fenstad is a primary researcher.) Often one will deal with partial recursive functions as well, and there may be benefit to considering the domain as proper subset of N. One author who has likely addressed this issue in an accessible text is Oddifreddi. Gerhard "Recursion Theory Is My Weakness" Paseman, 2020.08.03. $\endgroup$
    – Gerhard Paseman
    Commented Aug 3, 2020 at 20:17
  • $\begingroup$ If you are concerned about runtime complexity, then you should turn to computer science. There the exponents matter, and while the transformations in between are computationally equivalent, they may not be polytime or linear equivalent. Gerhard "Will Wait For Another Answer" Paseman, 2020.08.03. $\endgroup$
    – Gerhard Paseman
    Commented Aug 3, 2020 at 20:21
  • $\begingroup$ @Zero Yes. More generally, given any sets $S,T$ with bijections $\varphi\colon S\to \mathbb{N}$ and $\psi\colon \mathbb{N}\to T$, we can pre-compose with $\varphi$ and post-compose with $\psi$, and then ask about "computable" functions from $S\to T$ (relative to the "encodings" afforded by $\varphi$ and $\psi$). This was one reason I wanted to define the computable functions using the limited domain---because up to the "nice recursive bijections" you mention there is no difference. $\endgroup$
    – Pace Nielsen
    Commented Aug 3, 2020 at 20:42
  • 1
    $\begingroup$ I think this is addressed in R. L. Goodstein's Recursive number theory, where he develops the entire theory of primitive recursive functions and recursive functions in an absolutely minimalistic manner. Primitive recursive functions $\mathbb{N}^2\to\mathbb{N}$ are unavoidable but he carefully isolates what is essential about these. IIRC, the key thing is to get to $\max(m,n) = (m \mathop{\dot{\smash-}} n) + n$, where ${\dot{\smash-}}$ denotes truncated subtraction. $\endgroup$
    – François G. Dorais
    Commented Aug 3, 2020 at 21:28

1 Answer 1

Reset to default
4
$\begingroup$

Two papers of Julia Robinson seem to do the sort of thing you're looking for. Here are the MathSciNet data.

Robinson, Julia, General recursive functions, Proc. Amer. Math. Soc. 1, 703-718 (1950). ZBL0041.15101 MR0038912.

Robinson, Julia, A note on primitive recursive functions, Proc. Am. Math. Soc. 6, 667-670 (1955). ZBL0067.00204 MR0073536.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ For the benefit of those not familiar with these two papers, let me summarize the connections I see with my question. Robinson shows that there are some significant simplifications by working with functions with limited domains. First, "substitution" can be replaced with the simpler "composition" operation. Second, "primitive recursion" can be replaced with the simpler "repeat the function" operation. (That is, $g(x) = f^{\circ x}(0)=f(f(\cdots(f(0))\cdots))$.) Third, "$\mu$-minimization" can be replaced with the simpler "first inverse" operation. [to be continued...] $\endgroup$
    – Pace Nielsen
    Commented Aug 4, 2020 at 17:20
  • $\begingroup$ With respect to the basic, or initial, functions, things get a little muddier, but still (I believe) simpler. Robinson shows that a finite set of initial functions suffices. She shows that one function won't suffice, but shows that two will suffice. She gives numerous different lists of such functions. $\endgroup$
    – Pace Nielsen
    Commented Aug 4, 2020 at 17:43
  • $\begingroup$ Moreover, one can replace "repeat the function" with "add two functions" if working with recursive functions of more than one variable. etc... $\endgroup$
    – Pace Nielsen
    Commented Aug 4, 2020 at 17:48
  • $\begingroup$ The paper by Julia's husband Raphael, entitled "Primitive recursive functions" may also be useful to people. $\endgroup$
    – Pace Nielsen
    Commented Aug 4, 2020 at 18:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .