什么是图灵机？

Question

还有，图灵是哪国人

Answer 1

1936年，阿兰·图灵提出了一种抽象的计算模型 ── 图灵机 (Turing Machine)。图灵的基本思想是用机器来模拟人们用纸笔进行数学运算的过程，他把这样的过程看作下列两种简单的动作：

在纸上写上或擦除某个符号；

把注意力从纸的一个位置移动到另一个位置；

而在每个阶段，人要决定下一步的动作，依赖于 (a) 此人当前所关注的纸上某个位置的符号和(b) 此人当前思维的状态。为了模拟人的这种运算过程，图灵构造出一台假想的机器，该机器由以下几个部分组成：

一条无限长的纸带。纸带被划分为一个接一个的小格子，每个格子上包含一个来自有限字母表的符号，字母表中有一个特殊的符号 表示空白。纸带上的格子从左到右依此被编号为 0, 1, 2, ... ，纸带的右端可以无限伸展。

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

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

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

注意这个机器的每一部分都是有限的，但它有一个潜在的无限长的纸带，因此这种机器只是一个理想的设备。图灵认为这样的一台机器就能模拟人类所能进行的任何计算过程

图灵机停机问题(The Halting Problem)的不可判定性
图灵机停机问题: 能否给出一个判断任意一个图灵机是否停机的一般方法? 答案是NO.
这个问题实际上是问: 是否存在一台"万能的"图灵机 H, 把任意一台图灵机 M 输入给 H, 它都能判定 M 最终是否停机, 输出一个明确的 "yes" 或 "no" 的答案? 可以利用反证法来证明这样的 H 不可能存在. 假定存在一个能够判定任意一台图灵机是否停机的万能图灵机 H(M), 如果 M 最终停机, H 输出 "halt"; 如果 M 不停机, H 输出 "loop". 我们把 H 当作子程序, 构造如下程序 P:
function P(M) {
if (H(M)=="loop") return "halt";
else if (H(M)=="halt") while(true); // loop forever
}
因为 P 本身也是一台图灵机, 可以表示为一个字符串, 所以我们可以把 P 输入给它自己, 然后问 P(P) 是否停机. 按照程序 P 的流程, 如果 P 不停机无限循环, 那么它就停机, 输出"halt"; 如果 P 停机, 那么它就无限循环, 不停机; 这样无论如何我们都将得到一个矛盾, 所以假设前提不成立, 即不存在这样的 H. 或者说, 图灵机停机问题是不可判定的(undecidable)。

Answer 2

图灵机
1936年，阿兰·图灵提出了一种抽象的计算模型 —— 图灵机 (Turing Machine)。图灵的基本思想是用机器来模拟人们用纸笔进行数学运算的过程，他把这样的过程看作下列两种简单的动作：

在纸上写上或擦除某个符号；

把注意力从纸的一个位置移动到另一个位置；

而在每个阶段，人要决定下一步的动作，依赖于 (a) 此人当前所关注的纸上某个位置的符号和(b) 此人当前思维的状态。为了模拟人的这种运算过程，图灵构造出一台假想的机器，该机器由以下几个部分组成：

一条无限长的纸带。纸带被划分为一个接一个的小格子，每个格子上包含一个来自有限字母表的符号，字母表中有一个特殊的符号 表示空白。纸带上的格子从左到右依此被编号为 0, 1, 2, ... ，纸带的右端可以无限伸展。

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

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

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

注意这个机器的每一部分都是有限的，但它有一个潜在的无限长的纸带，因此这种机器只是一个理想的设备。图灵认为这样的一台机器就能模拟人类所能进行的任何计算过程

Answer 3

Answer 4

图灵机，又称图灵计算、图灵计算机，是由数学家阿兰·麦席森·图灵（1912～1954）提出的一种抽象计算模型，即将人们使用纸笔进行数学运算的过程进行抽象，由一个虚拟的机器替代人们进行数学运算。
所谓的图灵机就是指一个抽象的机器，它有一条无限长的纸带，纸带分成了一个一个的小方格，每个方格有不同的颜色。有一个机器头在纸带上移来移去。机器头有一组内部状态，还有一些固定的程序。在每个时刻，机器头都要从当前纸带上读入一个方格信息，然后结合自己的内部状态查找程序表，根据程序输出信息到纸带方格上，并转换自己的内部状态，然后进行移动。
阿兰·麦席森·图灵是英国数学家、被称为计算机科学之父

　　阿兰·麦席森·图灵（Alan Turing，也被译作阿兰-图林）生平简介：

　　1912年6月23日，出生于英国伦敦。
　　1931年-1934年，在英国剑桥大学国王学院（King's College）学习。
　　1932年-1935年，主要研究量子力学、概率论和逻辑学。
　　1935年，年仅23岁的图灵，被选为剑桥大学国王学院院士。
　　1936年，主要研究可计算理论，并提出“图灵机”的构想。
　　1936年-1938年，主要在美国普林斯顿大学做博士研究，涉及逻辑学、代数和数论等领域。
　　1938-1939年，返回剑桥从事研究工作，并应邀加入英国政府破译二战德军密码的工作。
　　1940年-1942年，作为主要参与者和贡献者之一，在破译纳粹德国通讯密码的工作上成就杰出，并成功破译了德军U-潜艇密码，为扭转二战盟军的大西洋战场战局立下汗马功劳。
　　1943年-1945年，担任英美密码破译部门的总顾问。
　　1945年，应邀在英国国家物理实验室从事计算机理论研究工作。
　　1946年，这个时候，图灵在计算机和程序设计原始理论上的构思和成果，已经确定了他的理论开创者的地位。由于图灵的杰出贡献，年轻的他被英国皇室授予OBE爵士勋衔。
　　1947年-1948年，主要从事计算机程序理论的研究，并同时在神经网络和人工智能领域做出开创性的理论研究。
　　1948年，应邀加入英国曼彻斯特大学从事研究工作，担任曼彻斯特大学计算实验室副主任。
　　1949年，成为世界上第一位把计算机实际用于数学研究的科学家。
　　1950年，发表论文“计算机器与智能”，为后来的人工智能科学提供了开创性的构思。提出著名的“图灵测试”理论。
　　1951年，从事生物的非线性理论研究。年仅39岁的图林，被选为英国皇家学会会员。
　　1952年，在当年保守愚昧和冷战的时代，当警察得知图灵与同性朋友密切交往的消息之后，同性恋倾向的图灵被逮捕入狱。在法庭审判过程中，图灵明确告知人们，他认为自己没有做错什么事。在那个观念落后的年代，为了避免被判刑入狱，图灵被迫选择了为期一年的雌性激素注射的所谓“治疗”，才得以重新返回研究工作。
　　1953年-1954年，继续在生物和物理学等方面的研究。被迫承受的对同性恋倾向的“治疗”，致使原本热爱体育运动的图灵在身心上受到极大的伤害。
　　1954年6月7日，图灵被发现死于家中的床上。死因是氰化物中毒，警方调查结论是自杀。一代英灵，就此过早离去，成为人类科学史上的一大遗憾。

　　阿兰-图灵（Alan Turing，也被译作阿兰-图林）生平简介：

　　1912年6月23日，出生于英国伦敦。
　　1931年-1934年，在英国剑桥大学国王学院（King's College）学习。
　　1932年-1935年，主要研究量子力学、概率论和逻辑学。
　　1935年，年仅23岁的图灵，被选为剑桥大学国王学院院士。
　　1936年，主要研究可计算理论，并提出“图灵机”的构想。
　　1936年-1938年，主要在美国普林斯顿大学做博士研究，涉及逻辑学、代数和数论等领域。
　　1938-1939年，返回剑桥从事研究工作，并应邀加入英国政府破译二战德军密码的工作。
　　1940年-1942年，作为主要参与者和贡献者之一，在破译纳粹德国通讯密码的工作上成就杰出，并成功破译了德军U-潜艇密码，为扭转二战盟军的大西洋战场战局立下汗马功劳。
　　1943年-1945年，担任英美密码破译部门的总顾问。
　　1945年，应邀在英国国家物理实验室从事计算机理论研究工作。
　　1946年，这个时候，图灵在计算机和程序设计原始理论上的构思和成果，已经确定了他的理论开创者的地位。由于图灵的杰出贡献，年轻的他被英国皇室授予OBE爵士勋衔。
　　1947年-1948年，主要从事计算机程序理论的研究，并同时在神经网络和人工智能领域做出开创性的理论研究。
　　1948年，应邀加入英国曼彻斯特大学从事研究工作，担任曼彻斯特大学计算实验室副主任。
　　1949年，成为世界上第一位把计算机实际用于数学研究的科学家。
　　1950年，发表论文“计算机器与智能”，为后来的人工智能科学提供了开创性的构思。提出著名的“图灵测试”理论。
　　1951年，从事生物的非线性理论研究。年仅39岁的图林，被选为英国皇家学会会员。
　　1952年，在当年保守愚昧和冷战的时代，当警察得知图灵与同性朋友密切交往的消息之后，同性恋倾向的图灵被逮捕入狱。在法庭审判过程中，图灵明确告知人们，他认为自己没有做错什么事。在那个观念落后的年代，为了避免被判刑入狱，图灵被迫选择了为期一年的雌性激素注射的所谓“治疗”，才得以重新返回研究工作。
　　1953年-1954年，继续在生物和物理学等方面的研究。被迫承受的对同性恋倾向的“治疗”，致使原本热爱体育运动的图灵在身心上受到极大的伤害。
　　1954年6月7日，图灵被发现死于家中的床上。死因是氰化物中毒，警方调查结论是自杀。一代英灵，就此过早离去，成为人类科学史上的一大遗憾。

是英国数学家、被称为计算机科学之父

阿兰-图灵（Alan Turing，也被译作阿兰-图林）生平简介：

1912年6月23日，出生于英国伦敦。
1931年-1934年，在英国剑桥大学国王学院（King's College）学习。
1932年-1935年，主要研究量子力学、概率论和逻辑学。
1935年，年仅23岁的图灵，被选为剑桥大学国王学院院士。
1936年，主要研究可计算理论，并提出“图灵机”的构想。
1936年-1938年，主要在美国普林斯顿大学做博士研究，涉及逻辑学、代数和数论等领域。
1938-1939年，返回剑桥从事研究工作，并应邀加入英国政府破译二战德军密码的工作。
1940年-1942年，作为主要参与者和贡献者之一，在破译纳粹德国通讯密码的工作上成就杰出，并成功破译了德军U-潜艇密码，为扭转二战盟军的大西洋战场战局立下汗马功劳。
1943年-1945年，担任英美密码破译部门的总顾问。
1945年，应邀在英国国家物理实验室从事计算机理论研究工作。
1946年，这个时候，图灵在计算机和程序设计原始理论上的构思和成果，已经确定了他的理论开创者的地位。由于图灵的杰出贡献，年轻的他被英国皇室授予OBE爵士勋衔。
1947年-1948年，主要从事计算机程序理论的研究，并同时在神经网络和人工智能领域做出开创性的理论研究。
1948年，应邀加入英国曼彻斯特大学从事研究工作，担任曼彻斯特大学计算实验室副主任。
1949年，成为世界上第一位把计算机实际用于数学研究的科学家。
1950年，发表论文“计算机器与智能”，为后来的人工智能科学提供了开创性的构思。提出著名的“图灵测试”理论。
1951年，从事生物的非线性理论研究。年仅39岁的图林，被选为英国皇家学会会员。
1952年，在当年保守愚昧和冷战的时代，当警察得知图灵与同性朋友密切交往的消息之后，同性恋倾向的图灵被逮捕入狱。在法庭审判过程中，图灵明确告知人们，他认为自己没有做错什么事。在那个观念落后的年代，为了避免被判刑入狱，图灵被迫选择了为期一年的雌性激素注射的所谓“治疗”，才得以重新返回研究工作。
1953年-1954年，继续在生物和物理学等方面的研究。被迫承受的对同性恋倾向的“治疗”，致使原本热爱体育运动的图灵在身心上受到极大的伤害。
1954年6月7日，图灵被发现死于家中的床上。死因是氰化物中毒，警方调查结论是自杀。一代英灵，就此过早离去，成为人类科学史上的一大遗憾。本回答被提问者采纳