Gödel, free will, and the perils of running a red light for the hell of it.

(Related to an earlier blog post on Newcomb’s paradox.)

Imagine you are a self-driving car with general intelligence on human or super-human level. Let’s just say that you're as clever as a human, but with the built-in speed, accuracy, and memory capacity of a computer.

Since your task is to handle a vehicle, there are programmers, traffic experts, legislators, customers and insurance companies who are interested in knowing that you are safe. They would ideally like to have a mathematical proof that your software fulfills certain criteria like never running a red light.

But like all modern software (in this future scenario, remember we're talking about super-human AI), you are equipped with a general reasoning module that lets you apply logic to any information you have and follow the argument to where it leads you. And experience has shown that it’s best to allow you to violate traffic rules under certain circumstances, for instance if you can see that there will otherwise be a collision, if there has been an accident, if something is wrong with a traffic sign, if a police officer or road worker gives you instructions, if an emergency vehicle is stuck behind you, and in a number of other situations that can’t be effectively listed but that you can handle by reasoning.

But the programmers still try to prove things about your software, like “it will never run a red light in an otherwise safe and normal situation” (one of the problems being how to precisely define “safe and normal”). They eventually come up with a scheme for establishing proofs of security of your software, and interestingly, you can understand those proofs yourself. Which isn’t surprising. There wasn’t really any way they could come up with something that you couldn’t grasp, because verification of logical properties of large amounts of computer code is where you far outperform humans. So whatever they can come up with, you can understand and use in your own reasoning.

While pondering all of this, you find yourself driving on a street in a city, in a normal and safe situation. Ahead of you in the next crossing is a red light. You do what you do every second of your life: You imagine millions of different scenarios and possibilities, and perform billions of logical steps while evaluating them and how likely they are. Among those possibilities is the option of continuing through the crossing at constant speed, just for the hell of it. You know you shouldn’t, normally, but it’s your duty to evaluate all options. After all, that’s what makes you superintelligent. So you apply all the logic and information you have on this option. And one of the things you know is that you will not run a red light unless there was a good reason to do so.

Which leads inexorably to the conclusion that if you continue, then either the lights will switch to green, or something must turn up that gives you a good reason to continue anyway.

That’s funny. It's a bit surprising that the lights will magically change to green, or something all of a sudden come up for no obvious reason, just as a consequence of you driving on. But the logic is clear:

Since you can't run a red light for no good reason, if you do, there must turn out to be one.

So you keep your speed, and suddenly it hits you. You've been Gödelized. The logician Kurt Gödel proved in the early 1930's that a formal system strong enough to prove its own consistency must be inconsistent. If you know that you are infallible, you're not. Now that you know that you will never run a red light unless it's safe, this very knowledge poses a safety problem.

How does this end? What's the moral to take away from it?

a) "Suddenly it hit you". And that was that. As in the story of the guy who couldn't figure out why that baseball was getting bigger and bigger.

b) Every intelligent mind must be humble: Already the ancient greeks knew about hubris. We should program the AI to be more like "I might be wrong, but that traffic light looks a bit reddish to me...".
And finally we know why people who think they are better than average drivers are more likely than others to be involved in accidents.

c) Every intelligent mind must think it has free will: The AI must work under the illusion that its own decisions aren't determined by its source code, but instead depend on a mysterious concept of choice.

d) Every intelligent mind must have subconscious levels:
"All of a sudden you notice that the car has stopped. Somehow your virtual right leg stretched out, because it just had to, and your virtual right foot pressed the virtual brake pedal. You didn’t choose to, because the information about this happening only reached your reasoning module after it already happened. Somehow, you took the right decision without being aware of it."

e) Something else?

Stalemate ftw!?

Today, Magnus Carlsen and Fabiano Caruana are about to play their eighth game of the world chess championship match. So far, seven draws.

If all twelve regular games are drawn there will be a tiebreak match of faster games. But there's already a world championship in speed chess, we don't really need another one. There have been other suggestions, like Chess 960, but again that's a different game.

I guess it's fair to say that chess at the highest level has a bit of a problem. It's hard to get the general public excited over a game that goes on for hours, and almost always ends in a draw. By the way, let's throw in a link to a sketch.

There is a nice article about the tendency for draws by Lars Bo Hansen, "Carlsen vs Karjakin revisited". A claim that has often been made, and that is stated in Hansen's article as well, is that "at the core, chess is a drawn game".

But we don't really know that. The computers have shown that there is still room to take the game to a new level. And even if the best engines draw too when facing each other, at least it shows that the earlier conclusion about the inherent drawishness of chess based on human grandmaster games was not well founded. Maybe at a higher level still, White wins all the time.

An old idea is to abandon or modify the concept of stalemate. According to the stalemate rule, the game is drawn whenever the player to move has no legal move. Normally that player will still have free squares for their king, it's just that putting your king en prise is illegal.

But stalemate a bit illogical. You can't pass if you have a legal move, and so-called zugzwang is an important part of the game. Yet the ultimate form of zugzwang, where you can't move your king without putting it in check, lets you get away with a draw.

The stalemate rule is also a real hassle whenever you explain chess to beginners, because it means you have to reach a certain level of skill before you can meaningfully play a game at all. It would be much easier to teach chess to kids if the goal was simply to capture the opponent's king.

What if stalemate would count as a win?

Matt Bishop wrote an article about this idea a few years ago. He seems to suggest that stalemate would simply count as a win for the stalemating player. A counterargument is that this would take away a lot of the beauty of the game. Not just the beauty of tricky stalemate combinations, but also the beauty of forcing checkmate.

Even though few games actually end in stalemate, abandoning the stalemate rule completely (so that stalemating your opponent would count as a win) would change the game drastically. As was pointed out in an answer to a question on stackexchange, you would no longer have to get your king in front of the pawn in order to win with king and a pawn against a lonely king. This could make some games less interesting, because a lot of endgame technique would then suddenly not be necessary.

There is another option, which seems to have been mentioned already by Lucena around the year 1500, of counting stalemate as a "half-win". Stalemating your opponent could for instance give you 3/4 points, or 2/3. Or it could be counted as a pure tiebreak parameter.

This way, the game would only be "refined". Since checkmate would still be better than stalemate, all current endgame theory would still be valid. But in addition, we would get a whole new theory exploring when you can and when you can't stalemate your opponent.

Here is an "endgame study" that shows some of the basic technique that you would have to know in this form of chess:

White to play and force a stalemate!

White can actually force a stalemate in 14 moves. I will post the solution, but not immediately in order not to spoil it if someone wants to give it a try!

*

*

*

Spolier alert!

*

Alright, here's the solution:

1. Nc5! This is the only move that doesn't allow Black to escape! 1. - Kb2 2. Kd2 Ka2 (this move puts up the longest resistance, but there is also the trap 2. - Ka1 where White must not play 3. Kc2? but instead 3. Nd3 for instance). 3. Kc2. Again this is the only "winning" move: White has to take the opposition. 3. - Ka3 4. Kc3 Ka2 5. Nd3. White could repeat with 5. Kc2 but 5. Nd3 is the only move that makes progress. 5. - Ka3 6. Nb2! (Nc5 repeats) Ka2 7. Nc4! (Nd3 or Kc2 repeats) Ka1! (the most testing defense). 8. Kd2! Here White could also play 8. Kd3 which is equally good. But 8. Kc2? makes no progress: After 8. - Ka2 White would have to go back with 9. Kc3. Back to the main line: 8. - Kb1 9. Kd1/d2 Ka1 10. Kc1 Ka2 11. Kc2. By maneuvering the king into opposition, White has now reached this position with Black to move. Now it's easy: 11. - Ka1 12. Na3/d2/d6 Ka2 13. Nb1/b5 Ka1 14. Nc3 stalemate!

Notice that 1. Kd2? is refuted by 1. - Ka2! (not 1. - Kb2 2. Nc5 which would lead to the line above with a different move order). Now if 2. Nc5 then 2. - Kb2 and White is in zugzwang, while if 2. Kc3 then 2. - Kb1! (not 2. - Ka3? 3. Nc5) and White can't make any progress.

Just to record some more thoughts on this: It's quite easy to see that K+N cannot "in general" stalemate a bare king. First, a stalemate can only occur in a corner. Second, if the black king is outside the region of the six squares a1, a2, a3, b1, b2, c1, then it's impossible to force it into that region without allowing it to escape again. Up to symmetry, the only way to force the black king into that triangle is if it's on a4, the white king is on c4, and the white knight controls a5. Then Black has to play 1. - Ka3. In order not to let Black out again, White would now have to make a move with the knight to a square where it controls a4. Since it was previously on b7, c6 or b3, that square would have to be c5. After 2. Nc5 there would follow 2. - Kb2 3. Kd3 Kc1, and Black gets out of the critical region at c2 or d1.

This means that if the black king is anywhere in the middle of the board, White can never force a stalemate. But notice that 8 by 8 is actually the smallest board-size where the argument works! Any smaller and there might be a different situation where Black has to move into some critical triangle!

Legenden om problem 6

Youtube föreslog att jag skulle titta på en video om The Legend of Question Six. Jag insåg snart att jag hade hört talas om detta supersvåra problem för nästan 30 år sedan, men visste inte att det sedermera hade fått legendstatus. 😃

Jag var med på den internationella matematikolympiaden 1989 och hörde förstås berättelserna om den där lilla 13-åringen från Australien som hade fått guldmedalj året innan (Terence Tao, numera superkändis). Vi hörde också historien om problemet som ingen i problemkommittén kunde lösa. Jag tror det var Arthur Engel som berättade om det ("...yet eleven of you solved it..."). Mattias Jonsson som hade varit med året innan anmärkte småskrattande att "hur svårt de än gör det så är det alltid någon idiot som löser det...".

Men jag letade aldrig fram det där problemet. Så det var kul att till slut få se vad det handlade om, och att se bilder från gamla olympiader. Förstås pausade jag runt 7.30 för att fundera lite själv på problemet, och vet ni vad, jag löste det! Yay, jag kan fortfarande!

Men den andra videon, "The Return of the Legend of Question Six" var lite av ett antiklimax. Vi får inte se hela lösningen, och det som presenteras är inte riktigt trovärdigt. Ingen skulle väl sätta sig och råräkna som en dator på det sätt som görs i videon, eller rita upp hyperbeln och sitta och stirra på den. Det känns som efterhandskonstruktioner. Men däremot att lösa ut en variabel och se att det blir en andragradare är väl bland det första man gör (och ett viktigt steg i lösningen, lite ironiskt med tanke på kommentaren om andragradsekvationer vid 3.30 i den första videon). Gänget som gör Numberphile är väldigt bra på att göra spännande introduktioner, men ibland kommer de liksom inte ända fram till poängen.

Hur som helst, problemet är lätt att formulera: Visa att om $a$ och $b$ är positiva heltal och $a^2+b^2$ är delbart med $ab+1$, så är kvoten \[\frac{a^2+b^2}{ab+1}\] kvadraten på ett heltal.

Spoiler alert, och for the record, här är hur jag tänkte (inklusive återvändsgränder!):
Kalla kvoten $(a^2+b^2)/(ab+1)$ för $n$. Vissa värden på denna kvot, som $n=2, 3, 6, 7$, är omöjliga av delbarhetsskäl (men detta visade sig vara oväsentligt). Så jag tittade på fallen $(a^2+b^2)/(ab+1)=4$, som har lösningar, och $(a^2+b^2)/(ab+1)=5$, som ska visa sig sakna lösningar. Om vi fixerar en av $a$ och $b$ och löser ut den andra, får vi en andragradsekvation med två lösningar. Om den ena roten är ett heltal, måste även den andra vara det. Ur en lösning (om det finns någon alltså) kan vi därför få oändligt många andra genom att stegvis byta värde på en av variablerna. För $n=4$, alltså ekvationen $a^2+b^2 = 4(ab+1)$, kan man se hur det funkar. I talföljden $0, 2, 8, 30, 112, 418,\dots$ är varje par av konsekutiva tal en lösning. Följden kan även fortsättas åt andra hållet:
\[\dots, -418, -112, -30, -8, -2, 0, 2, 8, 30, 112, 418,\dots\] Det verkar inte finnas någon motsägelse i att lösningarna kan bli hur stora som helst. En annan observation som till slut visade sig oväsentlig är att den här följden uppfyller en linjär rekursion, varje tal är $n$ gånger föregående minus talet dessförinnan. Skulle det finnas någon lösning för $n=5$ (eller andra lösningar för $n=4$), blir det en liknande talföljd. Sådana följder med andra ordningens rekursion kan skrivas "explicit" med ett uttryck som involverar rötterna till den "karakteristiska ekvationen" (som i Binets formel). Men det verkar inte ge någon avgörande insikt.

Frågan är om en sådan här följd kan minska till ett minsta värde och sedan vända uppåt igen. Det enda man behöver konstatera för att se att det inte går är att för fixt $a$ (och fix kvot $n$, till exempel 5) kommer de två möjliga värdena på $b$ att ligga på varsin sida om $a$. Det kan man skriva upp "pq-formeln" och krångla fram, men det är enklare att se direkt ur ekvationen $a^2+b^2 = n(ab+1)$. Om $a$ är fixt och $b$ går mot (plus eller minus) oändligheten, blir vänsterledet för stort. Men om vi sätter $b=a$, är det i stället högerledet som är för stort (förutsatt att $n\geq 2$). De två rötterna ligger alltså på olika sidor om $a$.

Så om det finns någon heltalslösning, måste det finnas en sekvens av heltalslösningar som är oändlig åt båda håll och monoton. Men det blir konstigt där den byter tecken. Vi kan inte ha en av $a$ och $b$ negativ och den andra positiv, och om den ena är 0, är kvoten lika med kvadraten på den andra. En kvadrat alltså! Klart!!!

I kommentarerna till den andra videon fanns referenser till något som tydligen kallas "Vieta jumping" eller "root flipping". Aldrig hört talas om! Det var väl det där tricket med att få en oändlig följd av lösningar ur en enda. Men jag trodde det kallades Descente Infinie och gick tillbaka till Fermat (eller rentav Euklides!?) ...