Why Has None of Computer Science been Formalized?
in [Logic]
|
Prev: Simple yet Profound Metatheorem
Next: Modal Logic
From: Patricia Shanahan on 18 Sep 2006 09:56 Steven Zenith wrote: > Charlie-Boo wrote: > >>> In computer science the specification of such functions are constrained >>> by pragmatics. In computer science programs executing such functions >>> have desirable formal properties - termination is one of them. >> You said (about 10 times) that the function doesn't terminate. How >> do you define a function terminating? > > Perhaps I was unclear. A function terminates when it produces a result > (and one might possibly add "and performs no further action"). > > In CSP/Occam, it is when any construction is complete (i.e., computed) > or it could be stated as when any subsequent behavior in the trace of > the function is SKIP, not STOP. I think you and Charlie-Boo are using the same term, "function", for two very different things. In mathematics, a function is a relation between elements of its domain and range, such that each element of the domain relates to exactly one element of the range. It is quite meaningless to talk about terminating or not terminating for a mathematical function. I think that is what Charlie-Boo means by "function". On the other hand, in some programming languages, "function" means a subprogram that, if it terminates, produces a result, not just side effects. Is that what you mean by "function"? The two are related, because a function (subprogram) is the natural representation in a computer program of a recursive function (mathematics). However, the subprogram sense includes non-terminating subprograms that do not implement a mathematical function. Patricia
From: Patricia Shanahan on 18 Sep 2006 10:00 Steven Zenith wrote: > Charlie-Boo wrote: >> How about zero times the square root of 2? >> >> "Computable" refers to manipulating recursively enumerable sets (e.g. >> integers or character strings), not the real numbers. >> >> If one wants a program to derive properties of the square roots, then >> one would represent them as formulas (not infinite decimal expansions.) >> We can even write its value to any (finite) number of decimal places. > > Since when is root 2 a real number? Since 2 was a non-negative real number. What do you think root 2 should be, if not a real number, and why? Patricia
From: Charlie-Boo on 18 Sep 2006 10:03 Steven Zenith wrote: > Are you aware that floating point units exist and that most language > libraries use the standards that they implement? None of them do real > number arithmetic and over the years those standards have changed. They > will again. Every programming language can perform real number arithmetic to any given number of decimal places. Every time you refer to "most programming languages" you are not referring to Computer Science. The first step in Computer Science is to realize that all programming languages are equivalent, and to abstract the notion of all programming languages to the set of recursive functions. This is due to the work of Godel, Post, Church, Turing and other logicians in the 1930's. C-B > You are boring me now. > > With respect, > Steven
From: Patricia Shanahan on 18 Sep 2006 10:13 Steven Zenith wrote: > Charlie-Boo wrote: >> How about zero times the square root of 2? > > That is an interesting case. And the answer in practice will be, it > depends (an optimizer may remove the expression, an interpreter may > disregard the function root 2 - all on the basis of the zero). > > But the answer formally is no, it does not terminate - because the > function that computes the root of 2 does not terminate. Don't forget the possibility of symbolic mathematical languages, in which numbers like the square root of 2 have representations and can be used in expressions. Here is a fragment of a Matlab session: EDU>> x = sym(sqrt(2)) x = sqrt(2) EDU>> 0*x ans = 0 EDU>> x*x ans = 2 Clearly there was no problem storing a representation of the square root of 2, or exactly evaluating its square and getting the integer result. Functions that compute the square root of 2, and do arithmetic with it, can and do terminate if they have a suitable way of representing it. Calculating the decimal (or any other integer radix) representation of the square root of 2 is a different matter. The best we can do is calculate it to any arbitrary required precision. Patricia
From: Charlie-Boo on 18 Sep 2006 10:15
Steven Zenith wrote: > Charlie-Boo wrote: > > > Every programming language can implement a function to calculate square > > root to a given number of places. It has nothing to do with > > "performance constraints". > > I used a function that calculates the root of 2 as a simple example of > a formally non-terminating function. Functions don't terminate. Programs terminate (or not.) Functions are defined (or not.) > The root of 2 is not a real number, Yes it is. What do you think it is? > so in most languages direct use of the number would formally > produce a type error, How can you "use the number in most languages"? How would that work, exactly? > I did then observe that even if we picked a number of decimal points, > either implicitly or explicitly, there was no guarantee that the value > could be computed on any computer No, all computers have the same computing power. > If you choose, as you suggest, to implement root 2 in a particular way > I would have to ask you if that way meets the pragmatic understanding > of the programmer - an arbitrary selection of precision may not be > compatible with the programmer's expectation. It is just a fact of life that real number arithmetic can be calculated to any given number of decimal places, or simulated to complete precision by symbolically representing the expressions e.g. the square root of 2. It has nothing to do with the programmer's "expectations". > The fact that this function is trivial example is not the point here - > it raises important questions. Oh really? Such as how you became so incredibly confused over such fundamental concepts as real numbers, functions, and the equivalence of programming languages? C-B > With respect, > Steven |