计算机或图灵机运行的程序和熵变

[forecasting]

Landauer的结果是Q=k_B T ln2，擦除1 bit信息要向外界释放 如等式所示的热量。忽略掉计算机或图灵机非计算所产生的热量，那么运算所产生能量就正比于 运算步（实施擦除的运算步）或计算复杂度。换言之，计算伴随着系统熵增或者信息减少，而系统熵不变，则计算可逆。一个问题是如果系统熵减而非不变，对应着什么计算？

[forecasting]

Landauer的结果是Q=k_B T ln2，擦除1 bit信息要向外界释放 如等式所示的热量。忽略掉计算机或图灵机非计算所产生的热量，那么运算所产生能量就正比于 运算步（实施擦除的运算步）或计算复杂度。换言之，计算伴随着系统熵增或者信息减少，而系统熵不变，则计算可逆。一个问题是如果系统熵减而非不变，对应着什么计算？

这表述是不是有问题？

[FoxMe]

不懂你什么意思。

因为k是很小很小的玻尔兹曼常数，这个公式得到的能量没有什么实际意义：

At room temperature, the Landauer limit represents an energy of approximately 0.018 eV (2.9×10−21 J). Modern computers use about a billion times as much energy per operation.

[forecasting]

Landauer的结果是Q=k_B T ln2，擦除1 bit信息要向外界释放 如等式所示的热量。忽略掉计算机或图灵机非计算所产生的热量，那么运算所产生能量就正比于 运算步（实施擦除的运算步）或计算复杂度。换言之，计算伴随着系统熵增或者信息减少，而系统熵不变，则计算可逆。一个问题是如果系统熵减而非不变，对应着什么计算？

https://www.sciencedirect.com/science/a ... via%3Dihub

Abstract
This paper describes the simulation of an S(n) space-bounded deterministic Turing machine by a reversible Turing machine operating in space S(n). It thus answers a question posed by Bennett in 1989 and refutes the conjecture, made by Li and Vitanyi in 1996, that any reversible simulation of an irreversible computation must obey Bennett's reversible pebble game rules.

[forecasting]

https://ieeexplore.ieee.org/document/507692

Abstract:
Reversible simulation of irreversible algorithms is analysed in the stylized form of a "reversible" pebble game. While such simulations incur little overhead in additional computation time, they use a large amount of additional memory space during the computation. We show that among all simulations which can be modelled by the pebble game, Bennett's simulation is optimal in that it uses the least auxiliary space for the greatest number of simulated steps. We give a trade-off of storage space versus irreversible erasure. Examples of reversible algorithms are algorithms for quantum computers.

[forecasting]

https://epubs.siam.org/doi/10.1137/0218053

Abstract
A reversible Turing machine is one whose transition function is
, so that no instantaneous description (ID) has more than one predecessor. Using a pebbling argument, this paper shows that, for any
, ordinary multitape Turing machines using time T and space S can be simulated by reversible ones using time
and space
or in linear time and space
. The former result implies in particular that reversible machines can simulate ordinary ones in quadratic space. These results refer to reversible machines that save their input, thereby insuring a global
relation between initial and final IDs, even when the function being computed is many-to-one. Reversible machines that instead erase their input can of course compute only
partial recursive functions and indeed provide a Godel numbering of such functions. The time/space cost of computing a
function on such a machine is equal within a small polynomial to the cost of computing the function and its inverse on an ordinary Turing machine.

别人的一个修正：https://epubs.siam.org/doi/10.1137/0219046

[forecasting]

上面几篇文章是就熵不变的计算（可逆计算）或者模拟不可逆计算的可逆计算 展开的。一个结果就是 可逆计算的空间计算复杂度与相应的确定性计算 的空间复杂度相当。

[FoxMe]

可逆计算与不可逆计算的计算能力有啥区别吗？

熵这个信息度量非常根本，我估计机器学习还是要用熵来研究，才可能解释得清楚。

[forecasting]

可逆计算与不可逆计算的计算能力有啥区别吗？

熵这个信息度量非常根本，我估计机器学习还是要用熵来研究，才可能解释得清楚。

不可逆计算计算复杂度要小于可逆计算。

理论上，量子计算必须是可逆计算，但我以为事实上量子计算不可能实现。

[cozofxx]

Landauer的结果是Q=k_B T ln2，擦除1 bit信息要向外界释放 如等式所示的热量。忽略掉计算机或图灵机非计算所产生的热量，那么运算所产生能量就正比于 运算步（实施擦除的运算步）或计算复杂度。换言之，计算伴随着系统熵增或者信息减少，而系统熵不变，则计算可逆。一个问题是如果系统熵减而非不变，对应着什么计算？

大多数的所谓可逆计算没有太大现实意义。有现实意义的计算，基本都是不可逆的。熵的减少，带来的正是所谓物理insights。因此，不产生物理insights的计算就是可逆计算。近似为可逆的计算，其主要用途也就是变换，主要的应用场景，无非也就是破解加密这类问题。

另外，现实世界的可以应用的计算机，必然是不可逆的。所以宣称发明了绝热的可逆量子计算机之类的人，类比于宣称计算当中的永动机。

[forecasting]

大多数的所谓可逆计算没有太大现实意义。有现实意义的计算，基本都是不可逆的。熵的减少，带来的正是所谓物理insights。因此，不产生物理insights的计算就是可逆计算。近似为可逆的计算，其主要用途也就是变换，主要的应用场景，无非也就是破解加密这类问题。

另外，现实世界的可以应用的计算机，必然是不可逆的。所以宣称发明了绝热的可逆量子计算机之类的人，类比于宣称计算当中的永动机。

可逆计算会不会收支熵正好平衡呢？

怎么肯定熵减就一定带来insight?

[FoxMe]

有点意思。

另外，现实世界的可以应用的计算机，必然是不可逆的。所以宣称发明了绝热的可逆量子计算机之类的人，类比于宣称计算当中的永动机。

[cozofxx]

可逆计算会不会收支熵正好平衡呢？

怎么肯定熵减就一定带来insight?

可逆的需要绝热，绝热的计算机是不可能的。孤立系统演化，必然熵增加。这玩意儿就是热二律。
计算机这玩意儿就类似于一个生命体，要吃熵，吃能量，然后，熵减。不吃能量，熵就不可能减。吃了外界能量，就不是绝热了。