1

In an (otherwise very enlightening) answer to another question of mine the question came up

What functions are allowed as building blocks for computable functions?

I was astonished that there is a matter of discussion: for me a computable function $f: \mathbb{N} \rightarrow \mathbb{N}$ has been just any $\mu$-recursive function. And there has not been a discussion about fancy "allowed building blocks" like $x\rightarrow \sqrt x$.

How do I have to deal with this objection?

If I want to remain in the realm of natural numbers, (why) do I have to consider "building blocks" like $x\rightarrow \sqrt x$, which may yield intermediate results not finitely expressible by natural numbers (without introducing new symbols)?

Community
  • 1
Hans-Peter Stricker
  • 18,159
  • Why does $x\mapsto\sqrt x$, in the context of the natural number not $\mu$-recursive? $$F(x)=\mu_y(y\cdot y=x)$$ – Asaf Karagila Jun 26 '14 at 23:35
  • Because it is not a total function? Do I have to consider arbitrary - not necessarily total = partial - functions? – Hans-Peter Stricker Jun 26 '14 at 23:52
  • 1
    In developing the theory, it is (was?) traditional to make the collection of "basic" functions very tiny, and let the tools (primitive recursion, minimalization) take care of the rest. Of course all functions are from $\mathbb{N}^k$ to $\mathbb{N}$. – André Nicolas Jun 26 '14 at 23:52
  • I don't understand your question, then. If you want to stay in the context of the natural numbers, what does $\sqrt2$ mean? – Asaf Karagila Jun 26 '14 at 23:53
  • It was not me who introduced $\sqrt{x}$. That's what my question is about. – Hans-Peter Stricker Jun 26 '14 at 23:55
  • The general theory of computable functions is intimately tied to partial functions. But when you say $\sqrt{x}$ do you mean the partial function $\mathbb{N}\to\mathbb{N}$, or some other, total function? Is there something special about $\sqrt{x}$ that makes the partial computable function $f(x,y) = x-y$ a worse example for your purposes? Those answers may help me answer the original question. – Carl Mummert Jun 27 '14 at 01:08
  • I just was irritated by user Sten's remark with respect to my original question: "The answer to this question heavily depends on what functions are allowed as building blocks [...] If we assume that $x\rightarrow x^2$ and $x\rightarrow \sqrt{x}$ are allowed [...]" When the partial function $x\rightarrow \sqrt{x}$ is perfectly OK I do not understand what Sten means with "depends heavily". – Hans-Peter Stricker Jun 27 '14 at 07:19

0 Answers0