文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 工程科技 > 信息与通信 > 计算的模型:图灵机与Petri网
侵权投诉

计算的模型:图灵机与Petri网

形式化的软件开发方法是建立在严格数学基础上的,其目标是通过严格的分析、验证发现软件设计及开发过程中的模糊性和不完备性,以达到对软件质量的有效控制。Petri网是形式化软件开发的一种很好的描述工具,它在描述异步并发的环境、模型验证等方面有着独到之处;图灵机是迄今为止计算能力最强的计算模型,在理论层面上有着其他模型不可替代的重要作用,它深刻地刻画了物理世界的可识别

2

西华大学学报 自然科学版

模型之一。

上具有指令特点的程序运算操作,存储程序式电为子数字计算机提供了强大的程序设计思想。它的结 构十分简单,作运算相当基本,能却出乎意料的操功强大,程形式的方式准确地刻画了计算这一基以过本的概念。几十年来,学工作者从图灵机出发采科用相近的构造、义方法,出一批计算能力强、定提使用方便、式各异的自动机,不同的观察事物和处形从

1模型、程、算及算法 过计 理论作为一个系统,其演绎推理是需要模型做支撑的。系统模型的定义分为 2类: ) 1以形式化的

方法定义,其特点是虽然不直观

但有利于演绎推理; 2具有图形化的特征的定义,特点是虽然直观但 )其不方便推理。

理问题的角度为计算机学科的发展奠定了重要的理 论基础。

模型是形式化方法解决问题的工具、出发点,缺少模型为基础的叙述不能称作一个理论系统。在计算机学科中,们对于过程、人计算以及算法的理解是 混乱的。过程是处理问题的一系列步骤的总和,可以是有限的也可以是无限的,有模型的要求,并没也

下面有关图灵机的基本概念来自于文献[ 4。 3—]定义 1图灵机 (uigmah e,简记为 T tr c i n n M) 是一个 7元组 M=(, 6 q,。 qj,里 Q,厂,,。g ',r e )这

不要求每一步骤是确定的。计算是指以模型为基础 的处理问题的一个过程,既然是过程,以步骤的总所

Q, F都是有穷集合。Q是状态集;是输入字母 , 表,不包括特殊空白符号口;是带字母表,中口厂其

和可以是有限的也可以是无限的,个步骤都是模每

∈,, c厂;: 6 Q×厂一 9X厂×{ R,是转移函 L, S}数 ( R,, 5分别代表读写头根据转移指令处理正注视的符号后的左移、右移或不动 ) q∈Q是起始状;。 态; g。。 Q是接受状态;。 Q是拒绝状态, q 且

型意义下的一条指令,有确定性。算法是基于模具 型的,现的所有步骤是有限的,实每条指令是确定的,其准确定义由丘奇一图灵命题给出:法的直觉算

概念等于图灵机算法。因此,以这样概括:法可算计算过程。在计算机科学研究中,过程、计算及算 法的概念不能交叉使用。

qe≠ g。I r。t p。 j

定义 2 uv称为一个格局。 q

它描述当前状态 q当前带内容是 l,读写头, l, V 的当前位置是的第 1个符号,上的最后符号带以后的符号都是空白符。在输入上的起始格 局是 qW。 o

人们对计算的理解是模糊的,常常将数字和符 号的运算与计算机软件理论中所指的计算混为一

团。的确,源于运算。10计算 90年伟大的数学家希 尔伯特提出的 2 3个数学问题中有 1 0个问题与

算法

定义 3接受输入 W,如果存在格局的序列 C,。

有关, 1问题是寻找一个算法判定一个多项式第 O个是否有整数根。计算机科学中的计算是指以图灵机 或等价模型为基础的解决问题的过程。 由于计算机科学“源于”学,个纠结的问题数一是数学与计算机科学特别是软件理论的区别何在? 数学与计算机科学的区别在于:者强调过程后者前

C,,使得: … C c是在输入 W上的起始格局;每 个产生 C;是接受格局。… C

定义 4

接受的字符串的集合 L ) (叫图灵

可识别的语言。 在 W上运行时可能出现 3种结果:接受、拒

绝、不停机 (也称循环,是并不是程序设计中的循但 环 )。

要求算法;前者注重演绎推理后者要求构造性证明; 前者研究的对象可以是连续的也可以是离散的,后 者研究的对象是离散的。

定义 5如果在 W上以接受或拒绝格局停 机," ̄定器。, )图灵可判定的。 M q- u J是 ( 可判定一定是可识别的,是可识别推不出可但

2图灵机及计算的度 图灵机是由 A a uig于 1 3 l Tr n n 9 6年提出的计算模型。T r g这种简单的数学机器出发,出了 ui从 n给计算的概念。图灵机引入了机器状态,用了本质使

判定。对于一个问题,们当然希望能得到判定器,人 因为机器对于输入经计算后输出是“ e”“ o。 Y s或 N”在判定器里,别的条件是充分必要的;识别器识在里,识别的条件是充分或必要的即可。在数学研究

计算的模型:图灵机与Petri网

上一页第2页

TOP相关主题

热门文档

相关文档

  • 基本图灵机的Petri网建模研究

    1 基本图灵机及 Petri 网 1.1 基本图灵机图灵机是一种抽象的计算模型。 图灵机基本模型有一个有穷控制器,一条输入带和一个带头,输入带被分成许多单元,带头在...

  • Petri网模型的语用计算机

    —问题与探索; 我对计算机的认识—二元计算模型; 现阶段的研究与开发— 语用...络伊曼 结构 图灵机 Petri网 ? 状态元素 内存单元 变化元素 机器指令 关系 ...

  • Petri网模型

    Petri网模型_信息与通信_工程科技_专业资料。Petri网模型及应用Petri网基本概念 1960年德国Carl Adam Petri博士首次提 出 Petri网是一种图论工具,适于对离散事 件动...

  • Web1.0、_Web2.0、Web3.0、Web4.0、Web5.0及Web6.0的涵义

    语用网里,计算应用 界的人们所关心的是他们设计的软件模块和语用文章。前者是 图灵机模型的应用,关注于算法的可计算性和计算复杂度问题; 后者是Petri网理论的应用...

  • 小多项式时间万能Petri网

    小型通用Petri网的库所/变迁数(14,42)和(14,29)用模拟已知的小通用图 灵机...因此,构建UPN是有效的计算模型。 接下来,PolyUPN(15,29)网由UPN(14,29 )网...

  • 计算机学科的12个核心概念

    概念和形式模型主要采用数学方法进行研究。例如用于研究计算能力的 常用计算模型有图灵机、递归函数、λ 演算等;用于研究并行与分布式特性的 常用并发模型有 Petri 网...

  • 算法与图灵机模型

    ? ? ? ? 图灵机缘起 图灵机描述 计算“X+1”的图灵机 通用图灵机 图灵机模型的启示 01:00 2.2.1图灵机概念 ? 1900,德国数学家希尔伯特提出"23个数学难题...

  • Petri网模型参数化可达图研究(1)

    s∈S: 2 参数化模型性质检测相关工作由于一般的 Petri 网模型可达图都是根据初始标识计算 出来的,如果系统模型是参数化的,即初始标识的位置标记 数量是变量参数,...

  • 三划分问题可多项式归约为唯一可达向量Petri网可达性问题

    可计算 性和计算复杂性理论中几个相关的基本概念111J.用 不确定的图灵机在...扩展的三划分问题的Petri网模型算法1 归约为Petri网三的可达性问题,算法1详细...

  • 语用网的搜索原理

    这个计算哲学模型的地位,在计算机科学领域里,就相当于"图灵机"和"Petri 网" . 我希望 10 年后我能够表达出这个计算哲学的系统模型来. 分享到: X 分享到: ...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email