理论计算机科学中的“僵尸”错误观念 (scottaaronson.blog)

本文探讨了理论计算机科学中一种常见的错误观念，即混淆了适用于无限序列和函数的概念与适用于单个整数和开放问题的概念。作者以计算理论中的可计算性概念为例，指出像 Busy Beaver 函数的值虽然是不可计算的，但这并不意味着像 BB(6) 这样的单个整数是不可计算的，因为总存在一个程序可以输出特定的整数。作者强调，这种错误观念源于对可计算性概念的误用，它忽略了可计算性是关于程序是否存在，而不是关于找到或编写程序的难度。