当前在线人数7825
首页 - 分类讨论区 - 电脑网络 - 葵花宝典版 - 同主题阅读文章

此篇文章共收到打赏
0

  • 10
  • 20
  • 50
  • 100
您目前伪币余额:0
未名交友
[更多]
[更多]
不同计算模型上计算复杂度,不是obvious的
[版面:葵花宝典][首篇作者:guvest] , 2021年09月16日10:18:04 ,87次阅读,0次回复
来APP回复,赚取更多伪币 关注本站公众号:
[分页:1 ]
guvest
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 1 ]

发信人: guvest (我爱你老婆Anna), 信区: Programming
标  题: 不同计算模型上计算复杂度,不是obvious的
发信站: BBS 未名空间站 (Thu Sep 16 10:18:04 2021, 美东)

【现今浏览器里模拟win2000,PC上的Android什么的都常见,且习以为常。
多数人不会认为其是一个suprise。所以UTM之学理重要性和困难性被遮蔽了。
随着技术的发展,这种遮蔽之力越拉越强,越来越难对其做还原性质的现象学分析。
简言之,当你对一个natural law不再惊奇的时候,你就离它越来越远。

但我们可以结合考古,对其试论一二。】

https://en.wikipedia.org/wiki/Antikythera_mechanism#/media/File:
AntikytheraMechanismSchematic-Freeth12.png
http://www.datadeluge.com/2018/02/gears-from-greeks-antikythera-mechanism.html

https://en.wikipedia.org/wiki/Antikythera_mechanism

我们现在知道,这个Antikythera机器上的一切计算,均可以在现代计算机上加上一个
固定长度的
Compiler模拟出来,因此,此机器上的计算复杂度与现代计算机之差为常数C。
但是,我们是真的知道知道这个事实,还是听老师说了所以接受了的那种知道?

我认为下面问题是有意义的:
假如一个人没有学过Turing的UTM那几段话,在他的面前放了这个Antikythera机器,和
一个算盘,
那么,他会理解一切Antikythera机器上的计算,可以在算盘上由一个固定长的口诀式
样的Compiler给Emulate出来吗?

对这个问题,当然每个人有自己的答案。我的答案是No,Never。我一辈子也不会知道。
UTM不是计算模型,是对不同计算模型之间关系的第一个定量研究,这样的成就于我而
言是
不可想象的。

假如你同意UTM在上述意义上不是obvious的。那这个结果就令人敬畏。
因为Turing在考虑这问题之前,必然也不知道此差异是Constant。
这似乎是世界构造的一部分,是没有别的承担的,孤立的自然律,简单说,这就是人类
处在这世界的运气,与牛顿定律类似。

我们再反过来想一下,假如图灵发现,不同计算模型之间的差不是一个定长度的
Costant,而是与计算问题有关的,是一个变数C(task),那么又会如何呢?
------自然语言之间的差异,似乎就是这个情况。



--
※ 修改:·guvest 於 Sep 16 10:42:56 2021 修改本文·[FROM: 2600:1700:74c4:a]
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 72.]

 
[分页:1 ]
[快速返回] [ 进入葵花宝典讨论区] [返回顶部]
回复文章
标题:
内 容:

未名交友
将您的链接放在这儿

友情链接


 

Site Map - Contact Us - Terms and Conditions - Privacy Policy

版权所有,未名空间(mitbbs.com),since 1996