• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Conference on Computability in Europe(CiE 2005); 20050608-12; Amsterdam(NL) >Abstract Geometrical Computation: Turing-Computing Ability and Undecidability
【24h】

Abstract Geometrical Computation: Turing-Computing Ability and Undecidability

机译：抽象几何计算：图灵计算能力和不确定性

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

In the Cellular Automata (CA) literature, discrete lines inside (discrete) space-time diagrams are often idealized as Euclidean lines in order to analyze a dynamics or to design CA for special purposes. In this article, we present a parallel analog model of computation corresponding to this idealization: dimensionless signals are moving on a continuous space in continuous time generating Euclidean lines on (continuous) space-time diagrams. Like CA, this model is parallel, synchronous, uniform in space and time, and uses local updating. The main difference is that space and time axe continuous and not discrete (i.e. R instead of Z). In this article, the model is restricted to Q in order to remain inside Turing-computation theory. We prove that our model can carry out any Turing-computation through two-counter automata simulation and provide some undecidability results.
机译：在元胞自动机（CA）文献中，（离散）时空图内的离散线通常被理想化为欧几里得线，以分析动力学或为特殊目的设计CA。在本文中，我们提出了与这种理想化相对应的并行计算模拟模型：无量纲信号在连续时间内在连续空间上移动，从而在（连续）时空图上生成欧几里得线。与CA一样，该模型是并行，同步的，在空间和时间上都是统一的，并使用本地更新。主要区别在于空间和时间是连续的而不是离散的（即R而不是Z）。在本文中，该模型仅限于Q，以便保留在Turing计算理论之内。我们证明了我们的模型可以通过两计数器自动机仿真来执行任何图灵计算，并提供了一些不确定性结果。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号