波斯特系统

E．波斯特在20世纪20年代设计的一种符号演算系统．当时波斯特的工作并未引起重视，论文直到1943年才发表。波斯特系统涉及两个基本概念：字和产生式．

设∑是一非空的有穷集合，称为字母表，其元素称为字母．由字母组成的有穷序列称为字，由∑中的字母组成的全体字的集合记作∑，称为∑上的字集．不含字母的空序列也是字，称为空字，记作．

产生式是由一些字产生另一些字的规则，其形式为

gSgSg…gSg→hShSh…hSh

其中g，…，g，h，…，h是字常项(可以为)；S，…，S是字变项；i，…，i是自然数1≤i，…，i≤m．(也就是说S(j=1，…，n)是S，…，S中的某一个，可能有重复．)

产生式的作用是从形如

gSgSg…gSg

的字产生出形如

hShSh…hSh

的新字。

由于对同一个字可以有不同的读法，所以根据一个产生式从同一字可能生出不止一个新字．例如设产生式q为

aSabS→Sb

(这里m=2，n=1，g=a，g=ab，g=，h=，h=b，i=2)，在q的作用下，由字

σ：aabab

可以生成

τ：abb

(取S=，S=ab)

也可以生成

τ：b

(取S=ab，S=)。

如果Q是一个产生式集合，在Q中的某个产生式q的作用下，由字σ得到字τ，就记作

στ(Q)

定义1 一个波斯特系统由以下三项内容组成：

(1)一个字母表∑

(2)一个非空的有穷字集A∑(公理集)

(3)一个非空的有穷的产生式集Q．

称为∑上的一个波斯特系统。

对于波斯特系统，如果存在字序列σ，σ…σ，满足

(1)σ∈A(σ是公理)，

(2)对每个i(1≤i＜n)有

σσ(Q)

则称σ为的定理，记作

的全体定理所组成的集合记作。

由于波斯特系统的产生式集是无序集，而且字又可以有不同的读法，所以波斯特系统不是单演系统(一个定理可能有多个后承)。

另外，使用波斯特系统产生一个字集时也允许使用该字集中不出现的字母，我们有

定义2 设∑是一字母表，X∑是∑上的一个字集，如果存在一个字母表∑∑，以及∑上的一个波斯特系统，使

则称X为波斯特可生成集。

对波斯特系统的产生式形状加以限制，可以得到各种特殊的波斯特系统，如半图厄系统、图厄系统、正规系统，等等．其中最重要的是正规系统。

定义3 如果波斯特系统的产生式都具有

gS→Sh

的形状，则称为正规系统。

波斯特证明：

定理1(范式定理) 如果X是波斯特可生成的，则X可以由一个正规系统生成。

以连续n个1组成的字表示自然数n，则自然数集N与｛1｝上的字集一一对应。

另取一个字母b作∑符号，则n元数组

(x，…，x)

可以表示为字

取∑=｛1｝，每个自然数上的n元函数f都可以表示为∑上的n元函数，仍记作f．集合

是f的图象。

定义4 如果D(f)是波斯特可生成集，则称f为波斯特可计算函数。

例如，波斯特系统：∑=｛1，b｝．公理A=｛b｝，产生式集Q=｛SbSb→S1bSSS1｝可以生成f(x)=x的图象。

波斯特系统：∑=｛1，b｝．公理A=｛bb｝，产生式集Q=｛SbSbS→S1bSbS1，SbSbS→SbS1bS1｝，可以生成函数f(x，y)=x+y的图象，于是x和x+y都是波斯特可计算的。

关于波斯特可计算函数，我们有：

定理2 X是波斯特可生成的当且仅当X是递归可枚举的。

由定理2和图象定理，立即得到：

定理3 f是波斯特可计算的当且仅当f是部分递归的。