论文部分内容阅读
<正> 计算理论研究各种计算模型、可计算性和计算的复杂性等计算的固有性质,是计算机科学理论研究的核心。可计算理论研究的基本问题是,什么是计算,什么是可计算和不可计算,它可以使我们精确地区分有算法的问题和没有算法的问题,从而可以在抽象意义上回答计算机究竟能干什么,不能干什么的问题。计算复杂性理论研究在可利用的空间和时