不同计算模型上计算复杂度，不是obvious的 - Programming版

本页内容为未名空间相应帖子的节选和存档，一周内的贴子最多显示50字，超过一周显示500字访问原贴

Programming版 - 不同计算模型上计算复杂度，不是obvious的

(共1页)

g****t
发帖数: 31659

【现今浏览器里模拟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),那么又会如何呢？
------自然语言之间的差异，似乎就是这个情况。

(共1页)

进入Programming版参与讨论

#	版面	帖数(主题数)
-	全站	4871 (796)
1	Military	3777 (569)
2	Stock	341 (51)
3	Joke	117 (17)
4	History	116 (3)
5	Automobile	100 (9)
6	USANews	55 (9)
7	Midlife	45 (1)
8	Headline	41 (41)
9	Dreamer	33 (13)
10	FleaMarket	32 (20)
11	Living	30 (7)

boards

未名新帖统计// 7月16日

历史上的今天