Is there actually exist a computable function that take any argument （such as real number)?But how can it be proved？

Question

First，i do not understand why the recursion equals computable.when i was study the computable function，could it is defined in the real number set?(recursion function is defined in natural number.Finally,how can we prove there is exist a computable function that take any argument （such as real number) by turing machine or lambda calculus model?

Answer 1

Reese already discussed what Turing called "o-machines" ("o" for "oracle"); another standard way to describe them is as having two tapes, one of which is "read-only" and has the bits of the input real printed on it. With work, we can even view o-machines as coding functions from reals to reals - see e.g. computable analysis.

Another approach is that of Blum-Shub-Smale, or equivalently and slightly more generally Friedman. Roughly speaking, a Turing machine works over the "structure" $\{0, 1\}$ equipped with the "swap" function $s:0\mapsto 1, 1\mapsto 0$; the operations a Turing machine can perform on a single cell are either leave it unchanged, or apply swap. This can be generalized to describe Turing machines based on any first-order structure (say, a ring or field, as in the case Blum-Shub-Smale focus on). See e.g. the book Complexity and Real Computation. This approach has a number of differences from the more traditionally Turing-based computable analysis, mentioned above.

Answer 2

I don't know what you mean by "if the recursion is necessary for computable"; generally, "recursive" and "computable" are considered synonyms.

The Turing machine model can sort of handle real arguments - what you can do is write out the real number in binary on the machine's tape before the machine begins to run. But that means that you can't expect it to read the entire real, output another real, and then halt - in order to read the input real, it must take infinitely many steps. This means that, for example, a Turing machine would not be able to tell that $0.1111\ldots$ and $1.0000\ldots$ denote the same real number.

If you want a model of computation that can handle real numbers in the way that most casual observers would consider "natural" - that is, a model that allows you to input a real and get a real out, which allows checking whether two reals are equal or doing elementary operations like addition - you have to look at other approaches. If you're at a graduate level of education or higher, I'd recommend Effective Mathematics of the Uncountable as a resource for these; but it's a bit more advanced than I'd suggest for a beginner.

So, to answer your question more directly: If we are only considering the standard Turing machine model of computation - or, equivalently, lambda calculus - only natural numbers can be taken as arguments. This isn't as limiting as it sounds; since we can "encode" an entire sentence as a natural number, we can give a natural number that "represents" any real number you care to name (for example, perhaps $\pi$ is represented by the number $1609$, directly translating the letters PI into two-digit numbers).