Sorted by New

Yeah, I think the engineer intuition is the bottleneck I'm pointing at here.

Thoughts from a Two Boxer

I think people make decisions based on accurate models of other people all the time. I think of Newcomb's problem as the limiting case where Omega has extremely accurate predictions, but that the solution is still relevant even when "Omega" is only 60% likely to guess correctly. A fun illustration of a computer program capable of predicting (most) humans this accurately is the Aaronson oracle.

This post has caused me to update my probability of this kind of scenario!

Another issue related to the information leakage: in the industrial revolution era, 30 years was plenty of time for people to understand and replicate leaked or stolen knowledge. But if the slower team managed to obtain the leading team's source code, it seems plausible that 3 years, or especially 0.3 years, would not be enough time to learn how to use that information as skillfully as the leading team can.

Topological Fixed Point Exercises

Awesome! I was hoping that there would be a way to do this!

Diagonalization Fixed Point Exercises

Currying doesn't preserve surjectivity. As a simple example, you can easily find a surjective function , but there are no surjective functions .

Iteration Fixed Point Exercises

Ex 6:

If at any point , then we're done. So assume that we get a strict increase each time up to . Since there are only elements in the entire poset, and is monotone, has to equal .

Ex 7:

For a limit ordinal , define as the least upper bound of for all . If , then the set for is a set of size that maps into a set of size by taking the value of the element. Since there are no injections between these sets, there must be two ordinals such that. Since is monotone, that implies that for every ordinal , and thus is a fixed point. Since this proves the exercise.

Ex 8:

Starting from , we can create a fixed point via iteration by taking , and iterating times as demonstrated in Ex 7. Call this fixed point . Suppose there was a fixed point such that and . Then at some point , but , which breaks the monotonicity of unless . So generated this way is always the smallest fixed point greater than .

Say we have fixed points . Then let be the least upper bound of , and generate a fixed point from . So will be greater than each element of since is monotone, and is the smallest such fixed point as shown in the above paragraph. So the poset of fixed points is semi-complete with upper bounds.

Now take our fixed points again. Now let be the greatest lower bound of , and generate a fixed point . Since and is monotonic, , and so is a lower bound of . It has to be the greatest such bound because itself is already the greatest such bound in our poset, and is monotonic.

Thus the lattice of fixed points has all least upper bounds and all greatest lower bounds, and is thus complete!

Diagonalization Fixed Point Exercises

Ex 8: (in Python, using a reversal function)

def f(s):
return s[::-1]

dlmt = '"""'
code = """def f(s):
return s[::-1]

dlmt = '{}'
code = {}{}{}
code = code.format(dlmt, dlmt, code, dlmt)
print(f(code))"""
code = code.format(dlmt, dlmt, code, dlmt)
print(f(code))

Topological Fixed Point Exercises

You can use 1d-Sperner to deal with all the cases effectively.

Topological Fixed Point Exercises

Found a nice proof for Sperner's lemma (#9):

First some definitions. Call a d-simplex with vertices colored in (d+1) different colored chromatic. Call the parity of the number of chromatic simplices the chromatic parity.

It's easier to prove the following generalization: Take a complex of d-simplices that form a d-sphere: then any (d+1)-coloring of the vertices will have even chromatic parity.

Proof by induction on d:

Base d=-1: vacuously true.

Assume true for d-1: Say you have an arbitrary complex of d-simplices forming a d-sphere, with an arbitrary d+1-coloring. Choose a vertex. W.L.O.G. we will call the color of the chosen vertex blue.

Take the complex of simplices that contain this vertex. Since a sphere has no boundary or branches, this complex will be a d-ball. Delete the chosen vertex, and keep only the opposite (d-1)-simplices that are left, which will form a (d-1)-sphere, call it the shell.

We need to choose a second color, say red. We'll call a (d-1)-simplex with vertices of all d+1 colors except red an R-chromatic face, and similarly with blue.

Now, replace all the red vertices in the shell with blue vertices, so that the shell is now R-chromatic. By induction it has an even number of R-chromatic faces. Consider what happens when we reconvert a vertex on the shell back to red: since the vertex was previously blue, any R-chromatic faces will get turned into B-chromatic faces. Let r be the number of R-chromatic faces on the shell, and b be the number of B-chromatic faces. The parity of r-b will remain even as we continue this process.

Let's go back to the vertex in the center of the shell. All currently chromatic simplices with this vertex have opposite faces which are B-chromatic, since this vertex is blue. We'll flip the vertex to red, which destroys chromatic simplices with opposite B-chromatic faces and creates chromatic simplices with opposite R-chromatic faces. Since r-b is even, the chromatic parity is preserved!

Since we've shown that arbitrary recoloring of vertices preserves the chromatic parity, it's clear that the chromatic parity will be even for any coloring.

Corollary: Sperner's lemma

Start with a d-simplex which has been divided into d-simplices, and where each face of the large simplex has one color which vertices on it are forbidden from taking. Take a point of each color, and match it with a face of the simplex that that color is allowed on. Then connect that vertex to each point on that face. This will create a bunch of non-chromatic simplices. Finally, create a simplex of all of the new points. This will create one chromatic simplex.

This will form a d-sphere, and thus will have an even chromatic parity. That means the original simplex must have had odd chromatic parity.