我想了解计算的理论基础是如何与现实世界的计算机联系起来的。据我所知,图灵机、递归函数、有限状态机、lambda演算、组合逻辑和其他模型在理论上都是等价的。在我看来,在最基本的层次上,这些模型似乎是计算的基础。
因此,我的主要问题是,这些纯粹的计算理论模型与现实世界的计算机体系结构有什么关系?我们如何从这些理论模型到一个实际的工具,利用电气工程和物理,在计算模型中没有考虑到的方面?例如,真实世界的计算机是图灵机的高级物理化身,还是完全偏离了目标?
编辑:我的问题不同于简单地问计算机是如何工作的。我特别要问的是实用的、现实的计算机和计算模型之间的关系。
发布于 2016-01-20 09:50:37
这些纯粹的计算理论模型与现实世界的计算机体系结构有什么关系?
他们不会。
λ微积分和图灵机的设计都是为了模拟人类计算的方式.它们不是为计算机建模而设计的。
这在图灵机中是最明显的,它在很大程度上模仿了“计算机”的方式(在艾伦·图灵的时代,这是一个人类的工作描述!)工作:把有限的信息保存在他的脑子里,然后把剩下的信息写在一张纸上。图灵使信息量任意大(但有限),并允许无限数量的纸张(他切成条纹,并把它们粘在一起,以得到一个简化的一维磁带),然而,即使考虑到不人道的信息量和物理上不可能的无限磁带,他可以证明,有些东西是无法计算的。
λ--微积分的发展同样是出于一种将计算的含义形式化的愿望,在这种情况下,它不是从人类如何在纸上写下计算的物理行为开始的,而是更多地基于一个人如何在头脑中评估一个函数的直觉。
图灵证明了通用图灵机的存在,即图灵机可以从磁带中读取任意图灵机的描述并执行图灵机的操作。这可以被认为是第一个解释器,也是第一个存储程序的计算机.
然而,真正参与开发第一台数字计算机的人声称,逻辑学家在计算模型方面的工作对建造第一台数字计算机的电气工程师和应用数学家的工作几乎没有影响,尽管它们有惊人的相似之处。
有些计算模型更接近于当前主流计算机的样子。例如,随机访问机是一个用于算法分析的成本模型,它更密切地模拟了在一台典型计算机中访问内存的方式,即使用恒定时间的随机访问,而不是图灵机,后者的访问时间是从当前内存位置到要访问的内存位置之间的线性关系(您必须一次将头穿过磁带一个单元)。
请注意,您使用的术语“真实世界的计算机架构”,好像只有一个。事实上,有很多不同的架构。例如,Reduceron是专为类似Haskell的语言设计的图形还原CPU,它的工作方式与典型的x86 CPU非常不同。有一些体系结构可以显式地对芯片上的通信成本进行建模,比如机队结构。哈佛架构严格分离代码和数据,而不是冯·诺依曼架构( von Neumann Architecture ),后者不区分它们。诸若此类。
https://softwareengineering.stackexchange.com/questions/307745
复制相似问题