信息学基础研究分享 http://blog.sciencenet.cn/u/geneculture 语言理解&知识表达

博文

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

已有 433 次阅读 2019-4-13 08:04 |个人分类:学术研究|系统分类:科研笔记| 图灵机, 形式化系统, 图灵测试, 计算机, 学习机

可否这样做一个简单的概括(希望听取不同的意见或建议!):

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

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

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

学习机器的想法对某些读者来说似乎有些矛盾,机器的操作规则怎么能改变呢?无论机器过去经历什么,未来会有什么变化,其操作规则都应该完整地描述机器会如何反应,即这些规则是不随时间变化的。

学习机器的一个重要特征是,老师通常对其内部发生的事情不了解,尽管老师仍然可以在一定程度上预测其学生的行为,经过实验而设计良好(或程序)的儿童机器的后期教育尤其如此。这一点与使用机器进行正常计算的过程形成鲜明对比:那里的目标是要清楚明白机器在计算中任意时刻的状态,而要达到此目标则需要付出艰苦的努力。如此,“机器只能按我们的要求做事”的观点就会显得很奇怪了,能够输入机器的大部分程序终归会做一些我们无法理解的事情,或者被认为是完全随机的行为。智能行为应该和完全服从命令的行为有别,但又不能太大,不应该产生随机的行为或无限循环。通过教育和学习使我们的机器能够进行模仿游戏的一个重要结果是,“人类犯错误”可能会被相当自然忽略掉,即不需要专门的“指导”(读者应该将其与第[454]页上的观点调和)。学习的过程并不会产生百分之百的确定结果,否则就不是学习了。

 

在一个学习机器中加入随机元素应该是明智的(参见第[445]页)。当我们寻找某个问题的解时,随机元素相当有用。例如,我们想找到一个介于50100之间的数,它等于各个数字的和的平方。我们可以从5152开始一直试下去直到找到满足条件的数。另一个方法是随机的选数直到找到满足条件的数,这种方法的优点是不需要跟踪已经尝试过的值,但缺点是一个数可能重复试两次,如果存在多个,这点并不很重要。系统化方法的一个缺点,是可能存在很大一段数中并不存在解,但我们需要先判断它。现在的学习过程可以看成寻找满足老师的要求(或一些其他的标准)的行为,既然可能存在大量的可能解,随机方法可能比系统方法更好。[w1] 应该注意到,在进化过程中有相似的方法,那里系统方法是不可能的,如何跟踪已经尝试过的不同基因组合,从而避免重复呢?

 

我们希望机器最终能和人在所有纯智力领域竞争,但何处是最好的开端?甚至这也成为困难的选择。许多人认为抽象的活动,例如国际象棋[w2] 可能是最好的选择;也有人认为最好用钱给机器买最好的传感器,然后教它听说英语[w3] ,和教一个正常的小孩一样,教它命名事物等等。我并不知道正确的答案,但是我想两方面都应该试试


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

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

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



附录:


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

On Computable Numbers, with an Application to the Entscheidungsproblem

https://en.wikipedia.org/wiki/Turing%27s_proof 

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] 


图灵的论文不是关于一种新型的形式逻辑,也不是对源于序数或相对编号的所谓“排序逻辑”系统感兴趣,在这种系统中,可以在相对准确性的基础上对真实状态进行比较。相反,图灵研究了使用康托尔的无限方法解决Godelian不完备性条件的可能性。因此可以说明这种情况 - 在所有具有有限公理集的系统中,排他性或条件适用于表达能力和可证明性;即一个人可以拥有能力,没有证据,证明也没有能力,但两者都不能。


本文是对哥德尔定理之后的形式数学系统的探索。哥德尔证明了任何形式系统S足以代表算术,有一个定理G是正确的,但系统无法证明。可以将G作为附加公理添加到系统中以代替证明。然而,这将创建一个新的系统S',它具有自己的不可证实的真定理G',依此类推。图灵的论文考虑将过程迭代到无穷大,创建一个具有无限公理的系统。


该论文在Alonzo Church的普林斯顿大学完成,是一部经典的数学着作,引入了序数逻辑的概念。[3]


马丁戴维斯表示,尽管图灵使用计算神谕不是论文的主要焦点,但事实证明,它在理论计算机科学中具有很高的影响力,例如:在多项式时间层次中。[4]


Systems of Logic Based on Ordinals 

https://academic.oup.com/mind/article/LIX/236/433/986238

https://en.wikipedia.org/wiki/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,是第一个向大众介绍他现在称为图灵测试的概念的论文。

图灵的论文考虑了“机器可以思考吗?”的问题。 由于“思考”和“机器”这两个词不能以一种满足每个人的明确方式来定义,图灵建议我们“用另一个与其密切相关的问题代替问题,用相对明确的词语表达。”[1] 要做到这一点,他必须首先找到一个简单而明确的想法来取代“思考”这个词,其次他必须准确地解释他正在考虑哪些“机器”,最后,凭借这些工具,他提出了一个与之相关的新问题。 首先,他认为他的回答是肯定的。


A.M. Turing, Computing machinery and intelligence, Mind,59, 433- 4601950. https://www.csee.umbc.edu/courses/471/papers/turing.pdf

Computing Machinery and Intelligence

https://en.wikipedia.org/wiki/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

上一篇:[转载]快速浏览几遍可启迪智慧并激发好奇心(这就够了)
下一篇:格雷厄姆·普里斯特(Graham Priest)在《Mind》上发表的文章分析

0

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备14006957 )

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

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部