|
|
|
|
|
|
by Retra
3207 days ago
|
|
|
I was reading very famous paper[1] today, and I stopped at the following: "To get an adequate definition of g [<] f we must therefore consider all possible algorithms for computing f."
You see, I was reading this paper because I'm currently looking into various ways of that the symmetries of Turing machines are modeled (I.e., the fact that a TM can emulate any other TM would seem to imply that the concept of an 'algorithm' must have fundamental features that are preserved across this kind of virtualization. Closely related to the concepts of an Oracle, a Non-deterministic TM, and recursion.)Now, this passage stood out to me because it seemed to be a set-theoretic, indirect phrasing of the exact symmetry I'm talking about. We have to consider all algorithms for computing f in order to recover the features that must be true for all f, and thus give identity to the notion of a general algorithm for f. Which in turn is used to establish theorems about such a general algorithm notion; (critically, its "relative complexity".) My point being that I would not have expressed this notion in set theoretic language because my intuition wants it expressed in algebraic language. Things are identified by their symmetries, and building theories around symmetries directly is more efficient and insightful than building theories around how those symmetries are embedded in set theory. And when I sit around thinking about how to design a good API or an efficient program, I want to do it by stating what must always be true about the problems I'm solving, in a high-level, abstract way. (I'm not so good at it in practice.) Set theory may be a simple model of many things, but it is only really intuitive for things that can be easily described in terms of unions and intersections. It is often just extra work elsewhere, at least if you have a frame of mind to see other ways. [1] https://www.cs.toronto.edu/~sacook/homepage/rabin_thesis.pdf |
|
|