理论计算机科学引论

An Introduction to Theoretic Computer Science

摘要: 本文介绍可计算理论和计算理论的基本内容,包括抽象可计算理论、递归计算、顺序计算、逻辑计算等内容。与以前的作法的主要不同是:用S表达式而不是自然数做为基本论域,用一般递归函数而不是图灵机做为基础模型。这样做可以使理论与实践更加接近。以本文的内容为骨干,充实以必要的讲解,配上适当的习题,可以做为研究生一学期的教材。

Abstract: This is an introduction to theory of computability and theory of compu-tation. It consists of: Ⅰ. Abstract Computer, Ⅱ. Symbolic Expressions, Ⅲ. RecursiveFunctions. Ⅳ. Sequential Computation, Ⅴ. Listable Sets, Ⅵ. Logical Computation.