2010-04-27

限定时间的计算单元

Lance在其博客里写到
Since the beginning of complexity we talked about time complexity t(n) as a function of the input size. But it has been the inverse of this function that we really care about: We have a roughly fixed number t of computation steps available on our computer and we want to know the largest problem we can solve within that running time.

一个限定时间的计算单元,它在给定的时间和资源消耗内一定会给出结果。从这个角度来看计算,这个世界的确变了。

但似乎现有的计算理论是没有可能的,我十分不敢肯定这点,这似乎需要新的计算理论来解释。即使将复杂的计算分解成一个个的计算单元(它时间固定,自然是可计算的),这将算法的停机问题转换为计算单元的组合问题。核心问题是,这个机制又是如何在有限时间内完成计算单元的选择与组合呢?好吧,我们可以接受一个精度,那就选择关键的吧。但这“关键”的信息有来自来自哪里呢?更何况我们所做出的选择,那些保证有足够精度的计算单元,他们的结果又是如何平滑地粘连成一个结果呢?

复杂、太复杂!

一个根据具有的能力去选择问题的世界,这的确是个神奇的世界。那么对一个基于编织记忆的系统呢?她的内容是连贯的(coherent),她不是去组合那些计算单元而是去生成内容,她有没有可能生存在这个世界里呢?!

我还需要更多的工作。

没有评论: