text:
# Multiple Components of the Luminous Compact X-ray Source at the Edge of Holmberg II observed by ASCA and ROSAT

## 1 Introduction

Off-nuclear (non-AGN) point-like luminous X-ray sources, which exceed the Eddington luminosity of a usual stellar-mass compact object like neutron stars and galactic binary blackholes ($`L_\mathrm{x}10^{39}`$ $`[\mathrm{erg}\mathrm{s}^1]`$) in nearby galaxies have been recognized in many galaxies (Fabbiano, 1989; Colbert & Mushotzky, 1999; Read, Ponman & Strickland, 1997). The luminosity distribution of these sources extends up to a few $`\times 10^{40}`$ $`[\mathrm{erg}\mathrm{s}^1]`$. The most luminous one has been found in the nuclear region of the starburst galaxy M82 (catalog ) (Ptak & Griffiths, 1999; Matsumoto & Tsuru, 1999) reaching $`10^{41}`$ $`[\mathrm{erg}\mathrm{s}^1]`$. The location of this source was recently verified to be offset from the dynamical center of the galaxy by Chandra (Matsumoto et al., 2001).

One interpretation of these X-ray sources is an accretion onto intermediate-mass blackholes of $`10^{23}`$ $`M_{\mathrm{}}`$, while there are other possibilities including beaming, super-Eddington accretion, and a young supernova remnant in a dense interstellar medium. Probably they do not form a single class of X-ray sources. The spectra of many of these sources can be described by a multicolor disk blackbody model with or without additional hard tail (Makishima et al., 2000; Colbert & Mushotzky, 1999). The inner disk temperatures of the sources studied by Makishima et al. (2000) are $`kT1.11.8`$ \[keV\]. Since these temperatures are higher than that from an intermediate ($`10^2M_{\mathrm{}}`$) blackhole accretion, they proposed a picture of a spinning (Kerr) blackhole with a much smaller inner-disk radius than that of a non-spinning (Schwarzschild) one.

The luminous X-ray source in the star-forming dwarf galaxy Holmberg II (UGC 4305) is particularly peculiar among these cases in terms of the nature of the host galaxy and the location of the X-ray source. The galaxy is nearby at a distance of 3.05 Mpc, which was derived from Cepheid observations (Hoessel, Saha & Danielson, 1998). It is a dwarf irregular galaxy in the M81 Group with an on-going star-formation activity. Like in other galaxies of this class, numerous HII regions are scattered throughout the galaxy (Hodge et al., 1994). The bright X-ray source, which has been cataloged in the ROSAT Bright Survey (RBS) (Schwope et al., 2000), is one of the most luminous X-ray source seen in dwarf galaxies ($`L_\mathrm{x}10^{40}`$ $`[\mathrm{erg}\mathrm{s}^1]`$).

It was observed three times with ROSAT PSPC as pointed observations and once with HRI. Zezas et al. (1999) (hereafter ZGW) studied the ROSAT data on this X-ray source. Their main conclusions were: 1) The X-ray source seems point-like and located near the edge of the galaxy. Its position is consistent with one of the compact HII region complexes of the galaxy considering an uncertainty of $`6`$ arcseconds for the ROSAT absolute astrometry from its star tracker. A chance spatial co-incidence of this HII-region to an unrelated X-ray source of this brightness is highly unlikely ($`\mathrm{3\hspace{0.33em}10}^6`$). 2) The source is time variable on scales of days and years. 3) The spectrum is soft and can be fitted with a steep power-law ($`\mathrm{\Gamma }2.7`$) or a thermal plasma (Raymond-Smith) of $`kT0.8`$ keV. Time variability suggests an accretion onto a compact object, but the luminosity is 2-4 orders of magnitude larger than typical X-ray binaries.

There is a radio-knot which is co-spatial with the HII-region in the X-ray source region. It is one of the three showing radio spectra suggestive of a non-thermal emission (Tongue & Westpfahl, 1995), suggesting a recent supernova or multiple supernovae. However, currently there is no indication of a special character in the optical-radio data in this particular HII-region which is presumably associated with the compact X-ray source compared with other knots in the galaxy.

As a part of our study of a sample of apparent non-AGN galaxies which have compact luminous X-ray sources, selected from the RBS, we have made further X-ray studies of Holmberg II. In particular, we have obtained a 20 \[ks\] ASCA observation of this X-ray source in order to search for the hard X-ray signature of an AGN-like activity. In this paper, we report the results from our data analysis of our ASCA observation and of the ROSAT data from archives.

The scope of the paper is as follows. In Sect. 2, we summarize the ASCA and ROSAT observations and data used in our analysis. In Sect. 3 we report our new spectral analysis of the X-ray source by a joint ASCA-ROSAT PSPC analysis. In Sect. 4, we searched for an extension by applying a wobble-correction to the ROSAT HRI data. Long and short-term X-ray light curves are examined in Sect. 5. Finally the results are discussed in Sect. 6.

## 2 Observations

Holmberg II was observed with ROSAT five times. Firstly, it was bright in the ROSAT All-Sky Survey (RASS) (Voges et al., 1999) and cataloged in the RBS Schwope et al. (2000). It was observed three times with ROSAT PSPC pointed observations in 1992-1993 for 3.7-11 \[ks\] each. Also it was observed with ROSAT HRI for 7.8 \[ks\]. The ROSAT pointed data have been retrieved from the High Energy Astrophysics Archival Research Center (HEASARC) located at NASA Goddard Space Flight Center.

The ASCA observation of Holmberg II has been made with a pointing at the X-ray source in 1999 as one of the accepted targets from our proposal in the ASCA EAO-6 (AO-7) program (PI=Lehmann). The brightness of the source is such that we can use the SIS FAINT mode for both the medium and high bit rates with the 1-CCD mode. Thus we chose to use the 1-CCD/FAINT modes throughout. For the subsequent analysis, we use the BRIGHT2 mode data converted from the FAINT mode. For GIS, we have used the PH mode as usual. The log of ROSAT and ASCA pointed observations is shown in Table 1.

## 3 X-ray Spectral Analysis using ASCA - ROSAT PSPC

### 3.1 Extracting ASCA and ROSAT spectra

Extraction and preparation of spectra and response matrices have been made using tools included in FTOOLS 5.0 and subsequent spectral fittings have been made using XSPEC 11.

The source spectra have been extracted from event files which have been screened using the standard screening criteria. The source-spectrum extraction radii were 6 and 3 arcminutes for the GIS and SIS respectively. The background spectra have been extracted from off-source areas from the same detector, excluding 7.5 and and 3.7 arcminutes from the X-ray source for the GIS and SIS data respectively. The background subtraction have been made by scaling the background spectra by the areas of extraction, as automatically made by XSPEC. Because of the brightness of the source, the analysis is little affected by the uncertainties related to background scalings. The two GIS and two SIS spectra are co-added respectively. The background spectra and response files have been generated respectively for the summed GIS 2+3 and SIS 0+1 spectra.

The ROSAT PSPC spectra have been extracted using an extraction radius of 1 arcminute. Background spectra have been extracted from an annular region around the source, between 1.25 and 3.75 arcminutes. One spectrum has been made for each of the three PSPC pointed observation (Table 1). We see no evidence of a spectral change among these three datasets (see below). Thus the three spectra for these three sequences have been co-added for the joint analysis with the ASCA data.

The ASCA and ROSAT spectra have been re-binned such that each bin contains at least 25 counts in order to utilize the $`\chi ^2`$ statistics during the spectral analysis. The source was bright enough for this re-binning process without sacrificing the resolution.

### 3.2 Spectral Analysis

The channel energy ranges used for the analysis are 0.15-2 keV, 0.6-10 keV, and 1.0-7 keV for the ROSAT PSPC, ASCA GIS, and ASCA SIS, respectively. Because of the calibration uncertainties related to the radiation damage, we have ignored ASCA SIS channels below 1 keV.

Firstly, we have verified the basic fitting results of ZGW with joint fits to the three PSPC spectra, where all model parameters are joined except for the global normalization. As observed by ZGW, slight variations of the global normalization have been observed. This is discussed in Sect. 5. When all parameters are separately fit for the three datasets, the best fit parameters are always consistent with the joint ones within errors. This warrants that we can use the summed spectra for PSPC for further analysis.

Next we have made a spectral analysis of ASCA only (GIS & SIS). We have tried to fit the spectra with three models: (A1) a single power-law, (A2) a thermal plasma using the XSPEC mekal model, and (A3) a disk blackbody (Mitsuda et al., 1984) (XSPEC model diskbb), where “A” stands for ASCA. The best-fit parameters are shown in Table 2 and fit residuals are shown in Fig. 1. The single power-law of photon index $`\mathrm{\Gamma }1.9`$ gave the best fit without inclusion of any absorption. The photon indices for separate fits to the gave $`\mathrm{\Gamma }=1.85\pm 0.07`$ and $`1.87\pm 0.07`$ for GIS and SIS, respectively ($`N_\mathrm{H}`$ fixed to 0). The agreement verifies the goodness of our background subtraction. The 90% upper-limit to the column density of the absorbing gas was $`N_\mathrm{H}\mathrm{1.3\hspace{0.33em}10}^{21}`$ $`[cm^2]`$. The thermal plasma model with $`kT5`$ \[keV\] also gave a good fit with $`\chi ^2/\nu =0.84`$. We have obtained a heavy element abundance of $`Z=0.2\pm 0.2Z_{\mathrm{}}`$, which is marginally consistent with the O/H ratio of $`0.4`$ (relative to solar) for this galaxy (Hunter & Gallagher, 1985). However note that the metallicity of the source of X-ray emission does not necessarily be equal to that of some average for the HII regions scattered throughout the galaxy and that the hard X-ray mainly measures the iron abundance, which does not necessarily match with that of oxygen.

The multicolor disk blackbody model failed to fit the ASCA data as shown in Fig. 1(c). Thus the disk-blackbody component does not dominate the hard X-ray emission observed by our ASCA observation, unlike the cases of, e.g., IC 342 (catalog ) source 1 and NGC 1313 (catalog ) source B studied by Makishima et al. (2000). The power-law index of the ASCA spectrum is much harder than that of ROSAT PSPC spectrum ($`\mathrm{\Gamma }2.7`$; ZGW), which has response in $`E2`$ keV.

Finally, we have made a joint spectral analysis using all the ROSAT PSPC and ASCA GIS/SIS data. We have summed all the three PSPC spectra for the joint spectral fits. We have joined all the model parameters except for the global normalization as before. Because the ROSAT spectrum, covering a lower energy range, is much softer than that of ASCA, we have tried models with hard power-law ($`\mathrm{\Gamma }1.9`$) with some soft excess and an absorbing column. Adding a softer power-law component did not give a satisfactory fit. As the soft component, we have tried the thermal plasma and disk blackbody models. As shown in Table 2, both “Power-law+Thermal” (J1) and “Power-law+Disk blackbody” (J2) models gave reasonable fits. Note that the abundance of the thermal plasma have been fixed to 0.4 (see above) for J1. When this was a free parameter, the fit could not constrain it. In both J1 and J2, the absorbing column was $`N_\mathrm{H}0.7\mathrm{1\hspace{0.33em}10}^{21}`$ $`[\mathrm{cm}^2]`$, which exceeds the galactic value implied by the 21cm data of $`N_\mathrm{H}\mathrm{3\hspace{0.33em}10}^{20}`$ (Dicky & Lockman, 1990), indicating an absorbing component within Holmberg II. The soft excess component, which can either be described as a $`kT0.3`$ \[keV\] thermal plasma or a $`kT_{\mathrm{in}}0.2`$ \[keV\] disk blackbody spectrum, has 20-30% of the total 0.5-2 keV total luminosity. The ROSAT and ASCA spectra are shown with folded models and residuals in Fig. 2 for J1. The total luminosity of the X-ray source is $`\mathrm{1.0\hspace{0.33em}10}^{40}`$ $`[\mathrm{erg}\mathrm{s}^1]`$ in the 0.1-10 keV after correcting for absorption (GIS normalization). This corresponds to an Eddington luminosity of $`80[M_{\mathrm{}}]`$.

For the fit J2, the GIS normalization of the disk blackbody component gives $`r_{\mathrm{in}}\sqrt{\mathrm{cos}\theta }=35007500`$ $`[km]`$, where $`r_{\mathrm{in}}`$ is the inner disk radius, $`\theta `$ is the viewing angle and the 90% confidence error was searched for by allowing all other variable parameters to vary. Assuming $`r_{\mathrm{in}}=3R_\mathrm{S}`$, where $`R_\mathrm{S}`$ is the Schwarzschild radius, this corresponds to a blackhole mass of 10-25 $`(\mathrm{cos}\theta )^{0.5}[M_{\mathrm{}}]`$, while Colbert & Mushotzky (1999) pointed out that the $`r_{\mathrm{in}}`$ estimation based on the disk blackbody within XSPEC is likely to be underestimated. Further discussion is made in Sect. 6

We have also tried a two-thermal plasma model fit (J3), where the relative abundances of two thermal plasma have been fixed to equal. This model gave an acceptable fit but with a hard thermal component (Thermalh) with $`kT_\mathrm{h}6`$ \[keV\] and a soft thermal component (Thermals) with $`kT_\mathrm{s}0.3`$ \[keV\]. In this case, the fitted abundance was very low $`Z=0.02_{.01}^{+.03}`$. We did not find a satisfactory fit for the model where the hard component is a thermal plasma and the soft component is a power-law.

One caveat on our joint fitting analysis is a possible cross-calibration problem. Iwasawa, Fabian & Nandra (1999) found that the ROSAT PSPC spectrum is much softer than that of ASCA SIS for the simultaneous observations of NGC 5548 ($`\mathrm{\Gamma }=2.35`$ for ROSAT PSPC versus $`\mathrm{\Gamma }=1.95`$ for ASCA SIS). This might have been partially be caused by the soft excess combined with the spectral resolution of PSPC or there may be real cross-calibration problems. The origin of this discrepancy is inconclusive. In our case, the difference of $`\mathrm{\Delta }\mathrm{\Gamma }0.7`$ between the ROSAT PSPC and ASCA GIS spectra is much larger than that Iwasawa, Fabian & Nandra (1999) observed for a similar ASCA index. Thus there certainly is a soft component over the extrapolation of the hard power-law even in case the discrepancy observed by Iwasawa, Fabian & Nandra (1999) was solely caused by calibration problems.

## 4 ROSAT HRI Wobble-Correction and Spatial Extension

There are wobble-phase dependent systematic errors with the aspect solution for the ROSAT, which could lead to a detection of spurious extended component in the HRI data (Harris et al., 1998; Morse, 1994). This has lead to ZGW make a conservative conclusion that they had detected no extension in the HRI image. We have applied a correction for this effect by creating images in 10 wobble-phases, centering each of these images independently, and re-constructing the image using the centering information Lehmann et al. (1999). The original and corrected HRI images are shown in Fig. 3. The faint knot seen in the NW in the original HRI image has disappeared in the corrected image. This reconstruction worked very well down to an HRI count rate of $`0.1`$ \[cts s-1\] for a large number of stars, but can be even used for fainter sources (Crawford et al., 1999).

The radial profile of the wobble-corrected HRI image has been compared with the theoretical HRI PSF from David et al (1995) and the re-calibrated HRI PSF in Fig. 4. The re-calibrated HRI PSF was derived from wobble-corrected HRI images of 21 stars from the RBS Schwope et al. (2000). The re-calibrate HRI PSF shows a slightly deviation from the theoretical PSF in the radial range between 10 and 30 arcseconds. The comparison of the radial profile with both PSF’s indicates an extended component. Subtracting the re-calibrated PSF, $`27\pm 5`$% (1$`\sigma `$ error) of the X-ray emission is in the extended component and most of the excess comes from a radius of $`10\mathrm{}`$, corresponding to $`150`$ \[pc\].

## 5 Variability

The ASCA GIS flux in the 0.5-2 keV band calculated using the spectral model J1 have been compared with the previous ROSAT observations. Because ASCA GIS is sensitive only above 0.6 keV, while ROSAT HRI has no spectral resolution and sensitive in 0.2-2 keV, we have made separate long-term light curves for the 0.2-2 and 0.5-2 keV bands. These are shown in Fig. 5. The fluxes from ROSAT are slightly different from Fig. 3. of ZGW probably because of the difference in spectral models. As seen in Fig. 5, there is a 30% decrease in flux between the first (April 1992) and third (March 1993) PSPC pointed observations and a factor of $`2`$ increase towards the HRI observation (Oct, 1994). The source brightness came back to a flux close to the PSPC observation during the ASCA observation in 1999. This does not necessarily mean that the source is variable at a time scale of “years”, rather it means that there is a variability at a timescale longer than the elapsed time of a single observation ($`10^510^6`$\[s\]).

We also searched for evidence of time variability in the ASCA data. First, we have defined the combined Good Time Intervals (GTI), which consist of the intersection of GTI’s from all the SIS and GIS detectors. We have used channels corresponding to 0.6-10 keV for the GIS’s and 0.7-7 keV for the SIS’s respectively. For each detector, binned source and background light curves have been extracted using a 1024 second binsize. The extraction regions are the same as those of the spectral analysis. For each time bin, only the interval overlapped with the combined GTI have been used to calculate the countrate. The background-subtracted light curves have been co-added to make the final light curve. There is no significant correlation between the background-subtracted source light curve and the background light curve. This also warrants goodness of the background subtraction.

The resulting light curve is shown with the best $`\chi ^2`$-fit constant value in Fig. 6. No point is more than 2$`\sigma `$ away from the constant value and $`\chi ^2/\nu =22.2/26`$. Thus there is no evidence for variability at time scales between $`10^3`$ and $`10^4`$ seconds in the ASCA data. Separate light curves for the hard ($`E2`$ \[keV\]) and soft ($`E<2`$ \[keV\]) bands did not show any sign of variability either. This is in contrast to the ROSAT light curves reported by ZGW, which show a convincing case of gradual decrease of flux by a factor of $`3`$ over $`2\times 10^5`$ seconds during the second pointed PSPC observation and less convincing indications of shorter timescale variabilities.

## 6 Discussion

Our analysis suggests at least two-components of the X-ray emission. An extended and a point-like component have been revealed by the spatial analysis. The variability also provides evidence for at least a compact component. The joint ASCA/ROSAT spectral analysis suggests a non-thermal power-law component plus a warm thermal component or a moderately low temperature disk blackbody component. The overall spectrum can also be described as a superposition of two thermal components with a very low metallicity. However, the variability observed in this object argues against total thermal origin of the X-ray source.

The X-ray source at the edge of Holmberg II shows unusual characters, even given the large number of off-nuclear X-ray sources in nearby galaxies at similar luminosities. While most of the X-ray sources studied by Colbert & Mushotzky (1999) reside in the nuclear region, this is at the very edge of a dwarf galaxy. Unlike a number of off-nuclear sources studied by Makishima et al. (2000), hard X-ray emission is not dominated by a disk blackbody component with $`kT_{\mathrm{in}}1`$ \[keV\]. If the soft excess component comes from a disk blackbody emission, the implied blackhole mass from the normalization of this component is 10-25 $`(\mathrm{cos}\theta )^{0.5}[M_{\mathrm{}}]`$ assuming a Schwarzschild blackhole (see Sect. 3). However, estimating the mass from the temperature $`kT_{\mathrm{in}}0.2`$ \[keV\] using Eq. (12) of Makishima et al. (2000), we obtain $`10^4`$ $`[M_{\mathrm{}}]`$. This large discrepancy argues against the disk-blackbody interpretation of the soft excess, even though we consider the underestimation of the mass pointed out by Colbert & Mushotzky (1999), nearly edge on viewing angle, and spinning of the blackhole.

One of the most surprising results from our analysis is that these two (or more) bright X-ray components co-exist in a compact region in one of the numerous HII regions and no other X-ray source with a comparable brightness exists in other part of the galaxy. All other X-ray sources scattered throughout the galaxy, which are either supernova remnants or X-ray binaries, have luminosities of $`L_\mathrm{x}10^{37}`$ $`[\mathrm{erg}\mathrm{s}^1\mathrm{cm}^2]`$ (Kerp & Walter, 2000). Thus it is unlikely that the two (or more) components have independent origins. The possible explanations of this X-ray source with observed multiple components are:

A supernova remnant (SNR) or a composite of SNRs (the $`kT`$ 0.3 \[keV\] extended thermal component) feeds an intermediate mass blackhole with gas.

An accretion onto a stellar-mass compact object, e.g., similar to galactic blackhole X-ray binaries, beaming towards our line of sight, is embedded in an SNR or a composite of SNRs.

The non-thermal power-law and the soft excess components (possibly blackbody emission from the accretion disk around an intermediate-mass blackhole) come from the same compact region while the extended component is caused by scattering/reflection of the central source.

The flat radio spectrum (Tongue & Westpfahl, 1995) in the region of this X-ray source shows an existence of a supernova remnant or a composite of supernova remnants. This supports the possibilities (a) or (b). However, the extended component is too luminous for thermal emission from a single (or a few) supernova remnant(s) (SNR), considering its size of $`200`$ pc and its 0.5-2 keV luminosity of a few $`\times 10^{39}`$ $`[\mathrm{erg}\mathrm{s}^1]`$. A single SNR can only be at this luminosity when it is very young ($`10^2`$ years) (Schlegel, 1994; Schlegel et al., 1999) and thus it cannot have grown into this scale size nor can feed the intermediate-mass blackhole located 200 \[pc\] away. Thus more than a few supernova remnants are needed to make the extended structure, which also feeds the blackhole causing the variable, non-thermal emission. From our current data, we are not able to distinguish whether the central source represents an accretion onto an intermediate-mass blackhole or a stellar mass compact object (e.g. X-ray binaries) with beaming towards our line of sight.

The possibility (c) is not likely for the following reasons. The possibility that electron-scattering by surrounding diffuse gas is the origin of the extended emission has the following difficulty. Scattering gas with a column density of $`N_\mathrm{H}10^{23}10^{24}`$ $`[\mathrm{cm}^2]`$ is required to account for the $`30\%`$ extended component. The gas would cause heavy photoelectric absorption unless the scattering diffuse gas is highly ionized (Wilson et al., 1992; Elvis et al., 1990). If the gas was thermally ionized, the temperature of the gas must be greater than a few million degrees \[K\] in order that the absorption features due to a column density of $`N_\mathrm{H}=10^{23}`$ $`[\mathrm{cm}^2]`$ is not visible in the ASCA spectrum. For demonstration, we assume a uniform sphere of gas of 200 \[pc\] in radius filled with hot ionized gas with a column density of $`N_\mathrm{H}=10^{23}`$ $`[\mathrm{cm}^2]`$ from the central source. Such a sphere of thermal gas would produce X-ray emission which is several orders of magnitude larger than observed. Photoionization also cannot be a valid explanation, because the lower limit of the ionization parameter required to be consistent with the ASCA spectrum also requires several orders of magnitude larger luminosity for the ionizing source. We also consider a picture where the surfaces of optically-thick molecular clouds scattered throughout the region (giant molecular clouds where star forming activities are embedded) reflect the radiation from the central source, while our line of sight to the central source is not blocked by any of them. This picture also has a similar difficulty. In order to attain sufficient reflectivity in the ROSAT band ($`E2`$) \[keV\], the surface of the clouds have to be highly ionized. Using the XSPEC model “pexriv” (Magdziarz & Zdziarski, 1995), we estimate that an ionization parameter of $`\xi L/(nR^2)>`$ a few hundred $`[\mathrm{erg}\mathrm{cm}\mathrm{s}^1]`$ is required to have the reflectivity of more than 20-30% in this band. For a central ionizing source luminosity of $`L`$ a few $`\times 10^{40}`$ $`[ergs^1]`$, at a distance of $`R=200`$ \[pc\], this ionization parameter corresponds to a gas density at the surfaces of the clouds of $`n10^3`$ $`[\mathrm{cm}^3]`$. This is much lower than that of a usual interstellar medium and scattered clouds of this density cannot be optically thick.

If the intermediate-mass blackhole picture of this X-ray source is the case, there is a question of its formation. Taniguchi et al. (2000) discussed possible origins of the off-nucleus “intermediate-mass” blackholes presumably responsible for off-nuclear luminous X-ray sources and their preferred model was multiple mergings of stellar remnants (stellar-mass blackholes and neutron stars). Matsushita et al. (2000) found a molecular superbubble in the vicinity of a similar off-nuclear X-ray source in M82, suggesting that an intensive star formation is connected to the formation of an intermediate-mass blackhole. This may be the case for the compact component of the X-ray source discussed here because of the intense star-forming activity in the region. However, the question remains as to why there is only one such X-ray source in this galaxy and not at the locations of other numerous HII regions. Probably the X-ray emission is a short-lived phenomenon, where an intermediate mass blackhole (similar things may exist in many star-forming regions) is fed by the passing of a shell of dense gas induced by multiple supernova explosions.

Chandra (scheduled as a GT target by Murray) and XMM-Newton (GT target by Watson) observations of this source will certainly improve our knowledge of this peculiar X-ray source. The Chandra observation can make spatially resolved X-ray spectroscopy and reveal whether the non-thermal component corresponds to the point-source and thermal to the extended component or it has a more complicated structure. The XMM-Newton observation would give a better spectral information with a much better statistics and much less cross-calibration uncertainties in the $`E1`$ keV region, where multiple components are apparent. It will also give variability information at short timescales.

## 7 Conclusions

We summarize the main conclusions of our analysis:

1. New ASCA and archival ROSAT data of the X-ray source in Holmberg II have been analyzed.
2. The combined ASCA and ROSAT spectrum shows can be described as a $`\mathrm{\Gamma }2`$ power-law and a soft excess which can either be described as a $`kT0.3`$ \[keV\] thermal plasma or $`kT_{\mathrm{in}}0.2`$ disk blackbody. We argue against the disk blackbody interpretation of the soft excess component based on the inconsistency between the luminosity and the temperature.
3. The wobble-corrected ROSAT HRI image indicates $`25\%`$ of the X-ray emission is extended at a scale of $``$10$`\mathrm{}`$ ($``$25%). Variability in the ROSAT data shows that the point-like component probably comes from accretion onto a compact object.
4. It is remarkable that this multiple-component X-ray source is the only one with a similar strength among the numerous HII regions in the galaxy with a similar nature. It is natural to suppose that these two components are related.
5. Possible explanations of the nature of the X-ray source include multiple supernova remnants (extended component) feeding the accretion onto an intermediate-mass blackhole. We cannot, however, exclude the possibility that the central source is a beamed radiation from an accretion onto a stellar mass (usual X-ray binaries) object. We argue against a picture where electron scattering or reflection by scattered optically-thick clouds of the central source makes the extended X-ray emission.

This research have made use of data and software obtained from the High Energy Astrophysics Archival Research Center (HEASARC) located at NASA Goddard Space Flight Center. The authors appreciate the effort of ASCA and ROSAT teams for having created and operated these superb observatories. The authors thank the referee, Hironori Matsumoto for his careful review and useful comments.


format: text

text:
# Number conserving cellular automata: from decidability to dynamics

## 1 Introduction

Cellular automata are widely known as formal models for complex systems ruled by local interactions . Despite of their apparent simplicity they display a richness of behaviors most of which are not yet fully understood. The classification of these behaviors has a main obstacle: most of the interesting properties about them are undecidable . Moreover, some other properties are “dimension sensitive”; for example, surjectivity is decidable in polynomial time for one-dimensional CA and undecidable for dimension $`2`$ .

We prove that *number-conservation*, a widely used property, can be decided in linear time (in the size of the CA) in *any* dimension. More precisely, it has linear time complexity if we assume that the access to the transition table costs constant time, independently of the dimension of the space. Otherwise the complexity is $`𝒪(s\mathrm{log}s)`$, where $`s`$ is the size of the transition table. A preliminary work had been carried out for one-dimensional CA on circular configurations (periodic boundary conditions) by Boccara et al. in . The decision problem in higher dimensions and general boundary conditions that we solved in the present paper is rather surprising and could not be expected from earlier works.

CA that satisfy number-conservation property are called number-conserving (NCA); roughly speaking they conserve the number of bits during their evolution. This class of CA has been introduced by  and is receiving a growing interest in Physics as a source for models of particles systems ruled by conservations laws of mass or energy.

Great attention has received the application of NCA to practical situations such as highway traffic flows. In this context different definitions of “number-conservation” were given according to the type of boundary conditions assumed (periodic, finite, infinite) . In Section 2 we prove that all of them are equivalent. We also give another equivalent definition in terms of densities. Section 3 is devoted to the proof of our main result: the linear time decision algorithm. In the second part of the paper we study NCA dynamics with focus on chaotic behavior. Number-conservation imposes strong “simplifications” in the dynamics allowing (in most cases) clear-cut situations that are not observed in the general case.

We stress that the class of NCA is not only big enough to give reliable models for car traffic and similar models allowing the study of traffic jams, critical traffic masses, crossing-roads, car accidents etc. But also they are interesting from a pure computer science point of view. For instance Morita et al. have given a reversible two-dimensional NCA capable of universal computation .

## 2 Definitions

We present in this section several definitions of number-conserving cellular automata that we prove to be equivalent. Proofs are given in a one-dimensional space but can be generalized to any dimension.

Cellular automata are formally defined as quadruples $`(d,S,`$ $`N,f)`$. The integer $`d`$ is the *dimension* of the space the cellular automaton will work on. $`S=\{0,1,\mathrm{},s\}`$ is called the set of *states*. The *neighborhood* $`N=(x_1,\mathrm{}x_v)`$ is a $`v`$-tuple of distinct vectors of $`^d`$. The $`x_i`$’s are the relative positions of the neighbor cells with respect to the cell, the new state of which is being computed. The states of these neighbors are used to compute the new state of the center cell. The *local function* of the cellular automaton $`f:S^vS`$ gives the local transition rule.

A *configuration* is an application from $`^d`$ to $`S`$. The set of configurations is $`S^^d`$ on which the *global function* $`A`$ of the cellular automaton is defined via $`f`$:

$$cS^^d,i^d,A(c)(i)=f(c(i+x_1),\mathrm{},c(i+x_v)).$$

We denote by $`𝒞_P`$ the set of (spatial) *periodic configurations,* (*i.e.,* configurations that are periodic in all dimensions of the space). We denote by $`\pi (c)`$ the period of a periodic configuration (*i.e.,* a vector.) The expression $`0k\pi (c)`$, $`k^d`$ means $`1id,0k_i\pi (c)_i`$ where $`d`$ is the dimension of the space and $`k_i`$ is the $`i`$-th component of $`k`$.

###### Definition 1

Let $`A`$ be a $`d`$-dimensional cellular automaton. $`A`$ is said to be *periodic-number-conserving (PNC)* iff

$$c𝒞_P,\underset{0k\pi (c)}{}c(k)=\underset{0k\pi (c)}{}A(c)(k).$$

We denote by $`𝒞_F`$ the set of *finite configurations,* (*i.e.,* those configurations that are almost everywhere equal to zero — non-zero in a finite number of cells).

###### Definition 2

Let $`A`$ be a $`d`$-dimensional cellular automaton. $`A`$ is said to be *finite-number-conserving (FNC)* iff

$$c𝒞_F,\underset{i^d}{}c(i)=\underset{i^d}{}A(c)(i).$$

We denote by $`𝒞`$ the set of *all configurations.*

###### Definition 3

Let $`A`$ be a $`d`$-dimensional cellular automaton. A *window* is a hypercube of $`^d`$ centered in $`\mathrm{𝟎}`$ thus determined by its size. Consider the sequence of windows $`\{F_n\}`$ of size $`2n+1`$ and denote by $`\mu _n(c)`$ the sum of states in $`F_n`$ of a configuration $`c𝒞`$. $`A`$ is said to be *number-conserving (NC)* iff

$$c𝒞,\underset{n\mathrm{}}{lim}\frac{\mu _n(c)}{\mu _n(A(c))}=1.$$

Remark that all these definitions imply that $`f(0,0,\mathrm{},0)=0`$, *i.e.,* $`0`$ is a *quiescent* state. The configuration with all quiescent states is denoted $`uz`$.

We are going to prove that all previous definitions are equivalent. The proof is given in dimension 1; the generalization to higher dimensions is straightforward.

###### Proposition 1

A cellular automaton $`A`$ is FNC if and only if it is PNC.

* Proof. We first prove that if $`A`$ is PNC then it is FNC. We show that if $`A`$ is not FNC then it is not PNC either.

Let $`A`$ be not FNC, then

$$\stackrel{~}{c}𝒞_F,\alpha ,\beta ,\alpha =\underset{i}{}\stackrel{~}{c}(i)\underset{i}{}A(\stackrel{~}{c})(i)=\beta .$$

Let $`k`$ be the length of the non-zero part of $`\stackrel{~}{c}`$ and $`l`$ the radius of the neighborhood of $`A`$. Then, the length of the non-zero part of $`A(\stackrel{~}{c})`$ is at most $`k+2l`$ (see Figure 1).

Let $`\widehat{c}`$ be the periodic configuration constructed from $`\stackrel{~}{c}`$ in the following way. We add $`l`$ zeros at both sides of the non-zero part of $`\stackrel{~}{c}`$ and we construct a periodic configuration with the segment obtained (such a configuration has a period $`p=k+2l`$, see Figure 1).

We have

$$\underset{0ip}{}\widehat{c}(i)=\alpha \beta =\underset{0ip}{}A(\widehat{c})(i),$$

hence $`A`$ is not PNC.

We now prove that if $`A`$ is FNC then it is PNC. We show that if $`A`$ is not PNC then it is not FNC either.

Let $`l`$ be the radius of the neighborhood. As $`A`$ is not PNC,

$$p,\alpha ,\beta ,\widehat{c}𝒞_P,\underset{0ip}{}\widehat{c}(i)=\alpha \beta =\underset{0ip}{}A(\widehat{c})(i),$$

where $`p`$ is the period of $`\widehat{c}`$.

We denote by

$`\widehat{c}_p`$ the $`p`$-length segment of $`\widehat{c}`$ centered at the origin;

$`\widehat{c}_{p\text{Suffix}_l}`$ the $`l`$-length suffix of $`\widehat{c}_p`$;

$`\widehat{c}_{p\text{Prefix}_l}`$ the $`l`$-length prefix of $`\widehat{c}_p`$.

We construct a finite configuration $`\stackrel{~}{c}𝒞_{F_A}`$ as shown in Figure 2: we repeat $`\widehat{c}_p`$ $`x`$ times and we complete the segment obtained in this way with $`\widehat{c}_{p\text{Prefix}_l}`$ at the right-hand-side and with $`\widehat{c}_{p\text{Suffix}_l}`$ at the left-hand-side of the segment.

Then,

$$\underset{i}{}\stackrel{~}{c}(i)=\underset{x\alpha }{\underset{}{x\underset{i=1}{\overset{p}{}}\widehat{c}_p(i)}}+\underset{ls}{\underset{}{\underset{i=1}{\overset{l}{}}\widehat{c}_{p\text{Prefix}_l}(i)}}+\underset{ls}{\underset{}{\underset{i=1}{\overset{l}{}}\widehat{c}_{p\text{Suffix}_l}(i)}}$$

and

$`{\displaystyle \underset{i}{}}A(\stackrel{~}{c})(i)`$ $`=`$ $`\underset{x\beta }{\underset{}{x{\displaystyle \underset{i=1}{\overset{p}{}}}A(\widehat{c}_p)(i)}}+\underset{2ls}{\underset{}{{\displaystyle \underset{i=1}{\overset{l}{}}}A(\widehat{c}_{p\text{Prefix}_l})(i)}}+\underset{2ls}{\underset{}{{\displaystyle \underset{i=1}{\overset{l}{}}}A(\widehat{c}_{p\text{Suffix}_l})(i)}}.`$
We obtain the following inequalities:

$$x\alpha \underset{i}{}\stackrel{~}{c}(i)x\alpha +2ls\text{ and }$$

$$x\beta \underset{i}{}A(\stackrel{~}{c})(i)x\beta +4ls.$$

Suppose that $`\alpha <\beta `$. If we choose an integer $`x`$ such that $`x>\frac{2ls}{\beta \alpha }`$, we are in a contradiction with the previous inequalities.

Similarly, if $`\alpha >\beta `$ then the contradiction is obtained by choosing $`x>\frac{4ls}{\alpha \beta }`$.

Hence, if $`A`$ is not PNC, it is not FNC either. $`\mathrm{}`$

###### Proposition 2

A cellular automaton $`A`$ is NC if and only if it is FNC.

* Proof. We first show that if $`A`$ is not FNC then it is not NC either. Let $`A`$ be a cellular automaton with a neighborhood of radius $`l`$. If $`A`$ is not FNC then there exist an integer $`\gamma `$ and a configuration $`c`$ in $`𝒞_F`$ such that

$$\underset{i}{}c(i)=\underset{i=\gamma }{\overset{\gamma }{}}c(i)\underset{i=\gamma l}{\overset{\gamma +l}{}}A(c)(i)=\underset{i}{}A(c)(i).$$

Let $`\{F_n\}`$ be a sequence of windows of size tending to the infinity, centered on the non-quiescent part of $`c`$. As the non-quiescent part of $`c`$ is finite, there exists $`k`$ such that, for all $`nk`$,

$$\mu _n(c)=\underset{i=\gamma }{\overset{\gamma }{}}c(i)\underset{i=\gamma l}{\overset{\gamma +l}{}}A(c)(i)=\mu _n(A(c)).$$

Hence, $`\underset{n=\mathrm{}}{lim}{\displaystyle \frac{\mu _n(c)}{\mu _n(A(c))}}1`$, so $`A`$ is not NC.

Now assume that $`A`$ is not NC. Then there exists a configuration $`c`$ such that $`{\displaystyle \frac{\mu _n(c)}{\mu _n(A(c))}}`$ does not converge to 1. Now let us call frontier of the window the stripe of width the diameter of the neighborhood at the window border. Let us now count $`\xi _n(c)`$ the number of non-zero cells of $`c`$ in this frontier.

First case: $`a,n,\mu _n<an`$. Thus there exist consecutive subsequences of unbounded size in which $`\mu _n(c)`$ is constant. Let us consider such a subsequence of length greater than the neighborhood. The frontier of the last window is thus full of zeros. Hence we can “cut off” the internal part, surround it by 0’s and thus obtain a finite configuration. As $`A`$ is not NC, it is not FNC either.

Second case: $`a,n,\mu _n>an`$. The idea is to “cut off” the windows to form periodic configurations. We can bound the perturbation on $`\mu _n(A(x)`$ by the number of non-zero cells in the frontier multiplied by the maximal state (a constant). We then remark that with the hypothesis above, $`\xi _n(c)=o(\mu _n(c))`$. Thus for $`n`$ sufficiently big, the unbalance of the ratio $`\frac{\mu _n(c)}{\mu _n(A(c))}`$ is transmitted to the periodic configuration obtained. Therefore $`A`$ is not PNC and so not FNC. $`\mathrm{}`$

## 3 A necessary and sufficient condition

We present below a necessary and sufficient condition for number-conservation. Our condition is rather complicated to construct. For the sake of simplicity, we first present it in dimension 2 with a square neighborhood $`2\times 2`$. Then we give the condition for neighborhood $`n\times m`$ (proof sketched).

###### Proposition 3

Let $`A=(2,N,Q,f)`$ be a 2D cellular automaton with $`N=\left(\begin{array}{cc}(0,0)\hfill & (0,1)\hfill \\ (0,1)\hfill & (1,1)\hfill \end{array}\right)`$ and thus $`f:Q^4Q`$. $`A`$ is number-conserving if and only if

$`f\left(\begin{array}{cc}a& b\\ c& d\end{array}\right)`$ $`=a`$ $`+\left[f\left(\begin{array}{cc}0& 0\\ 0& c\end{array}\right)f\left(\begin{array}{cc}0& 0\\ 0& a\end{array}\right)\right]`$
$`+\left[f\left(\begin{array}{cc}0& 0\\ 0& b\end{array}\right)f\left(\begin{array}{cc}0& 0\\ 0& d\end{array}\right)\right]`$
$`+\left[f\left(\begin{array}{cc}0& 0\\ c& d\end{array}\right)f\left(\begin{array}{cc}0& 0\\ a& b\end{array}\right)\right]`$
$`+\left[f\left(\begin{array}{cc}0& b\\ 0& d\end{array}\right)f\left(\begin{array}{cc}0& a\\ 0& c\end{array}\right)\right].`$
* Proof. We first show that the condition is necessary. Assume that $`A`$ is NC, let us denote by $`\mathrm{}c`$ the sum of the states in a finite configuration $`c`$ of $`A`$. As $`A`$ is in particular FNC (see Prop. 1)

$$\mathrm{}A\left(\begin{array}{cccccc}\mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}\\ \mathrm{}& 0& 0& 0& 0& \mathrm{}\\ \mathrm{}& 0& a& b& 0& \mathrm{}\\ \mathrm{}& 0& c& d& 0& \mathrm{}\\ \mathrm{}& 0& 0& 0& 0& \mathrm{}\\ \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}\end{array}\right)=a+b+c+d.$$

Moreover,

$`a+b+c+d`$ $`=`$ $`f\left(\begin{array}{cc}0& 0\\ 0& a\end{array}\right)+f\left(\begin{array}{cc}0& 0\\ b& 0\end{array}\right)+f\left(\begin{array}{cc}0& c\\ 0& 0\end{array}\right)+f\left(\begin{array}{cc}d& 0\\ 0& 0\end{array}\right)`$ (25)
$`+f\left(\begin{array}{cc}0& 0\\ a& b\end{array}\right)+f\left(\begin{array}{cc}c& d\\ 0& 0\end{array}\right)+f\left(\begin{array}{cc}0& a\\ 0& c\end{array}\right)+f\left(\begin{array}{cc}b& 0\\ d& 0\end{array}\right)`$
$`+f\left(\begin{array}{cc}a& b\\ c& d\end{array}\right)`$
Replacing $`a`$ by 0 yields:

$`b+c+d`$ $`=`$ $`f\left(\begin{array}{cc}0& 0\\ b& 0\end{array}\right)+f\left(\begin{array}{cc}0& 0\\ 0& b\end{array}\right)+f\left(\begin{array}{cc}0& c\\ 0& 0\end{array}\right)+f\left(\begin{array}{cc}0& 0\\ 0& c\end{array}\right)`$ (43)
$`+f\left(\begin{array}{cc}d& 0\\ 0& 0\end{array}\right)+f\left(\begin{array}{cc}c& d\\ 0& 0\end{array}\right)+f\left(\begin{array}{cc}b& 0\\ d& 0\end{array}\right)+f\left(\begin{array}{cc}0& b\\ c& d\end{array}\right)`$
Subtracting (43) from (25) we obtain:

$`f\left(\begin{array}{cc}a& b\\ c& d\end{array}\right)`$ $`=a`$ $`+f\left(\begin{array}{cc}0& 0\\ 0& b\end{array}\right)+f\left(\begin{array}{cc}0& 0\\ 0& c\end{array}\right)+f\left(\begin{array}{cc}0& b\\ c& d\end{array}\right)`$ (59)
$`f\left(\begin{array}{cc}0& 0\\ 0& a\end{array}\right)f\left(\begin{array}{cc}0& 0\\ a& b\end{array}\right)f\left(\begin{array}{cc}0& a\\ 0& c\end{array}\right)`$
Setting $`b=0`$ in (43), we have also:

$`c+d`$ $`=`$ $`f\left(\begin{array}{cc}0& 0\\ 0& c\end{array}\right)+f\left(\begin{array}{cc}0& c\\ 0& 0\end{array}\right)+f\left(\begin{array}{cc}0& 0\\ d& 0\end{array}\right)+f\left(\begin{array}{cc}d& 0\\ 0& 0\end{array}\right)`$ (73)
$`+f\left(\begin{array}{cc}0& 0\\ c& d\end{array}\right)+f\left(\begin{array}{cc}c& d\\ 0& 0\end{array}\right)`$
Subtracting (73) from (43) we obtain:

$`f\left(\begin{array}{cc}0& b\\ c& d\end{array}\right)`$ $`=b`$ $`+f\left(\begin{array}{cc}0& 0\\ d& 0\end{array}\right)+f\left(\begin{array}{cc}0& 0\\ c& d\end{array}\right)f\left(\begin{array}{cc}0& 0\\ 0& b\end{array}\right)`$ (87)
$`f\left(\begin{array}{cc}0& 0\\ b& 0\end{array}\right)f\left(\begin{array}{cc}b& 0\\ d& 0\end{array}\right)`$
We replace this term in (59):

$`f\left(\begin{array}{cc}a& b\\ c& d\end{array}\right)`$ $`=`$ $`a+bf\left(\begin{array}{cc}b& 0\\ d& 0\end{array}\right)+f\left(\begin{array}{cc}0& 0\\ c& d\end{array}\right)f\left(\begin{array}{cc}0& 0\\ a& b\end{array}\right)+f\left(\begin{array}{cc}0& 0\\ 0& c\end{array}\right)`$ (107)
$`f\left(\begin{array}{cc}0& 0\\ 0& a\end{array}\right)+f\left(\begin{array}{cc}0& 0\\ d& 0\end{array}\right)f\left(\begin{array}{cc}0& 0\\ b& 0\end{array}\right)f\left(\begin{array}{cc}0& a\\ 0& c\end{array}\right)`$
If $`A`$ is FNC then

$$\mathrm{}A\left(\begin{array}{cccccc}\mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}& \\ \mathrm{}& 0& 0& 0& \mathrm{}& \\ \mathrm{}& 0& b& 0& \mathrm{}& \\ \mathrm{}& 0& d& 0& \mathrm{}& \\ \mathrm{}& 0& 0& 0& \mathrm{}& \\ \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}& \end{array}\right)=b+d.$$

After similar calculi as above with the substitution of $`b`$ by 0, we obtain

$`f\left(\begin{array}{cc}b& 0\\ d& 0\end{array}\right)`$ $`=`$ $`b+f\left(\begin{array}{cc}0& 0\\ 0& d\end{array}\right)+f\left(\begin{array}{cc}0& 0\\ d& 0\end{array}\right)f\left(\begin{array}{cc}0& 0\\ 0& b\end{array}\right)f\left(\begin{array}{cc}0& 0\\ b& 0\end{array}\right)`$ (121)
$`f\left(\begin{array}{cc}0& b\\ 0& d\end{array}\right)`$
By replacing this term in (107), we obtain exactly the formula of our Proposition.

Let us prove now that this condition implies PNC. Then by Prop. 1, the theorem is proved. Consider a periodic configuration. Now sum this condition on the period; the terms $`[f(\mathrm{})f(\mathrm{})]`$ simplify and we get exactly the condition for PNC hence for NC. $`\mathrm{}`$

We now give the condition for more general neighborhood in dimension 2. We assert that an analogous formula can be obtained for higher dimension.

###### Theorem 1

Let $`A=(2,N,Q,f)`$ be a 2D cellular automaton with

$$N=\left(\begin{array}{cccc}(0,0)\hfill & (0,1)\hfill & \mathrm{}\hfill & (0,n1)\hfill \\ (1,0)\hfill & (1,1)\hfill & \mathrm{}\hfill & (1,n1)\hfill \\ \mathrm{}\hfill & \mathrm{}\hfill & & \mathrm{}\hfill \\ (m1,0)\hfill & (m1,1)\hfill & \mathrm{}\hfill & (m1,n1)\hfill \end{array}\right)$$

and thus $`f:Q^{m\times n}Q`$. $`A`$ is number-conserving if and only if

$$f\left(\begin{array}{cccc}x_{1,1}& x_{1,2}& \mathrm{}& x_{1,n}\\ x_{2,1}& x_{2,2}& \mathrm{}& x_{2,n}\\ \mathrm{}& \mathrm{}& & \mathrm{}\\ x_{m,1}& x_{m,2}& \mathrm{}& x_{m,n}\end{array}\right)=x_{1,1}$$

$$+\underset{i=0}{\overset{m1}{}}\underset{j=0}{\overset{n2}{}}f\left(\begin{array}{cc}\underset{\mathrm{j}+1}{\underset{}{\begin{array}{ccc}0& \mathrm{}& 0\\ \mathrm{}& & \mathrm{}\\ 0& \mathrm{}& 0\end{array}\text{ }}}\text{}\}\mathrm{i}\text{ }\text{}& 0\\ 0& \begin{array}{ccc}x_{1,2}& \mathrm{}& x_{1,nj1}\\ x_{2,2}& \mathrm{}& x_{2,nj1}\\ \mathrm{}& \mathrm{}& \mathrm{}\\ x_{mi,2}& \mathrm{}& x_{mi,nj1}\end{array}\end{array}\right)$$

$$+\underset{i=0}{\overset{m2}{}}\underset{j=0}{\overset{n1}{}}f\left(\begin{array}{cc}\underset{\mathrm{j}}{\underset{}{\begin{array}{ccc}0& \mathrm{}& 0\\ \mathrm{}& & \mathrm{}\\ 0& \mathrm{}& 0\end{array}\text{ }}}\text{}\}\mathrm{i}+1\text{ }\text{}& 0\\ 0& \begin{array}{ccc}x_{2,1}& \mathrm{}& x_{2,nj}\\ x_{3,1}& \mathrm{}& x_{3,nj}\\ \mathrm{}& \mathrm{}& \mathrm{}\\ x_{mi1,1}& \mathrm{}& x_{mi1,nj}\end{array}\end{array}\right)$$

$$\underset{i=0}{\overset{m1}{}}\underset{j=0\left(i+j>0\right)}{\overset{n1}{}}f\left(\begin{array}{cc}\underset{\mathrm{j}}{\underset{}{\begin{array}{ccc}0& \mathrm{}& 0\\ \mathrm{}& & \mathrm{}\\ 0& \mathrm{}& 0\end{array}\text{ }}}\text{}\}\mathrm{i}\text{ }\text{}& 0\\ 0& \begin{array}{ccc}x_{1,1}& \mathrm{}& x_{1,nj}\\ x_{2,1}& \mathrm{}& x_{2,nj}\\ \mathrm{}& \mathrm{}& \mathrm{}\\ x_{mi,1}& \mathrm{}& x_{mi,nj}\end{array}\end{array}\right)$$

$$\underset{i=0}{\overset{m2}{}}\underset{j=0}{\overset{n2}{}}f\left(\begin{array}{cc}\underset{\mathrm{j}+1}{\underset{}{\begin{array}{ccc}0& \mathrm{}& 0\\ \mathrm{}& & \mathrm{}\\ 0& \mathrm{}& 0\end{array}\text{ }}}\text{}\}\mathrm{i}+1\text{ }\text{}& 0\\ 0& \begin{array}{ccc}x_{2,2}& \mathrm{}& x_{2,nj1}\\ x_{3,2}& \mathrm{}& x_{3,nj1}\\ \mathrm{}& \mathrm{}& \mathrm{}\\ x_{mi1,2}& \mathrm{}& x_{mi1,nj1}\end{array}\end{array}\right)$$

* Proof. We give only the sketch of the proof. In order to show that the condition is necessary, we start from the configuration

$$\begin{array}{cccccccc}& \mathrm{}& \mathrm{}& \mathrm{}& & \mathrm{}& \mathrm{}& \\ \mathrm{}& 0& 0& 0& & 0& 0& \mathrm{}\\ \mathrm{}& 0& x_{1,1}& x_{1,2}& \mathrm{}& x_{1,n}& 0& \mathrm{}\\ \mathrm{}& 0& x_{2,1}& x_{2,2}& \mathrm{}& x_{2,n}& 0& \mathrm{}\\ \mathrm{}& 0& \mathrm{}& \mathrm{}& & \mathrm{}& 0& \mathrm{}\\ \mathrm{}& 0& x_{m,1}& x_{m,2}& \mathrm{}& x_{m,n}& 0& \mathrm{}\\ \mathrm{}& 0& 0& 0& & 0& 0& \mathrm{}\\ & \mathrm{}& \mathrm{}& \mathrm{}& & \mathrm{}& \mathrm{}& \end{array}$$

As $`A`$ is FNC, we have $`x_{1,1}+x_{1,2}+\mathrm{}+x_{m,n}=`$ sum of states obtained in each cell after the application of $`A`$, that is the sum of all $`f(\mathrm{})`$; we substitute in this equation $`x_{1,1}`$ by 0, then $`x_{1,2}`$ by 0, and so on, up to $`x_{1,n}`$. Then we obtain an analogous formula to (107)

$$f\left(\begin{array}{cccc}x_{1,1}& x_{1,2}& \mathrm{}& x_{1,n}\\ x_{2,1}& x_{2,2}& \mathrm{}& x_{2,n}\\ \mathrm{}& \mathrm{}& & \mathrm{}\\ x_{m,1}& x_{m,2}& \mathrm{}& x_{m,n}\end{array}\right)=x_{1,1}+x_{1,2}+\mathrm{}+x_{1,n}$$

$$f\left(\begin{array}{ccccc}x_{1,2}& x_{1,3}& \mathrm{}& x_{1,n}& 0\\ x_{2,2}& x_{2,3}& \mathrm{}& x_{2,n}& 0\\ \mathrm{}& & \mathrm{}& \mathrm{}& \mathrm{}\\ x_{m,2}& x_{1,2}& \mathrm{}& x_{m,n}& 0\end{array}\right)+\mathrm{}$$

Then, in order to obtain the final formula, starting from the configuration

$$\begin{array}{cccccccc}& \mathrm{}& \mathrm{}& \mathrm{}& & \mathrm{}& \mathrm{}& \\ \mathrm{}& 0& 0& 0& & 0& 0& \mathrm{}\\ \mathrm{}& 0& x_{1,2}& x_{1,3}& \mathrm{}& x_{1,n}& 0& \mathrm{}\\ \mathrm{}& 0& x_{2,2}& x_{2,3}& \mathrm{}& x_{2,n}& 0& \mathrm{}\\ \mathrm{}& 0& \mathrm{}& \mathrm{}& & \mathrm{}& 0& \mathrm{}\\ \mathrm{}& 0& x_{m,2}& x_{m,3}& \mathrm{}& x_{m,n}& 0& \mathrm{}\\ \mathrm{}& 0& 0& 0& & 0& 0& \mathrm{}\\ & \mathrm{}& \mathrm{}& \mathrm{}& & \mathrm{}& \mathrm{}& \end{array}$$

we establish the equation for

$$f\left(\begin{array}{ccccc}x_{1,2}& x_{1,3}& \mathrm{}& x_{1,n}& 0\\ x_{2,2}& x_{2,3}& \mathrm{}& x_{2,n}& 0\\ \mathrm{}& \mathrm{}& & \mathrm{}& \mathrm{}\\ x_{m,2}& x_{m,3}& \mathrm{}& x_{m,n}& 0\end{array}\right).$$

Then, we substitute $`x_{1,2}`$ by 0, then $`x_{1,3}`$, and so on, up to $`x_{1,n}`$.

The condition is sufficient: for periodic configurations, when calculating the sum of states on the period, every $`f`$-term is present two times. If it is present in the sum of $`f`$-terms with $`x_{1,1}`$ (resp. $`x_{2,2}`$) as first non-zero element, then it is present in the sum of $`f`$-terms with $`x_{1,2}`$ (resp. $`x_{2,1}`$) as first non-zero element. We so have as sum of states on a period $`_{i=1}^m_{j=1}^nx_{i,j}`$. Hence this condition implies PNC and by Prop. 1 the theorem is proved. $`\mathrm{}`$

###### Theorem 2

The property “number-conserving” is decidable in $`𝒪(s\mathrm{log}s)`$ for cellular automata of any dimension, where $`s`$ denotes the size of the transition table.

* Proof. Remark that the number of terms of our condition in Th. 1 is proportional to the number of neighbors. Thus the set of conditions to be checked is of size proportional to the size of the local transition rule of the cellular automata, which is upper bounded by the size of the cellular automaton in the chosen representation. Access to the table costs at most $`𝒪(\mathrm{log}s)`$. $`\mathrm{}`$

Remark that if cellular automata are given by a program computing their rule and not by the rule exhaustively, then our theorem does not hold. This drawback is often present in cellular automata theory. But if we consider that access to the transition table is performed in constant time, then the algorithm is linear.

## 4 Dynamics

NCA are often used for the simulation of real phenomena such as highway traffic flow, fluid dynamics and so on. Therefore, once we have established that our model is a NCA (by using the decision procedures given in the first part of the paper, for example), it is very important to forecast as much as possible its dynamics and, whenever possible, correlate experimental evidence (such as pattern growth) with other interesting theoretical properties. This is the matter of this second part of the paper.

### 4.1 Definitions and background

A *dynamical system* $`(X,F)`$ consists of a compact metric space $`X`$ and a continuous self-map $`F`$. Denote $`d`$ the metric on $`X`$ and $`F^n`$ the $`n`$-fold composition of $`F`$ with itself.

We first recall some classical definitions. A point $`xX`$ is an *equicontinuity* point for $`F`$ if for any $`ϵ>0`$ there exists $`\delta >0`$ such that for any $`yX`$, $`d(x,y)\delta `$ implies that $`t`$, $`d(F^t(x),F^t(y))<ϵ`$. If $`X`$ is perfect and all of its points is an equicontinuity point for $`F`$ then $`F`$ is *equicontinuous*. A dynamical system $`(X,F)`$ is *sensitive to initial conditions* if there exists $`ϵ>0`$ such that for any $`xX`$ and any $`\delta >0`$, $`0<d(x,y)<\delta `$ implies that there exists $`t`$ such that $`d(F^t(x),F^t(y))ϵ`$. We recall that in a perfect space any system with no equicontinuity points is sensitive to initial conditions and vice-versa. $`(X,F)`$ is *expansive* if there exists $`ϵ>0`$ such that for any $`x,yX`$, $`d(x,y)>0`$ implies that $`t`$ such that $`d(F^t(x),F^t(y))ϵ`$. If for any pair of non-empty open set $`U,V`$ there exists $`n`$ such that $`F^n(U)V\mathrm{}`$ then $`F`$ is *transitive*. A point $`x`$ is *periodic* if there exists $`n`$ such that $`F^n(x)=x`$. $`F`$ is *regular* if periodic points are dense in $`X`$.

Properties like sensitivity, expansivity, transitivity and regularity are often used as basic components of *chaotic behavior.* For example, Devaney, in a popular book , defines as chaotic all systems that are transitive, regular and sensitive to initial conditions.

We are interested in the study of dynamical systems in symbolic spaces. $`S^{Z^k}`$ is endowed with the product topology (also called Cantor topology) of a countable product of discrete space. For the sake of simplicity, we will study cellular automata in dimension $`k=1`$, the generalization of results to higher dimensions is straightforward for most of the results; Propositions 8 to 11 require deeper adaptations although no new idea is needed.

The metric $`d`$ on $`S^{}`$ defined as

$$x,yS^{},d(x,y)=2^n$$

where $`n=inf\left\{i0,x(i)y(i)\text{or}x(i)y(i)\right\}`$ induces the product topology on $`S^{}`$. Denote by $`S^{}`$ the set of finite words on $`S`$. For $`wS^{}`$, $`\mathrm{}\left(w\right)`$ denotes the length of $`w`$. For $`t,wS^{}`$, the sets

$$[w]_t=\left\{xS^{},x(t)=w(0),\mathrm{},x(t+\mathrm{}\left(w\right))=w(\mathrm{}\left(w\right))\right\}$$

are called *cylinders* and form a basis for the product topology on $`S^{}`$. The *shift map* $`\sigma `$ is often used as a paradigmatic example of chaotic symbolic system. It is defined as $`cS^{},i,\sigma (c)(i)=c(i+1)`$. Cellular automata are exactly those continuous maps from $`S^{}`$ to $`S^{}`$ that commute with the shift (*i.e.,* $`F\sigma =\sigma F`$.

### 4.2 Classification of dynamical behavior

In spite of their very simple definition cellular automata may have complex dynamical behavior (see for example ). The classification of these dynamical behaviors is known as the *classification problem* is one of the oldest, hardest and for this reason fascinating open problem in cellular automata theory. During the years many authors have proposed partial solutions (because of their undecidability). Each classification focuses on a particular aspect of cellular automata theory. For example, if one is interested in simulations of real life phenomena like car traffic (e.g. using number-conserving cellular automata that we call NCA for short), the study of dynamics on finite patterns deserves a particular importance. In this context a well-known classification of cellular automata with quiescent state is given in . In these papers cellular automata are classified according to their pattern divergence. Three classes of behavior are defined:

* $`x𝒞_Flim_t\mathrm{}\mathrm{}\left(F^t(x)\right)=0`$
* $`x𝒞_Fsup_t\mathrm{}\left(F^t(x)\right)<\mathrm{}`$
* $`x𝒞_Fsup_t\mathrm{}\left(F^t(x)\right)=\mathrm{}`$

People familiar with the study of complex analytic transformations will immediately remark the strong analogies with Julia and Fatou sets of complex transformations .

This classification is especially pertinent for NCA since $`0`$ is necessarily a quiescent state.

In the study of chaotic behavior one often finds that complex behavior is generated from “simple” local interactions. Again, using the metaphor of car traffic, traffic-jams and their consequences are generated by a “bad” interaction of a relatively small number of cars. In , Kůrka proposed a classification based on local behavior of cellular automata and increasing degrees of chaos. Kůrka proposed the following classes:

* equicontinuous cellular automata;
* cellular automata with equicontinuity points but not equicontinuous;
* cellular automata sensitive to initial conditions but not expansive;
* expansive cellular automata.

The following result is adapted from Knudsen . By using Proposition 4 one can express the properties defining (most of) Kůrka classes in term of behavior on finite patterns.

###### Proposition 4

$`F`$ is transitive (resp. sensible to initial conditions, equicontinuous) w.r.t. finite configurations if and only if $`F`$ is transitive (resp. sensible to initial conditions, equicontinuous).

The same result holds if in Proposition 4 we consider the set of spatial periodic configurations instead of finite configurations. In the rest of the section, we study the relations between dynamical behavior of NCA and the classifications of Kůrka and Cattaneo.

Given $`x𝒞_F`$, let

$$m(x)=\mathrm{min}\{i,x(i)0\},M(x)=\mathrm{max}\{i,x(i)0\}\mathrm{and}$$

$$s(x)=\underset{m(x)}{\overset{M(x)}{}}x(i).$$

Remark that $`x𝒞_F,m(\sigma ^k(x))=m(x)k`$ (the same holds if we put $`M`$ in place of $`m`$).

###### Proposition 5

The are no expansive NCA.

* Proof. For dimension greater than 1, this is a consequence of the well-known result of Shereshevsky . Consider a one-dimensional NCA $`F`$. Suppose that $`F`$ is expansive with expansive constant $`ϵ`$. Let $`i`$ be such that $`\frac{1}{2^i}<ϵ`$. Construct a finite configuration $`c_i(j)=1`$ if $`i=j`$, $`0`$ otherwise. Since $`F`$ is expansive there exists $`t_1`$ such that $`d(F^{t_1}(0),`$ $`F^{t_1}(c_i))>ϵ`$. For the same reason there exists $`t_2`$ such that $`d(F^{t_2}(0),F^{t_2}(c_i))>ϵ`$. Therefore there exists a time $`t\mathrm{max}\{t_1,t_2\}`$ for which $`F^t(c_i)`$ consists of at least two $`1`$’s, violating $`FNC`$ condition. $`\mathrm{}`$

###### Lemma 1

Let $`F`$ be a NCA. For any $`x𝒞_F`$, there exists $`c_x`$ such that $`t,\mathrm{}\left(F^t(x)\right)c_x`$.

* Proof. Let $`x𝒞_F`$. Since each cell can contribute at most $`q1`$ to the sum $`s(x)`$, it holds that $`t,\mathrm{}\left(F^t(x)\right)\frac{s(x)}{q1}`$. $`\mathrm{}`$

The following proposition is a trivial consequence of Lemma 1.

###### Proposition 6

There are no NCA in class $`C_1`$.

###### Proposition 7

There are no NCA in class $`K_1C_3`$.

* Proof. Let $`F`$ be a cellular automaton in $`C_3`$ and let $`c`$ be such that

$$\underset{t\mathrm{}}{lim}\mathrm{}\left(F^t(c)\right)=\mathrm{}.$$
(122)
We have two cases:

1. $`\underset{t}{sup}m(F^t(c))=\mathrm{}`$;
    2. $`\underset{t}{sup}m(F^t(c))=c`$ and $`\underset{t}{sup}M(F^t(c))=\mathrm{}.`$

We consider only the former case, the proof for the latter is similar. For any $`\delta >0`$, let $`\overline{n}`$ be such that $`\frac{1}{\overline{n}}\delta \frac{1}{\overline{n}1}`$. By (122), there exists a time $`t`$ such that $`m(F^t(c))=h>\overline{n}`$. Therefore $`d(\underset{¯}{0},\sigma ^h(c))\delta `$. Since $`F`$ commutes with $`\sigma `$, we have

$$m(F^t(\sigma ^h(c)))=m(\sigma ^h(F^t(c)))=m(F^t(c))+h=0$$

which implies that

$$d(F^t(\sigma ^h(\underset{¯}{0})),F^t(\sigma ^h(c)))=d(\underset{¯}{0},F^t(\sigma ^h(c)))=1.$$

Since $`\delta `$ is arbitrary, last inequality implies that $`\underset{¯}{0}`$ is not an equicontinuity point. Since we are in a perfect space we conclude that $`F`$ is not an equicontinuous system. $`\mathrm{}`$

A word $`WS^{}`$ is called *blocking* word if there exists an infinite sequence of words $`w_n`$ such that

1. $`n,\mathrm{}\left(w_n\right)=2h+1>r`$ with $`h`$;
2. $`cS^Z,(c_{k:k}=WtN\left\{0\right\}F^t(W)_{i:i}=w_t)`$ .

In other words $`W`$ partitions the evolution diagram of $`F`$ in two completely disconnected parts: perturbations made in one part are completely “blocked” by $`W`$. This notion is fundamental for characterizing cellular automata dynamics in the presence of equicontinuity points as we can see in the next proposition. It will also be crucial in the proof of Proposition 11.

###### Proposition 8 ()

Any equicontinuity point has an occurrence of a blocking word. Conversely if there exist blocking words, then any point with infinitely many occurrences of a blocking word to the left and to the right (of $`0`$) is an equicontinuity point.

###### Proposition 9 ()

Let $`X`$ be a $`\sigma `$-transitive SFT. If $`F`$ has an equicontinuity point then ($`F`$ onto $``$ regular).

The above proposition implies that surjective NCA in class $`K_2C_3`$ are regular.

###### Proposition 10 ()

A cellular automaton $`F`$ is equicontinuous and onto if and only if $`p>0`$ such that $`cS^{},F^p(c)=c`$.

A consequence of the above proposition is that surjective NCA in class $`K_1C_2`$ are periodic and non-surjective ones are ultimately periodic.

###### Proposition 11

There are no NCA in class $`K_2C_2`$.

* Proof. Since we are in a perfect space if a cellular automaton is not equicontinuous then there exists at least a configuration $`c`$ which is not an equicontinuity point. By Proposition 4 we can assume that $`c`$ is finite. By the hypothesis, there exists a constant $`K`$ such that $`t,\mathrm{}\left(F^n(c)\right)K`$. Assume that $`lim_t\mathrm{}m(F^t(c))=\mathrm{}`$ (if this is not the case then $`lim_t\mathrm{}m(F^t(c))=+\mathrm{}`$ and the rest of the proof will be perfectly similar). On the other hand, there exists at least an equicontinuity point and, by Proposition 8, there exists at least a blocking word $`W`$. Construct a configuration $`d`$ such that

$$iZ,d(i)=\{\begin{array}{cc}c(i)\hfill & \text{if}m(c)iM(c)\hfill \\ W(i)\hfill & \text{if}\mathrm{\hspace{0.33em}2}M(c)i2M(c)+\mathrm{}\left(b\right)\hfill \\ 0\hfill & \text{otherwise}.\hfill \end{array}$$

It is clear that $`\underset{t\mathrm{}}{lim}\mathrm{}\left(F^t(d)\right)=+\mathrm{}`$. $`\mathrm{}`$

For any cellular automaton $`F`$, denote $`F_F`$ the restriction of $`F`$ to $`C_F`$ and $`F_P`$ the restriction of $`F`$ to $`C_P`$.

###### Proposition 12

A NCA $`F`$ is surjective if and only if its restriction to $`F_F`$ is bijective.

* Proof. One implication is the well-known Moore-Myhill theorem . For the converse, remark that if $`F`$ is surjective every finite configuration has a pre-image. The FNC condition grants that this pre-image is finite. $`\mathrm{}`$

The following definition is essentially taken from .

###### Definition 4

A cellular automaton $`<S^{},G>`$ is said to be a *generalized subshift* on the set $`US^{}`$ iff

1. $`U`$ is $`G`$ positively invariant *i.e.,* $`G(U)U`$;
2. there exists a mapping $`T,T^{}:S^{}\{0\}`$ such that $`cU,G^{T(c)}(c)=\sigma ^{T^{}(c)}(c)`$.

The following lemma present peculiar properties of the shifting function of generalized subshifts on $`C_F`$.

###### Lemma 2

Let $`F`$ be a generalized subshift on $`C_F`$ and let $`T,T^{}`$ as in Definition 4. Then either $`xC_F,T(x)=T^{}(x)`$ or $`xC_F,T(x)=T^{}(x)`$.

* Proof. By contraposition, suppose that there exist $`x,yX`$ such that $`T(x)=T^{}(x)`$ and $`T(y)=T^{}(y)`$. Let $`n_x=\mathrm{max}_{0iT(x)}\mathrm{}\left(F^i(x)\right)`$ and $`n_y=\mathrm{max}_{0iT(y)}\mathrm{}\left(F^i(y)\right)`$. Build the following finite configuration

$$i,w(i)=\{\begin{array}{cc}y(i+\mathrm{}\left(y\right))\hfill & \text{if}\mathrm{}\left(y\right)n_yi1n_y\hfill \\ x(i1)\hfill & \text{if}\mathrm{\hspace{0.33em}1}+n_xi\mathrm{}\left(x\right)+n_x\hfill \\ 0\hfill & \text{otherwise}.\hfill \end{array}$$

Since $`lim_t\mathrm{}\mathrm{}\left(F^t(w)\right)=+\mathrm{}`$ there exists no $`n\left\{0\right\}`$ such that $`F^n(w)=\sigma ^n(w)`$ or $`F^n(w)=\sigma ^n(w)`$. $`\mathrm{}`$

The following lemma links properties of the evolution of $`F`$ with set properties of the maps $`F_F`$ and $`F_P`$.

###### Lemma 3

Let $`F`$ be a transitive cellular automaton. Then $`F_F`$ is bijective and $`F_P`$ is surjective.

* Proof. It is well-known that transitivity implies surjectivity. By Moore-Myhill theorem, this last property implies that $`F_F`$ is injective. By Proposition 4, transitive cellular automata are transitive over $`C_F`$. This fact implies that $`F_F`$ is surjective. Using Proposition 4 again, we have that transitive cellular automata are transitive over $`C_P`$ and hence $`F_P`$ is surjective. $`\mathrm{}`$

###### Proposition 13

Generalized subshift cellular automata on $`𝒞_F`$ are transitive and regular.

* Proof. Let $`F`$ be a generalized subshift cellular automaton on $`𝒞_F`$ and $`T,T^{}`$ as in Definition 4. We are going to prove that $`F`$ is transitive on $`C_F`$; by Proposition 4 we have the first part of the thesis. For any cylinder set $`[w]_t`$, let $`\overline{w}`$ the finite configuration such that $`\overline{w}_{i+t}=w_{i+t}`$ for $`0i\mathrm{}\left(w\right)`$ and $`0`$ elsewhere. Take two arbitrary cylinder sets $`[w]_t`$ and $`[z]_l`$. Let $`n_{\overline{w}}=\mathrm{max}_{0iT(\overline{w})}\mathrm{}\left(F^i(w)\right)`$ and $`n_{\overline{z}}=\mathrm{max}_{0iT(\overline{z})}\mathrm{}\left(F^i(z)\right)`$. Let $`m=T(\overline{w})T(\overline{z})`$. Finally, choose $`k,q`$ such that $`q>n_{\overline{z}}+n_{\overline{w}}`$ and $`t=km+q`$. Build a finite configuration $`c`$ such that $`c=\overline{w}\sigma ^{km+q}(\overline{z})`$, where $``$ is the bitwise “or” operation. It is not difficult to see that $`F^{km+q}(c)[z]`$ and $`c[w]`$; this completes the first part of the proof.

Since $`C_F`$ is dense in $`S^{}`$, for any configuration $`xS^{}`$, there exist a sequence $`\left\{u_i\right\}_iC_F`$ such that $`lim_i\mathrm{}u_i=x`$. and let

$$n_{u_i}=\underset{0jT(u_i)}{\mathrm{max}}\mathrm{}\left(F^j(u_i)\right).$$

For any $`u_i`$, build a spatial periodic configuration

$$y_i=0^{2n_{x_i}}x_i0^{2n_{x_i}}0^{2n_{x_i}}x_i0^{2n_{x_i}}\mathrm{}0^{2n_{x_i}}x_i0^{2n_{x_i}}\mathrm{}$$

such that $`(y_i)_k=(x_i)_k`$ for $`m(x_i)kM(x_i)`$. Clearly $`y_i`$ is ultimately periodic for $`F`$. By Lemma 3 we have that it is in fact periodic. The fact that $`lim_i\mathrm{}y_i=x`$ closes the proof. $`\mathrm{}`$

From Proposition 13 and , generalized subshift cellular automata on $`𝒞_F`$ are sensitive to initial conditions.

When studying asymptotic behavior of a cellular automaton it is of fundamental importance to understand the structure of the so called *limit set* $`\mathrm{\Omega }=_nF^n(S^{})`$. This set can be viewed as the set of configurations which have an infinite number of predecessors. It is well-known that is compact, non-empty and that it is the maximal (w.r.t. set inclusion) attracting set. In the sequel we will very interested in a special subset of the limit set: $`\mathrm{\Omega }_F=_nF^n(𝒞_F)𝒞_F`$, that is the set of finite configurations which have an infinite number of predecessors (of finite type). One can easily see that for any cellular automaton this set is non-empty for it should contain at least one homogeneous configuration. In the particular case of NCA, the following easy proposition proves that the cardinality of $`\mathrm{\Omega }_F`$ is always countably infinite.

###### Proposition 14

For any NCA, $`\mathrm{\Omega }`$ is an uncountable set while the cardinality of $`\mathrm{\Omega }_F`$ is countably infinite.

* Proof. Let $`c_1`$ be the configuration that has a $`1`$ in zero and $`0`$ elsewhere. Let $`h=|m(F^(c_1))|`$ (for $`a`$, $`|a|`$ is the absolute value of $`a`$). Let $`a_b=0^{2h+1}b0^{2h+1}`$ for $`b\{0,1\}`$. For any configuration $`x\{0,1\}^{}`$, build the configuration $`c_x=a_{x_0}a_{x_1}\mathrm{}a_{x_n}\mathrm{}`$ Note that $`c_x\mathrm{\Omega }`$. In particular if $`xC_F\{0,1\}^{}`$ then $`c_x\mathrm{\Omega }_F`$. It is easy to see for $`x,y\{0,1\}^{}`$, if $`xy`$ then $`c_xc_y`$. $`\mathrm{}`$

A cellular automaton $`F`$ is said to be a *ultimately generalized subshift* on $`US^{}`$ is $`F`$ is a generalized subshift on $`U`$ and $`xS^{}`$, there exists $`n=n_x`$ such that $`F^{n_x}(x)U`$.

###### Proposition 15

Non-surjective NCA in $`K_3C_2`$ are ultimately generalized subshifts on $`\mathrm{\Omega }_F`$. All surjective NCA in class $`K_3C_2`$ are generalized subshifts on $`𝒞_F`$.

* Proof. Consider a NCA $`F`$ in $`K_3C_2`$, we prove that it is a generalized subshift on $`\mathrm{\Omega }_F𝒞_F`$. Since $`F`$ is not equicontinuous for any finite configuration $`c`$ either $`m(F^t(c))`$ or $`M(F^t(c))`$ is not a constant function. Since $`FC_2`$ there exists $`L`$ such that $`t,\mathrm{}\left(F^t(c)\right)L`$. Therefore there exist $`t_1,t_2S^L`$ such that $`F^{t_1}(F^{t_2}(c))=\sigma ^{t_1}(F^{t_2}(c))`$. Clearly, $`\mathrm{\Omega }_F`$ is positively invariant and, by the above remarks, $`F`$ is a generalized subshift on it, for otherwise one can find a finite configuration in which $`m()`$ is constant. Moreover, since $`t,\mathrm{}\left(F^t(c)\right)L`$, there exists $`\overline{t}`$ such that $`F^{\overline{t}}(c)\mathrm{\Omega }_F`$. For the second part of the proof remark that surjective NCA are bijective on $`𝒞_F`$ (*cf.* Proposition 12) then $`\mathrm{\Omega }_F=𝒞_F`$. $`\mathrm{}`$

###### Proposition 16

Let $`F`$ be an ultimately generalized subshift on $`U𝒞_F`$ with $`|\mathrm{\Omega }_F|=\mathrm{}`$. Then $`F`$ is sensitive to initial conditions.

* Proof. We prove that they are sensitive to initial conditions on $`𝒞_F`$, by Proposition 4 we have the thesis.

Consider a finite configuration $`c`$ and $`B_\delta `$ the ball of radius $`\delta >0`$ centered on $`c`$. Choose an integer $`n`$ such that $`\frac{1}{n}<\delta `$. Let $`t`$ be such that $`F^t(c)\mathrm{\Omega }_F`$ (by the hypothesis, $`t`$ always exists). Let $`n_c=\mathrm{max}_{0iT(c)+t}\mathrm{}\left(F^i(c)\right)`$. Choose $`x\mathrm{\Omega }_F`$. By Lemma 2, without loss of generality we can assume that the patterns generated by $`c`$ and $`x`$ move to the left. Now, choose $`h>t`$ such that $`m(F^h(c))+n_c<0`$. Let $`n_x=\mathrm{max}_{0iT(x)}\mathrm{}\left(F^i(c)\right)`$. Choose $`k`$ such that $`kT(x)>h+n_x+n`$ and $`m(F^{kT(x)}(x))=0`$. Finally, build the configuration $`w=c\sigma ^{kT(x)}(x)`$, where $``$ is the usual bit-wise “or” operation. Is is not difficult to see that $`d(c,w)<\delta `$ and $`d(F^{kT(x)}(c),F^{kT(x)}(w))1`$. Since $`c`$ and $`\delta `$ were chosen arbitrarily we conclude that $`F`$ is sensible to initial conditions. $`\mathrm{}`$

The following corollary is an immediate consequence of Propositions 16 and 15.

###### Corollary 1

NCA of class $`C_2`$ that are ultimately subshift on $`U𝒞_F`$ are sensitive to initial conditions.

### 4.3 Examples

This section proposes several examples which illustrate representative behaviors in each class.

###### Example 1 (Class $`K_1C_2`$ is not empty)

$`K_1C_2`$ contains the identity cellular automaton.$`\mathrm{}`$

###### Example 2 (Class $`K_3C_2`$ is not empty)

Consider the NCA with the following local rule $`f`$ on the alphabet $`S=\{0,1\}`$:

| $`(x,y,z)`$ | $`000`$ | $`001`$ | $`010`$ | $`011`$ | $`100`$ | $`101`$ | $`110`$ | $`111`$ |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
| $`f(x,y,z)`$ | $`0`$ | $`0`$ | $`0`$ | $`1`$ | $`1`$ | $`1`$ | $`0`$ | $`1`$ |

Rule $`f`$ is called “rule $`184`$” in  and it often given an elementary example of car traffic modeling: symbols $`1`$’s are cars moving on a highway ($`0`$’s). When a $`1`$ finds a $`0`$ on its right (that a free path on the highway) it moves one cell to the right. If the cell is not free then it waits. $`\mathrm{}`$

###### Example 3 (Class $`K_2C_3`$ is not empty)

Consider the following local rule $`f`$ on the alphabet $`S=\{0,1,2\}`$:

| $`(x)`$ | $`2a`$ | $`1b`$ | $`12`$ | $`0a`$ |
| --- | --- | --- | --- | --- |
| $`f(x)`$ | $`2`$ | $`b`$ | $`1`$ | $`0`$ |

where $`aA`$ and $`b\{0,1\}`$. Let $`F`$ be the global rule induced by $`f`$. It is clear that $`W=2`$ is a blocking word. Define three configurations $`c,d,e`$ respectively as $`c(0)=2,c(1)=1,\mathrm{\hspace{0.17em}0}`$ otherwise; $`d(0)=1,d(1)=2,\mathrm{\hspace{0.17em}0}`$ otherwise; and $`e(1)=1,c(0)=0,c(1)=2,\mathrm{\hspace{0.17em}0}`$ otherwise. Since $`\underset{t}{sup}\mathrm{}\left(F^t(c)\right)=\mathrm{}`$ and $`F^1(d)=\{d,e\}`$, by Moore-Myhill theorem , $`F`$ is not surjective and hence not regular. Finally, since $`\underset{¯}{0}`$ is not an equicontinuity point we have that $`FK_2C_3`$. $`\mathrm{}`$

Cellular automata in class $`K_3C_3`$ seems to have a more rich variety of behaviors than other classes; as a consequence is much more difficult to have clear-cut situations: we can have system of particles with delayed propagation (Example 4) and others in which particles cross each other without interaction (Example 5). We also underline that it is exactly in this class that reversible NCA capable of universal computation have been found .

###### Example 4 (Class $`K_3C_3`$ is not empty)

Consider the NCA with the following local rule $`f`$ on the alphabet $`S=\{0,1,2\}`$:

| $`(x,y,z)`$ | $`00b`$ | $`002`$ | $`01a`$ | $`02a`$ | $`10a`$ | $`11a`$ |
| --- | --- | --- | --- | --- | --- | --- |
| $`f(x,y,z)`$ | $`0`$ | $`2`$ | $`a`$ | $`0`$ | $`1`$ | $`a`$ |

and

| $`(x,y,z)`$ | $`12a`$ | $`20b`$ | $`202`$ | $`21a`$ | $`22a`$ |
| --- | --- | --- | --- | --- | --- |
| $`f(x,y,z)`$ | $`1`$ | $`0`$ | $`2`$ | $`a`$ | $`2`$ |

One can verify that for any finite configuration $`c`$ there exists a time $`\overline{t}`$ such that for any $`t\overline{t}`$, $`F^t(c)`$ is such that all symbols $`1`$ (if any) are on the positive coordinates, while symbols of type $`2`$ are on the negative part. $`1`$’s and $`2`$’s propagate in opposite directions. Normally type $`2`$ symbols propagate at speed $`1`$ to the left (one unit displacement per time unit). This speed reduces of one half if $`2`$ encounters a $`1`$ like in $`102`$; in a sense type $`1`$’s symbols have precedence over $`2`$’s. Therefore for any $`ϵ>0`$ choose $`\overline{n}`$ such that $`\frac{1}{\overline{n}}ϵ\frac{1}{\overline{n}1}`$. Construct the following configuration $`\overline{c}`$ as follows:

$$i,\overline{c}(i)=\{\begin{array}{cc}c(i)\hfill & \text{if}m(c)iM(c)\hfill \\ 2\hfill & i=\mathrm{max}\{\overline{n},\overline{t}\}\hfill \\ 0\hfill & \text{otherwise}.\hfill \end{array}$$

Then there exists $`h2\mathrm{max}\{\overline{n},\overline{t}\}`$ such that $`d(F^h(c),F^h(\overline{c}))=1`$. From the fact that $`d(c,\overline{c})ϵ`$ and Proposition 4 we have that $`F`$ is sensitive to initial conditions. Note that $`F`$ is not surjective since its restriction to configurations on the alphabet $`\{0,1\}`$ coincides with elementary rule $`184`$ of Example 2 which is not surjective. $`\mathrm{}`$

###### Example 5

Consider a system which describes the interaction of two particles (denoted by 1 and 2) in a neutral media (symbols 0). Particles of type 1 move left to right while type 2 move in the opposite direction. A symbol 3 denotes the presence of a particle of type 2 and one of type 1 on the same site. These elementary rules are formalized by the following local rule:

| $`(x,y,z)`$ | $`0xa`$ | $`1xa`$ | $`2xa`$ | $`3xa`$ |
| --- | --- | --- | --- | --- |
| $`f(x,y,z)`$ | $`0`$ | $`1`$ | $`0`$ | $`1`$ |

and

| $`(x,y,z)`$ | $`0xb`$ | $`1xb`$ | $`2xb`$ | $`3xb`$ |
| --- | --- | --- | --- | --- |
| $`f(x,y,z)`$ | $`2`$ | $`3`$ | $`2`$ | $`3`$ |

where $`a\{0,1\}`$, $`b\{2,3\}`$ and $`x\{1,2,3,4\}`$.

It is easy to see that $`F`$ is injective and hence its restriction to spatial periodic configuration is injective (see ). The last property implies that $`F`$ is regular. $`F`$ is also transitive. In fact, for any finite configuration $`x=x_k\mathrm{}x_{k+h}`$ ($`k,hN`$) construct a configuration $`y`$ such that for $`khi<k`$, $`y(i)=1`$ or $`3`$ if $`x(i+h)=1`$, $`y(i)=0`$ otherwise. Moreover for $`k+h<ik+2h`$ let $`y(i)=2`$ if $`x(ih)=2`$ or $`3`$. Remark that $`F^h(y)=x`$. For any pair of cylinders $`C_1=C(w_k,\mathrm{},w_{k+h})`$ and $`C_2=C(z_g,\mathrm{},z_{g+n})`$ ($`k,h,g,nN`$). Choose $`cC_1`$. Let $`t`$ be such that $`m(F^t(c))<g+h`$ and $`M(F^t(c))>g+n+h`$. Define $`d`$ such that for $`gig+n`$, $`d(i)=z_i`$. Moreover, for $`m(F^t(c))im(F^t(c))+h`$ let $`d(i)=1`$ if $`w_{im(F^t(c))}=1`$ or $`3`$; for $`M(F^t(c))hiM(F^t(c))`$ let $`d(i)=2`$ if $`w_{iM(F^t(c))}=2`$ or $`3`$. Finally, $`d(i)=0`$ in all other cases. By construction $`dC_2`$. Using previous remark one can see that $`F^t(d)(j)=w_j`$ for $`kjk+h`$, that is to say that $`F^t(d)C_1`$. $`\mathrm{}`$

Table 1 summarizes the situation.

## 5 Conclusions and open problems

The paper discusses three formulations of the notion of being number-conserving which have arisen in recent works on the study of physical phenomena ruled by conservation laws of mass or energy. We have proved that all these formulations are equivalent and we have given another equivalent definition in terms of density.

Moreover, we have given a linear time algorithm for deciding if a CA (of any dimension and any state set) is number conserving. We stress that the linearity of the algorithm is something rather surprising since most of the interesting structural or dynamical properties of CA are known to be undecidable.

The strong constraints imposed by number-conservation simplifies the study of asymptotic evolutions. Results can be conveniently interpreted in terms of particles system. Class $`K_1C_3`$ is composed by systems with “non-moving” particles. In class $`K_3C_2`$ we find systems in which particles move along only one direction with identical speed (of course speed may vary from system to system). Systems in class $`K_2C_3`$ allow particles in many different directions (possibly opposite) with the peculiarity that particles have blocking collisions. Finally, systems in class $`K_3C_3`$ have the same properties as those in class $`K_2C_3`$ but with non-blocking collisions.

Although many aspects have been understood there are still many interesting open problems that we think they worth further study. For example, we have already said that surjectivity property is undecidable for CA in general. But maybe it turns out to be decidable for the sub-class of NCA. Surjectivity plays a prominent role in the study of CA dynamics since it is a necessary condition (for example) for many popular definitions of chaotic dynamics. In Section 4.2 we have found that, with exception for class $`K_3C_3`$, surjectivity is equivalent to the property of having a dense set of periodic points (again, this last property is one of the component of Devaney’s definition of chaos). For class $`K_3C_3`$ we do not know if this property holds or not.