[算法论]下集 -·科学社版

【算法论】下集 - 科学.pdf算 法(下册) A.A.馬尔科夫著 何,成 武 学 出版 社目(下册)第六章几个大量問题的不可判定性 1.合演算 52.等价性不可解围题的粒合演算构造.53.对差字等价的問题 4.波斯特演算.演算 6.结合演算 7.结合演算62 S.波斯特正规演算及 9.波斯特組合問题 10.短陣表达問题 11.結合演算性质的判定問题.AU{}中任何形如 T.U的字我們称为字母表A中的关系,此处T及U是A中的字.特别是A中的关系,字T称为关系的左部分.字U称为它的右部分.2.現在我們定义“结合演算”概念,此概念和正规算法概念有 許多共同处,但仍有本盾的差别.任何算法都是絲毫不差地以某种 方式,某种次序进行运算的某种指分,精合演算前不是指合,而只 是关于进行某种运算的决定.这种被决定的演算常有好几个,至 于选择其中的哪一个则不加任何限制,3.同正规算法相类似,任何结合演算均与某字母表有关,正 规算法的量婴翘成部分是其图式,即其替换公式的系.
———— 文字由OCR识别(未校验)，可能存在错字；请以原始完整版为准。