另外找寻斑图的路径可以沿着逻辑基础数学的传统探究来进行,象弗雷格、希尔伯特所表达的和丘奇、哥德尔、波斯特、罗素、图灵、和怀特海所先行的。最近的,也是和流行更有关联的方法则是回到柯尔莫哥洛夫和蔡汀,他们的研究领域恰巧在于重构单独的物件【35,38】;尤其是,他们聚焦于离散符号系统,而不是(说)实数或其他数学物件。用于表征斑图P的备选项有通用图灵机(Universal Turing machine, UTM)程序——尤其是,刚好生成物件O的最短UTM程序。这个程序的长度被叫作O的柯尔莫哥洛夫和蔡汀复杂度。注意到任何体系——自动机,语法,又或者有什么不是——这些是图灵等价的,而且对那些“长度”的观念是定义优良的,将用于表征体系。自从我们可以将这些一个设备转换到另一个——比如说,从一个波斯特标记系统【39】到图灵机——对第一个系统只使用有限的描述,当使用这种方法来衡量复杂性时,这类约束容易被融合到一块。 | 另外找寻斑图的路径可以沿着逻辑基础数学的传统探究来进行,象弗雷格、希尔伯特所表达的和丘奇、哥德尔、波斯特、罗素、图灵、和怀特海所先行的。最近的,也是和流行更有关联的方法则是回到柯尔莫哥洛夫和蔡汀,他们的研究领域恰巧在于重构单独的物件【35,38】;尤其是,他们聚焦于离散符号系统,而不是(说)实数或其他数学物件。用于表征斑图P的备选项有通用图灵机(Universal Turing machine, UTM)程序——尤其是,刚好生成物件O的最短UTM程序。这个程序的长度被叫作O的柯尔莫哥洛夫和蔡汀复杂度。注意到任何体系——自动机,语法,又或者有什么不是——这些是图灵等价的,而且对那些“长度”的观念是定义优良的,将用于表征体系。自从我们可以将这些一个设备转换到另一个——比如说,从一个波斯特标记系统【39】到图灵机——对第一个系统只使用有限的描述,当使用这种方法来衡量复杂性时,这类约束容易被融合到一块。 |