算法與遞歸函數

《算法與遞歸函數》，數理邏輯中算法論重要教科書。馬爾采夫著。蘇聯莫斯科科學出版社1965年出版，1986年第2版。收編於《世界百科名著大辭典》。

內容簡介

本書6章16節，每節附有補充敘述、例子及習題。第1章基本概念。闡述了函數、運算、基本可計算算子等概念。第2章原始遞歸函數及遞歸可枚舉集。第3章一般遞歸函數與部分遞歸函數。第4章編號和。討論了集合與函數的和的編號，集合的可編譯性和可創造性，任意和的編號，集合的通用系統和可創造系統。第5章算法與圖靈機。討論了字典集合與函數，圖靈機及其應用。第6章圖靈—波斯特機與算法的變型。討論了算法和算子算法、多帶機、тАΓ系統、刁番圖方程。本書具有重要學術價值。它系統論述了算法與遞歸函數的理論。精確定義了各種遞歸函數類，證明了這些函數類的基本特性，並構造了一個具有一系列特殊重要性的遞歸函數。研究了各種算法類，並使之能夠用於計算任意遞歸函數，又與圖靈—波斯特機具有緊密聯繫。指出了算法理論如何應用於代數、數理邏輯和數論。書中所包含的許多補充材料，對於從事數理邏輯、程序理論及數理語言學等學科的研究生和科技工作者均頗有裨益。

作者簡介

馬爾采夫(1909—1967)，蘇聯數學家、邏輯學家，蘇聯科學院院士。基本工作方向為代數和數理邏輯。是模型論創建人之一。其「局部性定理」開創了數理邏輯方法在代數中的系統應用。在群論、環論、線性代數、拓樸代數、群與李代數及算法論方面都有創造性研究。

《世界百科名著大辭典》凡例

1.本辭典為書籍文獻的綜合性、科學性和知識性的工具書。選收自然科學、技術科學、綜合性科學、社會和人文科學、文學藝術的各個學科，以及宗教的名著和重要典籍。

2.一部著作，或一篇論文、作品，立為一條詞目。古籍^[1]中個別篇章，習慣上認為有特殊意義的，也獨立設目。

3.一部著作^[2]一般只在一卷出現。少數著作是幾個學科不可缺少的，在有關各卷互見。互見條目用(參見第頁)註明。

視頻