量子逻辑 多值逻辑、模糊逻辑（剩余格值逻辑）

浅谈计算机科学的若干基础理论



信息科学与技术学院

计算机科学系


邱 道 文

2007年11月







计算学科的定义


ACM（Association for Computing Machinery, 美国计算机协会）
IEEE-CS (Institute of Electrical and Electronics Engineers—Computer Society, 美国电气与电子工程师学会计算机分会)
EATCS(欧洲理论计算机科学协会)
计算学科——对描述和变换信息的算法过程进行的系统研究，包括理论、分析、设计、效率、实现和应用等。
根本问题——什么能被有效地自动进行。它源于对算法理论、数理逻辑、计算模型、自动计算机器的研究。





计算学科的分支


计算机科学
信息系统
软件工程
计算机工程
信息技术
新增专业





内容纲要


计算概念的历史背景
计算机科学的若干基础理论
（１）数理逻辑与集合论

（２）代数系统

（３）图论

（４）形式语言与自动机

新的计算理论（非经典计算）——量子计算





计算机科学的最高奖——图灵奖


图灵（ １９１２－１９５４）：英国著名数学家，计算机逻辑的奠基者，计算技术与人工智能的先驱。１９３６年提出现代计算机的数学模型——图灵机。（哥德尔）
图灵奖：１９４６年，世界上第一台电子计算机诞生；１９６６年，ACM决定设立“图灵奖”——计算机科学中杰出的科学家，每年一般一名





数学家与图灵奖


大部分图灵奖获得者是学数学出生或数学家，例如：
M. Minsky, 1969

E.W. Dijkstra, 1972

D.E. Knuth, 1974

S.A.Cook,1982

D.M. Ritchie, 1983

R.M.Karp, 1985

R.E. Tarjan, 1986

J.Cocke, 1987

W.V. Kahan, 1989

R. Milner,1991, 还有很多计算复杂性的获奖者如 J.Hartmanis






另一重要奖——IEEE计算机先驱奖


IEEE-CS设立并颁发
１９８０开始
理论与实践、设计与工程实现、硬件与软件、系统与部件





什么是计算?


通俗的讲：从一个符号串f变换成另一个符号串g ，如:
四则运算
方程的求解、函数的微分积分
定理的证明推导
类型：数值计算和符号推导





计算的实质与Church－Turing论点


什么是计算、什么是可计算性
20世纪30年代到40年代，数理逻辑学家相继提出了四种计算模型 ：一般递归函数、λ可计算函数、图灵机和波斯特系统





经典计算的简要历史背景


1936年A.M. Turing提出了一类抽象的计算模型——Turing机（它与当今的计算机有同样的计算能力）。
同时期，还有A.Church（ 转换演算，1935年）。
K.Godel,S.C.Kleene,和E.Post (递归函数，1936年）等人的工作探讨可计算性问题。
Church-Turing命题：直观上可计算的函数类就是Turing机及任何与Turing机等价计算模型可计算的函数类。或任何算法过程都可被（概率）Turing机有效地模拟。





　　计算机科学与人工智能之父——A. Turing (图灵１９１２－１９５４): １９３６年提出图灵机；１９６６年第一届图灵奖（侧重在计算机科学理论和软件方面）






天才数学家，计算机之父——John von Neumann (冯·诺伊曼1903-1957 ):世界上第一台电子计算诞生于1946年2月美国






经典计算的简要历史背景（续）


1940’s和1950’s, 另一类更简单的计算模型——有限自动机及形式文法的提出（文本处理、编译程序、硬件设计、自动控制、人工智能等）。
1960’s S.Cook发展Church-Turing命题，提出计算复杂性——NP完全问题，如可满足性(SAT)。





计算机科学技术的主要分支
(从授予历届图灵奖得主的研究工作)


计算机体系结构
程序设计语言
算法设计与分析
操作系统和编译程序
数据库技术
计算复杂性理论
软件工程
人工智能





基础理论(I)——数理逻辑


形式逻辑（古典逻辑）——亚里士多德（公元前４世纪）：研究思维的形式及其规律的科学。苏格拉底三段论。
数理逻辑——符号逻辑，用数学的方法研究思维；莱布尼兹。
国际上很多关于数理逻辑的著名学术期刊，如Journal of Symbolic Logic





三个阶段：第一阶段


１７世纪６０年代至１９世纪８０年代
用一些初级的数学方法处理古典逻辑演绎推理的形式和规律，也即用符号和简单的代数方法处理传统逻辑的演绎推理，代表人物有笛卡尔、莱布尼兹、德摩根、布尔





第二阶段


１９世纪８０年代至２０世纪３０年代
把初等数论和集合论等数学方法运用到逻辑上，取得较大突破。代表人物，如弗雷格、皮亚诺、罗素、希尔伯特





第三阶段


２０世纪３０年代至今
形成了自己的理论体系，包括：逻辑演算；证明论；集合论；模型论；递归论，其中逻辑演算（命题演算和谓词演算）是基础





与计算机科学的关系：理论基础


莱布尼兹的思想：数理逻辑、数学、计算机出自同一目的——思维过程的演算化和计算化，并在计算机上实现
关于形式语言的研究，为程序语言提供了基础
关于形式系统的语法、语义的研究，解决计算机软件的语言设计问题
简化计算机线路问题归结为简化一个命题逻辑问题（硬件设计的应用）
计算机科学对数理逻辑的研究有推动作用
人工智能——人工智能逻辑




http://74.125.127.160/search?q=cache:5dBKNmQoOMMJ:www.cs.sysu.edu.cn/teaching/freshmen/fls202.ppt+%22%E9%87%8F%E5%AD%90%E8%AE%A1%E7%AE%97siwei%22&cd=3&hl=zh-CN&ct=clnk&gl=cn&st_usg=ALhdy2-F48lS69rKwTSMZ0AYheqK_SU7JQ


PPT] 量子计算模型及一些相关问题文件格式: Microsoft Powerpoint - HTML 版
莱布尼兹的思想：数理逻辑、数学、计算机出自同一目的——思维过程的演算化和计算 ..... 结合量子物理原理与经典计算理论，我们主要从理论上探讨量子计算与信息中的一些 ...
www.cs.sysu.edu.cn/teaching/freshmen/fls202.ppt - 类似结果

数理逻辑的发展


多值逻辑、模糊逻辑（剩余格值逻辑）
人工智能逻辑：用逻辑方法和成果研究智能主体如何处理知识的学问，研究主体的常识推理，如缺省逻辑、非单调模态逻辑、和限定逻辑
量子逻辑





命题演算


命题——能分辨真假的陈述句
逻辑联结词：否定、合取、析取、条件、双条件
命题符号化
公式的蕴涵：永真式
公式的范式





一阶谓词演算


凡是人都是要死的；苏格拉底是人，所以苏格拉底是要死的。
谓词P(x)
量词：全称量词（任意）、存在量词（存在）
变元(x)与常元(a)
程序设计理论、语义形式化及程序逻辑研究的基础；程序验证、定理证明和知识表示的有力工具





模态逻辑


（凡是人都是要死的；苏格拉底是人，所以苏格拉底是要死的。）
亚里士多德：“明天波斯和雅典将发生海战”。
事物的“势态”，人的“情态”以及过程的变迁：“必然、可能”，“应该、允许”，“一贯、偶然”等等。
□A——必然A; ◇A——可能A
模态命题逻辑与模态谓词逻辑





公理集合论——集合论


数学与计算机科学理论的必备工具
康托：１８７４年提出了“集合”和“无限”概念
庞加莱——有趣的“病理学的情形”
希尔伯特——“没有人能把我们从康托为我们创造的乐园中开除出去”





集合论的基本概念


康托：“一些确定的、不同事物的总体，这些事物人们可以意识到，并且能判别一个给定的事物是否属于这个总体。”
互异性、无序性、确定性
表示法：列举法、描述法、图示法、归纳法（公理集合论）





公理化


罗素悖论：理发师称不给“给自己理发的人理发”，只给“不给自己理发的人理发”，那么理发师给不给自己理发？
根源于没有建立“基础公理”：对任何非空集合A，存在x属于A,使得x和A没有任何相同元素。 若A属于A，则A不是集合。





集合的运算、覆盖与划分


交与并、差与对称差
覆盖
划分（两两不相交）





集合的基数


有限集合
无限集合：可数集合与不可数集合
连续统假设：不存在任何基数介于整数集合的基数与实数集合的基数之间





代数系统——抽象代数


运算的扩充
数集的扩充
积分的扩充





代数系统


在信息论（编码）中有重要应用
非空集合与若干n元运算——代数系统
特殊元素：幺元，逆元，零元
代数系统的同态与同构





特殊代数系统


半群与子半群
群
环和域





格——一类重要的代数系统


０，１上的布尔代数是计算机的逻辑基础
定义
偏序与交、并二元运算的关系





一些特殊的格


分配格——分配律
有界格
有补格
有补分配格——布尔代数





一些非经典逻辑的代数系统


剩余格——模糊逻辑
正交补格——正交逻辑
正交模格——量子逻辑





图论简介


研究图中点与点、点与线的性质
１８世纪，源于哥尼斯堡７桥问题——１７３６年，欧拉。
算法、数据库、操作系统、人工智能、网络设计、开关理论等方面应用广泛
计算复杂性理论——涉及很多NP完全问题，如顶点覆盖问题是NP完全的、哈密顿回路问题





计算模型——自动机及形式语言


有限自动机——正则语言——正则文法
下推自动机——上下文无关语言——上下文无关文法
线性有界自动机——上下文有关语言——上下文有关文法
图灵机——短语结构语言——短语结构文法





计算模型——有限自动机


五元组定义（或三元组）
如，超级市场的进出口门
计算能力不如图灵机，但能做很多事
２０世纪５０年代至今的重要研究领域（学术期刊，从理论到应用）
自动控制——模拟离散事件系统
模拟神经网络
识别正则语言
确定与非确定型





有限自动机的发展


概率有限自动机——M.O.Rabin于1963提出,他是１９７６年图灵奖得主
模糊有限自动机——受Zadeh模糊集的思想启发





我们的一个研究工作


用概率有限自动机和模糊有限自动机模拟离散事件系统（自动控制的重要方向）
模糊离散事件系统





下推自动机


比有限自动机能力更强
识别上下文无关语言
确定与非确定型





图灵机－１９３６年


识别短语结构语言（０型语言）
确定与非确定型——P与NP类





非经典计算——自然计算


遵循自然系统中的法则、原理和机制而进行计算
如细胞自动机、分子计算、光子计算、及研究最多的量子计算
信息处理：生物信息处理、量子信息处理





量子计算


量子计算机——以量子力学原理直接进行计算的计算机
量子信息与量子计算是信息论和计算机科学与量子物理交叉的学科





纲要


（量子）计算的研究背景与发展
简介部分已经开展的工作
可能开展的工作






量子计算的研究背景与发展









回忆刚才谈到的经典计算


1940’s和1950’s, 另一类更简单的计算模型——有限自动机及形式文法的提出（文本处理、编译程序、硬件设计、自动控制、人工智能等）。
1960’s S.Cook发展Church-Turing命题，提出计算复杂性——NP完全问题，如可满足性问题。





经典计算理论（ACM)


自动机理论
可计算性
计算复杂性
FOCS (IEEE-CS)

STOC (ACM)

Journal of the ACM

SIAM Journal on Computing (SIAM)

Information and Computation

Journal of Computer and System Sciences

Theoretical Computer Science









《Theoretical Computer Science》


Section A: Algorithms, automata, complexity and

games


Section B: Logic, semantics and theory of

programming


Section C: Natural computing (evolutionary

computing, neural network, molecular

computing, quantum computing, …)






二十世纪两项伟大的科学成就


量子力学的创建——它是20世纪人类文明发展的一个重大飞跃
计算概念的形式化（C-T 假设）——标志着人类对可计算函数与计算本质的认识达到了空前的高度，它是数学史上一块夺目的里程碑





几乎可以肯定，世界上没有第二张照片，能像这张一样，在一幅画面内集中了如此之多的、水平如此之高的人类精英






　这是1927年在布鲁塞尔举行的第五届索尔维会议上的照片。在这次会议上，爱因斯坦和玻尔这两个当时世界上最顶尖的物理学家，进行了科学史上著名的学术辩论。在这次辩论中，玻尔所代表的新生量子论学派获得了更广泛的支持，而维护经典理论的爱因斯坦则被认为不合时宜，站到了对立面。







非经典计算的提出：量子计算与分子计算的特征


用现实的物理和生物系统的原理与经典计算相结合而进行计算处理。
1994年11月，美国计算机科学家阿德勒曼(L.Adleman)在美国《科学》上公布DNA计算机的理论，并成功运用DNA计算机解决了一个有向哈密顿路径问题。 DNA计算机的提出，产生于这样一个发现，即生物与数学的相似性：生物体异常复杂的结构是对由DNA序列表示的初始信息执行简单操作(复制、剪接)的结果





光学计算机、量子计算机、蛋白质计算机等新型计算机模型层出不穷，它们使原有的计算方式发生了前所未有的变化。
量子计算与量子信息是研究基于量子力学原理进行计算和信息处理。量子计算机是一类遵循量子力学规律进行高速数学和逻辑运算、储存及处理量子信息的物理装置。
量子计算与经典计算的本质不同：复概率振幅；状态演化的酉性；量子状态叠加；量子相干；量子并行；量子纠缠。一些增强计算能力，而一些限制了计算能力。





存储能力


在经典计算机里，一个二进制位(bit)只能存储一个数据，n个二进制位只能存储n个一位二进制数或者1个n位二进制数，而在量子计算机里，一个量子位(Qubit)可以存储两个数据，n个量子位可以同时存储 ２的n次方个数据，从而大大提高了存储能力。





计算方式及其演变


简单地讲，所谓计算方式就是符号变换的操作方式，尤其指最基本的动作方式（筹算 、珠算 、笔算 、机器计算、１９４６年２月诞生的世界上第一台电子计算机 ）
DNA计算 （计算理念，化学性质）





计算方式及其演变 （续）


　　量子计算机使计算方式的进化又有了新的可能。电子计算机的理论模型是经典的通用图灵机——一种确定型图灵机，量子计算机的理论模型——量子图灵机则是一种概率型图灵机。直观一些说，传统电脑是通过硅芯片上微型晶体管电位的“开”和“关”状态来表达二进位制的0和1，从而进行信息数据的处理和储存。每个电位只能处理一个数据，非0即1，许多个电位依次串连起来，才能共同完成一次复杂的运算。这种线性计算方式遵循普通的物理学原则，具有明显的局限性。而量子计算机的运算方式则建立在原子运动的层面上，突破了分子物理的界限。






计算方式及其演变 （续）


　　根据量子论原理，原子具有在同一时刻处于两个不同位置、又同时向上下两个相反方向旋转的特性，称为“量子超态”。而一旦有外力干扰，模糊运动的原子又可以马上归于准确的定位。这种似是而非的混沌状态与人们熟知的常规世界相矛盾，但如果利用其表达信息，却能发挥出其瞬息之间千变万化而又万变不离其宗的神奇功效。因为当许多个量子状态的原子纠缠在一起时，它们又因量子位的“叠加性”，可以同时一起展开“并行计算”，从而使其具备超高速的运算能力。“电子线性计算方式如同万只蜗牛排队过独木桥，而量子并行运算好比万只飞鸟同时升上天空”。

例: 叠加——量子双向自动机

　纠缠——超密译码与量子隐形传输（量子通信）






量子计算理论


量子自动机
量子可计算性
量子计算复杂性





量子计算的历史


1973年Bennett证明了逻辑可逆Turing机的存在性。（不可逆运算导致耗能和芯片发热，Landauer）
1982年Benioff证明了量子计算机的计算能力不亚于经典计算机。
1982年Feynman指出在经典计算机上模拟量子物理系统演化的速度将呈指数减慢。
1985年Deutsch将上述思想形式化, 提出了所谓的Church-Turing principle, 并定义了量子计算模型－量子Turing机。
P.Shor于1994年发现了在量子计算机上进行大数分解的多项式时间算法（这是非常惊人的发现）。Grover 搜索算法，1996.





量子复杂性理论


量子复杂性理论(Bernstein and Vazirani, Quantum complexity theory, SIAM J. Comput. 26 (1997) 1411-1473.)
BPP 包含于BQP
量子Turing机可被量子电路有效模拟(A.C. Yao, Quantum circuit complexity, in: Proc. 34th IEEE Symp. Foundations of Computer Science, 1993, pp.352-361.)





量子复杂性理论（续）


量子通信复杂性 (Andrew M. Steane and Wim van Dam )与量子密码(Brassard and Crepeau 1996 )





量子信息的基本概念


Quantum bit—qubit, is represented by




where








量子信息的基本概念（续）


An operation on a qubit, called a unitary gate, is a unitary mapping




where is a two-dimensional Hilbert space.


Measurement--






量子信息的基本原理


Quantum state cannot be cloned—No-cloning theorem (1982,Nature)
Quantum state cannot be deleted—No-deleting principle (2000,Nature)





量子纠缠(量子通信）


Superdense coding（纠缠＋一个量子比特→传输两个经典比特）
Quantum teleportation（纠缠＋两个经典比特→传输一个量子比特）
量子算法





量子计算模型


Quantum Finite Automata
Quantum Pushdown Automata
Much more complexity than QFAs

Quantum Multi-stack machines
They can simulate QTMs

Quantum Counters








量子计算模型(续）


Quantum Sequential Machines
Quantum Neural Networks








简要介绍我们的一些工作


结合量子物理原理与经典计算理论，我们主要从理论上探讨量子计算与信息中的一些基本问题：


量子计算模型的等价性
量子计算的逻辑基础
量子状态的概率克隆与分辨
量子通信





量子计算模型的等价性


量子通信中的问题（略）
量子下推自动机
判定量子时序机的等价性
判定量子自动机的等价性
>








随机 (概率) 时序机


（概率自动机:Turing奖得主M.O.Rabin)

M=(S,I,O,A(y|x))

S=(q1，q2 ，．．．，qn)

aij(y|x)












随机时序机的等价性







M1=(S1,I,O,A1(y|x))

M2=(S2,I,O,A2(y|x))




|S1|+|S2|-1







量子时序机


M=(S,I,O,A(y|x))

S=(q1,q2,…,qn)

aij(y|x)















量子时序机的等价






M1=(S1,I,O,A1(y|x))

M2=(S2,I,O,A2(y|x))











等价性问题









Staley Gudder提出 一个公开问题：是否有类似于随机时序机的结果？









否定性结果(2002,Qiu)






M1=(S1,I,O,A1(y|x))

M2=(S2,I,O,A2(y|x))

当长度不超过|S1|+|S2|-1时，



但当长度超过|S1|+|S2|-1时，有时不相等．








量子时序机的等价性







《Theoretical Computer Science》












直接判定等价性的计算复杂性















等价性的多项式判定算法















与量子Turing机有关的几类计算模型之间的模拟


93年姚期智证明：量子线路多项式时间模拟量子Turing机。
量子多栈机、量子多计数机多项式时间模拟量子Turing机。





量子信息中的最近一个结果


　The well-known Helstrom limit for the　average error probability of ambiguous discrimination of two quantum states has been extended to a lower bound for the ambiguous discrimination of many quantum states.







量子计算的逻辑基础


量子逻辑的历史根源：

经典力学的命题演算的逻辑结构是一个布尔格（Boolean lattice，分配格）的结构；
量子力学命题演算的逻辑结构是正交有补模格（非分配格）。它首先是由Birkoff和von Neumann于1930’s年提出，人们把它作为描述量子力学的逻辑基础。





问题的提出



从计算的观点：经典计算的逻辑基础是布尔逻辑；那么，量子计算的逻辑基础是什么？
国内外学者的一些研究





可能进一步的部分研究


量子时序机的状态最小化，进一步得到量子自动机的状态最小化。
将量子纠缠引入到计算模型中，以增强计算能力。
将量子自动机应用于交互式证明系统（量子密码学）。
（概率）量子超密译码及量子通信复杂性。
还有很多重要问题值得研究．．．










Thanks for

your attention!