5月29日晚来自荷兰阿姆斯特丹大学ILLC的Peter van Emde Boas教授为我们做了题为“图灵机与铺砖”的报告。

对于图灵机的瞬时描述（configuration）文献里有不同的表示方式，如果图灵机的读写头用一个自然数标示是一种数学的表示方式，如果把状态符号直接标示在纸带上读写头正在扫描的符号的旁边则可以被称为一种内在表示。从数学上看，这两种表示方式并没有太大区别，但是，图灵机的主要用途一般是用来证明不可判定性结果或衡量时间、空间复杂性问题，对于处理这些具体问题来说，内在表示是优于数学表示的，事实上，历史上大部分文献都不自觉的采用了内在或半内在的表示方式。van Emde Boas教授指出，早在1936年，图灵本人那篇最原始的论文里已谈到了这两种不同的表示方式，并意识到了内在表示的优越性。
图灵机的各种变形，如多带、多头、非确定性等版本的图灵机在可计算能力上并没有任何增加，等价的计算模型仍有很多，但图灵机能够脱颖而出的原因不在于它与现实计算机多接近，也不在于它的编程方式，事实上，直接用图灵机编程序是极端复杂的，图灵机的优势在于它概念上的简单性，它是最易于理解的通用计算模型。而且，图灵最早提出的图灵机模型更一般和具有更大的灵活自由度，它允许一次进行多步操作，这时的图灵看上去更像个工程师而不是数学家和逻辑学家。很多问题，如一阶逻辑的不可判定性问题、命题逻辑可满足性的NP完全问题等等，如果选择图灵机的内在表示方式则证明就比较简单。
铺砖问题是一种特别简单易于理解的操作，单带图灵机的内在表示很容易通过铺砖来模拟，所以很多时间、空间的计算复杂性问题都可以通过铺砖来刻画。最后，van Emde Boas教授夫妇还详细讲解演示了如何通过铺砖模拟一段“+1”的图灵机程序。（李熙）