Why Has None of Computer Science been Formalized?
in [Logic]
|
Prev: Simple yet Profound Metatheorem
Next: Modal Logic
From: Steven Zenith on 19 Sep 2006 21:40 stephen(a)nomail.com wrote: > > I am using the term function in the computer science sense since the > > question has to do with the formalization of computer science and we > > are discussing functions in programs. In any case, a computer science > > function and a function in the mathematical sense (a map) are formally > > equivalent in that a CS function is the map of the arguments to the > > results. > > No, they are not formally equivalent, as there exist uncomputable > functions. A mathematical function is a mapping from one set > to another set. Not all mappings are uncomputable. The Halting > Function is the classic example. There is no computer science > function that is equivalent to this mathematical function. Not all mappings are computable. I understand. But there are uncomputable functions on both sides. You are saying that there is no equivalent of the Halting Function in mathematics? You may well be right. I guess this is borderline - was Turing a computer scientist or a mathematician? With respect, Steven
From: stephen on 19 Sep 2006 22:01 In sci.math Steven Zenith <stevenzenith(a)gmail.com> wrote: > stephen(a)nomail.com wrote: >> > I am using the term function in the computer science sense since the >> > question has to do with the formalization of computer science and we >> > are discussing functions in programs. In any case, a computer science >> > function and a function in the mathematical sense (a map) are formally >> > equivalent in that a CS function is the map of the arguments to the >> > results. >> >> No, they are not formally equivalent, as there exist uncomputable >> functions. A mathematical function is a mapping from one set >> to another set. Not all mappings are uncomputable. The Halting >> Function is the classic example. There is no computer science >> function that is equivalent to this mathematical function. > Not all mappings are computable. I understand. But there are > uncomputable functions on both sides. You are saying that there is no > equivalent of the Halting Function in mathematics? You may well be > right. I guess this is borderline - was Turing a computer scientist or > a mathematician? > With respect, > Steven No, I mean that there is no computer function, as in a piece of code that takes an input and produces an output, that computes the Halting Function. You seem to be defining a "computer science function" as a piece of code, e.g. int f(int x, int y) { // do stuff return value; } Only a subset (in fact a very small subset) of mathematical functions have a corresponding piece of code. The two types of functions are not formally equivalent. Stephen
From: Steven Zenith on 20 Sep 2006 00:47 stephen(a)nomail.com wrote: > No, I mean that there is no computer function, as in a piece > of code that takes an input and produces an output, that > computes the Halting Function. There are two things to observe here. Firstly, all formal, executable, side effect free, CS functions are equivalent to mathematical functions. You would say they are a subset of the mathematical functions I expect. Secondly, the class of functions that do not compute remain functions in theoretical computer science. The Halting Function that is not computable on any Turing machine is a part of the foundations of computer science I would suggest. That is, from a formal program validation and verification stand point non-computable functions would fail, but they would be recognized. With respect, Steven
From: Steven Zenith on 20 Sep 2006 01:10 Charlie-Boo wrote: > Steven Zenith wrote: > > Charlie-Boo wrote: > > > Economics has nothing to do with theoretical Computer Science. > > > If only that were true :-) > > What in the world does economics have to do with theoretical Computer > Science? Get real. Who is it that funds your research? What motivates that funding? Who is it that commits the resources to implement your formal systems? Who is it that decides to apply your techniques rather than those of another? Why do some techniques get applied even though they are clearly inferior to others? That's economics. With respect, Steven
From: Steven Zenith on 20 Sep 2006 01:15
Steven Zenith wrote: > ..., but they would be recognized. Perhaps "recognized" is the wrong word here since that infers an ability I am uncertain of. "acknowledged" may be a more suitable term. With respect, Steven |