描述层次和计算机系统.PDF

描述的层次和计算机系统 集智AI小组平庸的笨蛋 前 言 描述的层次描述的层次 图灵机图灵机 • 层次的意义在 • 图灵机想回答 哪里哪里 ？ 以及无法回答以及无法回答 的问题？ 计算机系统 • 如何制造如何制造一台计算机台计算机 ？？ 集智AI小组 目录 1 希尔伯特问题和图灵机 2 现代计算机系统模型 33 描述的层次描述的层次 集智AI小组 费马大定理 丢番都方程 ax+bby =c ax2+bx+c = 0 2 2 2 ax +by =c 给定方程给定方程 P ((x ,, yy ,, ...)) = 0 ，，如何判如何判 定方程在整数域内是否有解，如果有 ，如何高效找到所有解？这类问题称 为丢番图方程为丢番图方程 费马大定理 其中a b c n取正整数，当n2时， 不存在整数解存在整数解 集智AI小组 希尔伯特第十问题 1900年的第二界国际数学大 会在巴黎举行会在巴黎举行 ，2020世纪最后的世纪最后的 数学王者，大卫 希尔伯特在在 他八月他八月88号周三早上的演讲中号周三早上的演讲中 ， 提出了下个世纪将被研究的 23 个主要的数学问题个主要的数学问题。 第十问题：判定丢番图方程 的可解性的可解性 给定一个系数均为有理整数， 包含任意个未知数的丢番图方程包含任意个未知数的丢番图方程 ：设计一个过程，通过有限次的 计算计算 ，能够能够判定判定该方程在有理数该方程在有理数 整数上是否可解。 集智AI小组 图灵机的基本思想 图灵的基本思想是用机器来模拟人们用纸笔进行数学运算 的过程的过程 ，他把这样的过程看作下列两种简单的动作他把这样的过程看作下列两种简单的动作 ：： 在纸上写上或擦除某个符号； 把注意力从纸的一个位置移动到另一个位置； 而在每个阶段，人要决定下一步的动作，依赖于 (a) 此人当前所关注的纸上某个位置的符号 (b)(b) 此人当前思维的状态此人当前思维的状态。 基本乘法的过程 123123x4545=?? 集智AI小组 图灵机的基本思想 为了模拟人的这种运算过程，图灵构造出一台假想 的机器的机器 ，，该机器由以下几个部分组成该机器由以下几个部分组成 ： 1.一条无限长的纸带 TAPE。纸带被划分为一个接一个的小格 子，每个格子上包含一个来自有限字母表的符号，字母表中有一个特 殊的符号殊的符号 表示空白表示空白。。纸带上的格子从左到右依此被编号为纸带上的格子从左到右依此被编号为 00, 11, 22, ... ，纸带的右端可以无限伸展。 2.一个读写头 HEAD。该读写头可以在纸带上左右移动，它能 读出当前所指的格子上的符号读出当前所指的格子上的符号 ，并能改变当前格子上的符号并能改变当前格子上的符号。 3.