# You Think We Have Problems

*Some hard problems in philosophy*

Wikimedia Commons source |

Loki is a Jötunn or 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:

- the proof uses circular reasoning; or
- it uses infinite regress; 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

Ngrains of sand then I can certainly lift it withN+1 grains of sand (for it is absurd to think I can liftNgrains 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 simply that if *N* > 1 and you paint the numbers 1 to *N* red and green and start with red and end with green, then there must be an *i* so that *i* is red and *i*+1 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 *W* in which *X* is true and *Y* is assessable. Concepts of *necessity* and *possibility*— and in modal logic—quantify the ranges of *W* for such statements.

This still leaves the problem of *W* 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 *W* 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?

I used to think about the heap problem a lot when I was programming and I decided the heap quits being a heap as soon as you remove one grain because then it becomes two heaps.

Molyneux’s Problem was answered negatively by Charles Chaplin. At the end of the film City Lights, the ex-blind flower seller could only recognize Charlie after she touched him, not when she first saw him. Is this consistent with what happens when a blind person acquires, or reacquires the capacity to see?

Jon, thanks; Dick and I agree :-). I resisted temptation to add a crack that as for my academic interest in philosophy, finding that

soritesis considered a “problem” was the straw that broke the camel’s back.One longer thing left out was a paragraph on Agrippa’s trilemma (I like that term more than the image of Baron Münchhausen lifting himself and his horse out of a mire by his hair):

“Ken notes that the ancient Greek concept of

logos, which underlieslogic, has fluctuated in meaning between a ground for an argument by persuasion and the process of reasoned argument itself. In the domain of mathematical reasoning he thinkslogosis best identified with what logicians call amodel. He then sees Agrippa’s trilemma as the question of whether logic itself presumes some over-arching and unique model. When the trilemma is extended to the study of nature and human moral and personal domains it becomes the question of whether a unique model applies. He regards the practical solution as being that the writer and reader of an argument must first have agreed on a model as the basis for going forward—though it is perhaps often the other way: we spin a nice argument and try to use that to justify a particularlogos.”But I thought this maybe naive and better to leave Dick’s crisp ending undisturbed (not even mentioning a similar paradox about the grounds for accepting the doctrine of logical positivism). I do think the writer of 1 John was purposed toward this philosophical account of

logos: Christ as the unique model for reckoning not only the human domain but even nature.The Pascal sorting of the sorites played on moves beteeen heaps and stacks, but I’ve forgotten the details of that particular epiphany. The whole-system-theoretic point is clear enough though — the system as a whole makes a discrete transition from one state of organization to another.

One classical tradition views logic as a normative science, the one whose object is truth. This puts it on a par with ethics, whose object is justice or morality in action, and aesthetics, whose object is beauty or the admirable in itself.

The pragmatic spin on this line of thinking views logic, ethics, and aesthetics as a concentric series of normative sciences, each a subdiscipline of the next. Logic tells us how we ought to conduct our reasoning in order to achieve the goals of reasoning in general. Thus logic is a special application of ethics. Ethics tells us how we ought to conduct our activities in general in order to achieve the good appropriate to each enterprise. What makes the difference between a normative science and a prescriptive dogma is whether this telling is based on actual inquiry into the relationship of conduct to result, or not.

Here’s a bit more I wrote on this a long time ago in a galaxy not far away —

☞ Logic, Ethics, Aesthetics

Interesting work. Why do you think the Greeks became obsessed with truth? Is there a difference with beauty if Plato thought an ideal society would exclude art and artist? Aristotle wrote that, as he became older, he came to love the myth more and more.

Making reality our friend is necessary to survival and finding good descriptions of reality is the better part of doing that, so I don’t think we have any less interest in truth than the Ancients. From what I remember of him, Plato had specific objections to specific styles of art, poetry, or their interpretation, and hardly painted art in general with a broad brush. Indeed, there is a Pythagorean tradition that reads

The Republicas a metaphorical treatise on musical theory, applied no doubt to achieving harmony in society. Truth in fiction and myth is a matter of interpretation, and come to think of it, that’s not essentially different from truth in more literal forms of expression.Of course, Papadamitriou’s subclasses of TFNP based on non-constructive proof are one attempt to give some of these ideas meaning. You mention Sperner’s lemma, which corresponds to PPAD. The Sorites paradox could correspond to the following: we have a pair of polynomial-time computable functions that compute a successor and a predecessor in a consistent way, except for a first and last element. We also have a polynomial-time function c from these elements to “red” and “green”. If c(first)=red and c(last)=greed, find an x such that c(x)=red but c(succ(x))=green.

Cris, thanks! To elaborate the last part a bit for others: the domain (say {0,1}^n) of c has exponential size. Dick meant that the line changed only once, in which case the change point can be found in O(n) probes by binary search. But yes indeed if it can switch back and forth and you only have a probe for the color of the queried string then finding a place where c(x) is red and c(succ(x)) is green can be hard, hmmm…

Dear Prof Lipton,

Dear Prof Regan,

You have been discussing paradoxes hundreds of times. You never considered the Kleene-Rosser Paradox of Lambda-Calculus. On the other hand, you want to discover any computational nature of such and such paradoxes.

The Kleene-Rosser paradox does the job you are looking for. A full fledged computational paradox.

Isn’t this what you are looking for?

best,

Rafee Kamouna.

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 N grains of sand then I can certainly lift it with N+1 grains of sand (for it is absurd to think I can lift N grains but adding a single grain makes it too heavy to lift).Among people who actually lift things, the reliability of being able to lift starts declining as N increases beyond some threshold value. If N was in steps of kilograms instead of grains of sand, the range of N across which this happens (from always able to lift to never able to lift) is quite small. But since each kilogram measured at a particular precision translates into some large but definite range of number of grains of sand, it is pretty much the same thing.

I meant to ask whether some algorithms might show a similar property – they terminate normally for all inputs of size n, never terminate normally for inputs of size >= N, and show a gradual decline in how often they terminate normally for in between sizes. An algorithm running on a machine exercising the limit of the computer’s memory might display such behavior, if the space required for computation is not fixed for a particular input size but might vary a bit.

Is P equal to NP?

We pretend to show the answer of the P versus NP problem. We start assuming that P = NP. We prove a Theorem that states when P = NP, then the problem SUCCINCT HAMILTON PATH would be in P. But, we already know if P = NP, then EXP = NEXP. Since SUCCINCT HAMILTON PATH is in NEXP–complete, then it would be in EXP–complete, because the completeness of both classes uses the polynomial-time reduction. But, if some EXP–complete problem is in P, then P should be equal to EXP, because P and EXP are closed under reductions and P is a subset of EXP. However, as result of the Hierarchy Theorem the class P cannot be equal to EXP. To sum up, we obtain a contradiction under the assumption that P = NP, and thus, we can claim that P is not equal to NP as a direct consequence of applying the Reductio ad absurdum rule.

See more in

https://hal.archives-ouvertes.fr/hal-01249826

Thank RJ and KW, it’s always nice for those of us with limited math skills to get an opportunity for commenting. I was surprised you didn’t include Leibniz’ Law, the Identity of Indiscernibles. It would seem that with all the experts here in the ways of transformations that there might be some strong opinions about this ontological principle.

Thanks, RD. I considered that but decided not to overload with physics/quantum. I also had a vague recollection from Oxford days of the problem of “where does the evening sky change from blue to (violet or) black?” and that being connected to Vopenka’s ultrafinitism (!) but was unable to back up my recall with sources.