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

计算机结构(一) (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),接着再看更方便。

相关小说

七宗罪(扭曲) 连载中
七宗罪(扭曲)
TF唐风
七宗罪中的七位,信使无数,手下无数。
0.8万字9个月前
无限游戏:嘘!他在看着你 连载中
无限游戏:嘘!他在看着你
落花问情
漫天飞雪飘扬而落,只留一人伸出手接住了已经化水的雪。……无限游戏降临,路悯瓷在一家精神病医院内醒来,失去了记忆的甚至暂时性失明,他唯一能够依......
16.5万字8个月前
随笔:随想随写 连载中
随笔:随想随写
墨落成曦香
随想随写,不限时间,地点,人物等,很混乱的一篇文
0.2万字8个月前
凤舞九天传 连载中
凤舞九天传
锦鲤浮华
《原创!已完结撒花,放心入坑,爱你们呦!》六万年前魔君——擎苍带领妖魔两界讨伐天宫,只为挣得一袭之地!奈何妖魔横行乡里不服管教,天宫数百仙尊......
26.9万字8个月前
梦比喵斯的奥特CP聊天室 连载中
梦比喵斯的奥特CP聊天室
希利斯
CP:梦比优斯×希卡利;泰罗×托雷基亚;赛罗×泽塔;银河×维克特利;艾克斯×大空大地;欧布×伽古拉;泰迦和风马;……(想到了再补充)
0.7万字8个月前
醉心魂 连载中
醉心魂
一瞳ing
 ——痴心犹醉魂犹在。花开花落乃世间常态,可有的花一旦凋零,便再无开花的机会了,无法温养,三魂七魄破碎不堪……与君相逢君不识……千年来芜忘之......
41.2万字8个月前