{\huge A Request That We Passed On}

Peto de la Simons Instituto \vspace{.5in}

Alistair Sinclair is a ``British computer scientist and computational theorist''---to quote our friends at Wikipedia. British or not he is one of the leaders in the world on anything concerning randomized algorithms of all kinds. He has won the prestigious Gödel Prize and the Fulkerson Prize. The latter was for his brilliant work on the permanent, in a long project that culminated in his famous breakthrough paper with Mark Jerrum and my Georgia Tech colleague Eric Vigoda.

Today I want to talk about a request we just got from Alistair that Ken and I decided to take a pass on, and give a reason why we did so.

Alistair Sinclair just asked us if we would make an announcement about the exciting programs planned for the next academic year at the Simons Institute for the Theory of Computing at Berkeley. He kindly pointed out that:

If you see an opportunity, I wonder if you could post this in some form on your blog? You should definitely feel free to ignore this request: I fully realize that your blog is not primarily a bulletin board. But if you are able to welcome this it would be much appreciated.

Below is an official announcement; of course, you are welcome to abbreviate and/or modify this in any way you wish. The key pieces of information are the link and the deadline of Decemeber 15.

Ken and I discussed it at length and finally decided that even though we have both known Alastair for over thirty years, Ken originally while in Britain, we couldn't do exactly what he asked. The Simons Institute is a wonderful new resource, generously supported by Jim Simons, and is running some terrific programs. But well that is not really what we do.

His Request

Here what we were to announce for him, but we declined politely to do so, since we are usually not a ``bulletin board,'' as he put it. \textsf {Simons-Berkeley Research Fellowships are an opportunity for outstanding junior scientists (up to 6 years from PhD by Fall 2014) to spend one or two semesters at the Institute in connection with one or more of its programs. The programs for 2014-15 are as follows:

The last is by special invitation only. It will cover secrets of computer systems for hedge fund operations and high-speed trading, and apply the lessons learned to develop recommendations for fixing the beleaguered website healthcare.gov. Jim Simons himself will be leading the discussions. Since December 15th is Zamenhof Day, the birthday of the Esperanto creator Ludwik Zamenhof, applications written in Esperanto will be given special consideration. }

Okay we are joking about the last topic on ``Computational Finance,'' but wanted to be sure you were reading. Alistair did after all say we could ``abbreviate and/or modify this in any way you wish.'' But we do have a serious point, and it's not what you think.

A Little Quote Logic

We---especially Ken and new student Michael Wehar, whose work while a CMU undergrad we covered a year ago---have been thinking about provability predicates in logic and paradoxes arising from interpreting them as ways of quoting something. A proof predicate has the form $latex {P(f,c)}&fg=000000$ and says that $latex {c}&fg=000000$ is a valid proof (in a given formal system) of the formula $latex {f}&fg=000000$. This is the logical analogue of checking the validity of a computation $latex {c}&fg=000000$ by a particular machine. A provability predicate then has the form $latex {Pv(f) = (\exists c)P(f,c)}&fg=000000$.

The weird fact, which applies to the same natural strong formal systems $latex {F}&fg=000000$ that Kurt Gödel's famous incompleteness theorems hold for, is that there are statements $latex {f}&fg=000000$ such that $latex {F}&fg=000000$ proves $latex {Pv(f)}&fg=000000$. but does not prove $latex {f}&fg=000000$ itself. Call such a statement $latex {f}&fg=000000$ an ``ambivalence'' of $latex {F}&fg=000000$. Our analogy is that in this post, Alaistair's request on which we were ambivalent is $latex {f}&fg=000000$.

Indeed the English phrase ``to pass on'' has ambivalent meanings: it can mean to transmit or to decline. To ``take a pass on'' something can mean to decline it or to give it a go. ``Special consideration'' might be more positive or might be otherwise.

Are there helpful general properties known about such statements $latex {f}&fg=000000$? One can avoid them by adding suitable logical reflection principles to $latex {F}&fg=000000$, but we wish to know what happens without them. We are also interested in even more paradoxical cases where $latex {F}&fg=000000$ does not prove $latex {Pv(f)}&fg=000000$, but $latex {F + \neg f}&fg=000000$, that is assuming the negation of $latex {f}&fg=000000$, does prove $latex {Pv(f)}&fg=000000$. Note that the consistency of $latex {F}&fg=000000$ is expressed by the statement $latex {\mathsf{Con_F} = \neg Pv(0=1)}&fg=000000$. We are wondering especially about cases where $latex {f}&fg=000000$ itself might be $latex {\mathsf{Con_F}}&fg=000000$ or $latex {\neg \mathsf{Con_F}}&fg=000000$. Knowing some general properties might also help us with cases like $latex {F + \neg f}&fg=000000$ proving $latex {Pv(f')}&fg=000000$ where $latex {f'}&fg=000000$ is a slight modification of $latex {f}&fg=000000$, such as $latex {f = \mathsf{Con_F}}&fg=000000$ but $latex {f' = \mathsf{Con_{F + f}}}&fg=000000$ or maybe $latex {f' = \mathsf{Con}_{F + \neg f}}&fg=000000$.

Well, we try to be consistent on this blog, but we can't prove it.

Open Problems

Ooops, we were not supposed to actually let this out---this was just one of our brainstorming drafts. Oh well. I guess I clicked the publish button on the WordPress.com site. But for a possible future post or paper, can you help us with understanding ambivalent statements?