Experimental philosophy is the mainstream academic field that is most directly attempting to dissolve (where possible) persistent philosophical problems by revealing the cognitive algorithms that generate old philosophical debates. Those who want to catch up with some of what these researchers have discovered already may want to read this July 2011 review of the field.

Also see my post Are Deontological Moral Judgments Rationalizations?

Last year Yvain had organised a Diplomacy game between LessWrong users to test how well we perform in practical application of game theory. At least two games had been played, but as far as I know no analysis was made afterwards. One reason is probably that few games involving complex interactions between players constitute at most anecdotal evidence for whatever hypothesis one may test. The second one is lack of comparison to outside players. Although the games were fun, their value as a game theory experiment remains rather low. Could we test our game theoretic skills in a statistically more significant way?

Only recently I have learned about Robert Axelrod's experiment in which he run a competition of different strategies playing iteraded prisoner's dilemma, and got an idea to replicate it. I have already run a similar experiment with five contestants (all being my friends) and now a second run is being prepared, with at least nine strategies in the pool. I am interested in a third run, this time with strategies nominated by LessWrongers. The contestants of the second run which has identical rules are readers of my blog and neither of them is probably familiar with specific LW ideas. Therefore, they would serve as a fairly good control group to test LW's applied rationality skills (or a subset of). After matching the strategies in both groups separately, I plan to put all of them together and see who wins.

So, if you want to participate in this contest, feel free to send me your strategy. The rules are following.

1. By a strategy I mean a program sent by a contestant or coded according to his/her instructions. The strategies compete in iterated prisoner's dilemmas. A single iteration I will call a turn. In each turn each strategy has to choose between cooperating and defecting. The payoffs are:
   • if both cooperate, 4 points for each
   • if both defect, 1 point for each
   • else 7 points for the defector and 0 points for its cooperating opponent
2. By a match I mean a series of 100 iterations between the same opponents.
3. There will be two different competitions, the round-robin tournament and the evolutionary tournament. Two separate final standings will be made, one for each tournament. Any received strategy has to participate in both.
   • In the round-robin tournament strategies will play one match against each other (not against a copy of themselves). The winner will be the strategy which acquires the highest total number of points. Number of won or lost matches is disregarded.
   • The evolutionary tournament will simulate evolution of a population of strategies. In the beginning, equal number of copies of each strategy is present in the pool. Then the strategies are paired randomly (now a strategy may be paired against a copy of itself) and each pair plays one match. In the next generation pool, the strategies will be represented in numbers proportional to the total number of points won by all its copies in the present generation. The total population will be maintained at a constant level (probably 2,000 strategies, up to rounding errors). Strategies may go extinct. The strategy with the highest number of copies after the 100th generation will be considered a winner.
4. A strategy has access to results of all previous turns in its current match and the number of current turn. It can decide randomly (a pseudo-random generator will be used). It does not have access to results of other matches (including its own previous matches), the number of current generation, population sizes, number of points won by any strategy in any phase of the tournament (except the number of points already won in the current match which can be calculated from the previous turns results) and its opponent's identity (namely it doesn't know whether it plays against a copy of itself). The strategies obviously can't read their opponent's source code.
5. Each person can send only one strategy. Be honest.
6. The strategy can be described in any comprehensible language. If I find problems in understanding, which will probably happen if the strategy is described in Lisp or Basque, but can happen even if it is written in English, I will ask.
7. You should send your strategies by private message, not in comments to this post. Your opponents shouldn't know what you have prepared.
8. The strategy needn't be original, but if I get two identical strategies, I will treat them as one.
9. A Fully Random strategy is automatically included in the tournament. It plays defect or cooperate randomly with 50% chance each turn.
10. Names of the authors of the strategies will be published by default. If you wish your name excluded, specify it in your message, and your strategy will compete anonymously.

The simulation will probably not be run before at least eight strategies are collected and before the beginning of September. The competition is closed, no new strategies are accepted at this moment. 21 different strategies were accepted, their implementations are now being tested. Results will be probably posted on Sunday 4th September.

[Edit: Found inconsistency in using words round and turn to denote the same thing. Now turn is used everywhere.]

Part 1:  Transparent Newcomb with your existence at stake

Related: Newcomb's Problem and Regret of Rationality

Omega, a wise and trustworthy being, presents you with a one-time-only game and a surprising revelation.  

"I have here two boxes, each containing $100," he says.  "You may choose to take both Box A and Box B, or just Box B.  You get all the money in the box or boxes you take, and there will be no other consequences of any kind.  But before you choose, there is something I must tell you."

Omega pauses portentously.

"You were created by a god: a being called Prometheus.  Prometheus was neither omniscient nor particularly benevolent.  He was given a large set of blueprints for possible human embryos, and for each blueprint that pleased him he created that embryo and implanted it in a human woman.  Here was how he judged the blueprints: any that he guessed would grow into a person who would choose only Box B in this situation, he created.  If he judged that the embryo would grow into a person who chose both boxes, he filed that blueprint away unused.  Prometheus's predictive ability was not perfect, but it was very strong; he was the god, after all, of Foresight."

Do you take both boxes, or only Box B?

EDIT: This is now on the Wiki as "Quick reference guide to the infinite".  Do what you want with it.

It seems whenever anything involving infinities or measuring infinite sets comes up it generates a lot of confusion.  So I thought I would write a quick guide to both to

1. Address common confusions
2. Act as a useful reference (perhaps this should be a wiki article? This would benefit from others being able to edit it; there's no "community wiki mode" on LW, huh?)
3. Remind people that sometimes inventing a new sort of answer is necessary!

I am trying to keep this concise, in some cases substituting Wikipedia links for explanation, but I do want what I have written to be understandable enough and informative enough to answer the commonly occurring questions.  Please let me know if you can detect a particular problem. I wrote this very quickly and expect it still needs quite a bit more work to be understandable to someone with very little math background.

I realize many people here are finitists of one stripe or another but this comes up often enough that this seems useful anyway.  Apologies to any constructivists, but I am going to assume classical logic, because it's all I know, though I am pointing out explicitly any uses of choice.  (For what this means and why anyone cares about this, see this comment.)  Also as I intend this as a reference (is there *any* way we can make this editable?) some of this may be things that I do not actually know but merely have read.

Note that these are two separate topics, though they have a bit of overlap.

Primarily, though, my main intention is to put an end to the following, which I have seen here far too often:

Myth #0: All infinities are infinite cardinals, and cardinality is the main method used to measure size of sets.

The fact is that "infinite" is a general term meaning "larger (in some sense) than any natural number"; different systems of infinite numbers get used depending on what is appropriate in context. Furthermore, there are many other methods of measuring sizes of sets, which sacrifice universality for higher resolution; cardinality is a very coarse-grained measure.

Modern computational cryptography probes what is possible in our universe, and I think the results of this exploration may be interesting to people who wouldn't normally be exposed to it.

All of our algorithms will have a "security parameter" k. Our goal is to make it so that an honest participant in the algorithm needs to spend only about k time for each operation, while anyone trying to break the scheme needs to use a super-polynomial amount of time in k. These assumptions are specifically engineered such that they don't really depend on the type of computers being used.

When I say that a participant has a function in mind to evaluate, we are going to imagine that this function is described by its code in some programming language. It doesn't matter which language if you are willing to accept constant factor slowdowns; you can translate from any reasonable programming language into any other.

Now onto the results, stated very imprecisely and given roughly in increasing order of surprisingness. I have chosen a really random selection based on my own interests, so don't think this is an exhaustive list.

One-Way Function (OWF): A function is one-way if given x it is easy to compute f(x), but given f(x) it is hard to find either x or any other x' such that f(x') = f(x). For example, if I give you randomly chosen k-bit integers x, y, it is easy to compute their product x*y. But if I give you their product x*y, it is hard to recover x and y (or another pair of k-bit integers with the same product). We have many more explicit candidates for one-way functions, some of which are believed to be secure against quantum adversaries. Note that basically every other result here implies OWF, and OWF implies P != NP (so for the forseeable future we are going to have to make assumptions to do computational cryptography).

Pseudorandom Generator (PRG): Suppose I want to run a randomized algorithm that requires 1000000 bits of randomness, but I only have 1000 bits of randomness. A psuedorandom generator allows me to turn my 1000 bits of randomness into a 1000000 bits of psuedorandomness, and guarantees that any efficient randomized algorithm works just as often with a psuedorandom input as with a random input. More formally, a psuedorandom generator takes k random bits to k+1 psuedorandom bits in such a way that it is very difficult to distinguish its output from random. A PRG exists iff a OWF exists.

Private Key Cryptography: Suppose that Alice and Bob share a secret of length k, and would like to send a message so that an eavesdropper who doesn't know the secret can't understand it. If they want to send a message of length at most k, they can use a one time pad. Private key encryption allows them to send a much longer message in a way that is indecipherable to someone who doesn't know the secret. Private key cryptography is possible if a OWF exists.

Psuedorandom Function Family (PRF): A psuedorandom function family is a small family of functions (one for each k bit string) such that a black box for a randomly chosen function from the family looks exactly like a black box which chooses a random output independently for each input. A PRF exists iff a OWF exists.

Bit Commitment: If Alice and Bob meet in person, then Alice can put a message into an envelope and leave this envelope in plain view. Bob can't see the message, but if at some later time the envelope is opened Bob can guarantee that Alice wasn't able to change what was in the envelope. Bit commitment allows Alice and Bob to do the same thing when they only share a communication channel. So for example, Alice could take a proof of the Riemann Hypothesis and commit to it. If someone else were to later give a proof of the Riemann Hypothesis, she could "open" her commitment and reveal that she had a proof first. If she doesn't ever choose to open her commitment, then no one ever learns anything about her proof. Bit commitment is possible if a OWF exists.

Public Key Cryptography: Just like private key cryptography, but now Alice and Bob share no secret. They want to communicate in such a way that they both learn a secret which no eavesdropper can efficiently recover. Public key cryptography is not known to be possible if a OWF exists. We have a number of candidate schemes for public key cryptography schemes, some of which are secure against quantum adversaries. RSA is used in practice for this functionality.

Zero-Knowledge Proofs (ZKP): Suppose I know the solution to some hard problem, whose answer you can verify. I would like to convince you that I really do have a solution, but without giving you any other knowledge about the solution. To do this I can't just give you a static proof; we need to talk for a while. We say that an interactive proof is zero knowledge if the person verifying the proof can guess how the conversation will go before having it (if he can effectively sample from the distribution over possible transcripts of the conversation), but it will only be possible for the prover to keep up his end of the conversation if he really has a solution. ZKPs exist for NP problems if OWFs exist.

Non-Interactive Zero-Knowledge Proofs (NIZKP): Naively, zero-knowledge requires interaction. But we can make it non-interactive if we make use of a common random beacon. So for example, I am going to prove to you that I have a proof of the RH. In order to prove it to you, I say "Consider the sequence of solar flares that were visible last night. Using that as our random data, here is a verification that I really have a proof of the RH." Now we say that a protocol is zero-knowledge if the verifier can construct a non-interactive proof for apparently random strings of their own choice, but such that the prover can construct a proof for truly random strings if and only if he really has a solution. We have some candidate schemes for NIZKPs, but I know of none which are secure against quantum adversaries.

Digital Signatures: Modern law uses signatures extensively. This use is predicated on the assumption that I can obtain Alice's signature of a document if and only if Alice has signed it. I very much doubt this is true of real signatures; a digital signature scheme makes the same guarantee---there is no efficient way to compute Alice's signature of any document without having someone with Alice's private key sign it. Digital signature schemes exist which are secure against classical adversaries if claw-free permutation pairs exist. I don't know what the status of digital signatures against quantum adversaries is (they exist in the random oracle model, which is generally interpreted as meaning they exist in practice). RSA can also be used for this function in practice.

Homomorphic Public-Key Encryption: Just like public key cryptography, but now given an encryption of a message M I can efficiently compute the encryption of any function f(M) which I can compute efficiently on unencrypted inputs. There is a candidate scheme secure against quantum adversaries, but under pretty non-standard assumptions. There are no practical implementations of this scheme, although people who care about practical implementations are working actively on it.

Secure Function Evaluation: Suppose Alice and Bob have their own inputs A and B, and a function f(A, B) they would like to compute. They can do it easily by sharing A, B; in fact they can do it without sharing any information about their private input except what is necessarily revealed by f(A, B). If Alice cheats at any point, then the computational effort Bob needs to exert to learn f(A, B) is at most twice the computational effort Alice needs to exert to learn anything at all about B (this is a weaker assumption than usual in cryptography, but not that bad). There are no practical implementations of this functionality except for very simple functions.

And some random things I find interesting but which are generally considered less important:

Computationally Secure Arguments: Suppose that I am trying to prove an assertion to you. You only have a polynomial amount of time. I personally have an exponential amount of time, and I happen to also have a proof which is exponentially long. Conventional wisdom is that there is no possible way for me to prove the statement to you (you don't have time for me to tell you the whole proof---its really extraordinarily long). However, suppose you know that I only have an exponential amount of time in terms of the message size. There is a proof protocol which isn't perfectly secure, but such that faking a proof requires a super-exponential amount of time (in the random oracle model, which may correspond to a realistic cryptographic assumption in this case or may not).

Run-Once Programs: if I give you a program, you can copy it as much as you want and run it as often as you want. But suppose I have a special sort of hardware, which holds two messages but only gives one to the user (once the user asks for either message 0 or message 1, the hardware gives the specified message and then permanently destroys the other message). A run-once version of a program uses such hardware, and can be run once and only once. Run-once programs exist if public key encryption exists.

This post describes a toy formal model that helps me think about self-modifying AIs, motivationally stable goal systems, paperclip maximizers and other such things. It's not a new result, just a way of imagining how a computer sitting within a world interacts with the world and with itself. I hope others will find it useful.

(EDIT: it turns out the post does imply a somewhat interesting result. See my exchange with Nesov in the comments.)

A cellular automaton like the Game of Life can contain configurations that work like computers. Such a computer may contain a complete or partial representation of the whole world, including itself via quining. Also it may have "actuators", e.g. a pair of guns that can build interesting things using colliding sequences of gliders, depending on what's in the return value register. The computer's program reasons about its model of the world axiomatically, using a proof checker like in my other posts, with the goal of returning a value whose representation in the return-value register would cause the actuators to affect the world-model in interesting ways (I call this the "coupling axiom"). Then that thing happens in the real world.

The first and most obvious example of what the computer could want is suicide. Assuming the "actuators" are flexible enough, the program could go searching for a proof that putting a certain return value in the register eventually causes the universe to become empty (assuming that at the beginning it was empty except for the computer). Then it returns that value and halts.

You know that automated proof verifiers exist, right? And also that programs can know their own source code? Well, here's a puzzle for you:

Consider a program A that knows its own source code. The algorithm of A is as follows: generate and check all possible proofs up to some huge size (3^^^^3). If A finds a proof that A returns 1, it returns 1. If the search runs to the end and fails, it returns 0. What will this program actually return?

Wait, that was the easy version. Here's a harder puzzle:

Consider programs A and B that both know their own, and each other's, source code. The algorithm of A is as follows: generate and check all proofs up to size 3^^^^3. If A finds a proof that A returns the same value as B, it returns 1. If the search fails, it returns 0. The algorithm of B is similar, but possibly with a different proof system and different length limit. What will A and B return?

This second puzzle is a formalization of a Prisoner's Dilemma strategy proposed by Eliezer: "I cooperate if and only I expect you to cooperate if and only if I cooperate". So far we only knew how to make this strategy work by "reasoning from symmetry", also known as quining. But programs A and B can be very different - a human-created AI versus an extraterrestrial crystalloid AI. Will they cooperate?

I may have a tentative proof that the answer to the first problem is 1, and that in the second problem they will cooperate. But: a) it requires you to understand some logic (the diagonal lemma and Löb's Theorem), b) I'm not sure it's correct because I've only studied the subject for the last four days, c) this margin is too small to contain it. So I put it up here. I submit this post with the hope that, even though the proof is probably wrong or incomplete, the ideas may still be useful to the community, and someone else will discover the correct answers.

Edit: by request from Vladimir Nesov, I reposted the proofs to our wiki under my user page. Many thanks to all those who took the time to parse and check them.