字逻辑与布什自动机

摘要

图灵机和一阶逻辑追求完备性,企图用与外界隔绝的精确推理解决一切问题.布什自动机与二阶逻辑等价,是刻画程序的有用模型,它开启了ω-正则语言的研究,使我们对图灵机所定义的计算进行反思.也由此产生出了一大批应用于计算机科学的现代逻辑的研究成果,而布什定理就是打开这些成果的第一道闸门.从新的角度重证了布什定理,扩展了国内现代逻辑在计算进程相关方面的研究.