无注释号码

正如Georg Cantor度过了19世纪的最后一个季度，研究了从他的对角论的发明中出现的不可数套装，普林斯顿大学的研究人员将花费20世纪30年代，研究对未计算的数量的影响（Soare，2013）。特别是，历史突出了两个男人，阿隆佐教堂和艾伦的贡献。

Alonzo Church（1903-1995）是一位美国数学家和逻辑学家，他赢得了他的博士学位。在20世纪20年代普林斯顿大学的Oswald Veblen下。他的第一次公布的论文是在洛伦兹转型上。他最着名的结果包括证据证明，希尔伯特的决定问题（OntscheidungsProblem）是不可判定的（称为教会的定理），所以Peano算术是不可判定的，他的发明λ-Clulululul和他对教会所令人称赞的内容和他的铰接。论文关于可计算功能的性质。

现在闻名的Alan TINGE（1912-1954）是英国数学家最着名的是作为裂缝轴通信加密装置谜的成功盟军的旅游力量。对于数学家而言，图灵的名字不仅适用于这种应用工作的代名词，而是因为他在纯数学和逻辑中的异常愿望工作。

图灵于1912年出生于伦敦，但当时他17岁是剑桥国王学院学习数学的。他于1934年毕业于一流的荣誉，并在同年当选国王的一位老乡的仅仅基于他的理论，证明了中心极限定理的实力。他于1936年发布了他的知名论文“关于可计算数，申请东部的康迪坦斯问题”。它于11月30日至1936年12月23日在伦敦数学学会杂志的诉讼中发表了两部分。同年，图灵前往普林斯顿大学学习博士学位。在教堂的数学中。他获得了他的博士学位。 1938年。他的论文是“基于顺序的逻辑系统”，它引入了序数逻辑和相对计算的概念 - 使用所谓的Oracle机器增强他先前设计的图灵机器，允许研究超出能力的问题图灵机。虽然由von neumann询问博士后的博士后研究助理，但是，图灵拒绝了，而是回到英格兰。

作为Robert I. Soare Regounts（Copeland等，2013页），到1931年逻辑应用于可计算是一个年轻人的游戏。 Gödel于1906年出生的，他证明了正式系统不完整的时候，他已经25岁了。当他证明了基于λ-calculus的“有效计算性”的概念的概念，教堂是33岁的时候。在同一年的情况下，在具有图灵机械的发明中独立证明了相同的结果。 1912年出生，他当时24岁。

一个人的概念，概念，找到一种能够基于有限一组公理确定输入的算法的问题，该算法能够在莱布尼兹首次想象的情况下回到十七世纪（戴维斯，2000） 。后来，对于各种正规系统，该问题也由Schröder于1915年，Löwenheim于1915年，1918年，1921年在希尔伯特和阿克曼在1928年在Grundzuge Der Theoretischen Logik发表了一份正式声明，逻辑”）：

当我们知道允许任何给定的逻辑表达式的过程来解决这些程序时，entscheidungsprobrblem可以解决。

图灵的论文顾问Alonzo Church首次于1933年开始致力于解决问题。他提出了他提出的解决方案，其中他称之为1934年3月左右哥德尔可有效可计算的功能。据说，哥德尔拒绝了教会的方法，作为“彻底不满意”（Soare，2013）。基于λ-Calculus，教会的第一个命题表示：

首先定义可计算性（教会，1934）函数有效可在λ可定义的情况下可有效可计算。

教会和他的研究生斯蒂芬C.Kleene在自1931年以来将功能定义为λ-可定义的功能。到1934年，他们表明所有通常的数字理论功能都是可定义的。然而，由于Gödel知道，原始递归函数如他自己的1931纸上所述的原始递归函数不包括所有可计算的功能，因此对于所有数字的有效计算性来说，这是一个不足的基础。要考虑到这一点，Gödel在1934年春天扩大了卓越的Jacques Herbrand（1908-1931）的概念，以定义Herbrand-Gödel递归函数（现在已知只是递归函数），改善了Gödel1931纸中定义的那些，现在称为“原始”递归函数。在参加由哥德尔，教堂和Kleene持有的主题讲座后，最终修改了他们对赫尔邦 - 哥特递归职能（SOARE，2013）的计算定义：

计算性的第二个定义（教会，1936）正整数上的函数可有效可计算，如果才能递归。

教会和Keene后来能够表明他们在他们的第一个定义中使用的λ-可定义的功能和它们在其第二次中使用的赫尔邦-Gödel递归函数正式等同于。然而，哥德尔从未接受教会的计算定义（Gödel，1995），并与其方法根本不同意。教会论证的关键弱点根据SIEG（1994，P.80）是“在微积分中采取的步骤必须是受限制的性格，并且他们是[这里]假设没有论证是递归的”补充说“这正是在哪里我们遇到了教会分析的主要绊脚石“，这是一个绊倒的障碍，”教会“是教堂”，他自己和哥德尔一样清楚地看到了[两者]。

同时alan turing来到普林斯顿，以研究同样的问题，试图解决Hilbert的EntscheidungsProblob，而在该过程中提供了完整和最终的可计算的定义。 1936年11月30日在伦敦数学会计师42刊登的诉讼程序中发表，图灵的纸张定义了可计算性（SOARE，2013）：

计算性的定义（1936）的定义（1936）如果才能直观地（有效可计算），如果它仅当它是由图灵机可计算的话;也就是说，如图所定义的自动机器（A机器）（1936）

他的论文中的定义在他的定义中向教堂的论文发表了七个月之前发表了这个定义的相似性，陈述：“在最近的一篇文章中，Alonzo教堂介绍了”有效的计算能力“的想法，这相当于我的”可计算性“，但非常不同定义。“添加“教堂达到了关于entscheidungsproblus的类似结论”。

与教会和Kleene不同，图灵的定义并未依赖于哥特（1931）或Herbrand-Gödel（1934）的递归功能。相反，在叙述人类如何执行计算的情况下，进行分析，表现出相同的程序也可以由机器进行的步骤。就该分析的严谨性而言，Gandy（1988）后来写道：“图灵的分析不仅仅是提供一个论点，它证明了定理”，没有“不向计算机器的参考”。相反，“图灵机出现了他对人类的计算分析”（Soare，2013）的编码。

图灵发明了一个新的正式模型，他的机器或图灵机的概念。可以非正式地定义图灵机：

图灵机（A-Machine）是计算的数学模型，用于根据规则表在磁带带上操纵符号的抽象机器。尽管模型＆＃39; SILLICITY，给定任何计算机算法，可以构建能够模拟该算法和＃39;逻辑的图灵机。

图灵的定义与哥德尔的计算看（Soare，2013）相结合得更加紧密

＆＃34;但是图灵已经展示了更多。他已经表明，以这种方式定义的可计算函数正是您可以为其构建具有有限数量的机器的可计算功能，这将执行以下内容。如果你写下任何数字，N 2，......，nᵣ就在一张纸上，并将滑倒放入机器并转动曲柄然后在有限的转弯后，机器将停止和函数的值参数n₁，n 2，...，nᵣ将打印在纸上。＆＃34;

虽然我们知道的一组实数是不可数的，但是可计算数字集是可数的，因此我们知道大多数实数不是可计算的。可计算的证据是直观地引起的，因为它们可以通过图灵机器产生的事实，其中仅存在许多变化（即它们可以与自然数字一一对一体）。正式：

通过将Gödel号码分配给每个图灵机定义来证明可计算数字的数量的剪影产生与可计算数字对应的自然数的子集S。从S到可计算数字的阐述表明可计算的数字是最可计算的。

阿根廷 - 美国数学家Gregory Chaitin于1975年申请了一个不可计算的实际数字，现在称为Chaitin的恒定，Omegaω。它代表了随机构造的程序将停止/终止的概率：

Chaitin＆＃39; S思想实验（Barmpalias，2018）假设我们在随机二进制程序上运行一个通用的图灵机。具体而言，只要需要程序的下一位，我们都会翻转硬币并将二进制输出馈送到机器。图灵机会停止的可能性是什么？

Chaitin的思想实验是一个淘汰问题的原型示例。停止问题是从任意计算机程序的描述和输入的描述确定程序，程序是否将完成运行（停止）或继续运行。在自定义机器的上下文中，图灵机的停止概率ωᵤ占据以下表达式：

其中Σ表示随机有限二进制程序，U（Σ）↓表示U将停止在输入σ上的事实。

图灵的1936年纸证明，不存在用于解决所有可能的程序输入对的停止问题的一般算法。不计算暂停概率。该事实证明依赖于算法，其中，给定ω的第一个数字，解决了长度为n的节目的停止问题。由于停止问题不可确定，因此无法计算Ω。

TiborRadó在1962年题为“在不可计算的功能”的纸张中提出了以下问题：

什么是使用具有N个状态的图形机器在空白磁带上生产的最大有限数量？

问题稍后被称为繁忙的海狸问题。作为游戏，问题通常表示为：查找产生最大输出的给定大小的终止程序。问题具有自然表达式作为数学函数BB（n），其中如果n表示状态的数量，则设bb（n）表示可以通过该尺寸的机器写在空白磁带上的最大有限数量的1s。所以，BB（1）= 1，BB（2）= 4，BB（3）= 6.对于BB（4），问题变得更加困难。证明BB（4）= 13是博士学位。论文。 BB（5）的价值不知道，但至少4098（由Marxen＆amp; Buchtrock于1989年绑定），BB（6）至少3.5 x10¹⁸²⁶⁷（由2010年Kropitz发现）。

BB（n）函数是无解扣功能的示例。也就是说，没有计算BB功能的图灵机Mᴮᴮ。这是可证明的矛盾：

证据证明BB（n）不是可计算的（Roberts，2016）我们首先假设繁忙的BEAVER函数BB（n）是可计算的，并且存在具有β状态的图灵机Mᴮᴮ，其中将n作为输入，写入bb （n）输出的1s的数量，然后停止。让干净表示最初写在胶带上的1S的图灵机清洁序列。让双重表示图灵机评估函数n + n。鉴于带有N 1的胶带，它将在磁带上产生2N 1S，然后停止。现在创建例程＆＃39;双人间| evalbb |清洁＆＃39;让n₀是本机的状态数量。 LetCreate_N‖表示最初空白磁带上的图灵机创建N₀1S。让n表示总和n₀+n₀。让BADBB表示日常生活＆＃39; create_n₀|双人间| evalbb |清洁＆＃39;该机器具有n个状态（n₀+n₀）。在清除所有1S和暂停之前，运行BADBB将在磁带上生成BB（n）1S。但清洁步骤将继续至少BB（n）步骤，因此BADBB的计算时间必须严格大于BB（n），这与功能BB（n）的定义相矛盾。

除了一个有趣和挑战的数学游戏之外，繁忙的海狸问题也在实践中具有有趣的含义。对于希尔伯特的EntsheidungsProblob，假设任何数学猜想都可以通过计数器/存在的案例中的反例（例如Goldbach的猜想）来解析任何数学猜想。如果这种猜想是真的，则寻找反击的图灵机永远不会停止。如果不是真的，它将停止并通知我们已经找到了一个符合例子。如果我们模拟N状态图灵机并知道BB（N）的值，我们可以通过运行许多步骤来决定它是否会停止。如果，在BB（n）步骤之后，机器不会停止，我们知道它永远不会停止，因此没有反例，这将证明猜想是真的。

然而，理论上是真实的，这在实践中目前无法实现。 Wikipedia列出了两个原因：

繁忙的BEAVEV函数的值非常难以证明（案例，BB（6）具有至少3.5×10 1²值），并且假设一个人需要至少20-50个状态来制作有用的问题解决机器。此外，使用用于每个N状态图灵机的手动检查方法解决了解决的少数状态，这对于具有较大状态的机器来说，实际上不会实际上是可能的。

即使找到一个更有效的计算BB（n）状态的方式，函数的值也会变得非常大，非常快，（我们知道BB（17）大于G，Graham的号码）。即使是BB（6）需要直接执行的宇宙中已知部分的计算能力（LLOYD，2001）。

PenRose平铺是由非周期性的原型产生的非周期性平铺的示例。因为这种模式是非周期性的，所以它们缺乏翻译对称性。它们也是自我相似的（“分形”），因为它们在较大且较大的尺度上看起来相同。

1961年通过Hao Wang召集了一组瓷砖覆盖飞机的问题。此问题稍后被证明是无明确的。证明依赖于使用瓷砖模拟图尺寸，以这样的方式配置瓦片，只有当图灵机才能以空白磁带开始运行完整的完整平面。由于停止问题是不可判定的，因此必须不可思议的张大问题，因此也是无可腐的。

如今，在数学和计算机科学中，图灵机是定义可计算功能的主要形式主义（SOARE，2013页.213）。然而，为了认识到教会首先掌握这些功能的本质，现代制定关于可计算功能的性质的假设现在被称为教会图论文：

教会图灵论文函数可直观地计算，如果且仅当它由图定机器可计算，或者如果通过递归函数指定

没有通过机械过程进行的计算方法可以比图拉机更强大。

虽然被广泛采用，因为没有明确的方式证明或反驳其有效性，但主张仍然是猜想。关于论文发展历史的更详细说明是在维基百科提供的。