蓝星のXSK'S BLOG

-_-b 我对面那个负责的项目就是这个游戏...这个游戏已经有开源版本了...公司那群家伙居然还去自己做...弄得一团糟...真是的...在这咨讯的时代里做事要有效率啊...
- -继续BS不让做开发的上网的公司...
上次ZXH大的题目里其实就是从这个游戏出来的算法...

http://www.ibiblio.org/lifepatterns/
这里是LINK...开JAVA APPLET运行...如果你不能读取的话请装上JAVA的runtime...


------------------------------------------
在一个有许多正方格的大棋盘上随

意放一些棋子，称为胞体（cell），然后遵循下面的规则：

（1）复生：一个胞体在t时刻是"死"，而在t+1时刻是"活"，如果它的八个邻域有
三个胞体在t时刻是"活"的。

（2）死于孤单：一个活的胞体在t时刻没有或只有一个胞体邻域，就会在t+1时刻
死亡。

（3）死于过度拥挤：一个活的胞体在t时刻如有四个或四个以上的邻居，就会在
t+1时刻因过度拥挤而死去。

（4）生存之道：一个胞体在t时刻生存而能延续生命到t+1时刻，当且仅当它在t时
刻有二个或三个活邻域。

就是这样简单的规则，却可以随着初始状态的不同产生无穷无尽的变化，有兴
趣的读者可以连上
http://www.ibiblio.org/lifepatterns/，点击其中的"enjoy
life"键，随意自己设定初始状态，或者打开别人设计好的一些有趣的状态，看看
这个简单平台上出现的复杂世界。

1970年，这个"生命游戏"甫一发明出来便轰动了世界，很多人乐此不疲。据说
有一段时间，全世界四分之一的电脑都在运行这个程序。这个游戏的设计者，就是
本文的主人公，英国数学家John Horton Conway.

1、“逻辑”浅释
中文的“逻辑”显然音译自英文的“logic”。logic又来自中古拉丁文的logica，logica又源自希腊文logos（λóγｏｓ）。logos一般翻译为“逻格斯”，接近于中文里的“道”。
中文的“道”和希腊文“logos”都有以下两层意思：
（1）各种事物的定义或者各种活动的规则（西方各门学科的名字都以 -logy缀后的习惯）
（2）言说，言谈
这两层意思也是相互关联的。言谈是为揭示事物的道理，道理也往往通过言谈得以显示。我们可以构造一个有趣的句子“道道道”，意思是“道说是通往道理的道路”。
在言谈和辩论中，渐渐发展出逻辑学这一领域。从地域来分，古代逻辑学可以分为希腊逻辑学（亚里士多德），印度逻辑学（因明学）和中国逻辑学（墨子名学）。
在以往，逻辑学是哲学的一个分支。1800中期后，逻辑学也成为数学的一个分支。近代以来，逻辑学成为计算机科学的重要基础。根据应用的领域，逻辑可以分为哲学逻辑，数理逻辑和计算逻辑。

2、逻辑与哲学佛学的关系
逻辑与哲学是密切相关的，一直伴随着哲学的发展，从亚里士多德的《工具论》到弗雷格的《算术基础》。当代西方哲学的一个重要方向分析哲学(语言哲学)的发展史就是逻辑学的发展史，当代西方哲学的另一个重要方向现象学与逻辑也存在密切关系，现象学祖师胡塞尔就是从逻辑研究走向了现象学。此外，逻辑学给哲学研究提供了一个思维基础，现在哲学的各个子学科基本上都要求有逻辑的基础。比如伦理学也有规范伦理学。可以说，逻辑是哲学殿堂的基石和立柱。当然，逻辑也是科学的基石和立柱。你看，现代学科都要加上“-logy”的后缀。
佛学里也有思辨性相当强的集量论和唯识学，与当代西方的分析哲学（语言哲学）和现象学正好存在某种平行的关系。佛学里结合得很完美的集量论和唯识学，无疑将为西方哲学的走向提供一个重要的参考。分析哲学主要提供了研究的形式（手段），确保推理的保真性；现象学则主要提供了研究的内容，确保作为起点的公理的直观性。
此外，佛学在使用逻辑的时候，同时也批判逻辑的局限性。在言说真理的时候，我们不得不使用逻辑，但在某些时候我们又必须超越逻辑，才能进一步地认识真理。以下引禅宗一个故事：（赵州）问南泉：“如何是道。”南泉曰：“平常心是道。”师曰：“还可趣向否。”南泉曰：“拟向即乖。”师曰：“不拟时如何知是道。”南泉曰：“道不属知不知。知是妄觉。不知是无记。若是真达不疑之道。犹如太虚廓然虚豁。岂可强是非耶。”师言下悟理。

3、数理逻辑与计算机科学的关系
(1) 首先，从计算模型和可计算性的研究来看，可计算函数和可计算谓词（一种能够能行判定其真值的断言或逻辑公式）是等价的，相互之间可以转化。这就是说，计算可以用函数演算来表达，也可以用逻辑系统来表达。作为计算模型可以计算的函数恰好与可计算谓词是等价的，而逻辑系统又能通过自身的无矛盾性保证这样一种计算模型是合理的。由此可见，作为一种数学形式系统，图灵机及其与它等价的计算模型的逻辑基础是坚实的。人工智能领域的一个重要方向就是基于逻辑的人工智能。
(2) 实际计算机的设计与制造中，使用数字逻辑技术实现计算机的各种运算的理论基础是代数和布尔代数。布尔代数只是在形式演算方面使用了代数的方法，其内容的实质仍然是逻辑。
(3) 从计算机程序设计语言方面考察，语言的理论基础是形式语言、自动机与形式语义学。而形式语言、自动机和形式语义学所采用的主要研究思想和方法来源于数理逻辑和代数。程序设计语言中的许多机制和方法，如子程序调用中的参数代换、赋值等都出自数理逻辑的方法。此外，在语言的语义研究中，四种语义方法最终可归结为代数和逻辑的方法。而且，程序的语义及其正确性的理论基础仍然是数理逻辑，或进一步的模型论。
(4) 在计算机体系结构的研究中，象容错计算机系统、Transputer计算机、阵列式向量计算机、可变结构的计算机系统结构及其计算模型等都直接或间接与逻辑与代数密不可分。如容错计算机的重要基础之一是多值逻辑，Transputer计算机的理论基础是CSP理论，阵列式向量计算机必须以向量运算为基础，可变结构的计算机系统结构及其计算模型主要采用逻辑与代数的方法。
（以上参考赵致琢老师《计算科学导论》）

4、数理逻辑基础的两种教学模式
“数理逻辑基础”是计算机科学与技术专业核心基础课程，也是学科重点专业基础课程之一，属于教学计划中的必修课程。数理逻辑和代数是计算机科学最重要的数学基础。历史上，数理逻辑在发展中受不同数学学派的影响甚深，形成了不同的逻辑学派。各逻辑学派在表达数理逻辑基础内容时，在对内容的选材和表达形式方面存在很大不同，考虑到对计算机科学学科影响较大的是形式主义逻辑学派和直觉主义逻辑学派，因此，课程教学大纲在制定时划分为两个模式。
其中，第一模式介绍基于形式主义逻辑学派的数理逻辑基础内容，第二模式介绍基于直觉主义逻辑学派观点的数理逻辑基础内容。
本课程（第一模式）的教学任务是，以基础数学、计算机科学、科学哲学和人的日常生活为广泛的背景，从形式主义的观点，介绍作为数学基础分支之一的数理逻辑基础知识，帮助学生掌握数理逻辑基础最基本的知识，为今后逐步实现理性层面上的思维方式的数学化打下坚实的基础，为后续课程提供必要的数理逻辑基础。

5、课程内容
数理逻辑概述：数理逻辑的发展概述；数理逻辑与科学思想方法；逻辑演算与符号约定；
命题逻辑的非形式演算：基本概念；等值演算；范式；公式的蕴涵和推理；
命题逻辑的形式演算：形式系统简介；形式系统；形式系统的性质；
一阶谓词逻辑的非形式演算：基本概念；等值演算与前束范式；公式的蕴涵和推理；
一阶谓词逻辑的形式演算：形式系统；可证等值；形式系统的性质；模型；
归结原理：Skolem标准型与子句集；子句集的Herbrand域；Herbrand定理；合一算法；归结原理及其完备性
直觉主义逻辑：直觉主义的直观介绍；直觉主义的一阶谓词逻辑的非形式演算；直觉主义的一阶谓词逻辑的形式演算；直觉主义逻辑的Kripke语义；直觉主义逻辑的完备性；
数学系统：一个例子；含有等词的一阶系统；群论；一阶算术；形式集论；相容性与模型
(* Gödel不完全性定理：引言；可表达性；递归函数和递归关系；Gödel编码；不完全性定理)
数理逻辑与计算机科学（这部分内容结合短学期以讲座形式开设）：数理逻辑的发展；数理逻辑与计算理论；数理逻辑与算法；数理逻辑与程序设计语言；数理逻辑与程序设计；数理逻辑与人工智能；数理逻辑与计算机硬件系统；数理逻辑与其他分支学科。

6、使用教材和参考书：
1、Hamilton, logic for mathematicians, Cambridge University Press,1978(国内影印本，清华大学出版社，2003)
相应中译本：哈密尔顿著，骆如枫等译，《数学家的逻辑》，商务印书馆，1989年
2、胡世华、陆钟万著，《数理逻辑基础》，科学出版社，1981
3、陆钟万著，《面向计算机科学的数理逻辑》，科学出版社，1998
4、S.C.Kleene著，莫绍揆译，《元数学导论》，科学出版社，1985（数理逻辑与递归函数的关系有较深入展开）
5、Lassaigne, et al., logic and complexity, Springer, 2004（较新，关于逻辑与复杂性有较深入展开）