图灵机学习总结

图灵机学习总结

前段时间，计算机科学概论老师组织我们班同学利用周末时间进行了有关图灵机的讨论课。在课程中，我们了解了图灵这个伟大的计算机先驱，并且知道了什么是图灵机、图灵机的发展以及对图灵机算法的探索。

通过讨论学习，我们了解到图灵机是由英国数学家图灵在1936年提出来的，图灵机是由一个控制器、一条有限长携带有信息和运算指令的带子和一个可在带子上左右移动的读写头组成。虽然这个机器非常简单，但它在理论上却可以计算任何直观可计算函数。而这就是著名的图灵命题，现在图灵论题已被当成公理一样在使用着，它是数学的基础之一。

图灵的基本思想是用机器来模拟人们用纸笔进行数学运算的过程，他把这样的过程看作下列两种简单的动作：（1）在纸上写上或擦除某个符号；（2）把注意力从纸的一个位置移到另一个位置：而在每个阶段，人要决定下一个动作依赖于： (a）此人当前所关注的纸上某个位置的符号； (b）此人当前的思维状态。

为了模拟人的这种运算过程，图灵构造出一台假想的机器，该机器由以下几个部分组成：

1.格子上包含一个来自有限字母表的符号，字母表中有一个特殊的符合表示空白。纸带上的格子从左到右以此被编号为0、1、2······纸带的右端可以无限延伸。

2.一个读写头HEAD。该读写头可以在纸带上左右移动，它能读出当前所指的格子上的符号，并且能改变当前格子上的符号。

3.一套控制规则TABLE。它根据当前机器所处的状态以及当前读写头所指的格子上的符号来确定读写头下一步的动作，并改变状态寄存器 的值，另机器进入一个新的状态。

4.一个状态寄存器。它用来保存当前寄存器所处的状态。图灵机的所有可能状态的数目是有限的，并且有一个特殊的状态，称为停机状态。

经过课堂上的讨论，我们对图灵机有了一个整体认识。之后我们又在老师的引导下分小组讨论图灵机的计算步骤设计。通过各个组员的互相协助，我们做出了x+1以及x-1的计算程序。 (a)计算x+1;

现 A B B B C C C E D 读 * * 0 1 1 0 * 空 0 写 * * 1 0 0 1 1 * 0

动 左 右 右 左 左 右 左 右 右 新 B D D C C D E D D D D (b)计算x-1;

现 A B B B X C C D D D F E E E 1 * 1 * 右 不动 D 读 * 1 0 * * 0 1 1 0 * 0 0 1 * 写 * 0 1 * * 1 0 1 0 空 * 0 1 * 动 左 右 左 右 不动 左 右 右 右 右 右 右 右 右 新 B X C X X C D E E F E E E B 以上就是我们小组的学习总结，通过此次学习，我们不仅看到了前人超前的睿智思想，同时也感受到了合作学习的乐趣。这次的课程在让我们获得知识的同时，也让我们学会了解决问题的方法，那就是合作。通过合作，不仅可以高效的解决问题，还可以激发自己的学习

兴趣和取得最大的学习收获。在此次课程中，我觉得每个人都受益良多。