F Guilayn
email: felipe.guilayn@suez.com

Alexandre Leurent
email: alexandre.leurent@gmail.com

Roman Moscoviz
email: roman.moscoviz@suez.com

Malo Sanglier
email: malo.sanglier@inrae.fr

Maxime Rouez
email: maxime.rouez@suez.com

Renaud Escudie
email: renaud.escudie@inrae.fr

High-solid food waste AD: thermophilic versus mesophilic conditions, effect of biochar, ammonia stress and trace elements in long-term operation

Keywords: biogas, biowaste, inhibition

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Food waste (FW) is a trending Anaerobic Digestion (AD) feedstock as policies worldwide are evolving towards law-enforced source-separation and valorization technologies over elimination. However, FW can be a challenging AD input due notably to its high and fast biodegradability, protein content (leading to the generation of NH3an inhibitory compound) and overall poor trace element (TE) content necessary for co-enzymes [START_REF] Zhang | Role of trace elements in anaerobic digestion of food waste : Process stability, recovery from volatile fatty acid inhibition and microbial community dynamics[END_REF]. Straightforward process engineering strategies to overcome these challenges are dilution and co-digestion (e.g., sludge, green waste, manure). The first greatly increases costs while cosubstrates are not always available/authorized. Microbiome engineering comes thus into play.

Several studies reported the importance of TE supplementation and the use of biochar as an additive enhancing syntrophic propionate oxidation, an AD metabolic pathway that is critical at high NH3 concentrations. Moreover, AD temperature is a critical parameter as it can both impact the NH3 concentration (i.e., NH3/NH4 + equilibrium) while driving microbial selection towards microorganisms that are more/less sensible to NH3 inhibition. For instance, Capson-Tojo et al. (2019) suggested with a meta-analytical study that thermophilic archaea should be less impacted by NH3 than mesophilic, despite the higher free ammonia nitrogen (FAN, i.e., N-NH3) concentrations under the same total ammoniacal nitrogen level (TAN, i.e., N-NH3 plus N-NH4 + ). Most of FW AD studies testing these solutions seem to be performed at single to a few batches while, other than allowing microbiological acclimation, the full replacement of inoculum content by digested material requires a long-term operation (e.g., three retention times for 95 % replacement in a continuous stirred-tank reactor).

The aim of this study is to investigate different scalable microbiome engineering strategies for stabilizing AD of FW as a single feedstock: thermophilic operation, biochar addition and trace elements supplementation. This series of experiments aim ultimately to set the operational conditions of an industrial pilot treating 50 tons of food waste per year.

Material and Methods

Household FW was collected, ground to 2 mm, homogenized and stored in frozen aliquots. Before grinding, they were visually verified to be exempt from lignocellulosic green waste and gross plastic particles. The feedstock, inocula and biochar used in this study were characterized for total solids, volatile solids, total Kjeldahl nitrogen and metals forms by ICP-AES (P, K, S, Mg, Ca, Na, B, Co, Cu, Fe, Mn, Mo, Zn, Al, As, Cd, Cr, Hg, Ni, Pb, Se. Data under request).

The experiments were carried out in 0.5 L bottles and 0.25 L working volume, in AMPTS® II systems (BPC, Sweden) where methane is measured volumetrically after biogas scrubbing in a NaOH 3 M solution. The fed-batch strategy was designed to simulate a plug flow reactor with digestate recirculation. A batch duration (7 days) represents a plug-flow 'passing time'. In the end of each batch, 5:6 (w:w) of the digestate is recirculated so, at steady-state, the mean retention time is about 40 days. The biochar used in this study was a commercial hardwood biochar obtained by fast pyrolysis. Biochar doses are expressed in weight/weight. During startup, biochar was added to achieve the target dose, then added with the feedstock in order to keep a constant concentration. The TE solution was formulated as proposed by [START_REF] Angelidaki | Defining the biomethane potential (BMP) of solid organic wastes and energy crops : A proposed protocol for batch assays[END_REF] for BMP tests, added at ratio of 150 µL/gVS of input.

A total of 6 conditions were performed in triplicate, which are summarized in Table 1.1. The thermophilic bottles were inoculated with a digestate from a full-scale thermophilic Dry-AD plant treating the fine organic fraction of municipal solid waste (OFMSW), which was acclimated to a TAN concentration of around 3 g.L -1 (FAN estimated at 1 g.L -1 ). The mesophilic bottles were inoculated from a full-scale mesophilic Wet-AD plant treating mostly biowaste and industrial sludge, which was acclimated to a TAN concentration of around 4 g.L -1 (FAN estimated at 0.5 g.L -1 ).

Cumulative methane production was measured constantly as described previously. Volatile fatty acids (VFA), TAN, pH, total (TS) and volatile solids (VS) and soluble chemical oxygen demand (COD) were analyzed at the end of the batches. The Organic Loading Rate (OLR) was gradually incremented during start-up, starting from 4.0 up to a value of 4.5 and 6.0 gVS.L -1 d -1 for the mesophilic and thermophilic AD, respectively. In Batch 11, when all conditions seemed sufficiently stable, every thermophilic condition was supplemented with ammonium bicarbonate (NH4HCO3), in order to increase TAN concentration to an even more stressing level (from about 3 to a target of 5 gN.L -1 ).

Results and Conclusions

The methane yields and the total VFA concentrations at the end of each batch are presented in Figure 1.1 for the whole experiment. At the initial OLR of 4.0 gVS.L -1 .d -1 , thermophilic AD was unexpectedly capable of expressing 100 % of the BMP within the batch duration of 7 days (plug flow "passing time"). A slight VFA build-up was observed in the first two batches (up to about 5 gCOD.L -1 , mostly propionate) in each condition, and VFA were totally reconsumed between batches 3-4. No VFA accumulation was observed afterwards when OLR was increased to 4.5 and later to 6.0 gVS.L -1 .d -1 (interventions a. and b., Figure 1.1). No significant effect of biochar was observed.

The mesophilic conditions started with a more moderate kinetic (75 % of BMP within the first batch). As expected, the CH4 yield increased during the following batches but increasing VFA concentrations (mostly propionate) were observed. As a consequence, the OLR was increased to 4.5 gVS.L -1 .d -1 but no further. At the end of batch 4, all mesophilic conditions had accumulated 10-15 gCOD.L -1 of propionate. Starting from batch 5, only the conditions with biochar started to consume propionate, achieving negligible VFA concentrations between batches 8-10, which can be testified by full BMP expression. Whatever the conditions, at batch 10, the TAN concentrations were clearly converging to 2.5-3.0 g.L -1 (results not presented). Given the stable and secure operation in all thermophilic conditions, an ammonia stress was induced by adding ammonium bicarbonate for achieving a TAN of 5 g.L -1 (intervention c., Figure 1.1).

Following the TAN shock, all the thermophilic conditions started to steadily increase VFA concentration, converging to a semi-inhibited steady-state with a total VFA concentration of 25-30 gCOD.L -1 (> 2/3 as propionate). After a theoretical complete replacement of the initial inoculum by digested food waste, from batch 20, the condition without TE nor biochar addition started to demonstrate further inhibition. However, an unnoticed operational issue with temperature control during batches 22 and 23 (incident d., Figure 1.1), which resulted in a temperature drop, promoted an interesting re-consumption of VFA (e.g., up to 5 g COD.L -1 of less propionate at the end of batch 24 compared to 22). This result may represent opportunities for further research on fine temperature tuning, which was outside the experiment's scope. The temperature was adjusted back from 43 to 50 °C and the inhibition effect was again observed two batches later. A more moderate inhibition of the condition without TE supply but 2 % biochar might indicate that biochar contributed to TE supply. From batch 27, the inhibition trend of the bottles without TE supply could be reversed by adjusting the TE level to the same as the TE-supplied conditions (intervention e., Figure 1.1). This whole series of long-term experiments demonstrate that food waste thermophilic AD can perform better than mesophilic AD at higher loads (6.0 gVS.L -1 .d -1 ) and at a relatively high TAN concentration (3 g.L -1 ). In thermophilic tests, no positive effect of biochar was noticed until almost 5 months of operation, with relevant evidence of the effect being associated with TE supply by the biochar. At a more moderate load (4.5 gVS.L -1 .d -1 ), mesophilic AD coupled with biochar and TE supply was stable while adding no biochar resulted in inhibition. Ongoing genomic analyses to be presented in the conference could provide evidence of the role of biochar on promoting a microbial community shift, as suggested by the literature [START_REF] Lim | Methanogenic pathway and microbial succession during start-up and stabilization of thermophilic food waste anaerobic digestion with biochar[END_REF]. Under the same research project, these results will be used to define the operational strategy of an industrial pilot treating 50 tons of FW per year.

Figure 1 . 1

 11 Figure 1.1 Methane yield and total VFA concentration at the end of each batch under thermophilic and mesophilic conditions. The points represent the average value triplicate bottles, connected by lines. Shadows represent min. and max. values from triplicates. Vertical yellow lines/areas represent the following events: a. OLR increased from 4.0 to 4.5 gVS.L -1 .d -1 . b. OLR increased from 4.5 to 6.0 gVS.L -1 .d -1 . c. induced NH3 stress to all thermophilic conditions by the addition of ammonium bicarbonate targeting 5 gTAN.L -1 . d. temperature control failure (temperatures reached 43°C during this phase). e. TE supplied to the yet non-supplemented thermophilic conditions.

Table 1 .1

 1 Experimental design.

	Temperature	TE	TE supply	Biochar	Ammonium
		supply	from batch	dose	bicarbonate addition at
		from	27	(% w:w)	batch 11
		batch 1
	Thermophilic	No	Yes	0	Yes
	Thermophilic	Yes	Yes	0	Yes
	Thermophilic	No	Yes	2	Yes
	Thermophilic	Yes	Yes	2	Yes
	Mesophilic	Yes	Yes	0	No
	Mesophilic	Yes	Yes	2	No

Acknowledgements

The presented results were obtained in the scope of the Biogaz-RIO project, jointly financed by the Occitanie Region and the ERDF (European Regional Development Fund, funding n°24001371). The experiments were conducted at the SUEZ CIRSEE BioRessourceLab and at the LBE Bio2E platform (DOI: 10.15454/1.557234103446854E12).


Brendan Le Daré
email: brendan.le.dare@chu-rennes.fr

Sophie Allard

Aurélien Couette

Pierre-Marie Allard

Isabelle Morel

Thomas Gicquel

Dr Brendan Le Daré

Comparison of Illicit Drug Seizures Products of Natural Origin Using a Molecular Networking Approach

Keywords: drug seizure, molecular networking, high-resolution mass spectrometry, cocaine, heroin

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

INTRODUCTION

In 2018, total drug seizures in the United States amounted over 64M $ mainly with cocaine, heroin, marijuana, methamphetamine and fentanyl [START_REF] Daré | Customs and Border Protection[END_REF]. Drug origins can be diverse, involving various manufacturing methods and therefore different compositions. Highlighting illicit substances nature and presence in powders makes it possible to establish legal sanctions. Moreover, drug sample composition is of interest in the context of judicial investigations; the analysis of contaminants in these powders contributes to their origin and provides scientific evidence that can help in their manufacture localization.

In the case of natural drugs origin, we can distinguish two cases: extraction or hemi-synthesis.

Cocaine is a tropane alkaloid obtained from several species of Erythroxylum shrub leaves [START_REF] Rivier | Analysis of alkaloids in leaves of cultivated Erythroxylum and characterization of alkaline substances used during coca chewing[END_REF][START_REF] Casale | Chemosystematic identification of fifteen new cocainebearing Erythroxylum cultigens grown in Colombia for illicit cocaine production[END_REF]. Since the solvents used for cocaine extraction lead to only a few traces in the final product after evaporation, it is difficult to rely on their analysis for powder study. Conversely, cutting agents analysis such as levamisole, caffeine, lidocaine, acetaminophen or phenacetin provides more information on the methods used by traffickers and helps to discriminate between powders based upon their origin, purity and therefore their place in the supply chain [START_REF] Solimini | Adulteration Practices of Psychoactive Illicit Drugs: An Updated Review[END_REF][START_REF] Núñez | Purity and adulteration in cocaine seizures and drug market inspection in Galicia (Spain) across an eight-year period[END_REF]. Other illicit substances are produced by hemisynthesis, such as heroin. Therefore, the finished product can potentially contain substances from the plant extraction stage, contaminants from the hemisynthesis stage, as well as cutting products. These compounds can greatly vary in composition or in proportion, and therefore constitute elements of high value for profiling purposes. In the case of heroin, obtained by diacetylation of morphine extracted from Papaver somniferum, it is difficult to differentiate the hemisynthesis methods used [START_REF] Odell | A 'cold synthesis' of heroin and implications in heroin signature analysis[END_REF]. For this reason, the study of the cutting agents remains essential for powder discrimination.

Accepted manuscript / Final version

Drug profiling is not routinely performed in forensic toxicology laboratories and innovative data visualization solutions thus remain poorly used in such contexts. Molecular networking (MN) is a computational strategy that may help visualization and interpretation of the complex data arising from MS analysis. Initially developed within the field of natural products research, this tool is particularly useful for complex biological matrices analysis at the molecular level [START_REF] Wang | Sharing and community curation of mass spectrometry data with Global Natural Products Social Molecular Networking[END_REF][START_REF] Zhou | Identification of chemotypes in bitter melon by metabolomics: a plant with potential benefit for management of diabetes in traditional Chinese medicine[END_REF][START_REF] Allard | Integration of Molecular Networking and In-Silico MS/MS Fragmentation for Natural Products Dereplication[END_REF][START_REF] Allard | Deep metabolome annotation in natural products research: towards a virtuous cycle in metabolite identification[END_REF]. Data reprocessing using open source softwares such as MzMine 2 or Cytoscape allows visualization of the acquired data by non-targeted screening [START_REF] Wang | Sharing and community curation of mass spectrometry data with Global Natural Products Social Molecular Networking[END_REF][START_REF] Olivon | MZmine 2 Data-Preprocessing To Enhance Molecular Networking Reliability[END_REF]. MN is able to identify compounds and potential similarities among all MS/MS spectra within the dataset and to propagate annotation to unknown but related molecules. Also, it facilitates the comparison of different matrices in a semi-quantitative manner [START_REF] Allard | Application of a molecular networking approach for clinical and forensic toxicology exemplified in three cases involving 3-MeO-PCP, doxylamine, and chlormequat[END_REF][START_REF] Daré | A case of fatal acebutolol poisoning: an illustration of the potential of molecular networking[END_REF].

Recently, our laboratory reported a case of fatal poisoning by an unknown powder ingestion (incorrectly labelled as Tabernanthe iboga) and applied MN to identify the plant involved in a woman's death [START_REF] Allard | Comparative molecular networking analysis of a Rauwolfia plant powder and biological matrices in a fatal ingestion case[END_REF]. Here, in order to compare powders composition suspected to contain illicit substances, we applied this tool to law enforcement agencies seizures products. This study illustrates the utility of molecular networks to efficiently determine the nature and number of compounds structurally related to the main expected component in the frame of illicit drug seizures products analysis.

MATERIAL AND METHODS

Sample preparation

Powder samples analyzed in this study were collected from law enforcement agency seizures. The sample X, a beige powder sample soluble in methanol, was sold as heroin powder. The sample Y1, a white powder soluble in methanol, and the samples Y2 and Y3, white powders soluble in water, were sold as cocaine powders. The four samples were powdered to weigh 30 mg on a precision balance, dissolved in 3 mL of appropriate solvent, and diluted 1000 times for analysis.

Drug powder analysis

Samples were analysed on an Orbitrap Q Exactive™ mass spectrometer coupled to an Accela 1250 pump (both from Thermo Scientific, San Jose, CA) using a heated electrospray ionization source (HESI-II). Data acquisition, calibration and instrument control were managed using Xcalibur® 2.1 software (Thermo Scientific).

Quantitative assays of illicit drugs were performed using a LC-HRMS method. The mobile phases were composed of ammonium formate at 10 mM and formic acid 0.1% in water (phase A) and acetonitrile and formic acid 0.1% (phase B). LC was performed on a Hypersil Gold column (5 mm x 2.1 mm, 3 µm) (Thermo Scientific, San Jose, CA). Heroin and cocaine were quantified on calibration curves using heroin-D9 and cocaine-D3 as internal standards, respectively (LOQ = 5ng/mL, range : 10 -1000 ng/mL , r² > 0.999). Calibration solutions were purchased from LGC (Teddington, UK).

In order to achieve MN, untargeted screening LC-HRMS/MS analyses were performed according to [START_REF] Allard | Application of a molecular networking approach for clinical and forensic toxicology exemplified in three cases involving 3-MeO-PCP, doxylamine, and chlormequat[END_REF] [START_REF] Allard | Application of a molecular networking approach for clinical and forensic toxicology exemplified in three cases involving 3-MeO-PCP, doxylamine, and chlormequat[END_REF]. Briefly, LC separation was performed on a Hypersil GOLD PFP column (150 x 2.1 mm, 5 µm) (Thermo Scientific, San Jose, USA). The mobile phases were composed of 10 mM ammonium acetate and 0.1% formic acid in water (A), and 0.1% formic acid in acetonitrile (B) at a flow rate of 200 μL/min. Detection was performed by data dependent untargeted screening as previously described [START_REF] Allard | Application of a molecular networking approach for clinical and forensic toxicology exemplified in three cases involving 3-MeO-PCP, doxylamine, and chlormequat[END_REF].

Generation of molecular networks

Molecular networks were generated according to Le [START_REF] Daré | New insights into quetiapine metabolism using molecular networking[END_REF] [START_REF] Daré | New insights into quetiapine metabolism using molecular networking[END_REF]. Raw spectral data files were converted from .raw format into the .mzXML open mass format using Proteowizard software [START_REF] Kessner | ProteoWizard: open source software for rapid proteomics tools development[END_REF]. Spectra were converted from profile to centroid mode in the positive ionization mode.

Preprocessing of the data was required for the generation of multisample molecular networks, and the use of precursor ion abundance for relative quantification. Such processing additionally allows to take into account the retention time and thus to separate isomers into individual nodes in the resulting molecular networks. For this, the Feature Based Molecular Network process was followed [START_REF] Nothias | Feature-based molecular networking in the GNPS analysis environment[END_REF].

Preprocessed and aligned spectral file were saved as a single .mgf file using the integrated Global Natural Products Social Molecular Networking (GNPS) export module of MZmine 2 [START_REF] Nothias | Feature-based molecular networking in the GNPS analysis environment[END_REF]. The spectral file .mgf was uploaded to the GNPS platform (http://gnps.ucsd.edu). Due to the use of HR data, the basic parameters were set to 0.02 m/z for the mass tolerance of precursor and fragment ions used for MS/MS spectral library searching, and 0.02 m/z for the mass tolerance of fragment ions used for MN. Molecular networks and MS1-and MS2-level spectral annotations were viewed offline with Cytoscape 3.8.0 (http://www.cytoscape.org).

RESULTS

Powder X analysis

To identify compounds in a drug seizure suspected to contain heroin, we generated a molecular network that displayed the MS/MS data acquired during analysis (Figure 1). We annotated the nodes with the precursor ion mass, and we labeled the edges with the mass shift between the two connected nodes. During the generation of the network, nodes are linked together in clusters according to their MS² spectral similarities. The size of each node is proportional to the peak area of each compound, allowing semi-quantitative analysis. We performed node annotation on the basis of their chromatographic retention time (if available), exact mass, and the match between the fragmentation spectrum and the GNPS and/or mzCloud (https://www.mzcloud.org, HighChem LLC, Slovakia) spectral databases. We also used spectral in-house database and bibliography information for annotation.

Visual analysis of the molecular network allows us to raise several observations. First, the annotation step using spectral match revealed the presence of heroin (m/z 370.167), confirming illicit compound content. Its derivative 6-monoacetylmorphine (6-MAM) (m/z 328.156) was identified, linked to the heroin node by a mass shift of -42.0104 (typical of an acetyl group). Second, caffeine (m/z 195.088), acetaminophen (m/z 152.071), noscapine (m/z 414.156), papaverine (m/z 340.156) and 6monoacetylcodeine (m/z 342.172) were also detected as impurities (from synthesis or from plant origin) or cutting agents (Figure 1). Taken together, these results suggest that MN allows to quickly visualize groups of structurally similar compounds and thus to quickly differentiate cutting products from structurally related metabolites (coextracted compounds or synthetic impurities), with identification of illicit compounds.

The powder X quantitative analysis using LC-HRMS evaluated heroin content at 48 µg/mg of powder, corresponding to around 5% purity.

Products Y analysis

Three powders suspected to contain cocaine were compared using MN. In this sample-to-sample comparison network, we colored the nodes with a pie chart assigning a specific colour to each sample. In addition, the size of each colored section of the chart was proportional to the corresponding peak area in each powder. A cocaine-containing cluster was identified in the three powders (Figure 2). The semi-quantitative approach suggests that the Y1 (orange) powder contains more cocaine than the two others (turquoise and red) (Figure 2a). Other nodes linked to cocaine (m/z 304.156) were identified with a mass shift of +26.0155, putatively annotated as trans and ciscinnamoylcocaine (m/z 330.172); with a mass shift of -14.0156 giving rise to benzoylecgonine (m/z 290.141); with a mass shift of +5.953 giving rise to hexanoylecgonine methylester (m/z 298.303) and finally with a mass shift of +90.031 giving rise to trimethoxycocaine. Visual analysis also revealed a higher proportion of these cocaine structurally related compounds in Y1 powder (orange).

Interestingly, other isolated nodes annotated as phenacetin, levamisole and caffeine were found in powder Y3 (red), hydroxyzine, levamisole and caffeine in powder Y2 (turquoise) and phenacetin and levamisole in powder Y1 (orange). These compounds were found in different proportions according to the powders. Taken together, these results revealed differences in composition among these three powders, showing higher cocaine purity in the Y1 sample.

Quantitative analysis of the three powders (Y1, Y2, Y3) using LC-HRMS confirmed the presence of cocaine in different proportions. Y1, Y2 and Y3 powder samples contained cocaine ratios at 572 µg/mg, 397 µg/mg and 168 µg/mg of powder, corresponding to purity around 57%, 40%, and 17%, respectively.

DISCUSSION

Highlighting the presence of illicit substances in seized powders is mandatory to establish legal sanctions. In addition, comparison of multiple drug samples by their composition is of definite interest in judicial investigations. The aim of this study is to illustrate the utility of MN as a tool for i) drug powder composition determination, helping in their profiling, and ii) comparison of various powder sample profiles likely to contain illicit compounds. For these purposes, we analyzed powders likely to contain either heroin or cocaine.

In the first example concerning a seized powder suspected of containing heroin (powder X), molecular network analysis allowed us to organize numerous chemical species detected by LC-HRMS/MS. The LC-HRMS quantitative method using standard calibration curve revealed 5% purity.

Since heroin is produced by morphine diacetylation, it is expected that synthetic by-products would be present. We found 6-monoacetylmorphine (m/z 328.1562) and 6-monoacetylcodeine (m/z 342.1717), showing incomplete heroin synthesis and codeine acetylation, respectively [START_REF] O'neal | Acetylcodeine, an impurity of illicitly manufactured heroin, elicits convulsions, antinociception, and locomotor stimulation in mice[END_REF][START_REF] O'neal | The detection of acetylcodeine and 6-acetylmorphine in opiate positive urines[END_REF].

According to literature data, it is nowadays difficult to differentiate an hemi-synthesis using acetic anhydride or a trifluoroacetic anhydride/acetic acid mixture. However, specific techniques to detect in particular bis-trifluoroacetylmorphine, trifluoroacetylcodeine, and 3-acetyl-6trifluoroacetylmorphine can orient towards a synthetic pathway using trifluoroacetic anhydride [START_REF] Odell | A 'cold synthesis' of heroin and implications in heroin signature analysis[END_REF].

Since we did not detect these substances in our sample, we suggest that this heroin sample was not likely produced by this latter method. We also found other alkaloids of Papaver somniferum, namely noscapine and papaverine, reflecting the morphine extraction stage [START_REF] Wolf | Using Papaverine and Its Metabolites, 6-Desmethyl Papaverine and 4′,6-Didesmethyl Papaverine as Biomarkers to Improve the Detection Time of Heroin Use[END_REF]. Given that noscapine can also be used as a heroin adulterant, the high proportion found in our sample (regarding to the node Accepted manuscript / Final version size) oriented us toward this hypothesis [START_REF] Klemenc | Noscapine as an adulterant in illicit heroin samples[END_REF]. In a study analyzing 3476 heroin samples, Morelato et al. ( 2019) reported that heroin adulteration consisted almost exclusively in caffeine and acetaminophen [START_REF] Morelato | When does the cutting of cocaine and heroin occur? The first large-scale study based on the chemical analysis of cocaine and heroin seizures in Switzerland[END_REF]. This observation was consistent with previous reports, highlighting these two substances as the most frequent cutting products found in European heroin seizures since the beginning of the 1900s [START_REF] Kaa | Impurities, adulterants and diluents of illicit heroin. Changes during a 12-year period[END_REF]. Accordingly, we detected these two substances in this powder.

Therefore, MN allowed us to organize and visualize illicit content and major structurally related impurities, giving a good understanding of powder composition.

As a second example, three powders suspected to contain cocaine (Y1, Y2 and Y3 powders) were compared to further investigate the utility of molecular networks for drug seizure comparison. Since cocaine is reported to be adulterated by a diverse combination of cutting agents, we believe that such an approach is of particular relevance. Conversely to heroin, cocaine is a naturally present alkaloid, which can be directly extracted and thus requires no hemisynthesis. In addition, the diversity of cocaine powder compositions is known to reflect the origin of the market, which is more complex and dynamic for cocaine than for heroin [START_REF] Morelato | When does the cutting of cocaine and heroin occur? The first large-scale study based on the chemical analysis of cocaine and heroin seizures in Switzerland[END_REF]. In our experiments, MN provided information for profile comparisons, allowing discrimination between sample powders. At first glance, the cocaine node confirmed the illicit content, and a purity analysis can be initiated by the semi-quantitative approach. Higher cocaine content was found in powder Y1 compared with the two others, which was confirmed with LC-HRMS quantitative method using standard calibration curve (57% cocaine).

Other alkaloids from Erythroxylum genus shrub leaves (namely hexanoylecgonine methylester, trimethoxycocaine and trans/cis-cinnamoylcocaine) were also found in a higher proportion in Y1 powder, corroborating this observation [START_REF] Plowman | Cocaine and Cinnamoylcocaine Content of Erythroxylum Species[END_REF][START_REF] Casale | Alkaloid content of the seeds from Erythroxylum Coca var. Coca[END_REF][START_REF] Lociciro | Cocaine profiling for strategic intelligence purposes, a cross-border project between France and Switzerland[END_REF]. Four varieties of Erythroxylum are well known to be used by coca farmers for illicit cocaine production: E. novogranatense var novogranatense, E.

novogranatense var truxillense, E. coca var. ipadu and E. coca var. coca. Interestingly, trimethoxycocaine is only found in native E. coca var. coca and E. coca var. ipadu, historically cultivated by coca farmers in Peru/Bolivia and Colombia, respectively [START_REF] Casale | Chemosystematic identification of fifteen new cocainebearing Erythroxylum cultigens grown in Colombia for illicit cocaine production[END_REF][START_REF] Casale | Illicit coca grown in Mexico: An alkaloid and isotope profile unlike coca grown in South America[END_REF]. Moreover, Malette et al. (2016) showed that the combinations of alkaloids present in cocaine powders made it possible to carry out geographically sourcing, targeting more precisely the regions of origin of the plants used.

As a result, they determined that the majority of the trimetoxycocaine producing shrubs came from eastern colombia, bringing valuable information for our samples. [START_REF] Mallette | Geographically Sourcing Cocaine's Origin -Delineation of the Nineteen Major Coca Growing Regions in South America[END_REF]. However, new cultigens of cocaine-bearing Erythroxylum have been propagated by Colombian coca farmers in recent years, making geographic determination more difficult [START_REF] Casale | Chemosystematic identification of fifteen new cocainebearing Erythroxylum cultigens grown in Colombia for illicit cocaine production[END_REF][START_REF] Casale | Illicit coca grown in Mexico: An alkaloid and isotope profile unlike coca grown in South America[END_REF]. According to [START_REF] Lukaszewski | Impurities and Artifacts of Illicit Cocaine[END_REF], benzoylecgonine is commonly encountered in illicit cocaine samples, mostly because of cocaine hydrolysis degradation [START_REF] Lukaszewski | Impurities and Artifacts of Illicit Cocaine[END_REF]. Here, benzoylecgonine was found in our three cocaine samples.

Besides the semi-quantitative analysis of the alkaloids contained in these powders, cutting products analysis also provides valuable elements for their discrimination. Phenacetin, levamisole, lidocaine, caffeine, diltiazem, hydroxyzine, procaine, tetracaine, acetaminophen, creatine and benzocaine are among the most widespread cutting agents in Europe [START_REF] Morelato | When does the cutting of cocaine and heroin occur? The first large-scale study based on the chemical analysis of cocaine and heroin seizures in Switzerland[END_REF][START_REF] Martello | Levamisole in Illicit Trafficking Cocaine Seized: A One-Year Study[END_REF]. Consistent with these literature data, MN allows us to find levamisole and phenacetin in powder Y1, caffeine, hydroxyzine and levamisole in powder Y2, and caffeine, levamisole and phenacetin in powder Y3. Interestingly, adulterant nature can also bring valuable information regarding the supply chain. For instance, it is assumed that hydroxyzine is usually added at an early stage of the supply chain, while phenacetin and caffeine can be added at different levels, from distribution to consumption level. Lastly, levamisole adulteration, widely used in South America, seems to take place immediately after production or just before exportation [START_REF] Morelato | When does the cutting of cocaine and heroin occur? The first large-scale study based on the chemical analysis of cocaine and heroin seizures in Switzerland[END_REF]. Here, MN helped in sample-to-sample comparison, and appeared to be of particular interest in major component profile screening. Furthermore, all cocaine derivatives were grouped in a unique cluster, allowing to quickly discriminate cocaine-related ions from adulterants.

Illicit drug powder profiling usually corresponds to a combination of complex, expensive and timeconsuming analytical and mathematical methods hyphenated to adequate databases [START_REF] Morelato | When does the cutting of cocaine and heroin occur? The first large-scale study based on the chemical analysis of cocaine and heroin seizures in Switzerland[END_REF][START_REF] Broséus | Chemical profiling: A tool to decipher the structure and organisation of illicit drug markets[END_REF].

However, visualization tools, such as MN, appear to be under-used. [START_REF] Guéniat | Le profilage de l'héroïne et de la cocaïne: une méthodologie moderne de lutte contre le trafic illicite[END_REF] reported that powder comparison is usually based on GC-MS analysis, searching for major compounds (e.g. benzoic acid for cocaine). Minor compounds (e.g. meconine for heroin) and inorganic compounds (e.g. zinc or iron) are not included in this comparison, due to the high intersample variability [START_REF] Guéniat | Le profilage de l'héroïne et de la cocaïne: une méthodologie moderne de lutte contre le trafic illicite[END_REF]. Although different, this method remains complementary to the molecular network approaches. In this study, the use of MN allowed a simple and efficient visualization of the different drug design stages, including main compounds identification, organization and comparison.

Therefore, it brings many complementary elements to quantitative assays, without expensive external standards requirement. In recent years, the use of MN has diversified in many scientific disciplines.

Multiple applications have been described in the literature such as metabolomics [START_REF] Allard | Deep metabolome annotation in natural products research: towards a virtuous cycle in metabolite identification[END_REF], drug discovery [START_REF] Quinn | Molecular Networking As a Drug Discovery, Drug Metabolism, and Precision Medicine Strategy[END_REF], identification of known metabolites or de-replication [START_REF] Yang | Molecular Networking as a Dereplication Strategy[END_REF], toxicological screening [START_REF] Allard | Application of a molecular networking approach for clinical and forensic toxicology exemplified in three cases involving 3-MeO-PCP, doxylamine, and chlormequat[END_REF], or xenobiotic metabolism exploration, either of natural or synthetic origin [START_REF] Allard | Application of a molecular networking approach for clinical and forensic toxicology exemplified in three cases involving 3-MeO-PCP, doxylamine, and chlormequat[END_REF][START_REF] Daré | A case of fatal acebutolol poisoning: an illustration of the potential of molecular networking[END_REF][START_REF] Allard | Comparative molecular networking analysis of a Rauwolfia plant powder and biological matrices in a fatal ingestion case[END_REF][START_REF] Quinn | Molecular Networking As a Drug Discovery, Drug Metabolism, and Precision Medicine Strategy[END_REF]. Recently, byprodcuts [START_REF] Vincenti | Molecular Networking: A Useful Tool for the Identification of New Psychoactive Substances in Seizures by LC-HRMS[END_REF]. Here, we further extend the use of this tool for the analyze of drugs of natural origin.

These data reinforce the utility of MN in molecular mapping, and show that this tool can provide extremely accurate visual drug fingerprints facilitating legal investigations.

In further studies, it would be interesting to investigate the potential of information propagation of quantitative results via molecular networks under the following hypothesis: since a molecular clusters implies spectral similarity, it could be assumed that the presence within a given cluster implies potentially comparable ionization responses. This ionization response could thus be propagated within a cluster from a properly quantified standards to unknown but related analogues allowing the semi-quantitative approach to be refined and expended. These perspectives could be of interest in analytical toxicology, showing then a triple utility of the molecular network: grouping spectrally similar compounds and propagating both qualitative (type of structure) and quantitative information (expected similarity in the ionization response).

CONCLUSION

This is the first application of a molecular network approach for the analysis and comparison of illicit drug seizures of natural origin. Here, organization of data using MN brings a major benefit compared to classical approaches. It provide visual modeling that facilitates the interpretation and understanding of toxicological test results by forensic scientists and magistrates in the context of law enforcement agencies seizures analysis. When used in conjunction with spectral databases, it thus provides valuable information on the product manufacturing, from synthesis to final shaping. Further investigation and exploitation of the spectral similarities evidenced by MN in the frame of illicit drugs profiling will undoubtedly indicate such visualization approaches as necessary assets in the toolbox of the legal toxicologists.

• https://gnps.ucsd.edu/ProteoSAFe/status.jsp?task=d85ac138c806487aabab29d0b7be17cf

(Figure 1 -Heroin powder)

• https://gnps.ucsd.edu/ProteoSAFe/status.jsp?task=eaadf7631b6d4e269dfb99a371b1d490

(Figure 2 -Cocaine powders)

  Vincenti et al. (2020) reported the use of MN to analyze new psychoactive substances in two seizures collected by the Italian Department of Scientific Investigation of Carabinieri allowing the identification of fentanyl analogs and synthetic cannabinoids, and associated impurities or synthetic

Figure 1 .

 1 Figure 1. The overall molecular network, composed of nodes from the sample powder X. RT:

Figure 2 .

 2 Figure 2. a) The cocaine-containing cluster, composed of nodes from the sample Y1 (orange),

Funding

This research did not receive any specific grant from funding agencies in the public, commercial, or not-for-profit sectors

Availability of data and material

Full data processed through the GNPS platform are accessible with these links:

DECLARATIONS

Conflicts Of Interest

None


Samuel Nalin

Guillaume Theyssier

On Turedo Hierarchies and Intrinsic Universality

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.

Introduction

The field of biomolecular computing has given rise to several theoretical models that describe growing process of (molecular) assemblies governed by local interaction or gluing rules. One of the most studied one, the abstract Tile Assembly model (aTAM) [START_REF] Winfree | Algorithmic Self-Assembly of DNA[END_REF], describes a process where the growth can happen anywhere asynchronously. It was successfully implemented in vitro as DNA self-assembly [START_REF] Paul | Algorithmic self-assembly of DNA Sierpinski triangles[END_REF]. In oritatami systems, introduced more recently [START_REF] Geary | Oritatami: A computational model for molecular co-transcriptional folding[END_REF][START_REF] Geary | Programming biomolecules that fold greedily during transcription[END_REF] and inspired from RNA origami [START_REF] Geary | A singlestranded architecture for cotranscriptional folding of RNA nanostructures[END_REF][START_REF] Geary | RNA origami design tools enable cotranscriptional folding of kilobase-sized nanoscaffolds[END_REF], the growth happens at a unique given point of the assembly and in a sequential manner. Despite their obvious differences as models of biomolecular systems, they share common features as computational models. Both are limited by the fact that they can only grow shapes (and not erase them), but both were shown capable of embedding universal computations in different ways [START_REF] Geary | Proving the Turing universality of oritatami cotranscriptional folding[END_REF][START_REF] Geary | Proving the turing universality of oritatami cotranscriptional folding[END_REF][START_REF] Cook | Temperature 1 selfassembly: Deterministic assembly in 3D and probabilistic assembly in 2D[END_REF][START_REF] Lathrop | Computability and complexity in self-assembly[END_REF][START_REF] Winfree | Algorithmic Self-Assembly of DNA[END_REF]. Recently, it was also shown through new results on oritatami systems that the infinite limit shapes both models can generate from finite seeds have the same computational complexity and the same possible densities of occupied position in the plane [START_REF] Pchelina | Oritatami Systems Assemble Shapes No Less Complex Than Tile Assembly Model (ATAM)[END_REF]. The key ingredients of these new results were, on one hand, the introduction of a new model, called turedos, which abstracts away low level details of oritatami systems and is easier to program, and on the other hand, a proof that oritatami systems can simulate a large family of turedos. This underlines the interest of turedos but also the surprising capabilities of models of sequential growth process in the plane. The present work is entirely focused on the turedo model and aims at better understanding its limitations and its expressive power as a growth process and computational model.

Turedos. Intuitively, a turedo is a Turing machine whose head can move in the plane or in the 3-dimensional space but only in a self-avoiding way, i.e. without going back to a previously visited position. More precisely, the turedo's head can only move to empty or unmarked positions, and it must put a mark on each visited position when leaving it. The key ingredient of a turedo, and what makes its main computational power, is its lookup radius: when deciding a move and what mark to put on the visited position, the turedo has access to the local configuration of marks around its position, up to some finite distance. Like any Turing machine, a turedo also has a set of internal head states. Without entering into details, an oritatami system consists of a "molecule" made of "beads" that can attract each other. The molecule grows at each step following a periodic bead sequence and folds as follows: the δ most recently produced beads are free to move around to look for the position that maximizes the number of bonds they can make with each other ; then the first (oldest) bead among the δ most recent ones is fixed according to that position, a new free bead is added and the process iterates. This behavior can be realized in a turedo of radius δ + 1. The main result of [START_REF] Pchelina | Oritatami Systems Assemble Shapes No Less Complex Than Tile Assembly Model (ATAM)[END_REF] is that oritatami of delay 3 can simulate turedos of radius 1. In fact, turedos also naturally capture variants of oritatami systems: for instance, one can imagine negative (repulsive) bonds in the process of maximizing gluing strength, or add local rules forbidding two bead type to be neighbor of each other. Therefore negative results on turedos become negative results on oritatami systems, but also potential variants of them.

Simulations and universality. The main question we address here is how the capabilities of turedos change with their radius and what is the role of the dimension of space. We are interested in qualitative differences and don't compare turedos move by move and cell by cell. We rather use a notion of simulation allowing spatio-temporal rescaling, similar to the one used in cellular automata [START_REF] Delorme | Bulking ii: Classifications of cellular automata[END_REF][START_REF] Becker | Universality in freezing cellular automata[END_REF], in aTAM [START_REF] Pierre | The non-cooperative tile assembly model is not intrinsically universal or capable of bounded Turing machine simulation[END_REF][START_REF] Doty | The tile assembly model is intrinsically universal[END_REF][START_REF] Meunier | Intrinsic universality in tile self-assembly requires cooperation[END_REF] or in the simulation result of turedo by oritatamis [START_REF] Pchelina | Oritatami Systems Assemble Shapes No Less Complex Than Tile Assembly Model (ATAM)[END_REF]. Intuitively a cell can be simulated by a block of cells, and a step by a finite number of steps. We are naturally interested by hierarchy results (existence of turedos that can't be simulated by lower radius ones), or on the contrary by universality results (existence of turedos that can simulate all turedos or a large class of them). For instance, the existence of intrinsically universal systems in the aTAM model was much studied and it was shown that it crucially depends on natural parameters of the model [START_REF] Pierre | The non-cooperative tile assembly model is not intrinsically universal or capable of bounded Turing machine simulation[END_REF][START_REF] Meunier | Intrinsic universality in tile self-assembly requires cooperation[END_REF][START_REF] Doty | The tile assembly model is intrinsically universal[END_REF][START_REF] Hendricks | Universal simulation of directed systems in the abstract tile assembly model requires undirectedness[END_REF]. However, as natural as it might seem, a formal notion of simulation is never a neutral choice when tackling these questions [START_REF] Becker | Universality in freezing cellular automata[END_REF][START_REF] Delorme | Bulking ii: Classifications of cellular automata[END_REF][START_REF] Boyer | On factor universality in symbolic spaces[END_REF]. Thus, in addition to the parameters of the turedo model we also study the influence of the notion of simulation itself. For this we identify various ingredients, in particular the possibility of fuzz, i.e. the tolerance allowed for the simulating turedo to visit some regions of space close to the ongoing assembly that represent empty cells of the simulated turedo and are therefore not yet been visited by it. Note that a similar notion of fuzz appeared in the intrinsic universality results on aTAM [START_REF] Doty | The tile assembly model is intrinsically universal[END_REF]. We end up with three notions of simulation: the rigorous, the fuzzless and the liberal ones.

Our contributions. After formalizing all the concepts mentioned so far (Section 2), we establish a surprisingly diverse general picture of the capabilities of turedos of simulating each other. Separating the negative results (Section 3) from the positive ones (Section 4), our results are the following:

1. under fuzzless simulation, intrinsic universality is impossible whatever the dimension, there is a radius hierarchy, and actually the impossibility strikes at radius 2: no turedo can fuzzlessly simulate all radius 2 turedos (Theorem 1);

2. when restricting to radius 1, rigorous intrinsic universality is possible in dimension 3 (Theorem 5), but not in dimension 2 (Theorem 2);

3. however, we built a 2D turedo of radius 3 which is able to rigorously simulate all 2D turedo of radius 1 (Theorem 4);

4. for liberal simulations, we establish intrinsic universality in dimension 3 and a complete hierarchy collapse at radius 1 (Corollary 1);

5. finally we show that there is a 2D turedo of radius 2 which is impossible to simulate at radius 1, even under liberal simulations (Theorem 3).

Besides the above results, our contribution also lies in the constructions and proof techniques. For instance, the negative result 5 is based on a general lemma for 2D turedos of radius 1, which bounds the quantity of information (using Kolmogorov complexity) that can be carried from the seed to another connected component of the plane when the plane is divided by a 4-connected path. As another example on the constructive side, result number 3 above uses a novel construction technique (called heat sink trick) that fully exploits the potential of radius 3 and could be used in any place where two unbounded streams of information have to be crossed. Finally, in Section 5, we discuss various questions left open and present what we believe are promising future research directions.

Definitions

We denote by N the set of natural numbers (including 0), by N + the positive ones, and by Z the set of integers. We consider turedos on Z d for d = 2 or 3 (and in particular, we don't use the hexagonal lattice on the plane, mostly to simplify notations and dimension change). We fix a blank symbol ⊥used to represent empty positions and common to all turedos. The ball of radius r in dimension d, denoted B d (r), is the set of positions reachable in r elementary moves (moves along vector of the canonical based of Z d ) from the origin. B d (1) will always be the set of possible head moves in dimension d. We denote by c[z; S] the pattern of shape S around position z in configuration c, i.e. the map z ′ ∈ S → c z+z ′ .

Definition 1 (Turedo).

A turedo of dimension d and radius r is a triple T = (A, Q, δ) where A is its finite alphabet with ⊥ ∈ A, Q is its finite set of head states and

δ : Q × A B d (r) → Q × A \ {⊥} × B d (1) is its local transition map. A global state of T is a triple (c, z, q) ∈ G T = A Z d × Z d × Q specifying a configuration,
a position and a head state. The global transition map F T : G T → G T associated to T is defined by:

F T (c, z, q) = (c, z, q) if c(z) = ⊥ or c(z + µ) = ⊥ (c ′ , z + µ, q ′ ) else, where (q ′ , a, µ) = δ(q, c[z; B d (r)]) and configuration c ′ is defined by c ′ (z) = a and c ′ (z ′ ) = c(z ′ ) for all z ′ = z.
The domain of a global state (c, z, q) is the set of non-blank positions of c plus the head position, formally: D(c, z, q) = {z} ∪ {z ′ : c(z ′ ) = ⊥} A global state (c, z, q) is finite if its domain is finite. We are interested in orbits starting from finite initial global states, called finite seeds.

Example 1 (The spiral-XOR turedo). Let A = {⊥, 0, 1} and Q = {←, ↑, →, ↓}.

↑ (+0) ← (-1) mod2 ↑ (+0) ↑ → (+1) ↑ (+0) mod2 → (+1) ↑ ↓ (+2) ↑ (+0) mod2 ↓ (+2) ↑ ← (+3) ↑ (+0) mod2 ← (+3)
See Figure 1 for an example of orbit.

The main focus of this paper is to understand the role of radius and dimension in the computational complexity of turedos.

We will denote by TUR d (r) the set of turedos of dimension d and radius r, and

TUR d = r≥1 TUR d (r).
Before formalizing simulation, we first need to define block encodings which are ways to represent global states of a simulated turedo by blocks in the simulator.

Any The head holds a direction (where the black triangle is pointing to) and its self-avoiding trajectory since the beginning is drawn as a black path.

given b ∈ N d + defines a rectangular block R b = {z ∈ N d : 0 ≤ z i < b i for 1 ≤ i ≤

Definition 2 (Block encoding). Let us fix a dimension d. Given two pairs of alphabets and state sets

(A 1 , Q 1 ) and (A 2 , Q 2 ) with ⊥ ∈ A 1 ∩ A 2 , a block encoding of global states G 1 = A Z d 1 × Z d × Q 1 into G 2 = A Z d 2 × Z d × Q 2 is given by a block size b ∈ N d
+ and two partial onto maps:

• the headless block decoding map α : D α ⊆ A R b 2 → A 1 verifying ⊥ R b ∈ D α and α(⊥ R b ) = ⊥,
• the head block decoding map β :

D β ⊆ A R b 2 × R b × Q 2 → Q 1 × A 1 . A global state (c, z, q) ∈ G 2 is
valid for the encoding if it is made only of patterns from D α far from the head and D β around the head, precisely if:

(c[ρ b (z); R b ], µ b (z), q) ∈ D β and c[ρ b (z ′ ); R b ] ∈ D α for all z ′ ∈ Z d such that ρ b (z ′ ) = ρ b (z).
Finally, the global decoding map Γ associates to any valid global state (c 2 , z 2 , q 2 ) ∈ G 2 a global state (c 1 , z 1 , q 1 ) ∈ G 1 defined by application of decoding maps α or β on each block according to the presence of the head in the block, i.e. :

• b ⊗ z 1 = ρ b (z 2 ), • (q 1 , c 1 (z 1 )) = β(c 2 [ρ b (z 1 ); R b ], µ b (z 2 ), q 2 ), • c 1 (z) = α(c 2 [ρ b (z 2 ); R b ]) for all z = z 1 .
The map α and β being partial and onto intuitively means that not all global states are valid, and that any global state of

A Z d 1 × Z d × Q 1 can
be encoded. Note that the headless block decoding map α always decodes blank blocks ⊥ R b as blank state ⊥. Denote by D b (c 2 , z 2 , q 2 ) the block domain of global state (c 2 , z 2 , q 2 ) which is the set of blocks that are not entirely blank,

i.e. D b (c 2 , z 2 , q 2 ) = {z : b ⊗ z = ρ b (z 2 ) or c 2 [b ⊗ z; R b ] = ⊥ R b }.
We can now define simulations precisely using block encodings. Intuitively, we ask for the simulator to be able to reproduce any orbit of the simulated turedo starting from a finite seed, and using a (fixed) finite number of steps to simulate one step. Since we want the initial seed of the simulator to be neutral and without any pre-computed information about the future of the simulated orbit, we ask that its block domain correspond to the domain of the simulated seed. • corresponding block domain:

D(c 1 , z 1 , q 1 ) = D b (c 2 , z 2 , q 2 ),
• correct encoding:

(c 1 , z 1 , q 1 ) = Γ(c 2 , z 2 , q 2 ), then it holds ∀t ∈ N, F t T1 (c 1 , z 1 , q 1 ) = Γ F kt T2 (c 2 , z 2 , q 2 )).

Such simulations are the base upon which we define three variants (two restrictions and one generalization).

We say that a simulation is fuzzless if the block domain in the simulator orbit remains identical to the domain of the simulated orbit, precisely:

∀t ∈ N : D b (F kt T2 (c 2 , z 2 , q 2 )) = D(F t T1 (c 1 , z 1 , q 1 )
). We say that a simulation is rigorous if the movements of the head of T 2 in simulating orbits strictly remains inside blocks corresponding to the simulated head position of T 1 , even at intermediate steps, precisely: if z t 1 denotes the head position of

F t T1 (c 1 , z 1 , q 1 ) and z t 2 that of F t T2 (c 2 , z 2 , q 2 ), it holds for all t ′ with kt ≤ t ′ ≤ k(t + 1) : z t ′ 2 ∈ (b ⊗ z t 1 + R b ) ∪ (b ⊗ z t+1 1 + R b ).
Finally, a liberal simulation is a generalized simulation where we only ask that for each finite global state (c 1 , z 1 , q 1 ) ∈ G T1 there exists a global state (c 2 , z 2 , q 2 ) ∈ G T2 with corresponding block domain and correct encoding such that it holds ∀t ∈ N,

F t T1 (c 1 , z 1 , q 1 ) = Γ F kt T2 (c 2 , z 2 , q 2 )
). Liberal simulations can have fuzz and make non-rigorous head movements. Note that fuzzless simulations are equivalent to simulations where the headless block decoding map is such that α(u) = ⊥ ⇐⇒ u = ⊥ R b , i.e. that the only block coding ⊥ is ⊥ R b . Note also that a rigorous simulation is necessarily fuzzless because the head of the simulator has no opportunity, even at intermediate time steps, to visit blocks not corresponding to the domain of the simulated configuration. The power of fuzzless simulations compared to rigorous ones is to allow the head to go back to blocks that were previously visited. Thus the head can potentially retrieve information from non adjacent blocks that were written a long time ago. With rigorous simulation on the contrary, the head has only access to adjacent blocks during a simulation cycle.

We denote by ≤ the liberal simulation, by ≤ F L the fuzzless simulation and by ≤ R the rigorous simulation.

Among many properties of these simulation relations, we are particularly interested in universality: the capacity of a single turedo to simulate a whole set of turedos. Given a dimension d and a radius r, we denote by U ≤ d (r) the set of turedos T ∈ TUR d such that for any T ′ ∈ TUR d (r) it holds T ′ ≤ T . We denote by U ≤ d the set of turedos T ∈ TUR d such that for any T ′ ∈ TUR d it holds T ′ ≤ T . We use similar notations for simulation relations ≤ R and ≤ F L .

Separation Results

No Fuzz, no Fun

The fuzzless condition gives much importance to larger radii, simply because a turedo's head surrounded by blocks coding ⊥ cannot read information far away without moving inside these blocks and thus creating fuzz. The following theorem exploits this obvious limitation to show two immediate consequences: first, there is a radius hierarchy (new behaviors appear at radius r+1 that cannot be simulated at radius r) and thus no general fuzzless universality; second, universality is impossible even at radius 2: any turedo (whatever its radius) will fail to simulate some radius-2 turedo. The dimension plays no role in these results.

Theorem 1. For any d ≥ 2 and r ≥ 1, we have the following:

• there is T r+1 ∈ TUR d (r + 1) such that for all T r ∈ TUR d (r), T r+1 ≤ F L T r ; in particular, U ≤F L d = ∅.
• for any T r ∈ TUR d (r) there exists

T 2 ∈ TUR d (2) such that T 2 ≤ F L T r ; in particular, U ≤F L d (r) = ∅ for any r ≥ 2.
Proof. We prove the result for d = 2, the argument can be generalized to higher dimension straightforwardly (by completing 2D configurations by ⊥ everywhere else).

For the first item, simply consider a turedo T r+1 ∈ TUR 2 (r + 1) that has the following behavior when the head in position (0, 0) has only ⊥ letters at the north and at the south of its current position: read the letters at positions (r + 1, 0) and (0, r + 1) and move to the north is they are equal and to the south otherwise. Consider any turedo T r ∈ TUR 2 (r) and any block size b ∈ N 2 + . To simulate T r+1 fuzzlessly, T r has to move either to block b ⊗ (0, 1) or block b ⊗ (0, -1) depending on blocks b ⊗ (r + 1, 0) and b ⊗ (0, r + 1) without entering into any other neighboring block: this is impossible, because with radius r turedo T r can't have any information about either b ⊗ (r + 1, 0) or b ⊗ (0, r + 1) before making a decisive move (by entering inside either b ⊗ (0, 1) or b ⊗ (0, -1)) so it will fail to correctly simulate the orbit of at least one seed.

The second item can be proved similarly, using a pumping trick on the alphabet: for any fixed T r ∈ TUR 2 (r) with alphabet of cardinal k, choose T 2 ∈ TUR 2 (2) with an alphabet strictly larger than k r 2 so that at least on dimension of the block size b of any potential simulation of T 2 by T r has to be at least r + 1 (otherwise there is simply no way to code all letters of T 2 on different blocks of size b). Then, choosing T 2 to have the same behavior as T r+1 above, we get the same contradiction: there is a direction of b, let's say the vertical one, which overwhelms the radius r of T r so T r won't be able to read the content of block b ⊗ (0, 2) before making a decisive move and will therefore fail to correctly simulate at least one orbit.

Dimension 2 and Radius 1: the Jordan Curve Burden

A turedo's head in dimension 2 always moves drawing a 4-connected path. When the turedo has radius 1, it has no way to read information across such a path (while it could with a larger radius). Therefore head movements for turedos of radius 1 turns into potential information barriers. The precise way in which this simple observation affects the simulation power of such turedos depends on the type of simulation considered. Let us first consider rigorous simulations. Any turedo T (whatever its radius) can obviously do the following elementary copy-and-move operation (see Figure 3):

• move to the right to some position z;

• read the letter a present at position z + (1, 0);

• then move to position z + (0, 1) and leave behind letter a at position z.

In particular, if the head continues its way and later arrives at position z -(0, 1) from the south, it can read the information a copied at position z.

However, if we suppose that some T 1 ∈ TUR 2 (1) simulates T under rigorous simulations with block size b, the movement of its head inside block b ⊗ z to simulate the above copy-and-move step must be the following (see Figure 3):

• coming from the left side of the block, it draws some path inside it until it reaches the right border (if not it cannot read any information from the adjacent block to the right);

• then it must move north, otherwise it would be trapped in the south part of the blocks by the 4-connected path drawn so far that connects the left and right sides of the block; • it must finally escape through the north side. This head movement is such that at most 1 letter of T 1 is written on the south side of block b ⊗ z after having had the opportunity to read some information from the adjacent block that encodes letter a. In particular, if T 1 has smaller alphabet than T this is not enough to completely encode a on the south side of block b ⊗ z. So, this is a limitation that has to be dealt with if later in the simulation the head arrives from the south and has to read from the south side of block b ⊗ z. A single copy-and-move is not enough to get a contradiction because the simulation of T 1 could be organized so as to transport the complete information about a along the way and have it on hands already when arriving at the south of block b ⊗ z. However, by repeating such copy-and-move steps, one can saturate the simulator and show the following theorem that states that there is no universal turedo of radius 1 among turedos of radius 1 for rigorous simulations.

Theorem 2. For any

T ∈ TUR 2 (1) there is T ′ ∈ TUR 2 (1) such that T ′ ≤ R T . In particular U ≤R 2 (1) ∩ TUR 2 (1) = ∅. Proof.
Let Q be the state set of T , A be the alphabet of T and consider any alphabet A + with m = |A| < |A + | = m + . Then it is straightforward to construct a turedo T ′ ∈ TUR 2 (1) of alphabet A ′ = A + ∪ {↓, ←, ↑} that has the following behavior (see Figure 4):

• for any n ∈ N, any a = (a 0 , . . . , a n ) ∈ A n+1 + , a ′ ∈ A + and 0 ≤ i ≤ n, consider the finite seed σ( a, i, a ′ ) with head in position (0, 0), a j in position (3j + 2, 0) for 0 ≤ j ≤ n, a ′ in position (3i + 1, -3) and ↓ in positions (3(n + 1) + 2, 0) and (3(n + 1) + 2, -1), ← in position (3(n + 1) + 2, -2) and finally ↑ at position (3i, -2);

• from such a seed, T ′ starts a sequence of n + 1 copy-and-move steps that results in having a copy of a j at position (3j + 1, 0) for 0 ≤ j ≤ n; the end of this phase occurs at time step 5(n + 1) and the head reaches position (3(n + 1), 0);

• then T ′ reaches the first ↓ and follows the move indications of arrows (down, down, left), until it reaches the up arrow, and moves from position (3i + 1, -2) to (3i + 1, -1);

• finally, at position (3i + 1, -1) it moves right if a i = a ′ and left otherwise (it can do so because it has copied the value of a ′ when leaving position (3i + 1, -2)).

Let's call t n,i the time step at which occurs this final left or right move (t n,i only depends on i and n): at time t n,i , the head of T ′ must be either at position (3i, -1) or (3i + 2, -1). Thus T ′ implements on seed σ( a, i, a ′ ) the test of whether a i = a ′ . We are going to show that T cannot simulate T ′ under rigorous simulations. Suppose by contradiction that T ′ ≤ R T with block size b and time scaling factor k. Given n ∈ N and 0 ≤ i ≤ n, denote by A n ⊆ Z 2 the set of positions that are on the right side of block b ⊗ (3(n + 1), 0) (the block corresponding to the position reached by T ′ at the end of the copy-and-move sequence as detailed above). Denote by B i,n ⊆ Z 2 the set of positions that are on the south side of block b ⊗ (3i + 1, 0). Finally, denote by C i,n ⊆ Z 2 the set of positions made of the union of blocks (3i + 1, -3), (3i, -2), (3(n + 1) + 2, 0), (3(n + 1) + 2, -1), (3(n + 1) + 2, -2) (i.e. those corresponding to position a ′ or an arrow {↓, ←, ↑} in the seed σ( a, i, a ′ )). Consider now n ∈ N, a, c ∈ A n+1 + a ′ ∈ A + and 0 ≤ i ≤ n, and take any two global states g 1 and g 2 of T that correctly simulate the orbits of T ′ on seed σ( a, i, a ′ ) and σ( c, i, a ′ ) respectively and that are identical on C i,n Considering time step t 0 (n) = 5k(n + 1) corresponding to the end of the copy-and-move sequence, if global states T t0(n) (g 1 ) and T t0(n) (g 2 ) are identical on domains A n and B i,n and have the same head state, then both orbits must make the same final decision to move to the left block or the right block at the final time step kt n,i , precisely: the head in global state T ktn,i (g 1 ) is in the same block as the head in global T ktn,i (g 2 ) (and it must be either b ⊗ (3i, -1) or b ⊗ (3i + 2, -1)). Indeed, by the property of rigorous simulations and the behavior of T ′ , the only positions with content written before t 0 (n) that the head of T can possibly read between time step t 0 (n) and kt n,i are positions in A n ∪ B i,n ∪ C i,n , so the orbit starting from step t 0 (n) is completely determined by the content of the configuration in that domain and the internal state of T at time t 0 (n).

Claim 1. There must exist

n ∈ N, 0 ≤ i ≤ n, a ∈ A n+1 + , a ′ ∈ A + and c ∈ A n+1
+ with a j = c j for all j < i and a i = c i , and two global states g 1 and g 2 of T that correctly simulate seeds σ( a, i, a ′ ) and σ( c, i, a ′ ) respectively, and also such that T t0(n) (g 1 ) and T t0(n) (g 2 ) have same head state and are identical on domain

A n ∪ B i,n ∪ C i,n .
Proof of the claim. In this proof, we fix for each a ∈ A + a unique block of A R b that encodes it, and for any seed of T ′ we only consider a unique global state of T that simulates it. First, there are only a bounded number (bound in n) of possible content of a configuration on domain A n and state of T , so for each n there must exist u ∈ A An and q ∈ Q, a set X n ⊆ A n + of size Ω(m n + ) such that for each 0 ≤ i ≤ n and each a ∈ X n , the corresponding global state g of T simulating T ′ on seed σ( a, i, n), is such that T t0(n) (g) is equal to u on domain A n and with head state q.

Second, we claim that for large enough n there must be some i and a prefix a 0 , . . . , a i-1 ∈ A i + such that there are at least m + 1 choices of a i ∈ A + such that a 0 , . . . , a i can be completed into an element a ∈ X n . Indeed, otherwise we would have |X| ≤ m n which would contradict the fact that |X| ∈ Ω(m n + ) for large enough n since m < m + . Now consider the set of global states that simulates the seeds σ( a, i, a ′ ) where a ∈ X n are the m + 1 completed vectors from the common prefix a 0 , . . . , a i-1 , and a ′ ∈ A + . They are identical on the blocks corresponding to the common prefix a 0 , . . . , a i-1 of the seed they simulate. As already said, these global states at step t 0 (n) are also identical on domain A n and have same head state. Moreover, on domain B i,n and still at step t 0 (n), they agree because of the common prefix a 0 , . . . , a i-1 , except possibly on the lower-right corner where they can take at most m different values (see Figure 3 and discussion at the beginning of this section). We deduce that among the m + 1 choices for a i , at least 2 must correspond to global states that completely agree on B i,n . Denote by a ′ and c ′ these two choices and consider a and c to be the vectors completing the prefixes a 0 , . . . , a i-1 , a ′ and a 0 , . . . , a i-1 , c ′ respectively. The claim follows by choosing seeds σ( a, i, a ′ ) and σ( c, i, a ′ ).

The theorem follows from the claim by contradiction: as shown above, global states g 1 and g 2 force the same behavior of T starting from time t 0 (n), but at the same time their orbits should not end up in the same block because they simulate seeds of T ′ that do not have the same answer to the final equality test.

We will now establish a strong separation between TUR 2 (1) and TUR 2 (2) even under liberal simulations. We first establish a lemma expressing bounds on information leakage between too regions separated by a 4-connected path. It is formulated using Kolmogorov complexity. Recall that the (plain) Kolmogorov complexity of a string u ∈ {0, 1} * is the length of the shortest program that outputs u, more precisely the length of the shortest v ∈ {0, 1} * such that a suitable fixed universal Turing machine outputs u on input v (see [START_REF] Li | Algorithmic complexity[END_REF]). For any X ⊆ Z 2 and any (partial) configuration c ∈ Q X of finite domain, we denote by K(c) its Kolmogorov complexity, which is the Kolmogorov complexity of the finite binary string u that encodes c as a list of pairs (z, c(z)) such that c(z) = ⊥ given in lexicographical order. Lemma 1. Let C 0 ∈ N be some constant and T ∈ TUR 2 (1). Then there is another constant C ∈ N with the following property. Consider any 4-connected path ρ of Z 2 that divides Z 2 in 2 or more connected components, and any finite global state s ∈ G T with head at position (0, 0), and whose domain D(s) lies entirely in one of the connected components defined by ρ, denoted A 0 . Suppose moreover that for some n ∈ N, the orbit from global state s to global state (c, z, q) = F n T (s) is such that the head visits path ρ at most C 0 times. Then, the restriction of c to the complement of A 0 has 'small' kolmogorov complexity:

K(c |Z 2 \A0 ) ≤ C log(n).
Proof. We show that c |Z 2 \A0 can be computed from the following description D:

• the finite list of positions on ρ that are visited by the head during the n first steps of the run starting from s;

• the list of events corresponding to each such position z given as a triple: time at which the head leaves position z, letter written at that step, and move made by the head at that step.

This description is of size O(log(n)) because both positions z and time steps occurring in the above lists are bounded by n by definition (recall that the head is initially at (0, 0)).

Because T is of radius 1 and ρ is 4-connected, each time the head of the turedo is neither in A 0 nor on ρ, the local transition does not depend on the current configuration on domain A 0 . A Turing machine can therefore compute c |Z 2 \A0 from this description by maintaining the following partial information step by step:

• the current configuration restricted to domain Z 2 \ A 0 ,

• the partial information on the head position z: the exact position if z ∈ A 0 or the state "undefined" else.

This information is straightforward at the initial step since D(s) ⊆ A 0 so the head is in A 0 and the configuration is ⊥ everywhere outside A 0 . The partial information at step n is enough to give c |Z 2 \A0 and it is updated from one step i to the next i+ as follows:

• if the partial information on the head at step i is undefined and time step i + 2 does not appear in the lists of D, then don't change the partial information (the head is in A 0 and won't move to ρ at step i + 1);

• if the head information is undefined but step i + 2 appears in D, then updates the head position to the position on ρ that corresponds to the item stamped by time steps i + 2 in D;

• if the head position is on ρ then some item in the list of D must be stamped by time step i + 1 and gives all the information to update both the head position and the configuration on ρ;

• finally if the head position is neither in A 0 nor on ρ, then the knowledge of the current configuration restricted to domain Z 2 \ A 0 is enough to update the partial information (position and partial configuration).

Note that if the seed s has 'large' kolmogorov complexity, for instance Ω(n), then n steps are far from enough to transmit all the information about s to another connected component under the hypothesis of the above lemma. The power of this lemma lies in the fact that constant C does not depend on the path ρ nor on the seed s. In particular, one can choose ρ depending on s to apply the lemma. Turedos of radius 2 can overcome the limitation of Lemma 1 because they can transmit information over a path without writing on it. It turns out that this is enough to separate TUR 2 (2) from TUR 2 (1) even under liberal simulations. Theorem 3. There is T 2 ∈ TUR 2 (2) such that for any T 1 ∈ TUR 2 (1):

T 2 ≤ T 1 .
Proof. Let's consider the turedo T 2 ∈ TUR 2 (2) that behaves as follows on a seed made of a vertical word u of length n (see Figure 5): • it copies u to the right by making zigzags and does this n times (it implements a unary counter initialized to the length of u while making copies);

• it then moves one cell to the right without making copies (and thus leaving an empty column above);

• it then do again n copies of u by zigzag while moving to the right (note that the first copy can be done because T has radius 2);

• at the end of the last copy it goes around the last bloc of n copies by the north side until it encounters the empty column and then goes down into it until it is blocked.

Denote by z N and z S the northmost and southmost positions of the last sequence of n south moves of the head (see Figure 5), and by t N and t S the respective time steps at which the head is at position z N and z S . Note that t S is O(n 2 ) and it is the final step of the orbit considered here. Now suppose by contradiction that there is some T 1 ∈ TUR 2 (1) such that T 2 ≤ T 1 . Denote by k the time rescaling factor and b the block size involved in this simulation. Let's suppose that n is large enough (to be precised later) and that u has large kolmogorov complexity, let's say Ω(n). Consider a global initial state s 1 for T 1 from which starts a correct simulation of the run of T 2 . When the simulation reaches step kt N , the head of T 1 is inside bloc b ⊗ z N and there must be a finite 4-connected path p 1 , . . . , p m of empty positions from this position to some position inside bloc b ⊗ z S because T 2 has to simulate the state changes made by T 1 between steps t N and t S along the vertical segment of positions from z N to z S . Let ρ denote the infinite path that extends p 1 , . . . , p m infinitely to the north from p 1 and infinitely to the south from p m .

We claim that there is a bound C 0 depending only on T 1 , b and k, but not on n and neither on u, such that the run of T 1 starting from global state s 1 until time step kt N crosses at most C 0 times path ρ. First, by choice of p 1 , • • • , p m , such crossings can only happen at positions of ρ that are either at the north of p 1 or at the south of p m . The simulation is liberal, so the head of T 1 has some freedom of move but it must always remain at a bounded distance from the block corresponding to the simulated head position of T 2 during intermediate steps, precisely: if the head of T 2 is at position z at time step t, then the head of T 1 must be inside block b ⊗ z at time step kt and therefore at distance at most k of block b ⊗ z during time steps between kt and k(t + 1). A position is therefore potentially reachable by T 1 before time step kt N only if it is at distance at most k from a block b ⊗ z such that position z in the run of T 2 is visited before time step t N . The key observation is that in the run of T 2 , there are only finitely many positions that are visited before time t N and at distance less than k from either z N or any position at the north of it, or from z S or any position at the south of it. From this we deduce that ρ \ {p 1 , . . . , p m } is crossed a bounded number of times C 0 by the head of T 1 before time step kt N . The claim that ρ is crossed at most C 0 times before time step kt N follows since {p 1 , . . . , p m } are by definition empty before this time step.

Finally, note that path p 1 , . . . , p m cannot move away more than distance k from blocks b ⊗ z N to b ⊗ z S , so if n is large enough, the domain of s 2 is guaranteed to lie entirely inside the left connected component A 0 of Z 2 \ ρ. Similarly, the blocks containing the encoding of the rightmost copy of u must lie entirely inside Z 2 \ A 0 . In particular, the configuration c of T 1 reached at step kt N must be such that K(c |Z 2 \A0 ) ∈ Ω(n) by choice of u. However, Lemma 1 applied at step kt N to T 1 and ρ gives:

K(c |Z 2 \A0 ) ≤ C log(kt S ) ∈ O(log(n))
which is a contradiction for large enough n.

Universality Results

Radius 3 in 2D under Rigorous Simulations: the Heat Sink Trick

Theorem 2 shows that no turedo of radius 1 can be universal for TUR 2 (1) under rigorous simulations. We show that this is however possible with radius 3. In order to achieve universality, four key behaviours must be performed by our turedo at each simulation step. It needs to read all necessary information of neighbouring blocks, compute the next simulation step, write the computed letter and exit the current block (entering the correct next one). Figure 6 illustrate those behaviours. To rigorously simulate a turedo of radius 1, it seems natural to perform the 3 behaviours interacting with neighbours on the edge of the block, each on its layer, motivating a radius 3. But as we are dealing with universality, the so called necessary information is not only the letters of neighbouring blocks but also the transition table defining the simulated turedo.

Carrying this information has a direct impact on the width of the reading and writing layer, we propose an intertwined zigzag to merge the space occupied by those two, keeping the radius 3 and taking full advantage of it.

Theorem 4. U ≤R 2 (1) ∩ TUR 2 (3) = ∅.
Proof. We show that there is T 3 ∈ TUR 2 (3) such that for all T 1 ∈ TUR 2 (1):

T 1 ≤ R T 3 . Denote T 3 = (A 3 , Q 3 , δ 3 ). Let's take T 1 ∈ TUR 2 (1) some 2D turedo, T 1 = (A 1 , Q 1 , δ 1 ), a configuration c 1 ∈ A Z 2
1 and describe how T 3 simulates it with square blocks R (n,n) and n = 0 mod 4. We first focus on the organisation of transmittable information in a given block B, i.e. the transition table δ 1 and the letter a 1 ∈ A 1 in this position in c 1 . To be accessible to the neighbouring blocks, this information is present on the outside edges of B, repeated on each

transition tablebuffer a1 ∈ A1 buffertransition table b1 ∈ A1 Figure 6: Behaviour, in one block, of the presented 2D radius 3 turedo T 3 ∈ U ≤R 2 (1)
. The light blue rectangles represent the information to read of the neighbouring cells. In this example, a letter of A 1 is encoded by 3 letters of A 3 . We can see the 2 padding cells, the transition table (here of arbitrary small size for readability of the figure), the buffer of size 12 (to contain 4 letters of A 1 encoded), the padding, the letter of the block encoded by 3 letters of A 3 repeated 4 times each and again the the padding, the buffer, the table and the last 2 padding cells. The arrows represent the path followed by the turedo, entering the block in the bottom left of the figure. The blue part reads the content of the adjacent blocks, the grey one allows for turning, the orange one is where the computing takes place, the red one fetchs the computed letters (and writes them on the faces that will not be visited again before exiting the block) and the green one finishes to write the letters and exits to the next block.

edge such that B(0, i) = B(i, n -1) = B(n -1, n -1 -i) = B(n -1 -i, 0).
Considering a partial onto letter decoding map γ : A m 3 → A 1 with m ∈ N, the organisation on one edge of B is the following. The first two positions B(0, 0) and B(0, 1) are empty or irrelevant, then the next 3m|A 1 | positions from B(0, 2) to B(0, 3m|A 1 | + 1) are the encoding of the transition table with γ (which we assume to be a multiple of 4 without loss of generality). Positions B(0, 3m|A 1 | + 2) to B(0, m(3|A 1 | + 4) + 1) are reserved for a buffer in which 4 letters will be encoded (the ones contained in the 4 neighbouring blocks). Then m(3|A 1 | + 4) + 2 positions are empty or irrelevant, from B(0, m(3|A 1 | + 4) + 2) to B(0, 2m(3|A 1 | + 4) + 3), to allow the block to be spacious enough for the computation. Following that is written u ∈ A 4m 3 such that u(4i + k) = γ(a 1 )(i) for all 0 ≤ k < 4 (the redundancy is present to ensure proper reading later). Then again, from B(0, 2m(3|A 1 | + 6) + 4) to B(0, 3m(3|A 1 | + 4) + 2m + 5) is some irrelevant padding followed by the 4m sized buffer, the 3m|A 1 | sized transition table and 2 irrelevant position, finishing at B(0, m(12|A 1 | + 20) + 7). An illustration of this distribution is represented in figure 6.

Let's now describe the behaviour of T 3 in a block to achieve universality. As all necessary information to compute is contained in a m(3|A 1 | + 4) letters long word on A 3 , we base our construction on two types zigzags of this size : the square and the heat sink. A square gadget of even size k is a back and forth k/2 times of a k sized line during which the content of the original line is replicated on each four sides of the created square. This copy is possible thanks to the radius of T 3 being greater than 2. Its main use is to keep and spread information while cornering. A heat sink gadget is a zigzag with each back and forth being spaced by 2. The radius 3 of T 3 allows the heat sink to still copy information from the previous zag during a zig. Its purpose is to acquire and transmit data laterally while being intertwined with another heat sink. Both gadget and the simulation of a block are illustrated in figure 6 to illustrate the following explanation.

T 3 enters a block B at position B(0, 2) (or B(2, n-1), B(n, n-3), B(n-3, 0) up to rotation), it first continues forward by 2 (until reaching B(2, 2)) then turns 90 • counter-clockwise and starts a square gadget, initialised by the copy of the transition table and empty buffer available at distance 3. Those squares will be performed at each corners of the block with in between a heat sink which will both transmit the transition table already collected earlier and approach the outside edge of the neighbouring block at distance 3, reading its information and filling the buffer. (The heat sink has access to only half of this information but it has been taken care of by the redundancy detailed earlier). Once the information of all four neighbouring blocks collected, right after the last letter has been read, T 3 turns toward the center of the block, using the space left by the padding, performing one more square gadget. With a big enough transition table and a well chosen encoding, computing the next transition of T 1 can be performed in a square the size of the buffer and transition table encoded. As the only way to leave the center of the block is now a path of width 1, T 3 must transmit its computation before rejoining the edge of the block. It does so with a zigzag that follows along the the inside of the reading heat sink. This information is then retrieved by the writing process, with a heat sink intertwined with the reading one. The writing process writes on the edge of the block on the faces before the exit one and at distance 1 after. When following a square gadget, it copies the transition table and writes an empty buffer (which is possible because the square not only corners but copies information on all its sides), when following a reading gadget, it creates a heat sink gadget of its own, fetching the computed information and writing it on the face of the block. Lastly, once all the writing has been done, T 3 finishes filling its block by going back to the exit edge, following the writing path which had been shifted to the inside by 1 to allow for this, copying everything from the reading path to effectively write it on the edge making it attainable and finally T 3 exits the block at distance 2 from the corner.

The Power of Third Dimension and Liberal Simulations

Having a third dimension available allows for a lot more freedom to simulate a turedo. Let us first focus on TUR 3 (1) and rigorous simulations. In dimension Figure 7: One block of the presented 3D radius 1 turedo T ∈ U ≤R 3 [START_REF] Becker | Universality in freezing cellular automata[END_REF]. At this stage T comes from the block above, the front and left blocks are also nonempty and the others are empty. T will exit the block by entering the next block at its right. On the right is represented the disposition of information. The light blue cubes are information to read in adjacent blocks and the red ones are information written by T in the considered block. In this example, a letter of A ′ is encoded by 2 letters of A, the transition table is of arbitrary small size for readability and they are written in a cross on the faces of blocks. On the left is the behaviour of T in the same considered block, in blue is the reading phase (building also a skeleton), in orange the computation phase, in red the writing phase and in green the exit phase.

2 we had to use the heat sink trick to gather all required information and we used a radius of 3 to accommodate for a reading, a writing and an exiting layer. The third dimension allows us to shrink the radius to 1 thanks to its crossing capabilities. The trick to achieve this is to have a marker to indicate if the neighbouring block is empty or not, to prevent trying to read in spaces where the turedo will have to write later on.

Theorem 5. U ≤R

3 (1) ∩ TUR 3 (1) = ∅. Proof. We show that there is T ∈ TUR 3 (1), T = (A, Q, δ), such that for all T ′ ∈ TUR 3 (1): T ′ ≤ R T . Denote T ′ = (A ′ , Q ′ , δ ′ ). For a block B, the transmittable information is organised on the faces as follow. In the center of each faces, a marker is written, indicating that information is present. On the face of the block facing the next block (the exit face), added to the presence marker, is an empty cross of width 1 with only at its end a stop marker indicating the end the block. Surrounding it is a cross of width 3 in which is written the transition table and a buffer big enough to accommodate for the encoding of 6 letters of A ′ and one state from Q ′ (with the size of the transition table and the buffer plus 1 left before writing). On the face of the block facing other empty blocks, the same crossing pattern is used to only write the presence marker and the computed letter at distance 2 of the center of the face. See figure 7 for this organisation on an example.

T has the following behaviour in a block, also illustrated in figure 7. First, T performs a reading phase : entering a block by the middle of a face, it travels straight to the edge of the face until reading the stop marker. We assume T entering by the middle of the face as it truly enters at distance one of the middle but this shift of one position in one direction can be remembered and corrected immediately after entering. This allows T to turn and go back toward the center, reading the transition table and the buffer. All this information gathered, T follows a fixed path composed of shrinking zigzags, staying in the planes formed by the 3D cross centered in the block (hence the peculiar way we place information, to reserve space for this path). Doing so, it reaches the center of each face while carrying the transition table and filling the transition buffer when a presence marker is read. As the order in which the faces are visited is fixed, T can store in its head state which neighbouring blocks are empty. This reading phase has the added benefit to have created a skeleton in the block, enabling easy travel for the following phases. Next T enters the computing phase consisting of a square zigzag, using the transition table and the now filled buffer carried previously and so present in all the branches of the centered 3D cross. Once the next step of the simulation computed, T can carry the letter to encode following the skeleton and write it on all previously identified faces except the exit one. The last phase, the exit one, consists in carrying the encoded letter to the exit face, retrieve on the centered 3D cross the transition table and the buffer (reset with the new state and letter of the computed transition) and writing all this information as previously presented thanks to square and triangular zigzags. Finally T exits to the next block, at distance one of the center of the face (to get around the reading skeleton).

The combination of 3D and liberal simulations allows to shrink the radius of any turedo to 1. In this construction, the computation of simulated transitions is done internally in the simulating turedo's head. The challenging part however is in acquiring the states of distant neighbors. Thankfully the liberal nature of the simulation allows travel through empty blocks and the 3D enables crossing paths without intersection. Still, a rigorous organisation is needed in order to prevent overlapping. Theorem 6. For any radius r and any T r ∈ TUR 3 (r) there is T 1 ∈ TUR 3 (1) such that T r ≤ T 1 .

Proof. Let r ∈ N + and T r ∈ TUR 3 (r), T r = (A r , Q r , δ r ). We build T 1 = (A 1 , Q 1 , δ 1 ), with Q 1 big enough to encode in one state a position z ∈ Z 3 modulo 2r of each dimension and the |B 3 (r)| neighbouring letters. This allows for an instant computation of δ r once all needed information is gathered. Let b be the block size, the critical aspect of this simulation is for T 1 to visit all blocks b ⊗ z ′ with z ′ ∈ z + B 3 (r) for each simulation step. Therefore we have to assign non intersecting exploration paths for all positions at distance less than 2r. To achieve this, we define C = {0, ..., 8r 3 -1} a set of colors and we assign the color (z 1 mod 2r) + 2r(z 2 mod 2r) + 4r 2 (z 3 mod 2r) to the block b ⊗ (z 1 , z 2 , z 3 ). By taking b = 8r 3 l + 7 with l ∈ N + , in each block, for each color c ∈ C, we can reserve tubes of width l following the edges of a centered cube of edges of length lc + 1 and the direct extension of said edges to the face of the block (see figure 8b). This creates reserved spaces for each color consisting of centered nested cubes. Those cubes fill a space of 8r 3 l, we add 1 to have a proper center and 6 to have some padding near the faces of the blocks (we will discuss its necessity later). Note that l actually doesn't need to be large, l = 10 is enough. On each face of the block b ⊗ z, the letter a ∈ A r ⊂ A 1 is repeated in a cross pattern (see 8a). In red are the tubes of width l on the edges of the centered cube of edges of length lc + 1. In green are the extensions of said tubes, allowing to reach the reserved space for color c in the neighbouring blocks, completing the exploration path of color c (8b). Those extensions also allow the exploration path to access the blue cross containing the letter of position z in the configuration (to either read or write)(8c).

F Tr (c r , z r , q r ) is simulated as follow. Assuming T 1 knows the color c ∈ C of block b ⊗ z r (which is possible as its position in all directions modulo 2r is stored in its head state), we can define a reference starting position to explore the neighbouring blocks by ordering the directions of B 3 [START_REF] Becker | Universality in freezing cellular automata[END_REF]. Moreover, this ordering allows to decide a depth-first exploration of the blocks b ⊗ z ′ with z ′ ∈ B 3 (r) passing through each block at most seven times. Once the exploration done, back in block b ⊗ z, the head of T 1 contains all necessary information to compute δ r and all that remains to do is to write the computed letter in a cross pattern on the faces of the block. This is possible following a eulerian path, crossing only on the center of the faces, hence the padding of 2 defined earlier. The 1 padding left is for T 1 to align itself with its next color (which is possible since it knows its current color and has computed to in which block to go next).

By combining Theorem 5 and Theorem 6, we get the existence of an intrinsically universal 3D turedo for liberal simulations as expressed in the following corollary.

Corollary 1. U ≤

3 ∩ TUR 3 = ∅.

Discussion

The problem tackled in this work depends on three parameters (radius, dimension, simulation).

Our results give a rather clear picture of the simulation hierarchies in 3D, but we left several open question in the 2D case, in particular: is there a turedo in TUR 2 (2) which is universal for TUR 2 (1) under rigorous simulations? what if we allow liberal simulations? Actually even Theorem 2 raises questions: the simulation impossibility makes a crucial use of non-connected seeds, does this impossibility remain if we just ask simulation of orbits starting from connected seeds?

In this work we chose the square lattice in 2D (to simplify and as we also consider the 3D case) whereas oritatami are mostly considered on the hexagonal lattice. We don't expect any significant difference on the simulation hierarchy result by changing from square to hexagonal lattice on a given model (either turedos or oritatami). However, it is not clear that the delay hierarchy for oritatami behaves likes the radius hierarchy for turedos. In particular, we don't know if an analog of Theorem 4 holds for oritatami. The key difference between a large radius turedo and a large delay oritatami is that the turedo can gather information locally across obstacles, while the oritatami can only probe information around that can be reached by a path of empty positions (because it can only probe by trying to position a small strand of beads).

We end this paper by suggesting the following two directions in order to better understand the gap between turedos and oritatami systems: what if we restrict turedos to 'see' only neighboring positions that can be reached through a path of r empty positions? and what if we enrich oritatami systems by a more general 'magnetic' attraction law between beads where pairs of distant beads can still contribute to the total amount of attraction that the free strand at the end of the molecule is trying to maximize (let's say by a quadratic decrease with distance up to some radius)?

  d} and Z d can be tiled by translated copies of R b in a regular way by placing them on the sublattice b ⊗ Z d where ⊗ denotes the component-wise product. Each position z ∈ Z d can be uniquely decomposed into z = ρ b (z) + µ b (z) where ρ b (z) ∈ b ⊗ Z d is the reference point of a block and µ b (z) ∈ R b is an offset inside it.

Figure 1 :

 1 Figure1: Example of orbit of the spiral-XOR turedo (example 1) starting from a finite seed. Green represents 0, yellow represents 1 and white represents ⊥. The head holds a direction (where the black triangle is pointing to) and its self-avoiding trajectory since the beginning is drawn as a black path.

3 Figure 3 :

 33 Figure3: Example of a copy-and-move operation (on the left) and its rigorous simulation by a turedo of radius 1 with 3 × 3 block size (on the right). The color convention is as follows: in red the letters present in the seed, in dark yellow the initial position of the head, and in light yellow, the positions visited by the head during the orbit. The only position on the south side of the middle block that can depend on a is the lower right corner, marked with a X.

Figure 4 :

 4 Figure 4: Behavior of turedo T ′ on the seed σ( a, 2, a). The red and blue colors indicate letters present in the seed. The dark yellow color indicates the initial position of the head and light yellow cells represent the path of the head until the last step of the orbit. The orange cell correspond to the position of the head before moving left or right according to the result of the test .

Figure 5 :

 5 Figure 5: Orbit of turedo T 2 starting from a seed u of length n (in red) with the head initially in the position shown in dark yellow. The last part of the orbit is shown in orange.

  (a) The letter a ∈ Ar ⊂ A1 is repeated on all faces in a cross pattern. (b) Reserved space for the exploration path of color c ∈ C. (c) One face of a block.

Figure 8 :

 8 Figure 8: Representation of the reserved space for color c in block b ⊗ z.In red are the tubes of width l on the edges of the centered cube of edges of length lc + 1. In green are the extensions of said tubes, allowing to reach the reserved space for color c in the neighbouring blocks, completing the exploration path of color c (8b). Those extensions also allow the exploration path to access the blue cross containing the letter of position z in the configuration (to either read or write)(8c).

  Initial global state Global state after 10 stepsGlobal state after 307 steps