机械式手动计算机 机械计算机 ·法国数学家、哲学家帕斯卡在1642年发 明了一种机械计算机,并与1649年取得 专利。帕斯卡的计算机采用一种齿轮系 统,其中一小轮转十个数字,下一个小 轮便转动一个数字,通过齿轮系的联 动,可以进行加法和减法的运算 清华大学宋域恒 请华大学宋恒 图灵 图灵机模型 大半个世纪以来,数学家、计算机 有限状态 控制器 念英国数学家Iuri 912-1954)而设立的图灵奖成为计 读写头 带 清华大学末斌恒 请华大学宋恒 图灵机模型 图灵机定义 图灵机模型用一个无限长的带子作为无限存储 图灵机是一个7元组(Q,T,6,q0,q1,q2, 它还有一个读写头,这个读写头能在带子上读 其中Q,∑,都是有穷集合并宜 写和移动:开始时,带子上只有输入串,其它地 1)Q是状态集 方都是空的当它需要保存信息时,读写头就把 2)∑是输入字母表不包括特殊空白符号 信息写在带子上为了读某个输入或写下的信 ·3)r是带字母表,其中:∈T,∑是的子 息,带子可能将读写头往回移动到这个信息所 在的地方这样读,写和移动,机器不停的计算 4)6:Q×r→Q×r×{LR}是转移函数 直到产生输出为止机器实现设置了两种状态 0∈Q是起始状态 接受或拒绝 6)q1∈Q是接受状 7)q2∈Q是拒绝状态,且q2≠q1 清华大学末破恒 请华大学宋2 清华大学 宋斌恒 7 机械式手动计算机 清华大学 宋斌恒 8 机械计算机 • 法国数学家、哲学家帕斯卡在1642年发 明了一种机械计算机，并与1649年取得 专利。帕斯卡的计算机采用一种齿轮系 统，其中一小轮转十个数字，下一个小 轮便转动一个数字，通过齿轮系的联 动，可以进行加法和减法的运算. 清华大学 宋斌恒 9 图灵 • 大半个世纪以来，数学家、计算机 科学家提出了各种各样的计算模型 都被证明是同图灵机器等价的。这 一理论已被当成公理，它不仅是计 算机科学的基础，也是数学的基础 之一。为纪念英国数学家Turing (1912-1954) 而设立的图灵奖成为计 算机界的诺贝尔奖. 清华大学 宋斌恒 10 图灵机模型 清华大学 宋斌恒 11 图灵机模型 • 图灵机模型用一个无限长的带子作为无限存储 , 它还有一个读写头 ,这个读写头能在带子上读 , 写和移动 : 开始时 ,带子上只有输入串 ,其它地 方都是空的 .当它需要保存信息时 ,读写头就把 信息写在带子上 .为了读某个输入或写下的信 息 ,带子可能将读写头往回移动到这个信息所 在的地方 .这样读 ,写和移动 ,机器不停的计算 , 直到产生输出为止 .机器实现设置了两种状态 : 接受 或 拒绝 清华大学 宋斌恒 12 图灵机定义 • 一个图灵机是一个7元组(Q,∑,Γ,δ,q0,q1,q2), 其中Q,∑,Γ都是有穷集合,并且 • 1) Q 是状态集. • 2) ∑是输入字母表,不包括特殊空白符号︺. • 3) Γ 是带字母表,其中: ︺∈Γ,∑是Γ的子 集. • 4) δ: Q×Γ→Q×Γ×{L,R}是转移函数. • 5) q0∈Q是起始状态. • 6) q1∈Q是接受状态. • 7) q2∈Q是拒绝状态,且 q2≠q1