Charlie Stromeyer jr.
Registered: Not Yet
topology-limits-computability via NKS
Hi, I have previously considered the role of topology in various contexts such as M-theory (string theory physics) in which topology is thought to be emergent or relative. Also, later, I wil try to use an NKS perspective to examine the topology and networks of biological systems already studied by people such as Albert Barabasi. First, though, here is a speculation I had seven years ago about the potential for topology in computability theory which I have not really thought about since but will now begin to dwell upon. Do you know if anyone has thought about these kinds of concepts below from an NKS perspective? Thanks.
In the magazine Science  there was a brief mention by B. Citra describing a suggestion from Michael Freedman for approaching a proof that hard problems are, indeed, hard. First, think loosely of the idea of a "limit" as the residue of an infinite process. Then, Freedman wanted to "extend the concept of computation to include infinitely large problems, each one a limit of increasingly large, finite instances of the problem. The trick is to define the extension so that a particular criterion holds: Whenever the original computational problem has a polynomial time algorithm, each infinite example has a solution. The hope, then, is that for problems like the Traveling Salesman Problem [which is NP complete], there will be infinitely large examples without solution." Freedman then wanted to find out how to mathematically define the notion of "limit" for this case.
When this piece in Science first appeared, I tried to think about the "cardinality" and "ordinality" of Freedman's proposed sequence of increasingly large, finite instances of a problem, wondering if topology could be used to help define the convergence and limit of this sequence. At the time, I emailed Freedman these possible ideas (I didn't come up with a concrete realization, but Freedman's PNAS paper  at least introduces the concept of "ultrafilter limits" which may be a step forward):
1) Each different computational problem should have a unique infinite example of itself, i.e. each computational problem should have a unique limit. Perhaps this is somehow analogous to the statement that if a sequence of numbers has a limit it is unique, or more generally, that the space X is Hausdorff (e.g. a metric space) if and only if each filter in X has at most one limit.
2) The symbols +infinity & -infinity can be added to the set R of all real numbers which then creates the topological space R' and R' is the set of extended real numbers. Infinity can exist within a topological space and, likewise, one might want both the infinite and finite instances of a computational problem to exist in the same "space". (A sequence which diverges to infinity within a number system (e.g. R) can be mapped into a topological space as a family of points called a net or a Moore-Smith sequence, and this net can converge to infinity).
3) The notion of "convergence" can be extended to the case of generalized sequences where the index moves over a directed set, and the terms are in topological space. The convergence of nets and that of filters can be defined in a topological space X and, conversely, this convergence can define a toplogy of X.
4) A point at infinity, i.e. an ideal element, can be added to a topological space via Alexandrov's theorem, e.g. one point-compactification. This procedure makes infinity real within the topological space as a limit point, a point which must share at least one property in common with the points of the net.
5) Also, see the paper  by M. Sipser about a topological view of some problems in complexity theory. I wonder if such speculations about sequences and limits might also be relevant for trying to understand intermediate Turing degrees (from recursion theory).
P.S. Freedman also suggested that the concept of "limits" might be useful for some unsolved problems in geometry. Non-commutative geometry includes concepts of limits and one might look, say, at possibly (non-trivial) classical limits of non classical (e.g. bicovariant) calculi on a topological space.
 Science, vol.275, page 1570, March 14, 1997. (This brief piece does not say anything additional to what I have already written in the first paragraph above)
 M. Freedman, Proc. Natl. Acad. Sci. USA, Vol. 95, pp. 95-97, January 1998.
 Sipser, M. (1985) in "Theory of Algorithms", eds. Lovasz, L. & Szemeredi, E., Colloq. Math. Soc. Janos Bolyai (North-Holland, Amsterdam), Vol. 44, pp. 387-391.
Report this post to a moderator | IP: Logged