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?

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

One can think of many other equivalent conventions. For example, you can treat the input as a bona fide natural number, and use the C programming language rather than the string-based Turing machine. All reasonable definitions will result in the same notion of computable function.

In terms of computational complexity, the exact encoding (or other convention) used can be important. For example, graphs can be encoded either using adjacency matrices or as adjacency lists, and this can affect the complexity of algorithms operation on them.

| cite | improve this answer | |
  • $\begingroup$ I find it deeply dissatisfying that it’s handled that way, but I guess I have to accept it. I mean, the convention implicitly assumes the extra structure I was missing. $\endgroup$ – k.stm Jan 29 '15 at 17:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.