# What does it mean for a function $f\colon M → N$ between *any* sets $M, N$ to be computable?

In our lecture notes on lamdba calculus, I encountered the sentence:

Let $M$ be a set and $f\colon ℕ → M$ be computable.

Does this even make sense? Don’t we need aditional structure on $ℕ$ and $M$ to talk about computability and decidability? How can I make sense of this statement?

• I'd say the range of $f$ must be enumerable and each of its values computable. – reinierpost Jan 29 '15 at 12:11
• What does it mean for $M$ to be enumerable and what does it mean for its values to be computable? – k.stm Jan 29 '15 at 13:52
• Have you looked it up in Wikipedia or in a textbook? – reinierpost Jan 29 '15 at 15:00
• @reinierpost Wikipedia only mentions a definition for computability for functions $Σ^* → Σ^*$ or $ℕ → ℕ$. – k.stm Jan 29 '15 at 17:40

One convention is as follows. Your sets $\mathbb{N}$ and $M$ come with (injective) encodings as strings. In that way, you can think of $\mathbb{N}$ and $M$ simply as subsets of $\Sigma^*$.