Impossibility proofs
Proofs that something is impossible (the solution of quintic equations in radicals, squaring the circle, etc) have been crucial in mathematics since they require a very precise understanding. This has also been true in computer science: the impossibility of calculating the halting function requires a precise formulation of computability.
I have been thinking about the impossibility of more particular constructions in practical programming languages. One I have in mind is the following: in C is it possible to write a function which given two pointers to functions returns a pointer to the composite function? I don't think so. People (for example, Yuri Gurevich) have claimed to give a precise meaning to C and hence an impossibility proof is conceivable. I would like to see such a proof (or an example program refuting my conjecture).
I have been thinking about the impossibility of more particular constructions in practical programming languages. One I have in mind is the following: in C is it possible to write a function which given two pointers to functions returns a pointer to the composite function? I don't think so. People (for example, Yuri Gurevich) have claimed to give a precise meaning to C and hence an impossibility proof is conceivable. I would like to see such a proof (or an example program refuting my conjecture).
Labels: computing
posted by Unknown at 3:04 AM
1 Comments:
Without a precise definition, it's hard to even ask the question.
For example, i doubt you'd accept a solution which squirrels the two function pointers away in globals and returns a pointer to a function which uses those globals to do the work. The reason is because its a one trick pony - a subsequent use must either invalidate the first returned value or fail.
However, i could easily declare many functions, each using a different pair of globals, and return a new one each time. Of course, there's a static limit to how many times you can call compose, but that will be true in any system without unbounded memory.
I'm not saying this is a counterexample - i think its further fuel to the fire that a precise definition is needed. Presumably it would make clear whether either of the above were considered acceptable.
Post a Comment
<< Home