计算机的理论模型 |
您所在的位置：网站首页 › 图灵机基础原理 › 计算机的理论模型 |
计算机的理论模型
|
计算机的理论模型——图灵机
1. 图灵机的由来
图灵机由英国数学家阿兰·麦席森·图灵（Alan Mathison Turing）于1936年提出的一种抽象的计算模型，即一切可计算问题都可以由一个虚拟的机器代替人类进行计算。
图灵机的概念在《论数字计算在决断难题中的应用》中提出，原论文题目为《On Computable Numbers, with an Application to the Entscheidungsproblem》，链接https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf 可计算问题 定义：设函数f的定义域是D，值域是R，如果存在一种算法，对D中任意给定的x，都能计算出f(x)的值，则称函数f是可计算的 研究思路：为计算建立一个数学模型，然后证明，凡是这个计算模型能够完成的任务，就是可计算的任务 2. 图灵机的构成
（1）一条存储带 双向无限长 上面有一个个小方格 每个小方格可以存储一个数字/字母 （2）一个控制器 可以存储当前自身的状态 一个读写头，可以读、写存储带上小方格的数字/字母 可以根据读写头读到数字/字母和程序更改自身的状态 可以沿着存储带一格一格地左移或右移 3. 图灵机的工作步骤 3.1 前期准备工作 初始化存储带上的符号 设置控制器当前自身的状态 放置读写头于起始位置 准备好工作程序 3.2 工作流程 读写头读出存储带上当前方格中的数字/字母 根据自身当前的状态和读到的字符，找到相应的程序语句； 根据相应的程序语句，做如下三个动作： 在当前存储带的方格上写入一个相应的数字/字母 变更自身状态 读写头向左或向右移动一步，或保持不变 4. 头脑风暴 - 模拟图灵机工作 4.1 图灵机的程序构成图灵机的程序可以由五个元素为一组的序列定义： |
【本文地址】