Accéder directement au contenu Accéder directement à la navigation
Pré-publication, Document de travail

On Turedo Hierarchies and Intrinsic Universality

Abstract : 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.
Liste complète des métadonnées
Contributeur : Guillaume Theyssier Connectez-vous pour contacter le contributeur
Soumis le : vendredi 6 mai 2022 - 15:44:56
Dernière modification le : mardi 10 mai 2022 - 03:51:52


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-03661129, version 1
  • ARXIV : 2205.04103


Samuel Nalin, Guillaume Theyssier. On Turedo Hierarchies and Intrinsic Universality. 2022. ⟨hal-03661129⟩



Consultations de la notice


Téléchargements de fichiers