> There is indeed an infinite number of functions, or relationships between > natural numbers. I don't think that means that that any one of those > relationships is not computable because it is within the range of infinite > functions. The countable parts of a program can still accept an infinite > amount of input, like Turing's machine. So the best I can say is that all > functions (relationships between natural numbers) can be computable, but > humans may or may not have figured out a way to represent all natural > numbers.
Some of these functions/relations are known to be not computable. For example a function taking the "source code" of a program (in any Turing-complete language) and returning 1 if the program stops or 0 if it runs forever. (the halting problem http://en.wikipedia.org/wiki/Halting_problem ) This functions is mathematically perfectly well defined, but it can be proved it can not be computed. (No Turing machine can compute this function. It is important to understand it is not a complexity problem. It does not mean such a program would be too slow to be useful. It really means such a program can not exist.) -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
