turing-machines - 现实世界中的图灵完备性

Question

真正的程序可以在有足够的时间和空间的情况下解决问题。对于每个已知大小的问题实例，所消耗的空间量都有固定的上限。

给定“仅”足够大的内存，是否存在无法解决的问题（即无法计算的函数）？

更具体地说，是否存在只能由图灵机（具有无限磁带）计算而不能由传统程序计算的函数？

Answer 1

图灵机不可能在任何特定执行期间实际消耗无限量的磁带，因为它必须在有限数量的步骤后停止。如果它没有停止，那么它还没有“解决”任何问题。由于机器只能运行有限的步数，它只能从起点向任一方向移动有限的距离，因此只消耗有限量的磁带。

更具体地说，是否存在只能由图灵机（具有无限磁带）计算而不能由传统程序计算的函数？

当然。但仅是由于需要不合理（有限）的时间或空间。