时间：2009年4月5日
地点：三号会所
讨论内容：本次活动正值清明节，我们深切缅怀了两位天才 — 图灵和哥德尔
图灵是真正的“人工智能之父”，我们从《The Essential Turing》一书中选择了部分章节进行讨论，该书是2004年出版的图灵的论文集，其中包括图灵的著名论文《Computing Machinery and Intelligence》，图灵的介绍参见http://www.douban.com/group/topic/5960962/。
本来没打算这么早讨论哥德尔，但由于前几次讨论总是提到哥德尔不完备性定理并且大家有争议，所以这次就简单介绍了一下，主要目的是给出哥德尔定理的结论，以及把我搜集的一些关于哥德尔的资料和大家分享一下。我们没有深入讨论哥德尔定理的证明，有兴趣的可以阅读相应书籍（在slides的最后一页）。
http://groups.google.com/group/swarmagents_ai/
attach/5093c395c917c3e4/note_Godel.ppt?part=2
大家对哥德尔和图灵有什么问题可以继续在网上讨论和补充。
####################Alan M. Turing########################
The Essential Turing: Seminal Writings in Computing, Logic, Philosophy, Artificial Intelligence, and Artificial Life: Plus The Secrets of Enigma B. Jack Copeland主编，Oxford university press, 2004。
The Essential Turing（TET）介绍了图灵的生平，收集了图灵的重要著作，Copeland做了很多采访，添加了很多总结和背景性的文字，是一本值得仔细读来的书。
全书分为四部分，基本上按时间顺序，收集和讨论了图灵在不同时期的思想和著作。
第一部分：Computable Numbers: A Guide。包括图灵1937年发表的《论可计算数机器在判定问题中的应用》及其修正，1939年发表的《序数基础上的逻辑系统》，还收集了这个时期图灵的一些信件。
第二部分：Enigma（1941-1945）。这部分介绍了二战期间图灵在外交部Code and Cypher School的工作。在此期间，图灵和同事研制了解密机器Bombe，用来对付德国军队用的加密机器Wehrmacht Enigma。这个工作可能使欧洲的战程缩短了两年。这个期间的工作，也对图灵后来的人工智能和人工生命的思想的形成有较大影响。
第三部分：Artificial Intelligence（1947-1952）。这部分介绍图灵在人工智能方面的先驱性的工作。包括第第九到十四章。
9. Lecture on the Automatic Computing Engine (1947 )
10. Intelligent Machinery (1948 )
11. Computing Machinery and Intelligence (1950 )
12. Intelligent Machinery, A Heretical Theory (c.1951)
13. Can Digital Computers Think? (1951)
14. Can Automatic Calculating Machines Be Said to Think? (1952)
第四部分：Artificial Life。这部分介绍了图灵在用计算来模拟生命行为的一些尝试。morphogenesis：形态发生, 形态形成, 器官发生, 器官形成。
15. The Chemical Basis of Morphogenesis (1952)
16. Chess (1953)
17. Solvable and Unsolvable Problems (1954)
~~~~
注一：以下提到的ACE都是指Automatic Computing Engine，是图灵在 National Physical Laboratory(NPL)主持设计的计算机。图灵在设计中使用精简指令（类似现在的RISC），通用计算的观点，尽量使用计算来实现各种功能，而不是使用各种硬件来完成计算（类似加速卡的东西）。现在做图形加速卡厂商好像也都在朝通用计算方向发展，像NVIDIA的Tesla，ATI的Firestream，Intel的larrabee。
注二：以下所标页码为TET书中的实际页码。“~~~~”标记的是大家讨论时提到的内容。
##################################################
page 354
“Modern AI researchers speak of the method of ‘generate-and-test’. Potential solutions to a given problem are generated by means of a guided search. These potential solutions are then tested by an auxiliary method in order to find out if any actually is a solution. The bombe mechanized the first process. The testing of the stops, or potential solutions, was then carried out manually…”
“In 1948 Turing boldly hypothesized that ‘intellectual activity consists mainly of various kinds of search’ (Chapter 10, p. 431). His readers would no doubt have been astonished to learn of his wartime experience with mechanized search (still secret at that time). Some eight years later the same hypothesis was put forward independently by Herbert Simon and Allen Newell in the USA; through their influential work, it became one of the central tenets of AI.”
“产生-检验”法：先搜索一个可能的解，然后验证这个解。二战期间图灵研制解密机器Bombe就是这么工作的。现在流行的叫法是启发式搜索。图灵大胆假设智能活动主要就是搜索。因为军方保密的原因，图灵当时这些思想没有被继承下来，后来Simon和Newell独立提出相同的假设。
##################################################
page 374
. . .The disciplined action (of ACE) carries with it the disagreeable feature, which you mentioned, that it will be entirely uncritical when anything goes wrong. It will also be necessarily devoid of anything that could be called originality.
There is, however, no reason why the machine should always be used in such a manner: there is nothing in its construction which obliges us to do so. It would be quite possible for the machine to try out variations of behaviour and accept or reject them in the manner you describe and I have been hoping to make the machine do this. This is possible because, without altering the design of the machine itself, it can, in theory at any rate, be used as a model of any other machine, by making it remember a suitable set of instructions.
…Thus, although the brain may in fact operate by changing its neuron circuits by the growth of axons and dendrites, we could nevertheless make a model, within the ACE, in which this possibility was allowed for, but in which the actual construction of the ACE did not alter, but only the remembered data, describing the mode of behaviour applicable at any time…
完全按规则工作的机器，没有什么容错能力，也不会有什么创新性。可以试着改变机器的工作方式，让它尝试各种变化，然后接受或者拒绝变化产生的后果。这么做并不需要改变机器的设计，理论上只要机器能保存一组合适的指令，它就可以模拟任何其它机器。我们不用ACE的结构做任何改变，只要改变它保存的数据，就可以用它来模拟人脑。
图灵认为人脑和图灵机的原理是一样的，图灵机可以模拟人脑，也就能模拟各种智能行为。
##################################################
page 392
I expect that digital computing machines will eventually stimulate a considerable interest in symbolic logic and mathematical philosophy. The language in which one communicates with these machines, i.e. the language of instruction tables, forms a sort of symbolic logic. … Actually one could communicate with these machines in any language provided it was an exact language… Some attempts will probably be made to get the machines to do actual manipulations of mathematical formulae. To do so will require the development of a special logical system for the purpose. This system should resemble normal mathematical procedure closely, but at the same time should be as unambiguous as possible. As regards mathematical philosophy, since the machines will be doing more and more mathematics themselves, the centre of gravity of the human interest will be driven further and further into philosophical questions of what can in principle be done etc.
这里图灵预言，数字计算机可以用于符号逻辑和数学公式推导。和计算机交流，需要一种精确的语言，它的指令集形成一个代数系统。机器可能替人做越来越多的事情，人类的兴趣可能越来越转移到哲学问题…
##################################################
page 400
“to extend his work on the machine [the ACE] still further towards the biological side. I can best describe it by saying that hitherto the machine has been planned for work equivalent to that of the lower parts of the brain, and he [Turing] wants to see how much a machine can do for the higher ones; for example, could a machine be made that could learn by experience? This will be theoretical work, and better done away from here.”
At Manchester, Turing designed the input mechanism and programming system for an expanded version of Kilburn and William’s ‘Baby’ and wrote a programming manual for the new machine. At last Turing had his hands on a functioning stored-programme computer. He was soon using it to model biological growth—pioneering work in the field now known as Artificial Life .
1947年图灵从NPL离开，逐渐把工作扩展到生物方面。ACE实现了人脑底层的功能，图灵想看到在更高的层面上，机器能做到哪些，比如机器能否从经验中学习。在曼彻斯特，图灵开始人工生命方面的先驱性工作。第一个可以运行的象棋程序，就是在图灵的指导下，这里诞生的。
##################################################
page 419
If we now consider interference, we should say that each time interference occurs the machine is probably changed. It is in this sense that interference ‘modifies’ a machine. The sense in which a machine can modify itself is even more remote. We may if we wish divide the operations of the machine into two classes, normal and self-modifying operations. So long as only normal operations are performed we regard the machine as unaltered. Clearly the idea of ‘self-modification’ will not be of much interest except where the division of operations into the two classes is very carefully made. The sort of case I have in mind is a computing machine like the ACE where large parts of the storage are normally occupied in holding instruction tables. Whenever the content of this storage was altered by the internal operations of the machine, one would naturally speak of the machine ‘modifying itself ’.
对机器的操作可以分成两部分：正常的操作和自修改操作。只有对这两种操作的区分恰当时，自修改这个概念才有意义。ACE内部存贮着指令表，如果机器的内部操作能够修改自己的指令表，就可以认为机器在修改自己。
这里的自修改，讨论了机器通过内部操作，修改自身指令的可能性，没有讨论到到自复制问题。
##################################################
page 420
One way of setting about our task of building a ‘thinking machine’ would be to take a man as a whole and to try to replace all the parts of him by machinery. He would include television cameras, microphones, loudspeakers, wheels and ‘handling servo-mechanisms’ as well as some sort of ‘electronic brain’. … Thus although this method is probably the ‘sure’ way of producing a thinking machine it seems to be altogether too slow and impracticable.
Instead we propose to try and see what can be done with a ‘brain’ which is more or less without a body, providing at most organs of sight, speech and hearing. We are then faced with the problem of finding suitable branches of thought for the machine to exercise its powers in. The following fields appear to me to have advantages:
(i) Various games e.g. chess, noughts and crosses, bridge, poker;
(ii) The learning of languages;
(iii) Translation of languages;
(iv) Cryptography;
(v) Mathematics.
制造会思考的机器的一个途径是：把人的各部分都用相应的机械装置替换，用摄像机，装上扬声器，轮子，用事务处理机器做电子脑。但当时那种办法不切实际。作出来的机器人太大了。
现在的技术倒是可以做。
另一个途径是：做一个几乎没有身体的脑，至多只装上视觉、听觉和发声器官。这样的脑不能像机器人一样在现实世界中巡游，需要给它寻找一个适合的生存领域，比如游戏、语言学习，机器翻译、密码学和数学。
~~~~
边界问题
大脑就像浸泡在汤中，同时处理的输入输出都是不确定的，几乎无限多。像是从一堆神经元中随便圈出一片来，然后发现，某种智能是来自这里。如果给出确定的边界，用确定个数的输入输出来模拟，可能丢失了很多信息。不确定的输入输出就像是扰动和涨落，实际可能是智能中不可忽视的因素。工程可实现的模型是尽量简单的，都具有确定的输入和输出。
~~~~
知识与进化
对人类来说，知识独立于人的生物进化之外，但大家都能站在已有知识的基础上。文字的发明，可能是智能发展的一个里程碑。
~~~~
“裸脑”的存在性
哥德尔认为独立于身体的思维是存在的。
##################################################
page 421
… we should be wise to sometimes compare the circumstances of our machine with those of a man. It would be quite unfair to expect a machine straight from the factory to compete on equal terms with a university graduate. The graduate has had contact with human beings for twenty years or more. This contact has throughout that period been modifying his behaviour pattern. His
teachers have been intentionally trying to modify it. At the end of the period a large number of standard routines will have been superimposed on the original pattern of his brain. These routines will be known to the community as a whole. He is then in a position to try out new combinations of these routines, to make slight variations on them, and to apply them in new ways.
这一段通过比较一个研究生和工厂里的机器所处的环境的差异，寻找智能行为的起源。学生已经其它的人接触了二十多年，这些接触都会对他的行为模式产生影响。老师还会可以地去改变他。最终的结果是，他脑中形成一系列的标准规则（routine）。然后他就可以通过组合或者稍稍改变这些规则来处理新的情况。
We may say then that in so far as a man is a machine he is one that is subject to very much interference. In fact interference will be the rule rather than the exception. He is in frequent communication with other men, and is continually receiving visual and other stimuli which themselves constitute a form of interference. It will only be when the man is ‘concentrating’ with a view to eliminating these stimuli or ‘distractions’ that he approximates a machine without interference. … but it is important to remember that although a man when concentrating may behave like a machine without interference, his behaviour when concentrating is largely determined by the way he has been conditioned by previous interference.
从这个过程来看，他就像是一个机器，总是处于外界的干预之中。只有在他集中注意力有意识减少外来干预的时候，才近似是一个不受干预的机器。即便在这时，他集中注意时的所做的事情，仍然是由先前的外界干预决定的。
~~~~
忘了怎么说到这个的：互联网就是一个巨大的智能体。生态系统也表现出一定的智能行为。
##################################################
page 448
… It was suggested tentatively that the question, ‘Can machines think?’ should be replaced by ‘Are there imaginable digital computers which would do well in the imitation game?’ If we wish we can make this superficially more general and ask ‘Are there discrete state machines which would do well?’ But in view of the universality property we see that either of these questions is equivalent to this, ‘Let us fix our attention on one particular digital computer C. Is it true that by modifying this computer to have an adequate storage, suitably increasing its speed of action, and providing it with an appropriate programme, C can be made to play satisfactorily the part of A in the imitation game, the part of B being taken by a man?’
“机器能思考吗？”这个问题可以换成“数字计算机能在模拟游戏中表现的足够好吗？”如果机器有足够的存储容量，响应速度，配上合适的程序，它能很好地扮演A的角色吗？这一段在说机器有没有智能的判据，就是图灵测试。思考并不是一个可以看到得的过程，这里图灵用了行为来测试。如果在测试中，机器的表现和人一样好，那我们就认为机器能够思考。
测试的具体做法：
有一个男人A，一个女人B，一个提问者C。测试过程中，C看不到A，B，需要通过提问来判断A，B中哪个是男的。A尽力误导C让它做出错误判断。用机器来代替A时，C做出错误判断的次数和A是人的时候相比，一样多吗？
~~~~
人和图灵测试
我们不需要通过图灵测试去判断一个人有没有智能。人和人的组织结构都差不多，一个人有智能，可以推测那另一个人也有。但人和机器差太多，所以要测试一下。
~~~~
还有一个图灵测试的奖： Loebner Prize
这个奖基本是非专业人士搞的伪图灵测试，很不科学，通不通过确实和AI不大相关，但图灵测试本身是很重要的。
We have just discussed the main reasons why MGonz, and Jenny18, perform well on the Turing Test, and none of them seem to involve Artificial Intelligence (AI). So the time has come to ask: Is the Turing Test, and passing it, actually important for the field of AI? It may surprise the reader that my answer is “No”.
以上文字节选自 Mark Humphrys的How My Program Passed the Turing Test？他自己都觉得通过这个测试和AI没什么关系。
一本讲图灵测试的书：Parsing the Turing Test , Springer Netherlands, 2008
http://dx.doi.org/10.1007/978-1-4020-6710-5
##################################################
page 451
The short answer to this argument is that although it is established that there are limitations to the powers of any particular machine, it has only been stated, without any sort of proof, that no such limitations apply to the human intellect.
… We too often give wrong answers to questions ourselves to be justified in being very pleased at such evidence of fallibility on the part of the machines. Further, our superiority can only be felt on such an occasion in relation to the one machine over which we have scored our petty triumph. There would be no question of triumphing simultaneously over all machines. In short, then, there might be men cleverer than any given machine, but then again there might be other machines cleverer again, and so on.
有人认为计算机受哥德尔不完备定理限制，不可能在机器上实现智能。这一段是图灵的反驳。所有的机器都有这样的局限，那人为什么就一定没有？就算人比机器优越，也没什么问题。有比机器人聪明的人，就有比人聪明的机器。
哥德尔定理说会有机器没法证明的真命题，但这并不能构成多大的限制，知道它的就行了，不证明也没什么问题，人不是也常常把结论直接拿来用。而且机器遇到解决不了的问题可以停下来找人来解决。所以这个限制不是问题。
~~~~
相关的书：彭罗斯的《皇帝新脑》
图灵认为存在人脑就是机器，因此也存在人脑无法证明的问题。哥德尔和彭罗斯都同意机器可以模拟人脑的功能，他们认可“人脑是机器”的说法。但他们同时认为人还有其他的特质，原则上不存在人脑无法证明的数学问题。比如哥德尔说的“和物质分离的心”。这实际涉及到强AI之争的终极问题：机器能否有自由意志/自我意识/心/灵魂？或人是否真的有自由意志/自我意识/心/灵魂？
~~~~
霍金&哥德尔
霍金认为物理公理体系可能也会遭遇哥德尔的定理，所以物理学没有终极理论，物理学家不会失业。物理学的公理体系只是我们对认识到的那部分自然界的一种拟合，自然界自身是否自洽是没法知道的。
霍金怎么突然感兴趣起这个来的？ 可能是他年纪大了，开始寻求自身的各种思想自洽性。年轻人通常不会考虑这个，前后矛盾一点也没觉得有什么。好像人老了都喜欢干这种事情，总想追求内心的和谐。年轻的时候不考虑这些也活得好好的不是，所以不自洽不是问题~
##################################################
page 455
Our most detailed information of Babbage’s Analytical Engine comes from a memoir by Lady Lovelace. In it she states, ‘‘The Analytical Engine has no pretensions to originate anything. It can do whatever we know how to order it to perform’’ (her italics). This statement is quoted by Hartree who adds:‘This does not imply that it may not be possible to construct electronic equipment which will ‘think for itself ’, or in which, in biological terms, one could set up a conditioned reflex, which would serve as a basis for ‘learning’. Whether this is possible in principle or not is a stimulating and exciting question, suggested by some of these recent developments. But it did not seem that the machines constructed or projected at the time had this
property.’’
“分析机不会产生新的东西，它只会执行人的指令”，但这并不说明电子设备就一定不会自己思考。只是巴贝奇那个时代的技术水平限制，不大可能制造出的会思考的机器。
A variant of Lady Lovelace’s objection states that a machine can ‘never do anything really new’. This may be parried for a moment with the saw, ‘There is nothing new under the sun’. Who can be certain that ‘original work’ that he has done was not simply the growth of the seed planted in him by teaching, or the effect of following well-known general principles. A better variant of the objection says that a machine can never ‘take us by surprise’. This statement is a more direct challenge and can be met directly. Machines take me by surprise with great frequency. This is largely because I do not do suffcient calculation to decide what to expect them to do, or rather because,although I do a calculation, I do it in a hurried, slipshod fashion, taking risks.
另一种说法是“机器不会做真正是新的事情”，这个和说“阳光下没有新事物”差不多。一个好点的说法是“机器永远不会让我们出乎意料”。实际上机器让我出乎意料的时候相当多, 因为我事先没有做足够的计算，也不知道它们会是多少，也可能匆忙中就算错了。
…I believe, to a fallacy to which philosophers and mathematicians are particularly subject. This is the assumption that as soon as a fact is presented to a mind all consequences of that fact spring into the mind simultaneously with it. It is a very useful assumption under many circumstances, but one too easily forgets that it is false. A natural consequence of doing so is that one then assumes that there is no virtue in the mere working out of consequences from data and general principles.
这可能来源于哲学家和数学家持有的一个错误观念：当一个事实出现在脑子里的时候，它的全部后果也同时出现在了脑子里面。如果这么想的话，那从数据和一般原理得出结论，也不是什么智能行为。实际上，即使我们已经知道怎样从数据得出结论，这个过程仍然涉及到思考。结论即使是确定的，它也不会自动浮现到我们的大脑中。为了得到结论，必须付出代价，要么自己算，要么让机器来算。这个工作机器往往做得比人还要好。
##################################################
page 460
We have thus divided our problem into two parts. The child-programme and the education process. These two remain very closely connected. We cannot expect to find a good child-machine at the first attempt. One must experiment with teaching one such machine and see how well it learns. One can then try another and see if it is better or worse. There is an obvious connection between this process and evolution, by the identifications:
Structure of the child machine –> Hereditary material
Changes of the child machine —> Mutations
Natural selection –> Judgment of the experimenter
为了得到一个能模拟人脑的程序，可以用类似进化的办法，训练婴儿机器，然后做出选择。婴儿机器的结构可以看成是遗传因素，把机器的程序的变化当成是变异，然后实验者来做自然选择，挑出最合适的个体。
~~~~~~
结构与功能
人脑中存在固化的智能行为，生下来就会的。
小孩能区分1、2、3，但不能区分4以上的数，说明人类感知（而不是去数）数字的能力仅限于1~3的数字。面对更多的数字时就要把它化成感知能力范围内的数字来数，也就是“时间换空间”，而小孩还不具备“时间换空间”的能力，所以会把4以上的数都看成“很多”，而不再加以区分。从进化角度解释对数字的感知能力：这是与其它能力相适应的。面对1~3个敌人，也许能打得过，这时候需要弄清楚到底有几个，以采取不同的策略；如果
面对4个以上的敌人，那根本不用数了，基本上打不过，逃跑就是了。这种感知数目的本领，和挨个数的机制不一样，可以迅速做出反应。
智能是一种涌现现象，必须在神经元足够多时才出现。对牛弹琴显然不会有效果的。
线虫只几百个神经元，怎么教都不会有智能，果蝇就好很多，几十万个神经元，
就可以教它们识别图案。
##################################################
TET中第四部分介绍图灵在人工生命方面的工作。其中The chemical basis of mophogenesis一文中，图灵试图阐述，从均匀的空间中，如何产生出形状和图案来。他提出了一个动力学模型，包含了两种基本过程：“反应”和“扩散”，扩散速度的不同，会导致对称性的破缺，从而产生空间不均匀的图案。图案可能是动态的振荡，也可能是静态的，就像美洲豹的斑纹。
~~~~~~~~
page 525
The situation is very similar to that which arises in connexion with electrical oscillators. It is usually easy to understand how an oscillator keeps going when once it has started, but on a first acquaintance it is not obvious how the oscillation begins. The explanation is that there are random disturbances always present in the circuit. Any disturbance whose frequency is the natural frequency of the oscillator will tend to set it going. The ultimate fate of the system will be a state of oscillation at its appropriate frequency, and with an amplitude (and a wave form) which are also determined by the circuit. The phase of the oscillation alone is determined by the disturbance.
图灵斑图的产生机制和振荡器类似。振荡器开始工作后，就可以一直震的下去，但振荡是如何开始的？因为电路中存在随机噪声，当噪声的频率等于系统的本征频率时，振荡就会被触发。当有噪声存在时，系统最终必然会以自己的特征频率振荡起来。这里的振荡状态是系统内在的本征模式，但它的出现却必须由涨落和耗散过程引起。
If chemical reactions and difusion are the only forms of physical change which are taken into account the argument above can take a slightly different form. For if the system originally has no sort of geometrical symmetry but is a perfectly homogeneous and possibly irregularly shaped mass of tissue, it will continue indefinitely to be homogeneous. In practice, however, the presence of irregularities, including statistical fluctuations in the numbers of molecules undergoing the various reactions, will, if the system has an appropriate kind of instability, result in this homogeneity disappearing.
如果一个系统本来就是完全均匀的，那它终将归于均匀。而发生着各种反应，分子数目有统计涨落的系统，系统的均匀性就可能会被破坏。图案的出现就是不均匀性的体现。
讨论时提到的那篇图灵斑图的文章，“Two-stage Turing model for generating pigment patternson the leopard and the jaguar” Phys. Rev. E 74, 011914 (2006)，此处可以下载：http://people.maths.ox.ac.uk/~maini/PKM%20publications/212.pdf。Nature曾经Hightlight过这个工作：Nature 422 , Research Highlights p.604 (August10, 2006). 但原来的网页链接已经失效了，内容如下：
Spot the difference,Phys. Rev. E 74, 011914 (2006). Jungle cats only have true spots when they are kittens. As they grow, the spots become rosettes — broken rings in leopards (pictured) and polygons in jaguars. This changing pattern is the latest to be successfully described using Turing models.
Alan Turing suggested in 1952 that biological patterns could be generated by two chemicals diffusing between cells and interacting under the animal’s coat. Sy-Sang Liaw of National Chung-Hsing University in Taichung, Taiwan, and his team adjusted parameters in Turing’s reaction-diffusion equations to create spots. They then tweaked the parameters so that the patterns resembled the coats of middleaged big cats. However, no one has found the chemicals, which Turing called morphogens, that might make this model work in mammals.
关于图灵斑图可以参考以下这篇文章：生命的另一个奥秘——浅谈生物数学与斑图生成www.math.wm.edu/~shij/mathbio.pdf
######################EOF##########################