# 重温图灵的可计算性、基于序数的逻辑系统、计算机与智能

1936年图灵确立了通用计算机可计算的约束条件（可否计算的界限或标准）。

1938年图灵论证了基于序数的逻辑系统（对哥德尔定理之后的形式化数学系统的探索）。

1950年图灵不仅提出了后来被称为“图灵测试”的人工智能形式化判定方式（是否具有人工智能的界限或标准）而且还论及了学习机器。

[w1]基于统计的机器学习已经蕴含在其中了。

[w2]这项已经超越并进一步发展到围棋程序了。

[w3]这项在继续努力的进程中，例如：机器翻译已经有很大的进步了。

1936年，图灵发表了他的论文“关于可计算数字，对Entscheidungsproblem的应用”（1936）。[48] 在本文中，图灵重新阐述了KurtGödel于1931年关于证明和计算限制的结果，用形式化和称为图灵机的形式和简单假设设备取代了哥德尔基于通用算法的形式语言。 Entscheidungsproblem（决策问题）最初由德国数学家David Hilbert在1928年提出。图灵证明了他的“通用计算机”能够执行任何可以想象的数学计算，如果它可以表示为算法。 他继续证明决策问题没有解决办法，首先表明图灵机的暂停问题是不可判定的：无法通过算法决定图灵机是否会停止。

On Computable Numbers, with an Application to the Entscheidungsproblem

In 1936, Turing published his paper "On Computable Numbers, with an Application to the Entscheidungsproblem" (1936).[48] In this paper, Turing reformulated Kurt Gödel's 1931 results on the limits of proof and computation, replacing Gödel's universal arithmetic-based formal language with the formal and simple hypothetical devices that became known as Turing machines. The Entscheidungsproblem (decision problem) was originally posed by German mathematician David Hilbert in 1928. Turing proved that his "universal computing machine" would be capable of performing any conceivable mathematical computation if it were representable as an algorithm. He went on to prove that there was no solution to the decision problem by first showing that the halting problem for Turing machines is undecidable: It is not possible to decide algorithmically whether a Turing machine will ever halt.

1938年，基于序数的逻辑系统，数学家Alan Turing的博士论文。[1] [2]

Systems of Logic Based on Ordinals

Systems of Logic Based on Ordinals was the PhD dissertation of the mathematician Alan Turing.[1][2]

Turing’s thesis is not about a new type of formal logic, nor was he interested in so-called ‘ranked logic’ systems derived from ordinal or relative numbering, in which comparisons can be made between truth-states on the basis of relative veracity. Instead, Turing investigated the possibility of resolving the Godelian incompleteness condition using Cantor’s method of infinites. This condition can be stated thus- in all systems with finite sets of axioms, an exclusive-or condition applies to expressive power and provability; ie one can have power and no proof, or proof and no power, but not both.

The thesis is an exploration of formal mathematical systems after Gödel's theorem. Gödel showed for that any formal system S powerful enough to represent arithmetic, there is a theorem G which is true but the system is unable to prove. G could be added as an additional axiom to the system in place of a proof. However this would create a new system S' with its own unprovable true theorem G', and so on. Turing's thesis considers iterating the process to infinity, creating a system with an infinite set of axioms.

The thesis was completed at Princeton under Alonzo Church and was a classic work in mathematics which introduced the concept of ordinal logic.[3]

Martin Davis states that although Turing's use of a computing oracle is not a major focus of the dissertation, it has proven to be highly influential in theoretical computer science, e.g. in the polynomial time hierarchy.[4]

1950年，

“计算机器和智能”是由Alan Turing撰写的关于人工智能主题的开创性论文。 这篇论文于1950年出版于Mind，是第一个向大众介绍他现在称为图灵测试的概念的论文。

A.M. Turing, Computing machinery and intelligence, Mind,59, 433- 460

# Computing Machinery and Intelligence

"Computing Machinery and Intelligence" is a seminal paper written by Alan Turing on the topic of artificial intelligence. The paper, published in 1950 in Mind, was the first to introduce his concept of what is now known as the Turing test to the general public.

Turing's paper considers the question "Can machines think?" Since the words "think" and "machine" cannot be defined in a clear way that satisfies everyone, Turing suggests we "replace the question by another, which is closely related to it and is expressed in relatively unambiguous words."[1]To do this, he must first find a simple and unambiguous idea to replace the word "think", second he must explain exactly which "machines" he is considering, and finally, armed with these tools, he formulates a new question, related to the first, that he believes he can answer in the affirmative.

http://blog.sciencenet.cn/blog-94143-1172994.html

## 全部精选博文导读

GMT+8, 2019-10-23 10:40