论文标题
关于TureDo层次结构和内在普遍性
On Turedo Hierarchies and Intrinsic Universality
论文作者
论文摘要
本文是关于TureDos的，它们是Turing Machine，其头部可以在飞机上移动（或在较高维度的空间中），但只能以自动散发的方式移动，通过将标记（字母）放在访问的位置上并仅移动到未标记的位置，因此未访问的位置。 TureDos的关键参数是它们的查找半径：头部可以环顾四周的距离，以决定其移动到何处以及要编写的标记。在本文中，我们根据turedos的查找半径研究了层次结构，并使用模拟概念到时空缩放的概念（细胞自动机或自组装系统的标准方法）。我们确定TureDo参数与所考虑的仿真概念之间存在丰富的相互作用。对于最自由的模拟，我们特别展示了半径1的3D trudos的存在，它们在所有半径上都是本质上普遍存在的，但是在维度2中，这是不可能的，在尺寸2中，某些Radius 2 Turedo在半径1上是无法模拟的。使用模拟的更严格的概念，固有的通用性是不可能的，即使在Dimension 3中也是不可能的，并且是严格的grafius nirius hierarch hierarky。最后，当限制到半径1时，在维度3中再次实现了普遍性，但在维度2中不可能，但是我们表明半径3 turedo可以模拟所有半径1 turedos。
This paper is about turedos, which are Turing machine whose head can move in the plane (or in a higher-dimensional space) but only in a selfavoiding way, by putting marks (letters) on visited positions and moving only to unmarked, therefore unvisited, positions. The key parameter of turedos is their lookup radius: the distance up to which the head can look around in order to make its decision of where to move to and what mark to write. In this paper we study the hierarchy of turedos according to their lookup radius and the dimension of space using notions of simulation up to spatio-temporal rescaling (a standard approach in cellular automata or self-assembly systems). We establish that there is a rich interplay between the turedo parameters and the notion of simulation considered. We show in particular, for the most liberal simulations, the existence of 3D turedos of radius 1 that are intrinsically universal for all radii, but that this is impossible in dimension 2, where some radius 2 turedo are impossible to simulate at radius 1. Using stricter notions of simulation, intrinsic universality becomes impossible, even in dimension 3, and there is a strict radius hierarchy. Finally, when restricting to radius 1, universality is again possible in dimension 3, but not in dimension 2, where we show however that a radius 3 turedo can simulate all radius 1 turedos.
