首页 >
计算理论
✍ dations ◷ 2025-04-02 09:39:19 #计算理论
计算理论(英语:Theory of computation)是数学的一个领域,和计算机有密切关系。其中的理论是现代密码协议、计算机设计和许多应用领域的基础。该领域主要关心三个方面的问题:这三方面的问题可以用一个问题来总括:“电脑的基础能力及限制到什么程度?”计算理论的“计算”并非指纯粹的算术运算(Calculation),而是指从已知的输入透过算法来获取一个问题的答案(Computation),因此,计算理论属于计算机科学和数学。为了对计算进行严谨的研究,计算机科学家会将计算以数学的方式抽象化,称为计算模型。有几种当前在使用的计算模型,其中最出名的是图灵机。计算机科学家研究图灵机的原因是它很容易叙述,可以分析,用来证明结果,而且用此模式呈现了许多强而有力的计算模型(引用邱奇-图灵论题)。图灵机有潜在的,数量无限的记忆能力,这似乎是不可能达到的,不过所有图灵机解决的可判定性问题都只需要有限量的记忆能力。因此理论上,任何可以用图灵机解决的(可判定性)问题都只需要有限量的记忆能力。计算理论早在所有计算机发明之前便开始了,当时是使用数理逻辑,在20世纪此理论和数学分离,成为一个独立的学科。计算理论早期的重要贡献者有阿隆佐·邱奇、库尔特·哥德尔、艾伦·图灵、斯蒂芬·科尔·克莱尼、约翰·冯·诺伊曼及克劳德·香农等。
相关
- 微生物学微生物学是研究微生物的一门学科。微生物包括病毒、原核生物和简单的真核生物。目前,微生物学的最主要工作是用生物化学和遗传学方法完成的。由于很多病原(像是造成植物病害的
- 二十世纪1901年1月1日至2000年12月31日的这一段期间被称为20世纪。该世纪最初属于“不列颠治世”后期,是工业革命大爆发的年代,识字率大量提升,科学研究一日千里,人类学会了制造航天器与
- 神圣罗马帝国神圣罗马帝国(德语:Heiliges Römisches Reich;拉丁语:Sacrum Romanum Imperium),1512年以后的全称为德意志民族神圣罗马帝国或日耳曼民族神圣罗马帝国(德语:Heiliges Römisches Re
- Who Named It?《Whonamedit?》是一部记载医学名称及其有关人物的英语词典,由医学史家Ole Daniel Enersen(英语:Ole Daniel Enersen)负责维护,其服务器位于挪威。
- 嗜睡嗜睡症(hypersomnia)是一种会睡眠过度的疾病,主要有两种类型:原发性嗜睡症和反复性嗜睡症。两者的症状相同,但发生频率不同。患有嗜睡症的人会反复发生过度日间嗜睡(英语:Excessive
- 七月革命法国七月革命(法语:Révolution de Juillet;英语:July Revolution),是1830年欧洲的革命浪潮的序曲,因为波旁王室的专制统治令经历过法国大革命的法国人民难以忍受,以致法人群起反抗
- 激活素与抑制素激活素(英语:Activin,亦成为激活蛋白或活化素)与抑制素(英语:inhibin)是一种用于抑制卵泡刺激素分泌的与组合的梭氨酸 。参与在月经周期的调节中。抑制素包括一个由二硫键链接起来
- 小行星73079小行星73079(73079 Davidbaltimore)是一颗绕太阳运转的小行星,为主小行星带小行星。该小行星于2002年4月14日发现。小行星73079的轨道半长轴为2.3275630 UA,离心率为0.184。
- 松材线虫松材线虫(学名:Bursaphelenchus xylophilus)是常见的松树寄生虫。它通过松墨天牛(Monochamus alternatus)等媒介昆虫携播,被其感染的松树,针叶呈黄褐色或红褐色,整株干枯死亡,最终腐
- 林埈永林埈永(1978年1月8日-),艺名绿茶、Rim,台湾歌手、艺人。父亲是韩国人,母亲是山东华侨。曾在台湾、加拿大念书,也曾在加拿大、日本、韩国学音乐和舞蹈。2003年与黄鸿升、Junior组成