数学联邦政治世界观
超小超大

计算机结构(一) (6-1)

可计算性不总是基于自然数

我相信如果大家了解过一些递归论或者是可计算理论的内容,大多都会有一个模糊的印象,认为计算理论研究的是从ℕ 到 ℕ 的一个函数什么时候是可计算的,或者与之类似的相关问题。这个印象不能说是错的,对于自然数上可计算函数的研究的确是可计算性理论刚兴起时非常重要的内容。但在我们日常生活中或者在面对许许多多的数据结构的时候,这真的是我们唯一的对可计算性这个概念的理解方式吗?

首先,我们似乎不仅仅关心ℕ 上的可计算性问题。或许首先一个比较微不足道的观察是,在计算机理论中我们对 ℕ 有不同的表示方式,比如经常采用的是二进制数。因此严格来说,此时可计算性和可计算函数所基于的对象变成了 {0,1}* ,即 01-字符串构成的集合。当然,很多人会说这两者没有本质的区别,因此采用哪一个发展可计算性的理论没有关系;我们的经验也的确支持这种看法,因为它们二者是同构的。

但我们在日常生活中遇到的例子不是都像改变自然数的进制这样微不足道的。比如在编程中或者在理论计算机的研究中,我们经常遇见的情况是我们所想要考虑可计算性的数据集合上有更多的结构存在:比如在数据结构中我们经常使用树、图或者是表这样类型的数据结构,这些结构本质上和自然数的结构是不同的。如果采用递归类型 [inductive type] 或者是许多函数式编程 [functional programming] 语言中的表示方式,自然数ℕ 可以看作是如下的递归类型:

inductive N : Type :=

| zero : N

| succ : N ->N

换句话说,ℕ 的结构是由 0 和后继函数 [successor function] 递归生成的自由结构。我们同样可以类似地定义二元树的数据类型:

inductive Btr : Type :=

| leaf : Btr

| node : Btr ->Btr ->Btr

可以看见的是,二元树的递归生成方式是和ℕ 不同的。自然数生成的方式是给定一个自然数,生成一个其后继;而二元树是给定两个二元树,可以通过一个点将二者连起来形成一个新的二元树。我们还有许多其他的递归数据类型,其上的结构也自然和二元树与自然数都是不同的。但几乎在任何一个高级编程语言中,我们都可以编写输入为自然数 ℕ 输出为二元树类型的程序;根据 Church-Turing Thesis, 所有由这样定义的函数都应是可计算的。因此,尽管 ℕ 和二元树的数据结构不同,我们仍然可以谈论什么是不同数据结构之间的可计算函数,并且对此具有一定的直观。

数学联邦政治世界观提示您:看后求收藏(同人小说网http://tongren.me),接着再看更方便。

相关小说

是星 连载中
是星
吴涯0628
(小学生文笔,跃迁性思维,可能引起不适)(进度非常慢)如同星辰般散落进新的世界在合城的侵略计划温馨展开带着六芒星之咒降临的魔法师得到了祝福又......
2.2万字9个月前
旁(盘)白实体化 连载中
旁(盘)白实体化
阿清_41747394434452694
当旁白变成真人,会发生什样的故事?盘氏家族全体出动!
8.7万字9个月前
穿越异世我为王 连载中
穿越异世我为王
我是一朵冰凌花
王小米是生活在21世纪的一个纯纯粹粹的愤青。每天的生活就是指责这个老板不行,我要是他会怎么样。那个公司的行政总裁太次。我要是他会把工作干的什......
53.1万字9个月前
魔尊玉骨传 连载中
魔尊玉骨传
月影霞飞
【原创玄幻+女尊+仙魔虐恋+三生三世】末世,魔祖破除封印,率领千万阴兵屠世,五界六域,生灵涂炭。仙界之中,就只剩九天神女玉骨,还在负隅顽抗。......
23.5万字9个月前
蛇王追妻 连载中
蛇王追妻
楚星婉
遇妻,追妻,救妻,守妻,养妻,爱妻!
5.8万字9个月前
综穿之将军娱乐圈 连载中
综穿之将军娱乐圈
南宫墨风
原创:将军穿越娱乐圈完成每一个原主的愿望。
6.8万字9个月前