Intelligent Agent Foundations Forumsign up / log in

[deleted]


by Alex Mennen 450 days ago | link

\(g\) can be a fiber of \(f\), since for each \(n\), \(x_n\) and \(y_n\) could be distance greater than \(n\) from the basepoint.

Example: let \(X:=\{x_n,y_n|n\in\mathbb{N}\}\), with \(d(x_n,x_m)=d(y_n,y_m)=d(x_n,y_m)=2|n-m|\) for \(n\neq m\) and \(d(x_n,y_n)=6^{-n}\). Let \(x_0\) be the basepoint (so that \((x_0,x_0)\) is the point you were calling “\(0\)”). Let \(g(x_n):=0\), \(g(y_n):=1\), \(f(z,w):=g(z)\), and \(h_n(r):=3^nr\).

I also don’t see how to even construct the function \(g\), or, relatedly, what you mean by “geometrically nicely”, but I guess it doesn’t matter.

Also, I’m not convinced that metric spaces with uniform continuity on bounded subsets is a better framework than topological spaces with continuity.

reply

by Alex Mennen 449 days ago | link

This is intended as a reply to David Simmons’s comment, which for some reason I can’t reply to directly.

In the new version of your proof, how do we know \(Y_k\) isn’t too close to \(X_l\) for some \(l>k\)? And how do we know that \(g\) is uniformly continuous on bounded subsets?

About continuity versus uniform continuity on bounded sets:

It seems to me that your point 1 is just a pithier version of your point 4, and that these points support paying attention to uniform continuity, rather than uniform continuity restricted to bounded sets. This version of the problem seems like it would be a less messy version of the “fixed modulus of continuity” version of the problem you mentioned (which I did not understand your solution to, but will look again later).

I’m not sure what you’re getting at about singularities in point 3. I wouldn’t have asked why you were considering uniform continuity on bounded sets instead of uniform continuity away from singularities (in fact, I don’t know what that means). I would ask, though, why uniform continuity on bounded sets instead of uniform continuity on compact sets? As you point out, the latter is the same as continuity.

Your point 2 is completely wrong, and in fact this is the primary reason I was convinced that continuity is a better thing to pay attention to than uniform continuity on bounded sets. The type of object you are describing is an effective Polish space that remembers its metric. Typically, descriptive set theorists forget the metric, and the isomorphisms between Polish spaces are homeomorphisms (and the isomorphisms between effective Polish spaces are computable homeomorphisms). Changing the metric in a computably homeomorphic way does not change what can be done when points are represented as descending chains of basic open sets with singleton intersection. So the thing you described was really topological rather than metric in nature, even though it involves introducing a metric in the setup. I am not aware of any notions of computability in metric spaces in which the metric matters in the way you are suggesting. It is not true that uniform continuity gives you an algorithm for computing the function. As a counterexample, let \(a\) be an uncomputable number, and let \(f:\mathbb{R}\rightarrow\mathbb{R}\) be given by \(f(x)=a\) for every \(x\). \(f\) is clearly uniformly continuous, but not computable. It is also not true that uniform continuity is necessary in order for the function to be computable. For instance, \(\sin(1/x)\) is computable on \((0,1]\). Of course, \((0,1]\) is not complete, but for another example, consider an effective infinite-dimensional Hilbert space, and let \(\{e_n|n\in\mathbb{N}\}\) be an effective orthonormal basis. Let \(f_n(x):=\max(0,\frac{1}{2}-\Vert x-e_n\Vert)\). This sequence of functions is computable, they have disjoint support, and for any point, a sufficiently small neighborhood around it will be disjoint from the supports of all but at most one of these functions. Thus \(f(x):=\sum_n nf_n(x)\) is computable, but of course it is not uniformly continuous on the unit ball, which is bounded. However, it is true that every computable function is continuous, and conversely, every continuous function is computable with respect to some oracle. Of course, we really want computability, not computability with respect to some oracle, but this still seems to show that continuity is at least a good metaphor for computability, whereas uniform continuity on bounded sets doesn’t seem so to me.

Of course, all this about continuity as a metaphor for computability makes the most sense in the context of Polish spaces, and we can only talk about actual computability in the context of effective Polish spaces. Scott’s problem involves a space \(X\) and the exponential \([0,1]^X\). If \(X\) is a locally compact Polish space, then \([0,1]^X\) is also Polish. I think that this might be necessary (that is, if \(X\) and \([0,1]^X\) are Polish, then \(X\) is locally compact), although I’m not sure. If so, and if your proof is correct, it seems plausible that your proof could be adapted to show that there is no locally compact Polish space with the property that Scott was looking for, and that would show that there is no solution to the problem in which \(X\) and \([0,1]^X\) are both Polish spaces, and hence no computable solution, if computability is formalized as in effective descriptive set theory.

reply



NEW LINKS

NEW POSTS

NEW DISCUSSION POSTS

RECENT COMMENTS

There should be a chat icon
by Alex Mennen on Meta: IAFF vs LessWrong | 0 likes

Apparently "You must be
by Jessica Taylor on Meta: IAFF vs LessWrong | 1 like

There is a replacement for
by Alex Mennen on Meta: IAFF vs LessWrong | 1 like

Regarding the physical
by Vadim Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

I think that we should expect
by Vadim Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

I think I understand your
by Jessica Taylor on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

This seems like a hack. The
by Jessica Taylor on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

After thinking some more,
by Vadim Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

Yes, I think that we're
by Vadim Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

My intuition is that it must
by Vadim Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

To first approximation, a
by Vadim Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

Actually, I *am* including
by Vadim Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

Yeah, when I went back and
by Alex Appel on Optimal and Causal Counterfactual Worlds | 0 likes

> Well, we could give up on
by Jessica Taylor on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

> For another thing, consider
by Jessica Taylor on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

RSS

Privacy & Terms