图灵机是现代计算机诞生的源头
计算机基础2019-02-04 13:04
ALan Turing（阿兰.图灵）在1937年首次提出了一个通用计算机设备的设想。他设想所有的计算都可能在一种特殊的机器上执行，这就是现在所说的图灵机.尽管图灵对这样一种机器进行了数学上的描述，但他还是更有兴趣关注计算的哲学定义，而不是建造一台真实的机器，他将该模型建立在人们计算过程的行为上，并将这些行为抽象到用于计算的机器的模型中，这才真正改变了世界。
所谓的图灵机就是指一个抽象的机器，它有一条无限长的纸带，纸带分成了一个一个的小方格，每个方格有不同的颜色。有一个机器头在纸带上移来移去。机器头有一组内部状态，还有一些固定的程序。在每个时刻，机器头都要从当前纸带上读入一个方格信息，然后结合自己的内部状态查找程序表，根据程序输出信息到纸带方格上，并转换自己的内部状态，然后进行移动。
图灵机的结构包括以下几个部分
1 ，一条无限长的纸带（tape），纸带被分成一个个相邻的格子（square）每个格子都可以写上至多一个字符（symbol）。
2 ，一个字符表（alphabet），即字符的集合，它包含纸带上可能出现的所有字符。其中包含一个特殊的空白字符（blank），意思是此格子没有任何字符。
3 ，一个读写头（head），可理解为指向其中一个格子的指针。 它可以读取/擦除/写入当前格子的内容，此外也可以每次向左/右移动一个格子。
4 ，一个状态寄存器（state register），它追踪着每一步运算过程中，整个机器所处的状态（运行/终止）。当这个状态从运行变为终止，则运算结束，机器停机并交回控制权。如果你了解有限状态机，它便对应着有限状态机里的状态。
5，一个有限的指令集（instructions table），它记录着读写头在特定情况下应该执行的行为。可以想象读写头随身有一本操作指南，里面记录着很多条类似于“当你身处编号53的格子并看到其内容为0时，擦除，改写为1，并向右移一格。此外，令下一状态为运行。” 这样的命令。其实某种意义上，这个指令集就对应着程序员所写下的程序了。
详细工作原理
1，准备
存储带上符号初始化
控制器设置好自身当前状态
控制器置于起始位置
准备好工作程序
2，反复执行以下工作直到停机
读写头读出存储带上当前方格中的字母/数字
根据自身当前状态和所读到的字符，找到相应的程序语句
根据相应的程序语句，做三个动作
在当前存储带方格上写入一个相应的字母/数字
变更自身状态至新状态
读写头向左或右移一步
3，图灵机停机意味着什么呢？
停机表示计算完毕，表示当前存储带上保留的，是结算结果也就是说；停机意味着得出计算结果 对于一个问题的输入A 问A是否推证出B？A能否推证出B？如果能找到一个图灵机 得出对应的符号序列B，那么从A到B就是可计算的，否则该问题不可计算。
图灵机为什么受到重视？因为简单 强大 可实现。
详细的请提问......
举报/反馈
0
0
收藏
分享
