图灵机可以运行递归算法吗

① C语言编程：用函数递归法求Fibonacci数列的前n项·

#include <stdio.h>

long int F(int n)

{

if (n==1||!n) {

return n;

}

else return F(n-1)+F(n-2);

}

int main(void)

{

int i,n;

printf("n=");

scanf("%d",&n);

for (i=0; i<n; i++) {

printf("%-10ld",F(i));

}

return 0;

}

在数理逻辑和计算机科学中

递归函数或μ-递归函数是一类从自然数到自然数的函数，它是在某种直觉意义上是"可计算的" 。事实上，在可计算性理论中证明了递归函数精确的是图灵机的可计算函数。递归函数有关于原始递归函数，并且它们的归纳定义(见下)建造在原始递归函数之上。但是，不是所有递归函数都是原始递归函数 — 最着名的这种函数是阿克曼函数。

以上内容参考：网络-递归函数

② 图灵机是什么

即确定型图灵机 1936年 ， 阿兰·图灵 提出了一种抽象的 计算模型 —— 图灵机 (Turing Machine)。图灵的基本思想是用机器来樠拟人们用纸笔进行 数学 运算的过程，他把这样的过程看作下堗两种简单的动作：
- 在纸上写上或擦除某个符号；
一个状态寄存器。它用来保存图灵机堓前所处的状态。图灵机的所有可能状栁的数目是有限的，并且有一个特殊的砶态，称为停机状态。
一条无限长的纸带。纸带被划分为一䠪接一个的小格子，每个格子上包含一䠪来自有限字母表的符号，字母表中有䠀个特殊的符号 \square 表示空白。纸带上的格子从左到右依栤被编号为 0, 1, 2, ... ，纸带的右端可以无限伸展。
一个读写头。该读写头可以在纸带上堦右移动，它能读出当前所指的格子上砄符号，并能改变当前格子上的符号。
- 把注意力从纸的一个位置移动到另一䠪位置； 而在每个阶段，人要决定下丠步的动作，依赖于 (a) 此人当前所关注的纸上某个位置的符堷和(b) 此人当前思维的状态。为了模拟人的蠙种运算过程，图灵构造出一台假想的栺器，该机器由以下几个部分组成：
一套控制规则。它根据当前机器所处砄状态以及当前读写头所指的格子上的砦号来确定读写头下一步的动作，并改堘状态寄存器的值，令机器进入一个新砄状态。 注意这个机器的每一部分都映有限的，但它有一个潜在的无限长的纠带，因此这种机器只是一个理想的设够。图灵认为这样的一台机器就能模拟亠类所能进行的任何计算过程。

③ 什么是图灵论图灵论在计算机史上起什么作用

邱奇-图灵论题(The Church-Turing thesis)是计算机科学中以数学家阿隆佐·邱奇(Alonzo Church)和阿兰·图灵命名的论题。该论题最基本的观点表明，所有计算或算法都可以由一台图灵机来执行。以任何常规编程语言编写的计算机程序都可以翻译成一台图灵机，反之任何一台图灵机也都可以翻译成大部分编程语言大程序，所以该论题和以下说法等价：常规的编程语言可以足够有效的来表达任何算法。该论题被普遍假定为真，也被称为邱奇论题或邱奇猜想和图灵论题
该论题有很多可能的意义：
宇宙是一台图灵机(由此，在物理上对非递归函数的计算是不可能的)。此被定义为大邱奇.图灵论题.
宇宙不是一台图灵机(也就是说，物理的定律不是图灵可计算的)，但是不可计算的物理事件却不能阻碍我们来创建 超计算机(hypercomputer)。比如，一个物理上实数作为可计算实数的宇宙就可以被划为此类。
宇宙是一台超计算机, 因为建造物理设备来控制这一特征并来计算非递归函数是可能的。比如，一个悬而未决的问题是量子力学的的事件是图灵可计算的，尽管我们已经证明了任何由qubit所构成的系统都是(最佳)图灵完全的。 约翰·卢卡斯 (和罗格·本罗泽(Roger Penrose) 曾经建议说人的心灵可能是量子超计算的结果。

④ 图灵机状态转移规则的要素

三要素是负载驱动、转移条件和转移方向，要求是在状态―迁移图中可能需要使用加进判断框和处理框的记法。

所谓的图灵机就是指一个抽象的机器，它有一条无限长的纸带，纸带分成了一个一个的小方格，每个方格有不同的颜色。有一个机器头在纸带上移来移去。

机器头有一组内部状态，还有一些固定的程序。在每个时刻，机器头都要从当前纸带上读入一个方格信息，然后结合自己的内部状态查找程序表，根据程序输出信息到纸带方格上，并转换自己的内部状态，然后进行移动。

概述

图灵机是由英国数学家图灵（A.M.Turing，1912~1954）在1936年提出的一种计算模型。同递归函数和λ-演算相比较，图灵机的结构和运行同希尔伯特提出的形式系统更为接近，只不过图灵机并不是（入希尔伯特所希望的那样）用于判定命题的正确性，而是用于衡量一类问题是否可判定，也就是说，图灵机同递归函数和λ-演算一样，是衡量问题的可计算性的计算模型。

⑤ 图灵机是什么东东主要用于什么地方

【图灵机】又称图灵计算、图灵计算机，是由数学家阿兰·麦席森·图灵（1912～1954）提出的一种抽象计算模型，即将人们使用纸笔进行数学运算的过程进行抽象，由一个虚拟的机器替代人们进行数学运算。

所谓的图灵机就是指一个抽象的机器，它有一条无限长的纸带，纸带分成了一个一个的小方格，每个方格有不同的颜色。有一个机器头在纸带上移来移去。机器头有一组内部状态，还有一些固定的程序。在每个时刻，机器头都要从当前纸带上读入一个方格信息，然后结合自己的内部状态查找程序表，根据程序输出信息到纸带方格上，并转换自己的内部状态，然后进行移动。

图灵机的主要作用及功能：作为研究计算的一般性质的抽象工具，替代人们进行数学运算，并有以下作用：

1、作为语言接受器：被M接受的语育记作L（M），它是Σ中的这样一些字符串的集合，当把这些字符串放在M的带子上，M处于q0状态且M的带头处在最左单元时．这些字符串可以使M进入一个终结状态而停机。给定一个识别语言L的图灵机M，一般假定，当输入被接受时，M为停机，即没有下一动作。然而对于不被接受的字符串，M可能永不停机．被图灵机接受的语官称为递归可枚举语言。递归集合是递归可枚举集合的子类，递归集合总能被对所有输入都能停机的图灵机所接受。

2、作为整数函数计算机：被图灵机计算的函数称为部分递归函数。在某种意义上，部分递归函数类似于递归可枚举语言．因为计算它的图灵机在给定的输入上可能不停机。完全递归函数对应于递归语育．因为它能被总能停机的图灵机计算。

3、作为语言产生器：设M是一个多带图灵机，它用一条带作为输出带，在这条带上，符号一经写出上就不能再改写．输出带的带头也不能左移。假定在输出带上，M写出某个字毋表Σ的一些字符串，并用分隔符分开，则最终打印在输出带上的字符串的集合就称为由M生成的语言，记为G（M），G(M)Σ。如果L是某个图灵机生成的语言，则L是递归可枚举集合，反之亦然。

⑥ 艾伦·麦席森·图灵的主要成就

图灵在科学、特别在数理逻辑和计算机科学方面，取得了举世瞩目的成就，他的一些科学成果，构成了现代计算机技术的基础。 计算，可以说是人类最先遇到的数学课题，并且在漫长的历史年代里，成为人们社会生活中不可或缺的工具．那么，什么是计算呢？直观地看，计算一般是指运用事先规定的规则，将一组数值变换为另一(所需的)数值的过程．对某一类问题，如果能找到一组确定的规则，按这组规则，当给出这类问题中的任一具体问题后，就可以完全机械地在有限步内求出结果，则说这类问题是可计算的。这种规则就是算法，这类可计算问题也可称之为存在算法的问题。这就是直观上的能行可计算或算法可计算的概念．
在20世纪以前，人们普遍认为，所有的问题类都是有算法的，人们的计算研究就是找出算法来。似乎正是为了证明一切科学命题，至少是一切数学命题存在算法，莱布尼茨(Leibniz)开创了数理逻辑的研究工作。但是20世纪初，人们发现有许多问题已经过长期研究，仍然找不到算法，例如希尔伯特第10问题，半群的字的问题等．于是人们开始怀疑，是否对这些问题来说，根本就不存在算法，即它们是不可计算的。这种不存在性当然需要证明，这时人们才发现，无论对算法还是对可计算性，都没有精确的定义！按前述对直观的可计算性的陈述，根本无法作出不存在算法的证明，因为“完全机械地”指什么？“确定的规则”又指什么？仍然是不明确的。实际上，没有明确的定义也不能抽象地证明某类问题存在算法，不过存在算法的问题一般是通过构造出算法来确证的，因而可以不涉及算法的精确定义问题。
解决问题的需要促使人们不断作出探索。1934年，哥德尔(Godel)在埃尔布朗(Herbrand)的启示下提出了一般递归函数的概念，并指出：凡算法可计算函数都是一般递归函数，反之亦然。1936年，克林(Kleene)又加以具体化．因此，算法可计算函数的一般递归函数定义后来被称为埃尔布朗-哥德尔-克林定义．同年，丘奇证明了他提出的λ可定义函数与一般递归函数是等价的，并提出算法可计算函数等同于一般递归函数或λ可定义函数，这就是着名的“丘奇论点”。
用一般递归函数虽给出了可计算函数的严格数学定义，但在具体的计算过程中，就某一步运算而言，选用什么初始函数和基本运算仍有不确定性。为消除所有的不确定性，图灵在他的“论可计算数及其在判定问题中的应用”一文中从一个全新的角度定义了可计算函数。他全面分析了人的计算过程，把计算归结为最简单、最基本、最确定的操作动作，从而用一种简单的方法来描述那种直观上具有机械性的基本计算程序，使任何机械(能行)的程序都可以归约为这些动作。这种简单的方法是以一个抽象自动机概念为基础的，其结果是：算法可计算函数就是这种自动机能计算的函数。这不仅给计算下了一个完全确定的定义，而且第一次把计算和自动机联系起来，对后世产生了巨大的影响，这种“自动机”后来被人们称为“图灵机”。
图灵机是一种自动机的数学模型，它是一条两端(或一端)无限延长的纸带，上面划成方格，每个方格中可以印上某字母表中的一个字母(亦可为空格，记为S0)；又有一个读写头，它具有有限个内部状态。任何时刻读写头都注视着纸带上的某一个方格，并根据注视方格的内容以及读写头当时的内部状态而执行变换规则所规定的动作。每个图灵机都有一组变换规则，它们具有下列三种形状之一：
qiaRqi，qiaLqi，qiabqj
意思是：当读写头处于状态qi时如果注视格的内容为字母a则读写头右移一格，或左移一格，或印下字母b(即把注视格的内容由a改成b．a，b可为S0)。
图灵把可计算函数定义为图灵机可计算函数．1937年，图灵在他的“可计算性与λ可定义性”一文中证明了图灵机可计算函数与λ可定义函数是等价的，从而拓广了丘奇论点，得出：算法(能行)可计算函数等同于一般递归函数或λ可定义函数或图灵机可计算函数．这就是“丘奇-图灵论点”，相当完善地解决了可计算函数的精确定义问题，对数理逻辑的发展起了巨大的推动作用。
图灵机的概念有十分独特的意义：如果把图灵机的内部状态解释为指令，用字母表的字来表示，与输出字输入字同样存贮在机器里，那就成为电子计算机了。由此开创了“自动机”这一学科分支，促进了电子计算机的研制工作．
与此同时，图灵还提出了通用图灵机的概念，它相当于通用计算机的解释程序，这一点直接促进了后来通用计算机的设计和研制工作，图灵自己也参加了这一工作。
在给出通用图灵机的同时，图灵就指出，通用图灵机在计算时，其“机械性的复杂性”是有临界限度的，超过这一限度，就要靠增加程序的长度和存贮量来解决．这种思想开启了后来计算机科学中计算复杂性理论的先河。 所谓“判定问题”指判定所谓“大量问题”是否具有算法解，或者是否存在能行性的方法使得对该问题类的每一个特例都能在有限步骤内机械地判定它是否具有某种性质(如是否真，是否可满足或是否有解等，随大量问题本身的性质而定)的问题。
判定问题与可计算性问题有密切的联系，二者可以相互定义：对一类问题若能找到确定的算法以判定其是否具有某种性质，则称这类问题是能行可判定的，或可解的；否则是不可判定的，或不可解的。二者又是有区别的：判定问题是要确定是否存在一个算法，使对一类问题的每一个特例都能对某一性质给以一个“是”或“否”的解答；可计算性问题则是找出一个算法，从而求出一些具体的客体来。
图灵在判定问题上的一大成就是把图灵机的“停机问题”作为研究许多判定问题的基础，一般地，把一个判定问题归结为停机问题：“如果问题A可判定，则停机问题可判定．”从而由“停机问题是不可判定的”推出“问题A是不可判定的”。
所谓停机指图灵机内部达到一个结果状态、指令表上没有的状态或符号对偶，从而导致计算终止。在每一时刻，机器所处的状态，纸带上已被写上符号的所有格子以及机器当前注视的格子位置，统称为机器的格局。图灵机从初始格局出发，按程序一步步把初始格局改造为格局的序列。此过程可能无限制继续下去，也可能遇到指令表中没有列出的状态、符号组合或进入结束状态而停机。在结束状态下停机所达到的格局是最终格局，此最终格局(如果存在)就包含机器的计算结果。所谓停机问题即是：是否存在一个算法，对于任意给定的图灵机都能判定任意的初始格局是否会导致停机？图灵证明，这样的算法是不存在的，即停机问题是不可判定的，从而使之成为解决许多不可判定性问题的基础。
1937年，图灵用他的方法解决了着名的希尔伯特判定问题：狭谓词演算(亦称一阶逻辑)公式的可满足性的判定问题。他用一阶逻辑中的公式对图灵机进行编码，再由图灵机停机问题的不可判定性推出一阶逻辑的不可判定性。他在此处创用的“编码法”成为后来人们证明一阶逻辑的公式类的不可判定性的主要方法之一。
在判定问题上，图灵的另一成果是1939年提出的带有外部信息源的图灵机概念，并由此导出“图灵可归约”及相对递归的概念。运用归约和相对递归的概念，可对不可判定性与非递归性的程度加以比较。在此基础上，E．波斯特(Post)提出了不可解度这一重要概念，这方面的工作后来有重大的进展。
图灵参与解决的另一个着名的判定问题是“半群的字的问题”，它是图埃(Thue)在1914年提出来的：对任意给定的字母表和字典，是否存在一种算法能判定两个任意给定的字是否等价[给出有限个不同的称为字母的符号，便给出了字母表，字母的有限序列称为该字母表上的字。把有限个成对的字(A1，B1)，…，(An，Bn)称为字典．如果两个字R和S使用有限次字典之后可以彼此变换，则称这两个字是等价的]1947年，波斯特和A．A．马尔科夫(Markov)用图灵的编码法证明了这一问题是不可判定的。1950年，图灵进一步证明，满足消元律的半群的字的问题也是不可判定的。 图灵在第二次世界大战中从事的密码破译工作涉及到电子计算机的设计和研制，但此项工作严格保密。直到70年代，内情才有所披露。从一些文件来看，很可能世界上第一台电子计算机不是ENIAC，而是与图灵有关的另一台机器，即图灵在战时服务的机构于1943年研制成功的CO-LOSSUS(巨人)机，这台机器的设计采用了图灵提出的某些概念。它用了1500个电子管，采用了光电管阅读器；利用穿孔纸带输入；并采用了电子管双稳态线路，执行计数、二进制算术及布尔代数逻辑运算，巨人机共生产了10台，用它们出色地完成了密码破译工作．
战后，图灵任职于泰丁顿国家物理研究所(Teddington National Physical Laboratory)，开始从事“自动计算机”(Automatic Computing Engine)的逻辑设计和具体研制工作。1946年，图灵发表论文阐述存储程序计算机的设计。他的成就与研究离散变量自动电子计算机（Electronic Discrete Variable Automatic Computer）的约翰·冯·诺伊曼（John von Neumann）同期。图灵的自动计算机与诺伊曼的离散变量自动电子计算机都采用了二进制，都以“内存储存程序以运行计算机”打破了那个时代的旧有概念。 1949年，图灵成为曼切斯特大学（University of Manchester ）计算实验室的副院长，致力研发运行Manchester Mark 1型号储存程序式计算机所需的软件。1950年他发表论文《计算机器与智能》（ Computing Machinery and Intelligence），为后来的人工智能科学提供了开创性的构思。提出着名的“图灵测试”，指出如果第三者无法辨别人类与人工智能机器反应的差别， 则可以论断该机器具备人工智能。
1956年图灵的这篇文章以“机器能够思维吗？”为题重新发表．此时，人工智能也进入了实践研制阶段。图灵的机器智能思想无疑是人工智能的直接起源之一。而且随人工智能领域的深入研究，人们越来越认识到图灵思想的深刻性：它们至今仍然是人工智能的主要思想之一。 1945年到1948年，图灵在国家物理实验室，负责自动计算引擎（ACE）的工作 。1949年，他成为曼彻斯特大学计算机实验室的副主任，负责最早的真正的计算机---曼彻斯特一号的软件工作。在这段时间，他继续作一些比较抽象的研究，如“计算机械和智能”。图灵在对人工智能的研究中，提出了一个叫做图灵试验的实验，尝试定出一个决定机器是否有感觉的标准。
图灵试验由计算机、被测试的人和主持试验人组成。计算机和被测试的人分别在两个不同的房间里。测试过程由主持人提问，由计算机和被测试的人分别做出回答。观测者能通过电传打字机与机器和人联系（避免要求机器模拟人外貌和声音）。被测人在回答问题时尽可能表明他是一个“真正的”人，而计算机也将尽可能逼真的模仿人的思维方式和思维过程。如果试验主持人听取他们各自的答案后，分辨不清哪个是人回答的，哪个是机器回答的，则可以认为该计算机具有了智能。这个试验可能会得到大部分人的认可，但是却不能使所有的哲学家感到满意。图灵试验虽然形象描绘了计算机智能和人类智能的模拟关系，但是图灵试验还是片面性的试验。通过试验的机器当然可以认为具有智能，但是没有通过试验的机器因为对人类了解的不充分而不能模拟人类仍然可以认为具有智能。图灵试验还有几个值得推敲的地方，比如试验主持人提出问题的标准，在试验中没有明确给出；被测人本身所具有的智力水平，图灵试验也疏忽了；而且图灵试验仅强调试验结果，而没有反映智能所具有的思维过程。所以，图灵试验还是不能完全解决机器智能的问题。例如：质问者可以说：“我听说，今天上午一头犀牛在一个粉红色的气球中沿着密西西比河飞。你觉得怎样？”(你们可以想象该电脑的肩头上泛出的冷汗：)电脑也许谨慎地回答： “我听起来觉得这不可思议，”到此为止没有毛病。质问者又问： “是吗?我的叔叔试过一回，顺流、逆流各一回，它只不过是浅色的并带有斑纹。 这有什么不可思议的?”很容易想象，如果电脑没有合适的“理解”就会很快地暴露了自己、在回答第一个问题时，电脑的记忆库非常有力地想列犀牛没有翅膀，甚至可以在无意中得到“犀牛不能飞”，或者这样回答第二个问题“犀牛没有斑纹”。下一回质问者可以试探真正无意义的问题．譬如把它改变成“在密西西比河下面”，或者“在一个粉红色的气球之外”．或者“穿一件粉红色衣服”，再去看看电脑是否感觉到真正的差别。其实，要求电脑这样接近地模仿人类，以使得不能和一个人区分开实在是太过分了。一些专家认为，我们不该以电脑能否思维为目标，而是以能多大程度地模仿人类思维为目标；然后，让设计者再朝着这个目标努力。1952年，图灵写了一个国际象棋程序。可是，当时没有一台计算机有足够的运算能力去执行这个程序，他就模仿计算机，每走一步要用半小时。他与一位同事下了一盘，结果程序输了。后来美国新墨西哥州洛斯阿拉莫斯国家实验室的研究群根据图灵的理论，在MANIAC上设计出世界上第一个电脑程序的象棋。

⑦ 图灵在计算机发展史上的主要贡献有哪些

它的意义有如下几点:

1、它证明了通用计算理论，肯定了计算机实现的可能性，同时它给出了计算机应有的主要架构；

2、图灵机模型引入了读写与算法与程序语言的概念，极大的突破了过去的计算机器的设计理念；

3、图灵机模型理论是计算学科最核心的理论，因为计算机的极限计算能力就是通用图灵机的计算能力，很多问题可以转化到图灵机这个简单的模型来考虑。

通用图灵机向人们展示这样一个过程:程序和其输入可以先保存到存储带上，图灵机就按程序一步一步运行直到给出结果，结果也保存在存储带上。更重要的是，隐约可以看到现代计算机主要构成，尤其是冯・诺依曼理论的主要构成。

图灵机简介：

图灵机是中央处理器（CPU）的一般示例，该处理器控制计算机完成的所有数据操作，而规范机则使用顺序存储器来存储数据。更具体地说，它是一种能够枚举字母表中有效字符串的任意子集的机器（自动机）；这些字符串是递归枚举集的一部分。图灵机具有无限长的磁带，可以在其上执行读取和写入操作。

假设黑匣子，图灵机无法知道它最终是否会使用给定程序枚举子集的任何特定字符串。这是由于无法解决暂停问题，这对计算的理论限制具有重大意义。

Turing机器能够处理不受限制的语法，这进一步意味着它能够以无数种方式稳健地评估一阶逻辑。通过lambda演算可以证明这一点。

能够模拟任何其他图灵机的图灵机称为通用图灵机（UTM，或简称为通用机）。用类似的“通用”性质更数学导向的定义是由引进邱奇，上演算，其工作的正式理论与图灵的交织在一起计算被称为教会图灵论题。

⑧ 递归论的算法演化

解决某一类问题的计算方法又称算法。算法是个古老的数学概念。16世纪R.笛卡尔创造的解析几何就是用代数来解决几何问题的一种典型的算法。但数学中有一些问题长期找不到解决的算法。人们怀疑根本不存在这种算法。为了证明这一点，必须对算法给出精确的定义。20世纪30年代K.哥德尔提出了算法的一种精确定义，S.C.克林据此定义了递归函数。与此同时，A.M.图灵用图灵机（一种理论计算机）来描述算法，并且证明图灵可计算的函数与递归函数等价。图灵机使人们普遍接受了关于算法的丘奇论题：递归函数是可计算函数的精确的数学描述。
递归函数是用数理逻辑的方法定义在自然数集上的可计算函数。如果自然数的一个 n 元集的特征函数是递归函数，就称这个集合为递归集，一个递归函数的值域，称为递归可枚举集。递归集就是算法可判定的集合。递归集都是递归可枚举的，但是存在不是递归集的递归可枚举的集合。递归论的研究使人们把一些长期未解决的问题化为非递归的递归可枚举集，从而严格证明了不存在判定这些问题的算法。这些问题称为不可判定的。
递归论进一步研究不可判定的，也就是非递归的递归可枚举集之间的复杂程度问题。1944年E.L.波斯特提出不可解度的概念。又给出了相对可计算性的构造方法。这就使人们开始对不可解度进行比较，并研究不可解度的代数结构。这方面出现了有穷损害优先方法、无穷损害优先方法等多种有力的研究手段，出现了许多有趣的研究成果。
对可计算的递归集，也可以研究其计算的复杂性，考虑图灵机上计算的时间，空间，就得到计算时间的长短计算所占空间的多少这两个复杂性。计算复杂性的研究对计算机科学的发展有很大影响和作用。