亲爱的丘奇教授，
我附上了我的论文《类型理论的实用形式》的校样和重印订单。
看到克莱尼（Stephen Kleene ）对波斯特（Emile Post）（关于 Thue 问题【1】）论文的评论，让我想起我觉得我应该在某处说几句话来澄清波斯特提出的关于“图灵机 (Turing machine)”和“图灵约定机 (Turing convention machine)”的观点 [见 2.2]。波斯特观察到，我对机器的最初描述与我后来描述不同，因为后者受到许多约定（例如使用 E 和 F 方块），这些约定在我的论文中没有明确列举，并给“图灵机”的整个概念蒙上了一层阴影。波斯特列举了这些约定，并将它们体现在“图灵约定机”的定义中。
在撰写论文时，我在这方面的意图很明确，它们没有在论文中明确表达，但我认为现在有必要这样做。我的意图是，“图灵机”应该始终是没有附加约定的机器，并且所有关于机器的一般定理都应该运用此定义，我认为这一点得到了最好的遵守。另一方面，当涉及到描述特定机器的问题时，大量约定就变得可取了。显然，最好选择不限制机器基本通用性的约定，但不需要对此建立任何结果。如果可以找到遵守约定并能够执行所需操作的机器，那就足够了，保留任何固定的约定列表也是不可取的，人们随时都可能希望引入一个新的约定。
原文：
https://www.cse.chalmers.se/~aikmitr/papers/Turing.pdf (p102)：
Draft of a Letter from Turing to Alonzo Church Concerning the Post Critique
Dear Professor Church,
I enclose corrected proof of my paper ‘Practical forms of type theory’ and order for reprints.
Seeing Kleene’s review of Post’s paper (on problem of Thue) has reminded me that I feel I ought to say a few words somewhere to clear up the points which Post has raised about ‘Turing machines’ and ‘Turing convention machines’ [see 2.2]. Post observes that my initial description of a machine diVers from the machines which I describe later in that the latter are subjected to a number of conventions (e.g. the use of E and F squares). These conventions are nowhere very clearly enumerated in my paper and cast a fog over the whole concept of a ‘Turing machine’. Post has enumerated the conventions and embodied them in a definition of a ‘Turing convention machine’.
My intentions in this connection were clear in my mind at the time the paper was written; they were not expressed explicitly in the paper, but I think it is now necessary to do so. It was intended that the ‘Turing machine’ should always be the machine without attached conventions, and that all general theorems about machines should apply to this definition. To the best of my belief this was adhered to. On the other hand when it was a question of describing particular machines a host of conventions became desirable. Clearly it was best to choose conventions which did not restrict the essential generality of the machine, but one was not called upon to establish any results to this effect. If one could find machines obeying the conventions and able to carry out the desired operations, that was enough. It was also undesirable to keep any fixed list of conventions. At any moment one might wish to introduce a new one.
参考文献：
【1】RECURSIVE UNSOLVABILITY OF A PROBLEM OF THUE EMIL L. POST
https://www.wolframscience.com/prizes/tm23/images/Post2.pdf
转载本文请联系原作者获取授权，同时请注明本文来自柳渝科学网博客。
链接地址：https://wap.sciencenet.cn/blog-2322490-1463370.html?mobile=1
收藏
