Very interesting. Thanks for the insight.
Tim Washington Interruptsoftware.ca 416.843.9060 On Sat, Jul 28, 2012 at 6:40 AM, nicolas.o...@gmail.com < nicolas.o...@gmail.com> wrote: > > 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 > -- 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
