图灵与图灵机.doc

《图灵与图灵机.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、图灵与图灵机关于图灵的介绍：图灵是著名的数学家，逻辑学家，是计算机和人工智能之父。图灵对于人工智能的发展有诸多贡献，提出了一种用于判定机器是否具有智能的试验方法，即图灵测试，至今，每年都有试验的比赛。此外，图灵提出的著名的图灵机模型为现代计算机的逻辑工作方式奠定了基础。关于图灵机的介绍：根据了解，图灵机是一种抽象的机器（没有实体机），是一种任意解决数学逻辑过程的机器，是一种理论上的通用机（在50年代计算机只能解决某一特定逻辑问题）。图灵机是模拟人写字的过程，包括两个步骤：1.在纸上写入或擦去一个符号；2.把注意力从纸的一个位置移动到另一个

2、位置。把注意力从纸的一个位置移动到另一个位置。其包括了以下几个部件：1.读写头，它可以读出和改变纸上的符号，并且可以左右移动；2.状态寄存器，用于保存图灵机所处在的状态（包括停机问题）；3.控制规则，根据读写头的状态和纸带上的字符来确定下一步动作，并改变状态寄存器的值；4.无限长的纸带，字母符号记录的载体；这个机器可以解决人类已知的所有计算问题，以及由其衍生的停机问题对数学和计算机的发展产生重大影响。下面我来讲讲停机问题：其本质问题是:给定一个图灵机T，和一个任意语言集合S，是否T会最终停机于每一个s∈S。其意义相同于可确定语言。显然任意

3、有限个S是可判定性的，可列的S也是可停机的。通俗的说，停机问题就是判断任意一个程序是否会在有限的时间之内结束运行的问题。如果这个问题可以在有限的时间之内解决，则有一个程序判断其本身是否会停机并做出相反的行为，这时候显然不管停机问题的结果是什么都不会符合要求。所以这是一个不可解的问题。这和理发师的问题有着很大的相似性，停机问题是目前逻辑学的焦点，和第三次数学危机的解决方案。图灵机还有许多变种：多带图灵机，非确定性图灵机，枚举器等（来自百度，对此不太了解）