{\huge You Think We Have Problems}

Problems that are really hard \vspace{.5in}

Loki is a Jötunn or \c{\'O}ss in Norse mythology, who, legend has it, once made a bet with some dwarves. He bet his head, then lost the bet, and almost really lost his head----more on that in a moment.

Today Ken and I wanted to look forward to the new year, and talk about what might happen in the future.

We have many times before discussed the future, and in particular what might happen to some of the major problems that we have. For instance:

• The power of nondeterministic polynomial time computations---of course, the P=NP question.
• The power of quantum computers.
• The difficulty of some of our favorite problems such as Graph Isomorphism---probably largely resolved now---to Integer Factoring, probably still wide open---to lattice problems.

But along the way to thinking about our open problems we looked around at other fields of science. There are plenty of hard open questions in physics, chemistry, and other areas. But the area that seems to have problems that are easy to state, but hard to resolve, is Philosophy. So we thought that instead of a predictions post it might be interesting to look at just a few of their questions. Perhaps taking a computational point of view could help them get resolved? Besides we are terrible at predicting the future anyway.

Philosophy

Details on the following problems and others can be looked up at the online Stanford Encyclopedia of Philosophy (SEP), but for this intro post we will stay with the shorter descriptions in Wikipedia's article on unsolved problems. We start with its disclaimer:

This is a list of some of the major unsolved problems in philosophy. Clearly, unsolved philosophical problems exist in the lay sense (e.g. ``What is the meaning of life?", ``Where did we come from?", ``What is reality?", etc.). However, professional philosophers generally accord serious philosophical problems specific names or questions, which indicate a particular method of attack or line of reasoning. As a result, broad and untenable topics become manageable. It would therefore be beyond the scope of this article to categorize ``life" (and similar vague categories) as an unsolved philosophical problem.

So let's take a look at a few open problem that arise in philosophy, but are not impossible. We will pick ones that seem related to our field and also are perhaps attackable by computational methods. Hence we avoid ``what is reality?'' and even ``what is consciousness?''

The Trilemma Problem

The Münchhausen trilemma, also called Agrippa's trilemma, is not a new type of ``lemma.'' Rather it is a claim that it is impossible to prove anything with certainty. This goes way beyond any incompleteness theorem, and applies to math as well as logic.

The argument is simple: any proof must fail because of one of the following:

1. the proof use circular reasoning;
2. or it uses infinite regress;
3. or it rests on unproved axioms.

This seems a pretty strong argument to me---is it certain? Of course by the argument that is impossible. So maybe the argument fails, in which case there might be statements that are indeed certain. I am confused.

Sorites Paradox

Let's return to explain Loki's problem. Legend has it that he made a bet with dwarves, and should he lose the bet they would get his head. Sounds like a pretty scary bet---I hope it was not on the Jets to make the playoffs in the NFL. He lost the bet. And the dwarves came to collect. Loki saved himself by arguing that they could have his head, but they could not take any of his neck. The problem then became:

Where did his neck begin and his head end?

Since neither side could agree on exactly where the neck and head met exactly, Loki survived.

There are many other versions of this same issue.

Fred can never grow a beard. Fred is clean-shaven now. If a person has no beard, one more day of growth will not cause them to have a beard. Therefore Fred can never grow a beard.

Another one is:

I can lift any amount of sand. Imagine grains of sand in a bag. I can lift the bag when it contains one grain of sand. If I can lift the bag with $latex {N}&fg=000000$ grains of sand then I can certainly lift it with $latex {N+1}&fg=000000$ grains of sand (for it is absurd to think I can lift $latex {N}&fg=000000$ grains but adding a single grain makes it too heavy to lift). Therefore, I can lift the bag when it has any number of grains of sand, even if it has five tons of sand.

Even popular culture uses this paradox. Samuel Beckett has one character say this line in his play Endgame: ``Grain upon grain, one by one, and one day, suddenly, there's a heap, a little heap, the impossible heap.''

This ``paradox'' is essentially Sperner's lemma, which is due to Emanuel Sperner. It can be viewed as a combinatorial analog of the Brouwer fixed point theorem---one of my favorite theorems. In one dimension it says that if you paint the numbers $latex {1}&fg=000000$ to $latex {N>1}&fg=000000$ red and green and start with red and end with green, then there must be an $latex {i}&fg=000000$ so $latex {i}&fg=000000$ is red and $latex {i+1}&fg=000000$ is green. Thus there is a definite place where the line turns from red to green. Is it a paradox that a philosophy ``paradox'' is a lemma in mathematics?

We can make one more observation. When it comes to writing and verifying software systems, sorites matters more than an issue of words. When should adding an object to a collection be considered to change the collection's properties? Perhaps such depth is why sorites makes this list of ``Ten Great Unsolved Problems'' on the whole. Does adding one more good observation to a good blog post make it still a good blog post?

Molyneux's Problem

The Molyneux problem was first stated by William Molyneux to John Locke in the 17th century. Imagine a person born blind and who is able to tell a cube from a sphere. Imagine now that their sight is restored, somehow. Will they be able to tell a cube from a sphere solely by sight without touching them?

This problem was widely discussed after Locke added it to the second edition of his Essay Concerning Human Understanding. It is certainly an interesting question. Moreover, today there are cases of people who have had their sight repaired. So perhaps this question will be solved soon. In any event it would be nice to understand the brain enough to know what would happen. Will everyone be able to tell the objects apart? Or will just some? The Stanford article says much more about experiments through 2011 but without a clear resolution.

Counterfactuals

Wikipedia's discussion limits this to statements of the form ``If X then Y'' where X is false in our world. In logic such statements are true, but in a way that is unsatisfying because the relationship between X and Y is unexamined. The theoretical response is to enlarge our world to a set of possible worlds which may include some worlds $latex {W}&fg=000000$ in which X is true and Y is assessable. Concepts of necessity and possibility---$latex {\Box}&fg=000000$ and $latex {\diamondsuit}&fg=000000$ in modal logic---quantify the ranges of $latex {W}&fg=000000$ for such statements.

This still leaves the problem of $latex {W}&fg=000000$ having inferior status to our ``real world.'' The quantum computing progenitor David Deutsch, in his philosophical book The Fabric of Reality, suggests that maybe those $latex {W}&fg=000000$ don't have inferior status. His book is subtitled The Science of Parallel Universes---and its Implications. He tries to be quantitative with these parallel worlds in ways that go beyond the tools of modal logic. Again, it is possible that insights from computation may continue to help in judging his and the older frameworks.

Open Problems

Can we possibly shed computational light on any of these problems?