algorithm - 是否存在用于 pi 数字的常数空间生成器？

Question

要准确说明我对 pi 数字的常量空间生成器的含义，请考虑以下过程:

我用 n 字节的 RAM(对于一些常量 n)和打印机连接了一个微处理器。我开始这个过程。从现在开始，每 x 个周期，pi 的基数 b 中的一位数字将被发送到打印机，直到时间结束。

是否存在这样的算法？

Answer 1

答案是否定的。

没有无限空间，任何程序最终都必须终止或开始循环通过相同的状态。将“状态”视为所有内存字节的值 - 包括指令指针和其他所有内容 - 写为一个巨大的数字)。计算机基本上就是一个大的 DFA。如果您有 256 位状态，则您的程序在开始循环之前最多可以执行 2^256 步。

如果你骑自行车，你就不是在计算圆周率，因为它是先验的。