计算机科学家惊人发现：如何将空间压缩进时间里 | Chalk Talk

视频全文转录（中英双语）

以下为完整中英双语转录，已加标点。英文在前，中文在后，逐段对照。

由 Groq Whisper 转录 → M2.7 B 方案整文标点 + 分段 → M2.7 段号保留翻译 → 逐段对照。

[段 1]

Just a few months ago, a scientist showed a pretty astounding relationship between space and time, an earthquake of a result. But it’s not about this kind of space and time. Instead, it’s about the space and time of computation, like how long does it take to compute something, and how much memory does it use. Computational time gets a lot of attention. Like one of the most famous unsolved problems in computer science, P versus NP, is about distinguishing certain types of problems which can or cannot be solved quickly. But the next chapter is all about space, which is full of its own fascinating and fundamental questions. Recently, computer scientist Ryan Williams made an unexpected discovery that forced him to rethink the rules of computational space and time. So much so that he described it as disturbing. He found a way to trade in space for time in any program, like a lot of space. Some programs seem like they shouldn’t be able to give up any space. They’re using all of it. But he proved that it’s possible. It’s the first breakthrough of its kind in 50 years, and it’s pretty unbelievable. Unbelievable in a literal sense. many computer scientists, including Williams himself, didn’t believe it was true until he proved it.Here’s one obvious but very important difference between space and time. Space is reusable, whereas time is not.

[译文 1]

就在几个月前，一位科学家展示了一个关于空间和时间之间相当惊人的关系，一个像地震一样的结果。但这并不是关于我们通常理解的那种空间和时间，而是关于计算的空间和时间，比如计算某件事需要多长时间，以及使用多少内存。计算时间受到了很多关注。计算机科学中最著名的未解问题之一，P vs NP，就是关于区分某些类型的能快速解决或不能快速解决的问题。但下一章全是关于空间的，其中充满了自身迷人而基本的问题。最近，计算机科学家Ryan Williams有了一个意想不到的发现，迫使他重新思考计算空间和时间的规则。他甚至将其描述为令人不安的。他找到了一种方法，可以在任何程序中用空间换取时间，而且是大量的空间。有些程序看起来不应该能够放弃任何空间，因为它们正在使用所有空间。但他证明了这是可能的。这是50年来同类问题的首次突破，而且相当令人难以置信。字面意义上的令人难以置信。许多计算机科学家，包括Williams本人在内，在他证明之前都不相信这是真的。这里有一个明显但非常重要的空间和时间的区别：空间是可重复使用的，而时间则不是。

[段 2]

You’re probably aware of that. You can’t redo yesterday, but you could turn your living room into an office, using the space for something else entirely. And sometimes you can trade space for time. Like if you live in a tiny house, or you can’t leave your apartment because of a global pandemic, you might be reusing the same space over and over again. You put away the breakfast dishes, converting your table to your kid’s school classroom, pushing the couch aside to create a yoga studio. But this efficient use of space can cost time because you’re repeatedly rearranging the furniture. Space and time are fundamental constraints, both in our lives and in computer science. It’s still true that you can reuse space on a computer, but not computational time. So on a computer, when and how can you trade space for time? And what’s the exchange rate? Often when people talk about computational space or time, they’re using physical units like gigabytes or seconds. but these things are constantly in flux, changing with advances in technology and engineering. In order to talk more fundamentally about the space and time of a computation,about the space and time of a computation, computer scientists use a Turing machine, invented by the prolific Alan Turing. He wanted to study any possible computing machine, not just the very limited technology of the day.

[译文 2]

你可能已经意识到了这一点。你无法重做昨天，但你可以把你的客厅变成办公室，把空间用于完全不同的用途。有时候你可以用空间换取时间。比如如果你住在一个小房子里，或者因为全球大流行病你不能离开你的公寓，你可能会一遍又一遍地重复使用同一个空间。你收起早餐的餐具，把你的桌子变成你孩子的教室，把沙发推到一边，创造一个瑜伽工作室。但这种高效的空间利用可能会耗费时间，因为你需要反复重新布置家具。空间和时间是基本的约束，无论在我们的生活中还是在计算机科学中都是如此。在计算机上你仍然可以重复使用空间，但计算时间则不行。那么，在计算机上什么时候以及如何可以用空间换取时间？兑换比率是多少？通常当人们谈论计算空间或时间时，他们使用的是物理单位，如千兆字节或秒。但这些东西总是在波动，随着技术和工程的进步而变化。为了更基本地讨论计算的空间和时间，计算机科学家使用图灵机，它是由多产的Alan Turing发明的。他想要研究任何可能的计算机器，而不仅仅是当时非常有限的技术。

[段 3]

So he devised the Turing machine, which is sort of a computer of the mind. A Turing machine has an infinitely long strip of paper, referred to as the tape, separated into boxes. There’s a head, which reads and writes on the tape, and then moves one square left or right. A Turing machine is entirely theoretical. It’s a mathematical construct, but it sort of reminds me of a typewriter, which makes sense because the Turing machine was invented in the 1930s. A human controls a typewriter, decides the next keystroke. By contrast, a Turing machine decides what to do using a very specific set of instructions which are laid out in advance. On a Turing machine, the definitions of space and time are more straightforward than they are in the real world. We can measure time with a little ticker. Every time the head moves, reading a new square, the time ticker goes up, so the total time is the number of steps the head takes. To measure space or memory, we’ll use another ticker. Similarly, the ticker goes up every time the head reads another square, but only if it hasn’t read from that square before. It’s a new square.from that square before. It’s a new square. If you no longer need an earlier part of your computation, then you can just write over that part of the tape.

[译文 3]

于是他设计出了图灵机，这可以说是一种思维计算机。图灵机有一条无限长的纸条，称为纸带，被分成一个个格子。有一个读写头，在纸带上读取和写入，然后向左或向右移动一个方格。图灵机完全是理论性的。它是一种数学构造，但它让我想起打字机，这是有道理的，因为图灵机是在1930年代发明的。人类控制打字机，决定下一个按键动作。相比之下，图灵机使用一组非常具体的预先设定的指令来决定做什么。在图灵机上，空间和时间的定义比在现实世界中更直接。我们可以用一个小计数器来测量时间。每次读写头移动读取一个新方格，时间计数器就加一，所以总时间就是读写头采取的步数。要测量空间或内存，我们使用另一个计数器。同样，每次读写头读取另一个方格时计数器就加一，但前提是它之前没有从那个方格读取过。这是一个新的方格。如果你不再需要计算中较早的部分，你可以在纸带的那部分上直接写入覆盖。

[段 4]

You can reuse that space. But the time that you took to do that earlier computation is gone. So right away we can see that the amount of space a program uses will be less than the time it runs for. The time ticker is always running, but the space ticker isn’t. So if the time is 100, the space is definitely some number less than 100. But how much less space than time does a program require? Some programs use just a little bit of space, way less than the 100 bound. But we want an answer that applies to all algorithms, and some programs seem to store lots of information, a huge table, which would essentially require new space at every step, so the space would be very close to 100. But is it possible to create another program, which simulates the current one, meaning the same outputs from the same inputs, but uses significantly less space? It would seem unlikely given how much information some algorithms seem to store. But pretty early on in the study of computational complexity, researchers noticed that Turing machines can be kind of wasteful with their time. Like, let’s say that you want to check if two numbers are equal. One option is to go back through the tape, left, left, left, left, left, to find the other number. Look at the first digit, then go back, right, right, right, right, right, the first digits match.

[译文 4]

你可以重复使用那个空间。但你花在早期计算上的时间已经一去不复返了。所以我们可以立刻看到，一个程序使用的空间量将小于它运行的时间。时间计数器一直在运行，但空间计数器则不是。所以如果时间是100，空间肯定是小于100的某个数字。但程序需要的空间比时间少多少？有些程序只使用很少的空间，远低于100的上限。但我们想要一个适用于所有算法的答案，而有些程序似乎存储了大量信息，一个巨大的表格，这基本上每一步都需要新的空间，所以空间将非常接近100。但有没有可能创建另一个程序来模拟当前的程序，意思是相同的输入产生相同的输出，但使用明显更少的空间？鉴于某些算法似乎存储了多少信息，这看起来不太可能。但在计算复杂性研究的早期，研究人员注意到图灵机在时间方面可能是相当浪费的。比如，假设你想检查两个数字是否相等。一个选择是在纸带上往回走，左、左、左、左、左，找到另一个数字。看第一位数字，然后再往回，右、右、右、右、右，第一位数字匹配。

[段 5]

Now let’s compare the second digit, left, left, left, left, left, and so on. When it’s walking back and forth, the Turing machine is racking up time, but not space. And if it’s not walking back and forth, then the Turing machine didn’t need to store all that previous information, so we can just write over it, saving space. By exploiting these bottlenecks, researchers proved in 1968 that it’s possible to trade in space for time. In the original program, the space was a number less than 100, but they showed that it’s possible to create another program, which accomplishes the same thing, whose space is less than the square root of the original time, 10. The square root of a number is way smaller than a number, like way, way smaller. Instead of focusing on 110, let’s move to a general graph, showing the original time of the program and the bound on the amount of space. In the original program, we only knew that the space was less than the time. It’s below the blue line. But in the simulated program, we know that it’s way further down below the yellow line. This graph, it applies to single tape tearing machines, but not to the more powerfulTuring machines, but not to the more powerful multi-tape Turing machines. These work similarly to the single tape machines, except there are multiple tapes, each with its own head.

[译文 5]

现在让我们比较第二位数字，左、左、左、左、左，以此类推。当它来回走动时，图灵机在消耗时间，但不消耗空间。如果它不需要来回走动，那么图灵机就不需要存储所有那些之前的信息，所以我们可以直接覆盖它，节省空间。通过利用这些瓶颈，研究人员在1968年证明了可以用空间换取时间是可能的。在原始程序中，空间是小于100的数字，但他们证明了可以创建另一个程序，完成同样的事情，其空间小于原始时间的平方根，即10。平方根比原数小很多，非常非常小。与其专注于100，让我们转向一个通用的图表，显示程序的原始时间和空间量的上限。在原始程序中，我们只知道空间小于时间。它在蓝线下方。但在模拟程序中，我们知道它进一步在黄线下方。这个图表适用于单带图灵机，但不适用于更强大的多带图灵机。

[段 6]

It’s still controlled by a central logic, the state of the machine, but at every step, the state can direct each head to do something separate. In some ways, a multi-tape machine and a single tape machine are similar. They’re capable of performing the same computations. But a multi-tape machine is way faster, even if it just has two tapes. It can simultaneously read information off of the two tapes, and that saves a lot of time wandering back and forth. For example, to check that two numbers are equal, you can put one tape head at the beginning of each. No wandering back and forth required. So the multi-tape machine is way more time efficient than the single tape machine. You wouldn’t expect to see a graph like this for the multi-tape machine. In 1975, computer scientists proved that this graph can be reduced slightly. But in the 50 years since, no one has made any more progress. And most people thought it would be impossible to dramatically push that curve down. In fact, this intuition is so strong that last year, when Ryan Williams did find a way to greatly reduce the space on a multi-tape machine, he didn’t initially believe his proof.machine, he didn’t initially believe his proof. He just set it aside, figuring he would pick it up later, find the error, and learn something in the process.

[译文 6]

多带图灵机的工作方式与单带机器类似，只是有多个纸带，每个都有自己的读写头。它仍然由中央逻辑控制，即机器的状态，但在每一步，状态可以指示每个读写头执行单独的操作。在某些方面，多带机器和单带机器是相似的。它们能够执行相同的计算。但多带机器速度更快，即使只有两个磁带。它可以同时从两个磁带上读取信息，这节省了大量来回走动的时间。例如，要检查两个数字是否相等，你可以把一个磁头放在每个数字的开头。不需要来回走动。所以多带机器比单带机器在时间效率上要高得多。你不会期望在多带机器上看到这样的图表。1975年，计算机科学家证明了这条曲线可以略微降低。但在那之后的50年里，没有人取得任何进一步的进展。大多数人认为大幅降低那条曲线是不可能的。事实上，这种直觉非常强烈，以至于去年当Ryan Williams确实找到了大幅减少多带机器空间的方法时，他最初并不相信自己的证明。他把它放在一边，以为他稍后会再捡起来，找到错误，并在过程中学到一些东西。

[段 7]

But when he returned to the proof, he realized there was no error. He had actually proved something that seems unprovable. Any computation, which was originally constrained in time but not constrained in space, could be simulated using much, much less space. Specifically, the square root of t log t space, where t is the time of the original computation. This is only slightly bigger than the square root of t we saw for the single tape machine, although it’s mighty close, which is remarkable given how much more efficient the multi-tape machine seems. Creating this space-saving simulation is a two-step process. First, you map out the computation, unrolling the connections between the different parts. And second, you recombine these pieces. You need to recreate the original outcome, but using less space than before. And to push this red line so low will require some very surprising, nearly magical mathematics. First, let’s map the computation. Specifically, how information from the past affects the future steps. This is one way physicists sometimes distinguish time from space. By thinking about causality, the way one thing influences another,causality, the way one thing influences another. Influence only happens in one direction. An event in the future cannot cause something to happen in the past. We can imagine time as a long line, like a ruler, marking each time the Turing machine ticks along during a computation.

[译文 7]

但是当他回到证明时，他发现没有错误。他实际上证明了一个看似不可证的东西。任何本来在时间上受限而在空间上不受限的计算，都可以用少得多的空间来模拟。具体来说，是 t log t 空间的平方根，其中 t 是原始计算的时间。这比我们之前在单带图灵机上看到的 t 的平方根稍大一点，尽管非常接近，考虑到多带图灵机看起来高效得多，这一点非常了不起。创建这种节省空间的模拟是一个两步过程。首先，你把计算展开，梳理出各部分之间的联系。其次，你重新组合这些片段。你需要重现原始结果，但使用的空间更少。要把这条红线压得如此低，需要一些非常惊人、近乎神奇的数学。首先，让我们绘制计算图。具体来说，过去的信息如何影响未来的步骤。这是物理学家有时区分时间和空间的一种方式。通过思考因果关系——一件事如何影响另一件事——因果关系，即一件事如何影响另一件事，影响只在单一方向发生。未来事件不能导致过去发生某事。我们可以把时间想象成一条长线，像尺子一样，标记图灵机在计算过程中每一次 tick。

[段 8]

Let’s look at this moment in time, which I’ll color green. We could draw arrows from all the past moments which directly affect the green part of the computation, but this will very quickly become unwieldy. There are lots of points and lots of arrows. Instead, we’ll break the computation into intervals, little chunks of time, which for visual convenience correspond to the rainbow colors. So our computation starts with red and it goes up to the purple interval. We can still think about how these intervals influence each other. For example, if I want to simulate the computation during the green time interval, I need information from the previous time intervals. But which ones? Well, I certainly need to know what was happening directly beforehand. So there’s an arrow from yellow to green. The information in the yellow time interval influences the green time interval. But we might also need other information, for example, from the red interval, which isn’t really represented in the yellow. So we draw an arrow from red to green. Now, if we want to reproduce the little chunk of the computation that happened during the green time interval,of the computation that happened during the green time interval, all we need to do is follow those arrows backward to get the information from the end of the previous time intervals. We only did this for green, but you can do the same for every time interval, connecting it to the previous ones to show the flow of information.

[译文 8]

让我们看这个时刻，我用绿色标记。我们可以从所有直接影响计算中绿色部分的过去时刻画箭头，但这会很快变得很繁琐。会有很多点和很多箭头。于是，我们把计算划分为若干区间，即时间的细小片段，为了视觉方便，用彩虹的颜色来表示。因此，我们的计算从红色开始，一直延伸到紫色区间。我们仍然可以思考这些区间如何相互影响。例如，如果我想模拟绿色时间段内的计算，我需要从前面的时间区间获取信息。但具体是哪些呢？显然，我需要知道紧接其前发生的情况，所以有从黄色指向绿色的箭头。黄色时间段的信息会影响绿色时间段。但我们可能还需要其他信息，例如来自红色区间的信息，而红色区间并没有在黄色中真正体现。于是我们画一条从红色指向绿色的箭头。现在，如果我们想重现绿色时间段内发生的那一小段计算，所需要的只是沿着这些箭头逆向追溯，从前面时间区间的末端获取信息。我们只对绿色做了这个过程，但对每个时间段都可以做同样的事情，把它与前面的区间相连，以显示信息的流动。

[段 9]

This is a graph. Each time interval is a node, and they are connected by edges. We can unroll this graph to reveal exactly how each time interval depends on the others. For example, the purple depends on green, blue, and yellow, but green depends on red and yellow, which in turn depends on orange. We can similarly trace back the blue and yellow intervals. This tree shows the flow of information. It’s like a map of the connections. What’s necessary to compute what? Each node contains all the relevant information from that time interval, mostly what’s printed on the tape. To figure out what happens at the end of the computation, that’s the purple dot, we need to work our way back up, recombining the chunks, doing partial calculations along the way. Our goal is to do this in the most space-efficient way possible. We wouldn’t want to compute everything in parallel. That would take a lot of space. Instead, we want to compute things successively, in a clever order. But what’s that? Well, the most reasonable strategy seems to come from a silly little game involving pebbles. In fact, this pebbling game is so simple that I made a little website where you can play it. It’s linked in the description. On each turn, you’re allowed to do one of three things. You can place a pebble on a leaf.

[译文 9]

这是一张图。每个时间段都是一个节点，它们通过边相连。我们可以展开这张图，精确显示每个时间段如何依赖于其他时间段。例如，紫色依赖于绿色、蓝色和黄色，而绿色依赖于红色和黄色，黄色又依赖于橙色。我们可以同样回溯蓝色和黄色区间。这棵树展示了信息的流向，就像一张连接的地图。计算什么需要什么？每个节点包含该时间段所有相关信息，主要是写在磁带上的内容。要弄清楚计算结束时的情况，即紫色节点，我们需要向上回溯，重新组合这些片段，一路进行部分计算。我们的目标是以最节省空间的方式完成这件事。我们不想把所有计算并行化，那会占用大量空间。相反，我们希望按某种巧妙的顺序依次计算。但这个顺序是什么？嗯，最合理的策略似乎来源于一个涉及卵石的小游戏。事实上，这个卵石游戏非常简单，我专门做了一个小网站，你可以在上面玩。链接在描述中。每回合，你可以做三件事之一。你可以把一颗卵石放在叶子上。

[段 10]

Those are the bottom nodes. If both nodes below a node have a pebble on them, then you can slide one of those pebbles up. So here you can slide one up, but here you can’t. And you can remove a pebble anywhere. Your goal is to get a pebble to the root of the tree, the top node. Well, you could put pebbles on all the leaves, the bottom row, and then move them up row by row. But that’s too easy. Let’s make it harder. Here’s your new challenge. Get a pebble to the root of the tree using the least total number of pebbles. That’s why the third rule is useful. You can remove pebbles and reuse them. Last time we used eight pebbles, but let’s push it. If you only have seven pebbles, could you reach the root? What about six, five, four, three pebbles? You can also change the tree’s height, that’s the number of layers, and see what happens then. Give it a try yourself and let us know your results in the comments. andand let us know your results in the comments. The best strategy here, this pebbling strategy, seems to also be the best way to solve William’s problem, the most space-efficient way to combine the little pieces of the computation to get the final results. And just as you can reuse pebbles in the pebbling game, you can efficiently reuse space, memory, when working your way up the causal tree.

[译文 10]

这些是底部的节点。如果一个节点下面的两个节点都有卵石，你就可以把其中一颗卵石向上滑动。于是这里可以向上滑一颗，但这里不行。你可以在任何地方移除卵石。你的目标是把一颗卵石送到树的根节点，即最顶端的节点。好吧，你可以在所有叶子上放置卵石，即最底行，然后一行一行向上移动。但那样太简单了。让我们把它变得更难。这是你的新挑战：使用尽可能少的卵石总数把一颗卵石送到树根。这就是第三条规则有用的原因。你可以把卵石移除并重复使用。上一次我们用了八颗卵石，现在让我们挑战一下。如果你只有七颗卵石，能到达根吗？六颗呢？五颗、四颗、三颗呢？你也可以改变树的高度，即层数，然后看看会发生什么。自己去试试，并在评论中告诉我们你的结果。最好的策略——这种卵石策略——似乎也是解决 William 问题的最佳方式，即以最节省空间的方式把小块计算组合起来得到最终结果。正如在卵石游戏中可以重复使用卵石一样，在向上攀登因果树时，你也可以高效地重用空间、内存。

[段 11]

Like you might be recomputing the same thing many times. There’s a bunch of orange nodes, but that’s okay. We’re trying to conserve space, not time. The efficiency of this pebbling strategy is part of a formal conjecture made in 2018. The general version is called the tree evaluation problem. You’re given numbers on the leaves, the bottom of the tree, and functions on the other nodes. Each function takes as input two numbers below it and spits out a new one, which can be fed into the function above that, until all the way at the root you end up with a single number. The goal is to do this using the least amount of total space, or memory, possible. You want to find the best way to solve all these functions so that you can efficiently reuse space. Since you need to work your way up to solve for the root, it seems that a pebbling type strategy is the best. In other words, treating each pebble as a piece of memory and using and reusingas a piece of memory and using and reusing them in the same pattern is optimal. In fact, the computer scientists that created the tree evaluation problem bet $100 that you couldn’t substantially beat the pebbling strategy. And if that bet were right, it would be kind of a bummer for Williams because it wouldn’t actually save him any space.

[译文 11]

就像你可能会多次重新计算同样的东西。有很多橙色节点，但这没关系。我们努力节约的是空间，而不是时间。这种卵石策略的效率是 2018 年提出的一个正式猜想的部分内容。其一般形式称为树评估问题。你在树的叶子（即底部）得到数字，在其他节点上得到函数。每个函数接受它下面的两个数字作为输入，吐出一个新的数字，这个数字可以送入上方的函数，直到最终在根节点得到一个单一的数。我们的目标是使用尽可能少的总空间（或内存）完成这件事。你想找到解决所有这些函数的最佳方式，以便高效地重用空间。由于需要从下往上求解根，似乎采用类似卵石的策略是最优的。换句话说，把每颗卵石当作一块内存，以相同的模式使用并重用它们是最优的。事实上，提出树评估问题的计算机科学家们打赌 100 美元，赌你无法显著地击败卵石策略。如果这个赌注成立，对 Williams 来说会有点沮丧，因为它实际上不会为他节省任何空间。

[段 12]

The calculation would take up as much space as the original, which was not the goal. Luckily for him, numbers are not pebbles, and the inventors of the tree evaluation problem would eventually lose that $100 bet to a young duo of computer scientists, including the son of one of the original authors, who found a very clever way to use the same space in the computer’s memory to store information and calculate things, Like the same bits are serving multiple purposes at the same time. Here’s one clever thing that you can do with numbers that you cannot do with pebbles. Let’s say that we have two variables, a equals 9 and b equals 30, and we want to switch them, a equals 30 and b equals 9. How do we do that? Computers aren’t magic. We need to give it a set of instructions. We could try saying set the value of a to be the value of b, 30, but then the value of a disappears. We’ve lost the nine. The standard solution would be to create a temporary variable, set it equal to a. Then when we set a equal to b, we haven’t lost the value a. We can set b equal to the temporary variable and they’re swapped. But is it possible to swap a and b without creating an extra variable? Here’s one way to start.

[译文 12]

计算会占用和原来一样多的空间，这不是目标。幸运的是，数字不是卵石，树评估问题的发明者最终会在这 100 美元的赌注上输给两位年轻的计算机科学家，其中包括原始作者之一的儿子，他们找到了一种非常巧妙的方法，利用计算机内存中的同一块空间既存储信息又进行计算，就像相同的比特同时承担多种用途一样。这里有一个可以用数字实现但用卵石无法实现的巧妙技巧。假设我们有两个变量，a 等于 9，b 等于 30，我们想把它们交换，使 a 等于 30，b 等于 9。我们该怎么做？计算机不是魔法。我们需要给它一组指令。我们可以尝试把 a 的值设为 b 的值，即 30，但这样 a 的值就消失了，九就丢失了。标准的解决办法是创建一个临时变量，让它等于 a。然后当我们把 a 设为 b 时，我们没有丢失 a 的值；我们可以把 b 设为临时变量，这样就完成了交换。但是，有没有可能在不创建额外变量的情况下交换 a 和 b 呢？这里有一种开始的方式。

[段 13]

First we’ll switch everything to binary. So 9 is 1 0 0 1 and 30 is 1 1 1 1 0. I put the extra 0 in front of the A so they’re the same length but it doesn’t change the value. We put them in binary because we want to XOR them. That stands for exclusive OR, which means one or the other but not both. Another way to think about it is like a light switch. 1 means flip and 0 means leave it alone. So if you flip and and then leave it, the light is on. Or if you leave it and then flip, the light is also on. But if you flip it twice, the light is back to off. Just like if you didn’t do anything at all. Now we’re ready to swap the variables. You can pause here if you wanna try it on your own. First, set A to be A XOR B. That is, we take each of the bits separately and XOR them. Then we set that to be A. Now set B to be AX or B. But of course A is different than it was in the beginning, so we get something different.A is different than it was in the beginning, so we get something different. Finally, set A to be A, X, or B. Again. Now we have swapped the two variables.

[译文 13]

首先我们把所有的数转换成二进制。9是1 0 0 1，30是1 1 1 1 0。我在A前面加了一个额外的0，这样它们长度一致，但这不会改变数值。我们把它们转换成二进制是因为我们要对它们进行异或运算。异或代表的是-exclusive OR，意思是两者中的某一个，但不能同时为真。另一种理解方式是把它想象成电灯开关。1表示翻转，0表示保持不变。所以如果你翻转一下然后保持不变，灯就亮了。或者如果你先保持不变再翻转，灯也是亮的。但如果你翻转两次，灯就又灭了。就像你什么都没做一样。现在我们准备交换变量。如果你想自己试试的话可以在这里暂停。首先，把A设为A XOR B。也就是说，我们分别对每一位进行异或运算。然后把结果赋给A。现在把B设为A XOR B。但当然A和开始时已经不同了，所以我们会得到不同的结果。最后，把A设为A XOR B。同样的。现在两个变量就交换好了。

[段 14]

We can also convert them back to base 10. In practice, this is often not the best way to swap variables, but it’s cool that it’s possible, and the intuition behind it reveals some surprising mathematical possibilities. So why does it work? Well, XOR resets itself every cycle of two. It cancels itself out. So A XOR A is always zero. And even if you do some things in the middle, A XOR B XOR A, those A’s still cancel. Because of the cancellations, you can continue to store the variable while also modifying it. In general, that’s the magic technique. The same part of memory can be used for multiple purposes. storage, and computation because of some clever cancellation tricks. When we swapped two variables using XOR, we did the same thing twice and we ended up back where we started. That’s where the cancellation was. But there are other systems in math with similar properties, including the roots of unity. For example, the fifth roots of unity are these five points around a circle. They represent sweeping a dial a fifth of the way around, two-fifths of the way around, three fifths of the way around and so on. If you pick any of these points and repeat that same sweeping motion five times, you’ll always end up back where you started. In other words, they cancel. Last year, James Cook and Ian Mertz used these number systems, the roots of unity, to find a shockingly space-efficient way to solve the tree evaluation problem.

[译文 14]

我们也可以把它们转换回十进制。实际上，这通常不是交换变量的最佳方法，但能实现这一点本身就很酷，而其背后的原理揭示了一些令人惊讶的数学可能性。为什么它能起作用呢？异或在每两个周期的循环中会重置自身。它会相互抵消。所以A XOR A总是零。即使你在中间做了一些操作，A XOR B XOR A，那些A仍然会相互抵消。由于这种抵消特性，你可以在修改变量的同时继续存储它。一般来说，这就是神奇的技巧。同一部分内存可以用于多个目的——存储和计算，因为一些巧妙的抵消技巧。当我们用异或交换两个变量时，我们做了同样的事情两次，最终回到了起点。那就是抵消发生的地方。但在数学中还有其他具有类似性质的体系，包括单位根。例如，五次单位根是圆周围的五个点。它们代表将刻度盘转动五分之一圈、五分之二圈、五分之三圈，以此类推。如果你选择这些点中的任何一个，并将同样的转动动作重复五次，你总是会回到起点。换句话说，它们会相互抵消。去年，James Cook和Ian Mertz利用这些数字系统，即单位根，找到了一种令人震惊的节省空间的方法来解决树评估问题。

[段 15]

Instead of always using new space, new memory, to compute the functions and then store their values, their new technique used the same chunks of memory over and over again to both store and calculate the values. Their procedure for solving the tree evaluation problem doesn’t even really compute these intermediate values. They’re all sort of scrambled together, layered and intertwined. But at the very top root node, because the roots of unities cancel, these scrambled numbers straighten out and produce the correct value. The original authors didn’t anticipate this because you can’t XOR pebbles or manipulate them like the roots of unity. But Cook and Mertz took advantage of the strange properties of numbers. In the end, it was enough to win them $100. And that, in turn, was enough for Ryan Williams to simulate any algorithm using way less space than expected. After breaking down the whole computation into this massive tree showing the flow of information,massive tree showing the flow of information, he could apply Cook and Merz’s super efficient algorithm to compute the top node, the end of the computation. But actually, this whole tree is really big and the goal is to save space, so he only computes little pieces of the tree, branches, on an as-needed basis. So ultimately, any computation can be performed using way less space than the original time estimate. But the route to get there is pretty strange.

[译文 15]

与其总是使用新的空间、新的内存来计算函数然后存储它们的值，他们的新技术反复使用相同的内存块来存储和计算值。他们解决树评估问题的过程甚至并没有真正计算这些中间值。它们都被混合在一起，层层叠加，交织缠绕。但在最顶端的根节点，由于单位根会相互抵消，这些混合的数字会理顺并产生正确的值。原始作者没有预料到这一点，因为鹅卵石不能进行异或运算，也不能像单位根那样操作。但Cook和Mertz利用了数字的奇异特性。最终，这足以让他们赢得100美元。而这反过来又足以让Ryan Williams用比预期少得多的空间来模拟任何算法。在将整个计算分解成这棵显示信息流的大树之后，他可以应用Cook和Mertz的超高效算法来计算顶端节点，即计算的终点。但实际上，这整棵树非常大，而目标是节省空间，所以他只在需要时计算树的小部分、分支。最终，任何计算都可以用比原始时间估计少得多的空间来执行。但到达那里的路径相当奇怪。

[段 16]

It requires taking off little interwoven chunks of the original computation, these branches of a tree, and then layering those on top of each other, using wild XOR-style tricks to super efficiently compute the final answer. And in the end, this takes way less space, square root of t log t. But can we do better? is it possible to push the red curve even lower? No one knows. But unexpected breakthroughs often snowball. They build on themselves, spreading in new directions. Last year, computer scientists found a strange and remarkably efficient way to solve the tree evaluation problem. And then this year, that led to a startling separate discovery, a way to trade in space for time. What could come next, anything is possible.you

[译文 16]

它需要取出原始计算中交织的小片段——这些树的分支，然后将它们层层叠加，利用疯狂的异或风格技巧来超级高效地计算最终答案。最终，这大大节省了空间，为t的平方根乘以log t。但我们能做得更好吗？有可能把红线压得更低吗？没人知道。但意想不到的突破往往会滚雪球般发展。它们相互叠加，向新方向扩展。去年，计算机科学家找到了一种奇怪而高效的方法来解决树评估问题。而今年，这引发了一个惊人的独立发现，一种用空间换取时间的方法。接下来会发生什么，一切皆有可能。