# Search for Non-Tensorial Gravitational-Wave Backgrounds in the NANOGrav
15-Year Data Set

Zu-Cheng Chen<EMAIL_ADDRESS>Department of Physics and Synergistic
Innovation Center for Quantum Effects and Applications, Hunan Normal
University, Changsha, Hunan 410081, China  Department of Astronomy, Beijing
Normal University, Beijing 100875, China  Advanced Institute of Natural
Sciences, Beijing Normal University, Zhuhai 519087, China  Yu-Mei Wu
<EMAIL_ADDRESS>School of Fundamental Physics and Mathematical Sciences,
Hangzhou Institute for Advanced Study, UCAS, Hangzhou 310024, China  School of
Physical Sciences, University of Chinese Academy of Sciences, No. 19A Yuquan
Road, Beijing 100049, China  Yan-Chen Bi<EMAIL_ADDRESS>School of
Physical Sciences, University of Chinese Academy of Sciences, No. 19A Yuquan
Road, Beijing 100049, China  CAS Key Laboratory of Theoretical Physics,
Institute of Theoretical Physics, Chinese Academy of Sciences, Beijing 100190,
China  Qing-Guo Huang<EMAIL_ADDRESS>School of Fundamental Physics and
Mathematical Sciences, Hangzhou Institute for Advanced Study, UCAS, Hangzhou
310024, China  School of Physical Sciences, University of Chinese Academy of
Sciences, No. 19A Yuquan Road, Beijing 100049, China  CAS Key Laboratory of
Theoretical Physics, Institute of Theoretical Physics, Chinese Academy of
Sciences, Beijing 100190, China

###### Abstract

The recent detection of a stochastic signal in the NANOGrav 15-year data set
has aroused great interest in uncovering its origin. However, the evidence for
the Hellings-Downs correlations, a key signature of the gravitational-wave
background (GWB) predicted by general relativity, remains inconclusive. In
this paper, we search for an isotropic non-tensorial GWB, allowed by general
metric theories of gravity, in the NANOGrav 15-year data set. Our analysis
reveals a Bayes factor of approximately 2.5, comparing the quadrupolar (tensor
transverse, TT) correlations to the scalar transverse (ST) correlations,
suggesting that the ST correlations provide a comparable explanation for the
observed stochastic signal in the NANOGrav data. We obtain the median and the
$90\%$ equal-tail amplitudes as
$\mathcal{A}_{\mathrm{ST}}=7.8^{+5.1}_{-3.5}\times 10^{-15}$ at the frequency
of 1/year. Furthermore, we find that the vector longitudinal (VL) and scalar
longitudinal (SL) correlations are weakly and strongly disfavoured by data,
respectively, yielding upper limits on the amplitudes:
$\mathcal{A}_{\mathrm{VL}}^{95\%}\lesssim 1.7\times 10^{-15}$ and
$\mathcal{A}_{\mathrm{SL}}^{95\%}\lesssim 7.4\times 10^{-17}$. Lastly, we fit
the NANOGrav data with a general transverse (GT) correlations parameterized by
a free parameter $\alpha$. Our analysis yields $\alpha=1.74^{+1.18}_{-1.41}$,
thus excluding both the TT ($\alpha=3$) and ST ($\alpha=0$) models at the
$90\%$ confidence level.

##  I Introduction

A pulsar timing array (PTA) is dedicated to the detection of gravitational
waves (GWs) with frequencies in the nanohertz range by regularly monitoring
the spatially correlated fluctuations caused by GWs on the time of arrivals
(TOAs) of radio pulses emitted by an array of pulsars Sazhin (1978); Detweiler
(1979); Foster and Backer (1990). There are three major PTA projects: the
European PTA (EPTA) Kramer and Champion (2013), the North American Nanoherz
Observatory for GWs (NANOGrav) McLaughlin (2013), and the Parkes PTA (PPTA)
Manchester  _et al._ (2013). Over the course of more than a decade, these
projects have been monitoring the TOAs from dozens of millisecond pulsars with
an observation cadence ranging from weekly to monthly. These PTAs along with
the Indian PTA (InPTA) Joshi  _et al._ (2018) constitute the International PTA
(IPTA) Hobbs  _et al._ (2010); Manchester (2013). Meanwhile, the Chinese PTA
(CPTA) Lee (2016) and the MeerKAT PTA Miles  _et al._ (2023) hold observer
status within the IPTA.

Recently, NANOGrav Agazie  _et al._ (2023a, b), PPTA Zic  _et al._ (2023);
Reardon  _et al._ (2023), EPTA along with InPTA Antoniadis  _et al._ (2023a,
b), and CPTA Xu  _et al._ (2023) have independently announced compelling
evidence for a stochastic signal in their latest data sets. These data sets
demonstrate varying levels of significance in supporting the presence of
Hellings-Downs (HD) Hellings and Downs (1983) spatial correlations as
predicted by general relativity. While the PTA window covers a broad range of
possible sources Li  _et al._ (2019); Vagnozzi (2021); Chen  _et al._ (2021);
Wu  _et al._ (2022a); Chen  _et al._ (2022a); Benetti  _et al._ (2022); Chen
_et al._ (2022b); Ashoorioon  _et al._ (2022); Wu  _et al._ (2022b, 2023a);
Falxa  _et al._ (2023); Wu  _et al._ (2023b); Dandoy  _et al._ (2023); Madge
_et al._ (2023); Bi  _et al._ (2023a); Wu  _et al._ (2023c), the exact origin
of the observed signal remains under active investigation, whether from
astrophysical phenomena or cosmological processes Afzal  _et al._ (2023);
Antoniadis  _et al._ (2023c); King  _et al._ (2023); Niu and Rahat (2023);
Ben-Dayan  _et al._ (2023); Vagnozzi (2023); Fu  _et al._ (2023); Agazie  _et
al._ (2023c); Basilakos  _et al._ (2023a). A variety of sources can
potentially explain the PTA signal Bian  _et al._ (2023); Wu  _et al._
(2023d); Ellis  _et al._ (2023a); Figueroa  _et al._ (2023), including the GW
background (GWB) generated by supermassive black hole binaries Agazie  _et
al._ (2023d); Ellis  _et al._ (2023b); Shen  _et al._ (2023); Bi  _et al._
(2023b); Barausse  _et al._ (2023), domain walls Kitajima  _et al._ (2023);
Blasi  _et al._ (2023); Babichev  _et al._ (2023), cosmic strings Kitajima and
Nakayama (2023); Ellis  _et al._ (2023c); Wang  _et al._ (2023a); Antusch  _et
al._ (2023); Ahmed  _et al._ (2023a, b); Basilakos  _et al._ (2023b); Chen
_et al._ (2023a), phase transitions Addazi  _et al._ (2023); Athron  _et al._
(2023); Zu  _et al._ (2023); Jiang  _et al._ (2023); Xiao  _et al._ (2023);
Abe and Tada (2023); Gouttenoire (2023); An  _et al._ (2023), and scalar-
induced GWs Cai  _et al._ (2020); Yuan  _et al._ (2019, 2020a); Chen  _et al._
(2020); Yuan  _et al._ (2020b); Liu  _et al._ (2023a); Franciolini  _et al._
(2023); Jin  _et al._ (2023); Liu  _et al._ (2023b); Yi  _et al._ (2023a);
Harigaya  _et al._ (2023); Zhao  _et al._ (2023); Balaji  _et al._ (2023);
Wang  _et al._ (2023b); Firouzjahi and Talebian (2023); Wang  _et al._
(2023c); Cai  _et al._ (2023); Liu  _et al._ (2023c); Yi and Zhu (2022); Yi
and Fei (2023); Yi  _et al._ (2023b); You  _et al._ (2023); Yi  _et al._
(2023c) accompanying the formation of primordial black holes Liu  _et al._
(2019a); Chen and Huang (2018); Chen  _et al._ (2019); Chen and Huang (2020);
Liu  _et al._ (2019b, 2020); Wu (2020); Chen  _et al._ (2022c, 2023b); Meng
_et al._ (2023); Lu  _et al._ (2019); Gao  _et al._ (2021); Yi  _et al._
(2021a, b); Yi (2023); Liu  _et al._ (2023d); Chen  _et al._ (2023c); Zheng
_et al._ (2023); Bhaumik  _et al._ (2023); Bousder  _et al._ (2023); Hosseini
Mansoori  _et al._ (2023); Gouttenoire  _et al._ (2023); Huang  _et al._
(2023); Depta  _et al._ (2023).

Identifying a GWB as predicted by general relativity hinges on the observation
of its quintessential quadrupolar characteristics, specifically the HD spatial
correlations within PTA data. To achieve this, it is crucial to conduct a
consistency test to confirm that the signal exhibits clearly quadrupolar
characteristics Allen  _et al._ (2023), thereby ruling out other reasonable
explanations such as the monopolar or dipolar correlations. While the NANOGrav
15-year data set strongly disfavors monopole and dipole signals Agazie  _et
al._ (2023b), it is important to note that this does not exclude the
possibility of alternative GW polarization modes allowed in general metric
theories of gravity. In fact, a most general metric gravity theory can have
two scalar modes and two vector modes in addition to the two tensor modes,
each with distinct correlation patterns Lee  _et al._ (2008); Chamberlin and
Siemens (2012); Gair  _et al._ (2015); Boîtier  _et al._ (2020). It is worth
noting that earlier studies Chen  _et al._ (2021); Arzoumanian  _et al._
(2021); Wu  _et al._ (2022a); Chen  _et al._ (2022a) have tentatively reported
evidence for scalar transverse (ST) correlations. To determine whether the
observed PTA signal indeed originates from a GWB as predicted by general
relativity, it is imperative to fit the data with all plausible correlation
patterns. In this paper, we perform the Bayesian search for the stochastic GWB
signal, modeled by a power-law spectrum with a varying power-law index. Our
analysis considers all the six polarization modes in the NANOGrav 15-year data
set.

##  II Detecting non-tensorial GWBs with PTAs

Pulsar timing experiments take advantage of the regular arrival rates of radio
pulses emitted by extremely stable millisecond pulsars. GWs can perturb the
geodesics of these radio waves, leading to the fluctuations in the TOAs of
radio pulses Sazhin (1978); Detweiler (1979). The presence of a GW will result
in unexplained residuals in the TOAs, even after compensating for a
deterministic timing model that accounts for the pulsar spin behavior and the
geometric effects caused by the motion of the pulsar and the Earth Sazhin
(1978); Detweiler (1979). Through regularly monitoring TOAs of pulsars from an
array of the highly stable millisecond pulsars Foster and Backer (1990), and
analyzing the expected cross-correlations among pulsars in a PTA, it becomes
possible to extract the GW signal from other systematic effects, such as the
clock errors.

The cross-power spectral density of timing residuals induced by a GWB at the
frequency $f$ for two pulsars, $a$ and $b$, can be expressed as Lee  _et al._
(2008); Chamberlin and Siemens (2012); Gair  _et al._ (2015)

$S_{ab}(f)=\sum_{P}\frac{h_{c,P}^{2}}{12\pi^{2}f^{3}}\Gamma^{P}_{ab}(f).$ (1)

Here, $h_{c}^{P}(f)$ represents the characteristic strain, and the summation
encompasses all six possible GW polarizations that can be inherent in a
general metric gravity theory, specifically denoted as $P=+,\times,x,y,l,b$.
The symbols “$+$” and “$\times$” refer to the two spin-2 transverse traceless
polarization modes; “$x$” and “$y$” correspond to the two spin-1 shear modes;
“$l$” designates the spin-0 longitudinal mode; and “$b$” identifies the spin-0
breathing mode. The overlap reduction function (ORF) $\Gamma^{P}_{ab}$ for a
pair of pulsars is defined as Lee  _et al._ (2008); Chamberlin and Siemens
(2012)

$\displaystyle\Gamma^{P}_{ab}(f)=$ $\displaystyle\frac{3}{8\pi}\int
d\hat{\Omega}\left(e^{2\pi ifL_{a}(1+\hat{\Omega}\cdot\hat{p}_{a})}-1\right)$
$\displaystyle\times\left(e^{2\pi
ifL_{b}(1+\hat{\Omega}\cdot\hat{p}_{b})}-1\right)F^{P}_{a}(\hat{\Omega})F^{P}_{b}(\hat{\Omega}),$
(2)

where $\hat{p}$ is the direction of the pulsar with respect to the Earth,
$L_{a}$ and $L_{b}$ are the distance from the Earth to the pulsar $a$ and $b$
respectively, and $\hat{\Omega}$ is the propagating direction of the GW.
Besides, the antenna patterns $F^{P}(\hat{\Omega})$ are expressed as

$F^{P}(\hat{\Omega})=e^{P}_{ij}(\hat{\Omega})\frac{\hat{p}^{i}\hat{p}^{j}}{2(1+\hat{\Omega}\cdot\hat{p})},$
(3)

where $e^{P}_{ij}$ stands for the polarization tensor corresponding to
polarization mode $P$ Lee  _et al._ (2008); Chamberlin and Siemens (2012). As
per the conventions established in Cornish  _et al._ (2018), we define

$\displaystyle\Gamma^{\mathrm{TT}}_{ab}(f)$
$\displaystyle=\Gamma^{+}_{ab}(f)+\Gamma^{\times}_{ab}(f),$ (4)
$\displaystyle\Gamma^{\mathrm{ST}}_{ab}(f)$
$\displaystyle=\Gamma^{b}_{ab}(f),$ (5)
$\displaystyle\Gamma^{\mathrm{VL}}_{ab}(f)$
$\displaystyle=\Gamma^{x}_{ab}(f)+\Gamma^{y}_{ab}(f),$ (6)
$\displaystyle\Gamma^{\mathrm{SL}}_{ab}(f)$
$\displaystyle=\Gamma^{l}_{ab}(f).$ (7)

For the GW polarization modes $\mathrm{TT}$ and $\mathrm{ST}$, the ORFs
exhibit a notable property of being nearly independent of both distance and
frequency, which can be analytically computed by Hellings and Downs (1983);
Lee  _et al._ (2008)

$\displaystyle\Gamma^{\mathrm{TT}}_{ab}(f)$ $\displaystyle=$
$\displaystyle\frac{1}{2}(1+\delta_{ab})+\frac{3}{2}k_{ab}\left(\ln
k_{ab}-\frac{1}{6}\right),$ (8) $\displaystyle\Gamma^{\mathrm{ST}}_{ab}(f)$
$\displaystyle=$
$\displaystyle\frac{1}{8}\left(3+4\delta_{ab}+\cos\zeta_{ab}\right),$ (9)

where $\delta_{ab}$ represents the Kronecker delta symbol, $\zeta_{ab}$
denotes the angular separation between pulsars $a$ and $b$, and
$k_{ab}\equiv(1-\cos\zeta_{ab})/2$. Note that $\Gamma^{\mathrm{TT}}_{ab}$ is
commonly referred to as the HD correlations, which are closely associated with
the quadrupolar nature of GW signals. In contrast, analytical expressions for
the vector longitudinal (VL) and scalar longitudinal (SL) polarization modes
are not readily available. Therefore, we rely on numerical methods to compute
these functions. In this work, we adopt the pulsar distance information
collected in Table 2 of Agazie  _et al._ (2023e) to estimate the ORFs. It’s
worth noting that the ORFs for $\mathrm{TT}$ and $\mathrm{ST}$ polarization
modes only differ by the presence or absence of the term
$\kappa_{ab}\ln\kappa_{ab}$. To generalize these ORFs, we adopt a
parameterized form, following a similar approach as described in Chen  _et
al._ (2022a),

$\Gamma_{ab}=\frac{1}{8}(3+4\delta_{ab}+\cos\xi_{ab})+\frac{\alpha}{2}\kappa_{ab}\ln\kappa_{ab}.$
(10)

Here, the parameter $\alpha$ allows us to seamlessly transition between the
$\mathrm{TT}$ mode (when $\alpha=3$) and the $\mathrm{ST}$ mode (when
$\alpha=0$). For later convenience, we refer to this parameterization as the
“general transverse” (GT). This approach provides a unified framework for
handling these polarization modes with varying values of $\alpha$.

Table 1: Parameters and their prior distributions used in the analyses. parameter | description | prior | comments
---|---|---|---
White Noise
$E_{k}$ | EFAC per backend/receiver system |  Uniform $[0,10]$ | single-pulsar analysis only
$Q_{k}$[s] | EQUAD per backend/receiver system |  log-Uniform $[-8.5,-5]$ | single-pulsar analysis only
$J_{k}$[s] | ECORR per backend/receiver system |  log-Uniform $[-8.5,-5]$ | single-pulsar analysis only
Red Noise
$A_{\rm{RN}}$ | red-noise power-law amplitude |  log-Uniform $[-20,-11]$ | one parameter per pulsar
$\gamma_{\rm{RN}}$ | red-noise power-law spectral index |  Uniform $[0,7]$ | one parameter per pulsar
GWB Process
$\gamma_{I}$ |  power-law index of polarization $I$ |  Uniform $[0,7]$ | one parameter for PTA
$\mathcal{A}_{\mathrm{TT}}$ | GWB amplitude of TT polarization |  log-Uniform $[-18,-14]$ | one parameter for PTA
$\mathcal{A}_{\mathrm{ST}}$ | GWB amplitude of ST polarization |  log-Uniform $[-18,-14]$ | one parameter for PTA
$\mathcal{A}_{\mathrm{VL}}$ | GWB amplitude of VL polarization |  log-Uniform $[-19,-15]$ | one parameter for PTA
$\mathcal{A}_{\mathrm{SL}}$ | GWB amplitude of SL polarization |  log-Uniform $[-20,-16]$ | one parameter for PTA

Since current PTA data is not able to distinguish between various spectral
shapes of the GWB energy density Afzal  _et al._ (2023); Wu  _et al._ (2023d);
Bian  _et al._ (2023), we employ a power-law energy density spectrum in our
analysis. This leads to the following expression:

$S_{ab}(f)=\sum_{I={\mathrm{TT},\mathrm{ST},\mathrm{VL},\mathrm{SL}}}\Gamma^{I}_{ab}\frac{\mathcal{A}_{I}^{2}}{12\pi^{2}}\left(\frac{f}{f_{\mathrm{yr}}}\right)^{-\gamma_{I}}f_{\mathrm{yr}}^{-3},$
(11)

where $\mathcal{A}_{I}$ is the GWB amplitude of polarization mode $I$,
$f_{\mathrm{yr}}=1/\mathrm{year}$, and $\gamma_{I}$ corresponds to the
spectral index for polarization mode $I$ that we treat as a free parameter.
The dimensionless GW energy density parameter per logarithm frequency for the
polarization mode $I$ is related to $\mathcal{A}_{I}$ by, Thrane and Romano
(2013),

$\Omega_{\mathrm{GW}}^{I}(f)=\frac{2\pi^{2}}{3H_{0}^{2}}f^{2}h_{c,I}^{2}=\frac{2\pi^{2}f_{\mathrm{yr}}^{2}}{3H_{0}^{2}}\mathcal{A}_{I}^{2}\left(\frac{f}{f_{\mathrm{yr}}}\right)^{5-\gamma_{I}},$
(12)

where $H_{0}$ is the Hubble constant and we take
$H_{0}=67.4\,\mathrm{km}\sec^{-1}\mathrm{Mpc}^{-1}$ from Planck 2018 Aghanim
_et al._ (2020).

##  III data analysis

The NANOGrav 15-year data set Agazie  _et al._ (2023a) comprises data from
$68$ pulsars. Among these, $67$ pulsars have been observed over a timespan
exceeding three years and are used in the search for the GWB signal Agazie
_et al._ (2023b). Consistent with the NANOGrav approach Agazie  _et al._
(2023b), our analyses focus on the same $67$ pulsars with timing baselines
exceeding three years.

The timing residuals for each individual pulsar, obtained by subtracting the
timing model from the TOAs, can be expressed as Arzoumanian  _et al._ (2016)

$\delta\bm{t}=M\bm{\epsilon}+F\bm{a}+\bm{n}.$ (13)

The term $M\bm{\epsilon}$ serves to accommodate inaccuracies that can arise
during the subtraction of timing model, where $M$ represents the timing model
design matrix, and $\bm{\epsilon}$ is a vector that denotes minor deviations
of the timing model parameters. The term $F\bm{a}$ encompasses all low-
frequency signals, including both the red noise that is intrinsic to each
pulsar and the common red noise signal shared among all pulsars, such as a
GWB. Here, $F$ corresponds to the Fourier design matrix, featuring components
of alternating sine and cosine functions. Given timespan $T$, $\bm{a}$ is a
vector that signifies the amplitude of the Fourier basis functions, and these
functions are associated with specific frequencies of
$\\{1/T,2/T,\cdots,{N_{\text{mode}}}/T\\}$. Similar to NANOGrav Agazie  _et
al._ (2023b), we employ $30$ frequency components to account for the intrinsic
red noise specific to each pulsar, and these are characterized by a power-law
spectrum. Additionally, we utilize $14$ frequency components for the GWB
signal. The final term $\bm{n}$ is responsible for modeling the timing
residuals stemming from white noise, which includes a scale parameter on the
TOA uncertainties (EFAC), an added variance (EQUAD), and a per-epoch variance
(ECORR) for each backend/receiver system Arzoumanian  _et al._ (2016).

Similar to NANOGrav Agazie  _et al._ (2023b), we adopt the JPL solar system
ephemeris (SSE) DE440 Park  _et al._ (2021) as the fiducial SSE. Our Bayesian
parameter inference follows a procedure closely aligned with the one outlined
in Arzoumanian  _et al._ (2018, 2020). The model parameters and their
associated prior distributions are provided in Table 1. In our analyses, we
choose to keep the white noise parameters fixed at their maximum likelihood
values to reduce the computational costs. We use enterprise Ellis  _et al._
(2020) and enterprise_extension Taylor  _et al._ (2021) software packages for
the calculation of likelihood and Bayes factors. For Markov chain Monte Carlo
sampling, we utilize the PTMCMCSampler Ellis and van Haasteren (2017) package.
To expedite the burn-in process for the chains, we employ samples drawn from
empirical distributions to handle the red noise parameters of the pulsars.
These distributions are constructed based on posteriors obtained from an
initial Bayesian analysis that exclusively incorporates the pulsars’ red
noise, excluding any common red noise processes, as carried out in Aggarwal
_et al._ (2019); Arzoumanian  _et al._ (2020).

##  IV Results and discussion

Model | ST | VL | SL | TT + ST | GT-best
---|---|---|---|---|---
BF | $0.40(3)$ | $0.12(2)$ | $0.002(1)$ | $0.943(5)$ | $3.9(3)$
Table 2: The Bayes factors for various models compared to the TT model that
considers the full Hellings-Downs spatial correlations. For all models, we use
the power-law spectrum for the SGWB with a varied power-law index fitted by
the data. The digit in the parentheses gives the uncertainty on the last
quoted digit. Figure 1:  Bayesian posteriors for the amplitude and power-law
index obtained in the ST model. We show the $1\sigma$, $2\sigma$, and
$3\sigma$ contours in the two-dimensional plot. Figure 2:  Bayesian posteriors
for the amplitude and power-law index obtained in the VL model. We show the
$1\sigma$, $2\sigma$, and $3\sigma$ contours in the two-dimensional plot.
Figure 3:  Bayesian posteriors for the amplitude and power-law index obtained
in the SL model. We show the $1\sigma$, $2\sigma$, and $3\sigma$ contours in
the two-dimensional plot.

Our findings are summarized in Table 2, which presents the Bayes factors for
different models compared to the TT model that incorporates the full HD
spatial correlations. The Bayes factor of the ST model relative to the TT
model is $0.40\pm 0.03$, indicating there is no statistically significant
evidence either supporting or refuting the ST correlations over the HD
correlations in the NANOGrav 15-year data set. We obtain the median and the
$90\%$ equal-tail amplitudes as
$\mathcal{A}_{\mathrm{ST}}=7.8^{+5.1}_{-3.5}\times 10^{-15}$ at the reference
frequency $f_{\rm{yr}}$. The posterior distributions for the amplitude
$A_{\mathrm{ST}}$ and the power-law index $\gamma_{\mathrm{ST}}$ are
illustrated in Fig. 1.

The Bayes factor of VL model versus the TT model is $0.12\pm 0.02$, implying
the VL correlations are slightly disfavoured in comparison to the HD
correlations. Additionally, the Bayes factor of SL model relative to the TT
model is $0.002\pm 0.001$, strongly disfavouring the SL correlations compared
to the HD correlations. Consequently, we establish upper limits for the
amplitudes as $\mathcal{A}_{\mathrm{VL}}\lesssim 1.7\times 10^{-15}$ and
$\mathcal{A}_{\mathrm{SL}}\lesssim 7.4\times 10^{-17}$. Note that the
constraint on the amplitude for the SL model is two orders of magnitude
tighter than that from other polarizations, mainly due to the strong auto-
correlations inherent to the SL mode. The posteriors for the VL and SL models
are shown in Fig. 2 and Fig. 3, respectively. Notably, the power-law indexes
derived from different polarizations, namely $\gamma_{\mathrm{ST}}$,
$\gamma_{\mathrm{VL}}$, and $\gamma_{\mathrm{SL}}$, exhibit broad consistency.

Figure 4:  Bayesian posteriors for the amplitude and power-law index obtained
in the TT+ST model. We show the $1\sigma$, $2\sigma$, and $3\sigma$ contours
in the two-dimensional plot. Figure 5:  Bayesian posteriors for the $\alpha$
parameter in the GT model with a parameterized ORF as defined by Eq. (10). The
two vertical dashed lines correspond to the ST ($\alpha=0$) and TT
($\alpha=3$) ORFs, respectively.

We also consider a TT+ST model that simultaneously incorporates both the TT
and ST correlations. The Bayes factor between the TT+ST model and the TT model
is $0.943\pm 0.005$, indicating that there is no significant evidence
supporting or refuting the ST correlations in addition to the HD correlations.
The contour plot and the posterior distributions of the TT and ST components
in the TT+ST model are depicted in Fig. 4. The presence of the peak around
$-14.5$ for the amplitude $\log_{10}A_{\mathrm{ST}}$ confirms that the
NANOGrav data does not rule out the possibility of an ST signal in the data.

To gain further insights into the optimal correlations that best describe the
data, we also fit the NANOGrav 15-year data set with a parameterized ORF (the
GT model) as defined in Eq. (10). The posterior distribution for the free
parameter $\alpha$ is displayed in Fig. 5. Our analysis yields a value of
$\alpha=1.74^{+1.18}_{-1.41}$, thus excluding both the TT and ST models at the
$90\%$ confidence level. However, it is worth noting that the TT and ST models
remain consistent with the NANOGrav 15-year data set at the $3\sigma$
confidence level. Furthermore, the Bayes factor between the GT-best model,
where $\alpha$ is set to the best-fit value, and the TT model is $3.9\pm 0.3$,
confirming that NANOGrav can be better described by the correlations with
$\alpha\simeq 2$ than by the HD correlations with $\alpha=3$.

In summary, our analysis indicates that the NANOGrav 15-year data set can be
effectively described by either the TT correlations or the ST correlations. No
compelling evidence exists to strongly favor one over the other. The current
PTA data cannot provide a definitive verdict on the spatial correlations
within the stochastic signal, thereby posing a challenge for the unequivocal
detection of the SGWB predicted by general relativity through PTAs. We
anticipate that future PTA data with a longer observation timespan and a
larger number of pulsars will provide the necessary insights to pinpoint the
origin of the observed stochastic signal.

## Acknowledgments

We acknowledge the use of HPC Cluster of ITP-CAS. QGH is supported by the
grants from NSFC (Grant No. 12250010, 11975019, 11991052, 12047503), Key
Research Program of Frontier Sciences, CAS, Grant No. ZDBS-LY-7009, the Key
Research Program of the Chinese Academy of Sciences (Grant No. XDPB15). ZCC is
supported by the National Natural Science Foundation of China (Grant No.
12247176) and the China Postdoctoral Science Foundation Fellowship No.
2022M710429.

## References

  * Sazhin (1978) M. V. Sazhin, “Opportunities for detecting ultralong gravitational waves,” Soviet Astronomy 22, 36–38 (1978).
  * Detweiler (1979) Steven L. Detweiler, “Pulsar timing measurements and the search for gravitational waves,” Astrophys. J. 234, 1100–1104 (1979).
  * Foster and Backer (1990) R. S. Foster and D. C. Backer, “Constructing a pulsar timing array,” Astrophys. J. 361, 300–308 (1990).
  * Kramer and Champion (2013) Michael Kramer and David J. Champion (EPTA), “The European Pulsar Timing Array and the Large European Array for Pulsars,” Class. Quant. Grav. 30, 224009 (2013).
  * McLaughlin (2013) Maura A. McLaughlin, “The North American Nanohertz Observatory for Gravitational Waves,” Class. Quant. Grav. 30, 224008 (2013), arXiv:1310.0758 [astro-ph.IM] .
  * Manchester  _et al._ (2013) R. N. Manchester _et al._ , “The Parkes Pulsar Timing Array Project,” Publ. Astron. Soc. Austral. 30, 17 (2013), arXiv:1210.6130 [astro-ph.IM] .
  * Joshi  _et al._ (2018) Bhal Chandra Joshi, Prakash Arumugasamy, Manjari Bagchi, _et al._ , “Precision pulsar timing with the ORT and the GMRT and its applications in pulsar astrophysics,” Journal of Astrophysics and Astronomy 39, 51 (2018).
  * Hobbs  _et al._ (2010) G. Hobbs _et al._ , “The international pulsar timing array project: using pulsars as a gravitational wave detector,” Class. Quant. Grav. 27, 084013 (2010), arXiv:0911.5206 [astro-ph.SR] .
  * Manchester (2013) R. N. Manchester, “The International Pulsar Timing Array,” Class. Quant. Grav. 30, 224010 (2013), arXiv:1309.7392 [astro-ph.IM] .
  * Lee (2016) K. J. Lee, “Prospects of Gravitational Wave Detection Using Pulsar Timing Array for Chinese Future Telescopes,” in  _Frontiers in Radio Astronomy and FAST Early Sciences Symposium 2015_ , Astronomical Society of the Pacific Conference Series, Vol. 502, edited by L. Qain and D. Li (2016) p. 19.
  * Miles  _et al._ (2023) Matthew T. Miles _et al._ , “The MeerKAT Pulsar Timing Array: first data release,” Mon. Not. Roy. Astron. Soc. 519, 3976–3991 (2023), arXiv:2212.04648 [astro-ph.HE] .
  * Agazie  _et al._ (2023a) Gabriella Agazie _et al._ (NANOGrav), “The NANOGrav 15 yr Data Set: Observations and Timing of 68 Millisecond Pulsars,” Astrophys. J. Lett. 951, L9 (2023a), arXiv:2306.16217 [astro-ph.HE] .
  * Agazie  _et al._ (2023b) Gabriella Agazie _et al._ (NANOGrav), “The NANOGrav 15 yr Data Set: Evidence for a Gravitational-wave Background,” Astrophys. J. Lett. 951, L8 (2023b), arXiv:2306.16213 [astro-ph.HE] .
  * Zic  _et al._ (2023) Andrew Zic _et al._ , “The Parkes Pulsar Timing Array Third Data Release,” (2023), arXiv:2306.16230 [astro-ph.HE] .
  * Reardon  _et al._ (2023) Daniel J. Reardon _et al._ , “Search for an Isotropic Gravitational-wave Background with the Parkes Pulsar Timing Array,” Astrophys. J. Lett. 951, L6 (2023), arXiv:2306.16215 [astro-ph.HE] .
  * Antoniadis  _et al._ (2023a) J. Antoniadis _et al._ (EPTA), “The second data release from the European Pulsar Timing Array I. The dataset and timing analysis,” Astron. Astrophys. 678, A48 (2023a), arXiv:2306.16224 [astro-ph.HE] .
  * Antoniadis  _et al._ (2023b) J. Antoniadis _et al._ (EPTA), “The second data release from the European Pulsar Timing Array III. Search for gravitational wave signals,” Astron. Astrophys. 678, A50 (2023b), arXiv:2306.16214 [astro-ph.HE] .
  * Xu  _et al._ (2023) Heng Xu _et al._ , “Searching for the Nano-Hertz Stochastic Gravitational Wave Background with the Chinese Pulsar Timing Array Data Release I,” Res. Astron. Astrophys. 23, 075024 (2023), arXiv:2306.16216 [astro-ph.HE] .
  * Hellings and Downs (1983) R. w. Hellings and G. s. Downs, “UPPER LIMITS ON THE ISOTROPIC GRAVITATIONAL RADIATION BACKGROUND FROM PULSAR TIMING ANALYSIS,” Astrophys. J. Lett. 265, L39–L42 (1983).
  * Li  _et al._ (2019) Jun Li, Zu-Cheng Chen, and Qing-Guo Huang, “Measuring the tilt of primordial gravitational-wave power spectrum from observations,” Sci. China Phys. Mech. Astron. 62, 110421 (2019), [Erratum: Sci.China Phys.Mech.Astron. 64, 250451 (2021)], arXiv:1907.09794 [astro-ph.CO] .
  * Vagnozzi (2021) Sunny Vagnozzi, “Implications of the NANOGrav results for inflation,” Mon. Not. Roy. Astron. Soc. 502, L11–L15 (2021), arXiv:2009.13432 [astro-ph.CO] .
  * Chen  _et al._ (2021) Zu-Cheng Chen, Chen Yuan, and Qing-Guo Huang, “Non-tensorial gravitational wave background in NANOGrav 12.5-year data set,” Sci. China Phys. Mech. Astron. 64, 120412 (2021), arXiv:2101.06869 [astro-ph.CO] .
  * Wu  _et al._ (2022a) Yu-Mei Wu, Zu-Cheng Chen, and Qing-Guo Huang, “Constraining the Polarization of Gravitational Waves with the Parkes Pulsar Timing Array Second Data Release,” Astrophys. J. 925, 37 (2022a), arXiv:2108.10518 [astro-ph.CO] .
  * Chen  _et al._ (2022a) Zu-Cheng Chen, Yu-Mei Wu, and Qing-Guo Huang, “Searching for isotropic stochastic gravitational-wave background in the international pulsar timing array second data release,” Commun. Theor. Phys. 74, 105402 (2022a), arXiv:2109.00296 [astro-ph.CO] .
  * Benetti  _et al._ (2022) Micol Benetti, Leila Lobato Graef, and Sunny Vagnozzi, “Primordial gravitational waves from NANOGrav: A broken power-law approach,” Phys. Rev. D 105, 043520 (2022), arXiv:2111.04758 [astro-ph.CO] .
  * Chen  _et al._ (2022b) Zu-Cheng Chen, Yu-Mei Wu, and Qing-Guo Huang, “Search for the Gravitational-wave Background from Cosmic Strings with the Parkes Pulsar Timing Array Second Data Release,” Astrophys. J. 936, 20 (2022b), arXiv:2205.07194 [astro-ph.CO] .
  * Ashoorioon  _et al._ (2022) Amjad Ashoorioon, Kazem Rezazadeh, and Abasalt Rostami, “NANOGrav signal from the end of inflation and the LIGO mass and heavier primordial black holes,” Phys. Lett. B 835, 137542 (2022), arXiv:2202.01131 [astro-ph.CO] .
  * Wu  _et al._ (2022b) Yu-Mei Wu, Zu-Cheng Chen, Qing-Guo Huang, Xingjiang Zhu, N. D. Ramesh Bhat, Yi Feng, George Hobbs, Richard N. Manchester, Christopher J. Russell, and R. M. Shannon (PPTA), “Constraining ultralight vector dark matter with the Parkes Pulsar Timing Array second data release,” Phys. Rev. D 106, L081101 (2022b), arXiv:2210.03880 [astro-ph.CO] .
  * Wu  _et al._ (2023a) Yu-Mei Wu, Zu-Cheng Chen, and Qing-Guo Huang, “Search for stochastic gravitational-wave background from massive gravity in the NANOGrav 12.5-year dataset,” Phys. Rev. D 107, 042003 (2023a), arXiv:2302.00229 [gr-qc] .
  * Falxa  _et al._ (2023) M. Falxa _et al._ (IPTA), “Searching for continuous Gravitational Waves in the second data release of the International Pulsar Timing Array,” Mon. Not. Roy. Astron. Soc. 521, 5077–5086 (2023), arXiv:2303.10767 [gr-qc] .
  * Wu  _et al._ (2023b) Yu-Mei Wu, Zu-Cheng Chen, and Qing-Guo Huang, “Pulsar timing residual induced by ultralight tensor dark matter,” JCAP 09, 021 (2023b), arXiv:2305.08091 [hep-ph] .
  * Dandoy  _et al._ (2023) Virgile Dandoy, Valerie Domcke, and Fabrizio Rompineve, “Search for scalar induced gravitational waves in the International Pulsar Timing Array Data Release 2 and NANOgrav 12.5 years datasets,” SciPost Phys. Core 6, 060 (2023), arXiv:2302.07901 [astro-ph.CO] .
  * Madge  _et al._ (2023) Eric Madge, Enrico Morgante, Cristina Puchades-Ibáñez, Nicklas Ramberg, Wolfram Ratzinger, Sebastian Schenk, and Pedro Schwaller, “Primordial gravitational waves in the nano-Hertz regime and PTA data – towards solving the GW inverse problem,” (2023), arXiv:2306.14856 [hep-ph] .
  * Bi  _et al._ (2023a) Yan-Chen Bi, Yu-Mei Wu, Zu-Cheng Chen, and Qing-Guo Huang, “Constraints on the velocity of gravitational waves from NANOGrav 15-year data set,” (2023a), arXiv:2310.08366 [astro-ph.CO] .
  * Wu  _et al._ (2023c) Yu-Mei Wu, Zu-Cheng Chen, Yan-Chen Bi, and Qing-Guo Huang, “Constraining the Graviton Mass with the NANOGrav 15-Year Data Set,” (2023c), arXiv:2310.07469 [astro-ph.CO] .
  * Afzal  _et al._ (2023) Adeela Afzal _et al._ (NANOGrav), “The NANOGrav 15 yr Data Set: Search for Signals from New Physics,” Astrophys. J. Lett. 951, L11 (2023), arXiv:2306.16219 [astro-ph.HE] .
  * Antoniadis  _et al._ (2023c) J. Antoniadis _et al._ (EPTA), “The second data release from the European Pulsar Timing Array: V. Implications for massive black holes, dark matter and the early Universe,” (2023c), arXiv:2306.16227 [astro-ph.CO] .
  * King  _et al._ (2023) Stephen F. King, Danny Marfatia, and Moinul Hossain Rahat, “Towards distinguishing Dirac from Majorana neutrino mass with gravitational waves,” (2023), arXiv:2306.05389 [hep-ph] .
  * Niu and Rahat (2023) Xuce Niu and Moinul Hossain Rahat, “NANOGrav signal from axion inflation,” (2023), arXiv:2307.01192 [hep-ph] .
  * Ben-Dayan  _et al._ (2023) Ido Ben-Dayan, Utkarsh Kumar, Udaykrishna Thattarampilly, and Amresh Verma, “Probing The Early Universe Cosmology With NANOGrav: Possibilities and Limitations,” (2023), arXiv:2307.15123 [astro-ph.CO] .
  * Vagnozzi (2023) Sunny Vagnozzi, “Inflationary interpretation of the stochastic gravitational wave background signal detected by pulsar timing array experiments,” JHEAp 39, 81–98 (2023), arXiv:2306.16912 [astro-ph.CO] .
  * Fu  _et al._ (2023) Chengjie Fu, Jing Liu, Xing-Yu Yang, Wang-Wei Yu, and Yawen Zhang, “Explaining Pulsar Timing Array Observations with Primordial Gravitational Waves in Parity-Violating Gravity,” (2023), arXiv:2308.15329 [astro-ph.CO] .
  * Agazie  _et al._ (2023c) G. Agazie _et al._ (International Pulsar Timing Array), “Comparing recent PTA results on the nanohertz stochastic gravitational wave background,” (2023c), arXiv:2309.00693 [astro-ph.HE] .
  * Basilakos  _et al._ (2023a) Spyros Basilakos, Dimitri V. Nanopoulos, Theodoros Papanikolaou, Emmanuel N. Saridakis, and Charalampos Tzerefos, “Induced gravitational waves from flipped SU(5) superstring theory at $\mathrm{nHz}$,” (2023a), arXiv:2309.15820 [astro-ph.CO] .
  * Bian  _et al._ (2023) Ligong Bian, Shuailiang Ge, Jing Shu, Bo Wang, Xing-Yu Yang, and Junchao Zong, “Gravitational wave sources for Pulsar Timing Arrays,” (2023), arXiv:2307.02376 [astro-ph.HE] .
  * Wu  _et al._ (2023d) Yu-Mei Wu, Zu-Cheng Chen, and Qing-Guo Huang, “Cosmological Interpretation for the Stochastic Signal in Pulsar Timing Arrays,” (2023d), arXiv:2307.03141 [astro-ph.CO] .
  * Ellis  _et al._ (2023a) John Ellis, Malcolm Fairbairn, Gabriele Franciolini, Gert Hütsi, Antonio Iovino, Marek Lewicki, Martti Raidal, Juan Urrutia, Ville Vaskonen, and Hardi Veermäe, “What is the source of the PTA GW signal?” (2023a), arXiv:2308.08546 [astro-ph.CO] .
  * Figueroa  _et al._ (2023) Daniel G. Figueroa, Mauro Pieroni, Angelo Ricciardone, and Peera Simakachorn, “Cosmological Background Interpretation of Pulsar Timing Array Data,” (2023), arXiv:2307.02399 [astro-ph.CO] .
  * Agazie  _et al._ (2023d) Gabriella Agazie _et al._ (NANOGrav), “The NANOGrav 15 yr Data Set: Constraints on Supermassive Black Hole Binaries from the Gravitational-wave Background,” Astrophys. J. Lett. 952, L37 (2023d), arXiv:2306.16220 [astro-ph.HE] .
  * Ellis  _et al._ (2023b) John Ellis, Malcolm Fairbairn, Gert Hütsi, Juhan Raidal, Juan Urrutia, Ville Vaskonen, and Hardi Veermäe, “Gravitational Waves from SMBH Binaries in Light of the NANOGrav 15-Year Data,” (2023b), arXiv:2306.17021 [astro-ph.CO] .
  * Shen  _et al._ (2023) Zhao-Qiang Shen, Guan-Wen Yuan, Yi-Ying Wang, and Yuan-Zhu Wang, “Dark Matter Spike surrounding Supermassive Black Holes Binary and the nanohertz Stochastic Gravitational Wave Background,” (2023), arXiv:2306.17143 [astro-ph.HE] .
  * Bi  _et al._ (2023b) Yan-Chen Bi, Yu-Mei Wu, Zu-Cheng Chen, and Qing-Guo Huang, “Implications for the Supermassive Black Hole Binaries from the NANOGrav 15-year Data Set,” (2023b), arXiv:2307.00722 [astro-ph.CO] .
  * Barausse  _et al._ (2023) Enrico Barausse, Kallol Dey, Marco Crisostomi, Akshay Panayada, Sylvain Marsat, and Soumen Basak, “The PTA detections: implications for LISA massive black hole mergers,” (2023), arXiv:2307.12245 [astro-ph.GA] .
  * Kitajima  _et al._ (2023) Naoya Kitajima, Junseok Lee, Kai Murai, Fuminobu Takahashi, and Wen Yin, “Gravitational Waves from Domain Wall Collapse, and Application to Nanohertz Signals with QCD-coupled Axions,” (2023), arXiv:2306.17146 [hep-ph] .
  * Blasi  _et al._ (2023) Simone Blasi, Alberto Mariotti, Aäron Rase, and Alexander Sevrin, “Axionic domain walls at Pulsar Timing Arrays: QCD bias and particle friction,” (2023), arXiv:2306.17830 [hep-ph] .
  * Babichev  _et al._ (2023) E. Babichev, D. Gorbunov, S. Ramazanov, R. Samanta, and A. Vikman, “NANOGrav spectral index $\gamma=3$ from melting domain walls,” (2023), arXiv:2307.04582 [hep-ph] .
  * Kitajima and Nakayama (2023) Naoya Kitajima and Kazunori Nakayama, “Nanohertz gravitational waves from cosmic strings and dark photon dark matter,” Phys. Lett. B 846, 138213 (2023), arXiv:2306.17390 [hep-ph] .
  * Ellis  _et al._ (2023c) John Ellis, Marek Lewicki, Chunshan Lin, and Ville Vaskonen, “Cosmic Superstrings Revisited in Light of NANOGrav 15-Year Data,” (2023c), arXiv:2306.17147 [astro-ph.CO] .
  * Wang  _et al._ (2023a) Ziwei Wang, Lei Lei, Hao Jiao, Lei Feng, and Yi-Zhong Fan, “The nanohertz stochastic gravitational-wave background from cosmic string Loops and the abundant high redshift massive galaxies,” (2023a), arXiv:2306.17150 [astro-ph.HE] .
  * Antusch  _et al._ (2023) Stefan Antusch, Kevin Hinze, Shaikh Saad, and Jonathan Steiner, “Singling out SO(10) GUT models using recent PTA results,” (2023), arXiv:2307.04595 [hep-ph] .
  * Ahmed  _et al._ (2023a) Waqas Ahmed, Talal Ahmed Chowdhury, Salah Nasri, and Shaikh Saad, “Gravitational waves from metastable cosmic strings in Pati-Salam model in light of new pulsar timing array data,” (2023a), arXiv:2308.13248 [hep-ph] .
  * Ahmed  _et al._ (2023b) Waqas Ahmed, Mansoor Ur Rehman, and Umer Zubair, “Probing Stochastic Gravitational Wave Background from $SU(5)\times U(1)_{\chi}$ Strings in Light of NANOGrav 15-Year Data,” (2023b), arXiv:2308.09125 [hep-ph] .
  * Basilakos  _et al._ (2023b) Spyros Basilakos, Dimitri V. Nanopoulos, Theodoros Papanikolaou, Emmanuel N. Saridakis, and Charalampos Tzerefos, “Gravitational wave signatures of no-scale Supergravity in NANOGrav and beyond,” (2023b), arXiv:2307.08601 [hep-th] .
  * Chen  _et al._ (2023a) Zu-Cheng Chen, Qing-Guo Huang, Chang Liu, Lang Liu, Xiao-Jin Liu, You Wu, Yu-Mei Wu, Zhu Yi, and Zhi-Qiang You, “Prospects for Taiji to detect a gravitational-wave background from cosmic strings,” (2023a), arXiv:2310.00411 [astro-ph.IM] .
  * Addazi  _et al._ (2023) Andrea Addazi, Yi-Fu Cai, Antonino Marciano, and Luca Visinelli, “Have pulsar timing array methods detected a cosmological phase transition?” (2023), arXiv:2306.17205 [astro-ph.CO] .
  * Athron  _et al._ (2023) Peter Athron, Andrew Fowlie, Chih-Ting Lu, Lachlan Morris, Lei Wu, Yongcheng Wu, and Zhongxiu Xu, “Can supercooled phase transitions explain the gravitational wave background observed by pulsar timing arrays?” (2023), arXiv:2306.17239 [hep-ph] .
  * Zu  _et al._ (2023) Lei Zu, Chi Zhang, Yao-Yu Li, Yu-Chao Gu, Yue-Lin Sming Tsai, and Yi-Zhong Fan, “Mirror QCD phase transition as the origin of the nanohertz Stochastic Gravitational-Wave Background,” (2023), arXiv:2306.16769 [astro-ph.HE] .
  * Jiang  _et al._ (2023) Siyu Jiang, Aidi Yang, Jiucheng Ma, and Fa Peng Huang, “Implication of nano-Hertz stochastic gravitational wave on dynamical dark matter through a first-order phase transition,” (2023), arXiv:2306.17827 [hep-ph] .
  * Xiao  _et al._ (2023) Yang Xiao, Jin Min Yang, and Yang Zhang, “Implications of Nano-Hertz Gravitational Waves on Electroweak Phase Transition in the Singlet Dark Matter Model,” (2023), arXiv:2307.01072 [hep-ph] .
  * Abe and Tada (2023) Katsuya T. Abe and Yuichiro Tada, “Translating nano-Hertz gravitational wave background into primordial perturbations taking account of the cosmological QCD phase transition,” (2023), arXiv:2307.01653 [astro-ph.CO] .
  * Gouttenoire (2023) Yann Gouttenoire, “First-order Phase Transition interpretation of PTA signal produces solar-mass Black Holes,” (2023), arXiv:2307.04239 [hep-ph] .
  * An  _et al._ (2023) Haipeng An, Boye Su, Hanwen Tai, Lian-Tao Wang, and Chen Yang, “Phase transition during inflation and the gravitational wave signal at pulsar timing arrays,” (2023), arXiv:2308.00070 [astro-ph.CO] .
  * Cai  _et al._ (2020) Rong-Gen Cai, Zong-Kuan Guo, Jing Liu, Lang Liu, and Xing-Yu Yang, “Primordial black holes and gravitational waves from parametric amplification of curvature perturbations,” JCAP 06, 013 (2020), arXiv:1912.10437 [astro-ph.CO] .
  * Yuan  _et al._ (2019) Chen Yuan, Zu-Cheng Chen, and Qing-Guo Huang, “Probing primordial–black-hole dark matter with scalar induced gravitational waves,” Phys. Rev. D 100, 081301 (2019), arXiv:1906.11549 [astro-ph.CO] .
  * Yuan  _et al._ (2020a) Chen Yuan, Zu-Cheng Chen, and Qing-Guo Huang, “Log-dependent slope of scalar induced gravitational waves in the infrared regions,” Phys. Rev. D 101, 043019 (2020a), arXiv:1910.09099 [astro-ph.CO] .
  * Chen  _et al._ (2020) Zu-Cheng Chen, Chen Yuan, and Qing-Guo Huang, “Pulsar Timing Array Constraints on Primordial Black Holes with NANOGrav 11-Year Dataset,” Phys. Rev. Lett. 124, 251101 (2020), arXiv:1910.12239 [astro-ph.CO] .
  * Yuan  _et al._ (2020b) Chen Yuan, Zu-Cheng Chen, and Qing-Guo Huang, “Scalar induced gravitational waves in different gauges,” Phys. Rev. D 101, 063018 (2020b), arXiv:1912.00885 [astro-ph.CO] .
  * Liu  _et al._ (2023a) Lang Liu, Xing-Yu Yang, Zong-Kuan Guo, and Rong-Gen Cai, “Testing primordial black hole and measuring the Hubble constant with multiband gravitational-wave observations,” JCAP 01, 006 (2023a), arXiv:2112.05473 [astro-ph.CO] .
  * Franciolini  _et al._ (2023) Gabriele Franciolini, Antonio Iovino, Junior., Ville Vaskonen, and Hardi Veermae, “The recent gravitational wave observation by pulsar timing arrays and primordial black holes: the importance of non-gaussianities,” (2023), arXiv:2306.17149 [astro-ph.CO] .
  * Jin  _et al._ (2023) Jia-Heng Jin, Zu-Cheng Chen, Zhu Yi, Zhi-Qiang You, Lang Liu, and You Wu, “Confronting sound speed resonance with pulsar timing arrays,” JCAP 09, 016 (2023), arXiv:2307.08687 [astro-ph.CO] .
  * Liu  _et al._ (2023b) Lang Liu, Zu-Cheng Chen, and Qing-Guo Huang, “Probing the equation of state of the early Universe with pulsar timing arrays,” (2023b), arXiv:2307.14911 [astro-ph.CO] .
  * Yi  _et al._ (2023a) Zhu Yi, Zhi-Qiang You, You Wu, Zu-Cheng Chen, and Lang Liu, “Exploring the NANOGrav Signal and Planet-mass Primordial Black Holes through Higgs Inflation,” (2023a), arXiv:2308.14688 [astro-ph.CO] .
  * Harigaya  _et al._ (2023) Keisuke Harigaya, Keisuke Inomata, and Takahiro Terada, “Induced Gravitational Waves with Kination Era for Recent Pulsar Timing Array Signals,” (2023), arXiv:2309.00228 [astro-ph.CO] .
  * Zhao  _et al._ (2023) Zhi-Chao Zhao, Qing-Hua Zhu, Sai Wang, and Xin Zhang, “Exploring the Equation of State of the Early Universe: Insights from BBN, CMB, and PTA Observations,” (2023), arXiv:2307.13574 [astro-ph.CO] .
  * Balaji  _et al._ (2023) Shyam Balaji, Guillem Domènech, and Gabriele Franciolini, “Scalar-induced gravitational wave interpretation of PTA data: the role of scalar fluctuation propagation speed,” JCAP 10, 041 (2023), arXiv:2307.08552 [gr-qc] .
  * Wang  _et al._ (2023b) Sai Wang, Zhi-Chao Zhao, Jun-Peng Li, and Qing-Hua Zhu, “Implications of Pulsar Timing Array Data for Scalar-Induced Gravitational Waves and Primordial Black Holes: Primordial Non-Gaussianity $f_{\mathrm{NL}}$ Considered,” (2023b), arXiv:2307.00572 [astro-ph.CO] .
  * Firouzjahi and Talebian (2023) Hassan Firouzjahi and Alireza Talebian, “Induced gravitational waves from ultra slow-roll inflation and pulsar timing arrays observations,” JCAP 10, 032 (2023), arXiv:2307.03164 [gr-qc] .
  * Wang  _et al._ (2023c) Sai Wang, Zhi-Chao Zhao, and Qing-Hua Zhu, “Constraints On Scalar-Induced Gravitational Waves Up To Third Order From Joint Analysis of BBN, CMB, And PTA Data,” (2023c), arXiv:2307.03095 [astro-ph.CO] .
  * Cai  _et al._ (2023) Yi-Fu Cai, Xin-Chen He, Xiaohan Ma, Sheng-Feng Yan, and Guan-Wen Yuan, “Limits on scalar-induced gravitational waves from the stochastic background by pulsar timing array observations,” (2023), arXiv:2306.17822 [gr-qc] .
  * Liu  _et al._ (2023c) Lang Liu, Zu-Cheng Chen, and Qing-Guo Huang, “Implications for the non-Gaussianity of curvature perturbation from pulsar timing arrays,” (2023c), arXiv:2307.01102 [astro-ph.CO] .
  * Yi and Zhu (2022) Zhu Yi and Zong-Hong Zhu, “NANOGrav signal and LIGO-Virgo primordial black holes from the Higgs field,” JCAP 05, 046 (2022), arXiv:2105.01943 [gr-qc] .
  * Yi and Fei (2023) Zhu Yi and Qin Fei, “Constraints on primordial curvature spectrum from primordial black holes and scalar-induced gravitational waves,” Eur. Phys. J. C 83, 82 (2023), arXiv:2210.03641 [astro-ph.CO] .
  * Yi  _et al._ (2023b) Zhu Yi, Zhi-Qiang You, and You Wu, “Model-independent reconstruction of the primordial curvature power spectrum from PTA data,” (2023b), arXiv:2308.05632 [astro-ph.CO] .
  * You  _et al._ (2023) Zhi-Qiang You, Zhu Yi, and You Wu, “Constraints on primordial curvature power spectrum with pulsar timing arrays,” (2023), arXiv:2307.04419 [gr-qc] .
  * Yi  _et al._ (2023c) Zhu Yi, Qing Gao, Yungui Gong, Yue Wang, and Fengge Zhang, “The waveform of the scalar induced gravitational waves in light of Pulsar Timing Array data,” (2023c), arXiv:2307.02467 [gr-qc] .
  * Liu  _et al._ (2019a) Lang Liu, Zong-Kuan Guo, and Rong-Gen Cai, “Effects of the surrounding primordial black holes on the merger rate of primordial black hole binaries,” Phys. Rev. D 99, 063523 (2019a), arXiv:1812.05376 [astro-ph.CO] .
  * Chen and Huang (2018) Zu-Cheng Chen and Qing-Guo Huang, “Merger Rate Distribution of Primordial-Black-Hole Binaries,” Astrophys. J. 864, 61 (2018), arXiv:1801.10327 [astro-ph.CO] .
  * Chen  _et al._ (2019) Zu-Cheng Chen, Fan Huang, and Qing-Guo Huang, “Stochastic Gravitational-wave Background from Binary Black Holes and Binary Neutron Stars and Implications for LISA,” Astrophys. J. 871, 97 (2019), arXiv:1809.10360 [gr-qc] .
  * Chen and Huang (2020) Zu-Cheng Chen and Qing-Guo Huang, “Distinguishing Primordial Black Holes from Astrophysical Black Holes by Einstein Telescope and Cosmic Explorer,” JCAP 08, 039 (2020), arXiv:1904.02396 [astro-ph.CO] .
  * Liu  _et al._ (2019b) Lang Liu, Zong-Kuan Guo, and Rong-Gen Cai, “Effects of the merger history on the merger rate density of primordial black hole binaries,” Eur. Phys. J. C 79, 717 (2019b), arXiv:1901.07672 [astro-ph.CO] .
  * Liu  _et al._ (2020) Lang Liu, Zong-Kuan Guo, Rong-Gen Cai, and Sang Pyo Kim, “Merger rate distribution of primordial black hole binaries with electric charges,” Phys. Rev. D 102, 043508 (2020), arXiv:2001.02984 [astro-ph.CO] .
  * Wu (2020) You Wu, “Merger history of primordial black-hole binaries,” Phys. Rev. D 101, 083008 (2020), arXiv:2001.03833 [astro-ph.CO] .
  * Chen  _et al._ (2022c) Zu-Cheng Chen, Chen Yuan, and Qing-Guo Huang, “Confronting the primordial black hole scenario with the gravitational-wave events detected by LIGO-Virgo,” Phys. Lett. B 829, 137040 (2022c), arXiv:2108.11740 [astro-ph.CO] .
  * Chen  _et al._ (2023b) Zu-Cheng Chen, Sang Pyo Kim, and Lang Liu, “Gravitational and electromagnetic radiation from binary black holes with electric and magnetic charges: hyperbolic orbits on a cone,” Commun. Theor. Phys. 75, 065401 (2023b), arXiv:2210.15564 [gr-qc] .
  * Meng  _et al._ (2023) De-Shuang Meng, Chen Yuan, and Qing-Guo Huang, “Primordial black holes generated by the non-minimal spectator field,” Sci. China Phys. Mech. Astron. 66, 280411 (2023), arXiv:2212.03577 [astro-ph.CO] .
  * Lu  _et al._ (2019) Yizhou Lu, Yungui Gong, Zhu Yi, and Fengge Zhang, “Constraints on primordial curvature perturbations from primordial black hole dark matter and secondary gravitational waves,” JCAP 12, 031 (2019), arXiv:1907.11896 [gr-qc] .
  * Gao  _et al._ (2021) Qing Gao, Yungui Gong, and Zhu Yi, “Primordial black holes and secondary gravitational waves from natural inflation,” Nucl. Phys. B 969, 115480 (2021), arXiv:2012.03856 [gr-qc] .
  * Yi  _et al._ (2021a) Zhu Yi, Qing Gao, Yungui Gong, and Zong-hong Zhu, “Primordial black holes and scalar-induced secondary gravitational waves from inflationary models with a noncanonical kinetic term,” Phys. Rev. D 103, 063534 (2021a), arXiv:2011.10606 [astro-ph.CO] .
  * Yi  _et al._ (2021b) Zhu Yi, Yungui Gong, Bin Wang, and Zong-hong Zhu, “Primordial black holes and secondary gravitational waves from the Higgs field,” Phys. Rev. D 103, 063535 (2021b), arXiv:2007.09957 [gr-qc] .
  * Yi (2023) Zhu Yi, “Primordial black holes and scalar-induced gravitational waves from the generalized Brans-Dicke theory,” JCAP 03, 048 (2023), arXiv:2206.01039 [gr-qc] .
  * Liu  _et al._ (2023d) Lang Liu, Zhi-Qiang You, You Wu, and Zu-Cheng Chen, “Constraining the merger history of primordial-black-hole binaries from GWTC-3,” Phys. Rev. D 107, 063035 (2023d), arXiv:2210.16094 [astro-ph.CO] .
  * Chen  _et al._ (2023c) Zu-Cheng Chen, Shen-Shi Du, Qing-Guo Huang, and Zhi-Qiang You, “Constraints on primordial-black-hole population and cosmic expansion history from GWTC-3,” JCAP 03, 024 (2023c), arXiv:2205.11278 [astro-ph.CO] .
  * Zheng  _et al._ (2023) Li-Ming Zheng, Zhengxiang Li, Zu-Cheng Chen, Huan Zhou, and Zong-Hong Zhu, “Towards a reliable reconstruction of the power spectrum of primordial curvature perturbation on small scales from GWTC-3,” Phys. Lett. B 838, 137720 (2023), arXiv:2212.05516 [astro-ph.CO] .
  * Bhaumik  _et al._ (2023) Nilanjandev Bhaumik, Rajeev Kumar Jain, and Marek Lewicki, “Ultra-low mass PBHs in the early universe can explain the PTA signal,” (2023), arXiv:2308.07912 [astro-ph.CO] .
  * Bousder  _et al._ (2023) M. Bousder, A. Riadsolh, A. El Fatimy, M. El Belkacemi, and H. Ez-Zahraouy, “Implications of the NANOGrav results for primordial black holes and Hubble tension,” (2023), arXiv:2307.10940 [gr-qc] .
  * Hosseini Mansoori  _et al._ (2023) Seyed Ali Hosseini Mansoori, Fereshteh Felegray, Alireza Talebian, and Mohammad Sami, “PBHs and GWs from $\mathbb{T}$2-inflation and NANOGrav 15-year data,” JCAP 08, 067 (2023), arXiv:2307.06757 [astro-ph.CO] .
  * Gouttenoire  _et al._ (2023) Yann Gouttenoire, Sokratis Trifinopoulos, Georgios Valogiannis, and Miguel Vanvlasselaer, “Scrutinizing the Primordial Black Holes Interpretation of PTA Gravitational Waves and JWST Early Galaxies,” (2023), arXiv:2307.01457 [astro-ph.CO] .
  * Huang  _et al._ (2023) Hai-Long Huang, Yong Cai, Jun-Qian Jiang, Jun Zhang, and Yun-Song Piao, “Supermassive primordial black holes in multiverse: for nano-Hertz gravitational wave and high-redshift JWST galaxies,” (2023), arXiv:2306.17577 [gr-qc] .
  * Depta  _et al._ (2023) Paul Frederik Depta, Kai Schmidt-Hoberg, Pedro Schwaller, and Carlo Tasillo, “Do pulsar timing arrays observe merging primordial black holes?” (2023), arXiv:2306.17836 [astro-ph.CO] .
  * Allen  _et al._ (2023) Bruce Allen, Sanjeev Dhurandhar, Yashwant Gupta, Maura McLaughlin, Priyamvada Natarajan, Ryan M. Shannon, Eric Thrane, and Alberto Vecchio, “The International Pulsar Timing Array checklist for the detection of nanohertz gravitational waves,” (2023), arXiv:2304.04767 [astro-ph.IM] .
  * Lee  _et al._ (2008) K. J. Lee, F. A. Jenet, and Richard H. Price, “Pulsar Timing as a Probe of Non-Einsteinian Polarizations of Gravitational Waves,” Astrophys. J. 685, 1304–1319 (2008).
  * Chamberlin and Siemens (2012) Sydney J. Chamberlin and Xavier Siemens, “Stochastic backgrounds in alternative theories of gravity: overlap reduction functions for pulsar timing arrays,” Phys. Rev. D 85, 082001 (2012), arXiv:1111.5661 [astro-ph.HE] .
  * Gair  _et al._ (2015) Jonathan R. Gair, Joseph D. Romano, and Stephen R. Taylor, “Mapping gravitational-wave backgrounds of arbitrary polarisation using pulsar timing arrays,” Phys. Rev. D 92, 102003 (2015), arXiv:1506.08668 [gr-qc] .
  * Boîtier  _et al._ (2020) Adrian Boîtier, Shubhanshu Tiwari, Lionel Philippoz, and Philippe Jetzer, “Pulse redshift of pulsar timing array signals for all possible gravitational wave polarizations in modified general relativity,” Phys. Rev. D 102, 064051 (2020), arXiv:2008.13520 [gr-qc] .
  * Arzoumanian  _et al._ (2021) Zaven Arzoumanian _et al._ (NANOGrav), “The NANOGrav 12.5-year Data Set: Search for Non-Einsteinian Polarization Modes in the Gravitational-wave Background,” Astrophys. J. Lett. 923, L22 (2021), arXiv:2109.14706 [gr-qc] .
  * Cornish  _et al._ (2018) Neil J. Cornish, Logan O’Beirne, Stephen R. Taylor, and Nicolás Yunes, “Constraining alternative theories of gravity using pulsar timing arrays,” Phys. Rev. Lett. 120, 181101 (2018), arXiv:1712.07132 [gr-qc] .
  * Agazie  _et al._ (2023e) Gabriella Agazie _et al._ (NANOGrav), “The NANOGrav 15 yr Data Set: Bayesian Limits on Gravitational Waves from Individual Supermassive Black Hole Binaries,” Astrophys. J. Lett. 951, L50 (2023e), arXiv:2306.16222 [astro-ph.HE] .
  * Thrane and Romano (2013) Eric Thrane and Joseph D. Romano, “Sensitivity curves for searches for gravitational-wave backgrounds,” Phys. Rev. D 88, 124032 (2013), arXiv:1310.5300 [astro-ph.IM] .
  * Aghanim  _et al._ (2020) N. Aghanim _et al._ (Planck), “Planck 2018 results. VI. Cosmological parameters,” Astron. Astrophys. 641, A6 (2020), [Erratum: Astron.Astrophys. 652, C4 (2021)], arXiv:1807.06209 [astro-ph.CO] .
  * Arzoumanian  _et al._ (2016) Z. Arzoumanian _et al._ (NANOGrav), “The NANOGrav Nine-year Data Set: Limits on the Isotropic Stochastic Gravitational Wave Background,” Astrophys. J. 821, 13 (2016), arXiv:1508.03024 [astro-ph.GA] .
  * Park  _et al._ (2021) Ryan S. Park, William M. Folkner, James G. Williams, and Dale H. Boggs, “The jpl planetary and lunar ephemerides de440 and de441,” The Astronomical Journal 161, 105 (2021).
  * Arzoumanian  _et al._ (2018) Z. Arzoumanian _et al._ (NANOGRAV), “The NANOGrav 11-year Data Set: Pulsar-timing Constraints On The Stochastic Gravitational-wave Background,” Astrophys. J. 859, 47 (2018), arXiv:1801.02617 [astro-ph.HE] .
  * Arzoumanian  _et al._ (2020) Zaven Arzoumanian _et al._ (NANOGrav), “The NANOGrav 12.5 yr Data Set: Search for an Isotropic Stochastic Gravitational-wave Background,” Astrophys. J. Lett. 905, L34 (2020), arXiv:2009.04496 [astro-ph.HE] .
  * Ellis  _et al._ (2020) Justin A. Ellis, Michele Vallisneri, Stephen R. Taylor, and Paul T. Baker, “Enterprise: Enhanced numerical toolbox enabling a robust pulsar inference suite,” Zenodo (2020).
  * Taylor  _et al._ (2021) Stephen R. Taylor, Paul T. Baker, Jeffrey S. Hazboun, Joseph Simon, and Sarah J. Vigeland, “enterprise_extensions,”  (2021), v2.2.0.
  * Ellis and van Haasteren (2017) Justin Ellis and Rutger van Haasteren, “jellis18/ptmcmcsampler: Official release,”  (2017).
  * Aggarwal  _et al._ (2019) K. Aggarwal _et al._ , “The NANOGrav 11-Year Data Set: Limits on Gravitational Waves from Individual Supermassive Black Hole Binaries,” Astrophys. J. 880, 2 (2019), arXiv:1812.11585 [astro-ph.GA] .


Department of Computer Science, Williams College, Williamstown, Massachusetts,
United Statesjmg8@williams.eduhttps://orcid.org/0000-0002-7631-6146 Jonathan
Geller [300]Theory of computation Problems, reductions and completeness

###### Acknowledgements.

The author would like to thank Aaron Williams for many helpful discussions on
the topic.

# Baba is You is Undecidable

Jonathan Geller

###### Abstract

We establish the undecidability of 2019 puzzle game Baba is You through a
reduction from the Post correspondence problem. In particular, we consider a
restricted form of the Post correspondence problem introduced by Neary (STACS
2015) that is limited to five pairs of words. Baba is You is an award winning
tile-based game in which the player can reprogram the game’s mechanisms by
pushing blocks that spell out the rules. We achieve undecidability through a
generalization of the size of the playfield in the horizontal direction,
adding a “hallway” to one side of the level. The undecidability of Baba is You
has been claimed several times online using different source problems,
including the simulation of Turing machines and Conway’s Game of Life,
however, this contribution appears to be the first formal proof of the result.

###### keywords:

Baba is You, Undecidability, Turing-Completeness

##  1 Introduction

Many puzzles and games have been shown to admit reductions from NP- or PSPACE-
hard problems, though it is rare that solutions to such puzzles cannot be
found in PSPACE. While some video games, particularly Dwarf Fortress, Cities:
Skylines [1], and Minecraft, have been shown informally to be Turing-Complete,
the author is only aware of more formal proofs of the undecidability of Braid
[5] and Magic: the Gathering [2]. The computational complexity of sliding
block puzzles such as Sokoban and Rush Hour, however, has been studied
extensively. A general framework for demonstrating PSPACE-completeness of such
puzzles is presented in [6].

The 2019 puzzle game Baba is You [9] could be classified as a sliding block
puzzle, but we will see that the game admits much more complex behavior than
almost any other. Levels generally consist of players pushing objects around
to reach some sort of end goal, much like any other block-pushing puzzle game.
Unlike these other games, however, Baba is You allows the player to constantly
reshape the rules of the game, as rules are formatted as sentences which exist
in the level as interactable objects. No objects innately have special
properties: all properties of an object are granted by rules which exist in
the level as text, as is visible in Figure 1. For a more detailed explanation
of how other aspects of the game used in this reduction work, see the videos
in [4] which contain brief demonstrations of all relevant game mechanics.

Figure 1: An example section of a Baba is You level. In the first image, the
rule baba is you means that if the player moves to the right, the baba object
will move to the right, pushing the text banana and baba to the right, as seen
in the second image. Now, the rule formed is banana is you, so if the player
moves right again, the banana object will move rather than the baba object.

Using the conventional restrictions on levels in the game results in a bounded
number of reachable states from any initial finite level, so the game with no
modifications is decidable. However, we present here a slight modification to
the function of the level boundary which enables a reduction from the Post
correspondence problem to the game Baba is You. In particular, this is
apparently the first undecidability result for any block-pushing puzzle game.

######  Definition 1.1.

An instance of baba+2 consists of some finite rectangular level with an
additional 2-tile tall “hallway” appended to the right side of the level.
Objects may pass arbitrarily far into this hallway while having their
positions stored, and the top and bottom of this hallway behave just as the
level border normally does. Such an instance is a yes instance if there is
some finite sequence of moves which can be executed that guarantees that a
player will at some point reach the win victory condition, ignoring Too
Complex and Infinite Loop end conditions in any level state with a valid
interpretation of all rules, and without ever forming rules of the form empty
is ___.

The reasoning behind the formalisms of this definition is presented in Section
2 along with more detailed information about Baba is You, and a full reduction
from a variant of the Post correspondence problem to baba+2 is presented in
Section 3.

##  2 Background

###  2.1 More on Baba is You

As alluded to earlier, an unmodified version of Baba is You is still
decidable. If more than six copies of a single object are stacked in one
location, the number of those objects on that tile is automatically reset to
six. Additionally, there are only a finite number of distinct objects
available in the game. Keeping these restrictions in place, we find that the
number of states which are reachable from some initial level is bounded by
some exponential in the size of the level. As a result, if none of these
restrictions are relaxed, there does exist an algorithm that can determine if
a given Baba is You level can be won by simply calculating the result of every
possible move at every possible state reachable from some initial level and
searching for a sequence of moves that results in a victory.

A few examples of tools which could be used to prove Turing-completeness of a
modified version of Baba is You have been demonstrated, such as the
construction of Conway’s Game of Life in [3] and [8], though none of these
examples have explicitly stated what generalizations to Baba is You they
require. Additionally, none of these constructions include demonstrations of
how their gadgets can be used to win or lose a level, so the existence of
these levels does not strictly rule out that there could be an algorithm which
determines if a generalized Baba is You level can be won. Here, we present a
simple generalization of Baba is You which can be the object of a formal
reduction from a known undecidable problem.

###  2.2 Formalizing the decision problems

The ultimate goal of the reduction is to reduce a simplified version of the
Post correspondence problem to a slight modification of Baba is You. First, we
define the decision problem pcp5-2:

######  Definition 2.1.

An instance of pcp5-2 consists of ten binary strings, $\alpha_{1}$,
$\alpha_{2}$, $\alpha_{3}$, $\alpha_{4}$, $\alpha_{5}$, $\beta_{1}$,
$\beta_{2}$, $\beta_{3}$, $\beta_{4}$, $\beta_{5}$. An instance of pcp5-2 is a
yes instance when there exists some finite nonempty sequence of integers from
1 to 5, $(i_{1},i_{2},i_{3},\cdots,i_{n})$ such that
$\alpha_{i_{1}}\alpha_{i_{2}}\cdots\alpha_{i_{n}}=\beta_{i_{1}}\beta_{i_{2}}\cdots\beta_{i_{n}}$,
where $\alpha_{1}\alpha_{2}$ represents concatenation of the two strings.

The version of this problem in which the ten strings are constructed from an
arbitrary finite alphabet has been shown to be undecidable in [7]. It is easy
to reduce that problem to pcp5-2 by associating each character in an alphabet
$\Sigma$ with a distinct binary string of length
$\lceil\log_{2}|\Sigma|\rceil$ and replacing each string in the original
instance of the problem with the corresponding binary string. Thus, pcp5-2 is
undecidable.

Defining an appropriate decision problem for Baba is You is more complicated.
A few aspects of the game in particular must be taken into consideration to
ensure that our decision problem is well defined. When there are more than two
copies of an object with the tele property, the game selects where to teleport
objects at random, and so undoing and redoing the same move can lead to
different results. Additionally, if a certain recursion depth is exceeded in
resolving the rules of a level at a particular timestep, or if certain aspects
of the rules become too computationally difficult to resolve in any other way,
the game will exit the level and display a screen with “Infinite Loop” or “Too
Complex,” respectively. Since this is a limit imposed by the difficulty of
computing rules of the game and not the rules of the game itself, we will
ignore it. Embedding a genuine paradox in the rules still counts as losing the
level, since there is no valid way to continue the level (consider the rule
not group is group, which has no valid resolution), but any set of rules that
can be resolved will allow the level to continue, regardless of how
computationally complex it is to evaluate the correct interpretation of the
rules.

Finally, in order to demonstrate that a version of Baba is You is undecidable,
we will need some way of storing arbitrary amounts of information in a single
level. A few possible methods exist for this, but here we will consider a
modification in which an arbitrarily long, two-tile-tall space is appended to
the edge of an otherwise finite level. This space begins empty, but if other
tiles somehow enter this space, their positions are stored and they continue
to behave as they would anywhere else in the level. The top and bottom of this
additional space behave in the same fashion as a normal level border, and any
objects/text must begin the level inside some finite-sized level. Finally, in
the event that a rule such as empty is rock is formed, the empty tiles in the
hallway would not all be turned into rocks, resulting in the creation of
infinitely many rocks, a situation with no clear resolution. Thus, we disallow
forming rules of the form empty is. This all gives rise to the definition of
baba+2 presented in Section 1.

##  3 The reduction

Consider the following instance of pcp5-2.

$i$ | 1 | 2 | 3 | 4 | 5
---|---|---|---|---|---
$\alpha_{i}$ | 1 | 0 | 010 | 11 | 010
$\beta_{i}$ | 10 | 10 | 01 | 1 | 10

This instance of pcp5-2 is a yes instance, as demonstrated by the following
solution:

$i$ | 1 | 2 | 1 | 3 | 3 | 4
---|---|---|---|---|---|---
$\alpha_{i}$ | 1 | 0 | 1 | 010 | 010 | 11
$\beta_{i}$ | 10 | 10 | 10 | 01 | 01 | 1

We demonstrate a particular baba+2 instance corresponding to this instance of
pcp5-2, then generalize to show how a level can be constructed in general to
be solvable if and only if a given instance of pcp5-2 is also solvable.

###  3.1 Writing strings

Figure 2 depicts an instance of baba+2 corresponding to the above pcp5-2
instance. It certainly should not be clear at this point how that problem
corresponds to this level, though this image will serve as a reference for the
remainder of this section.

Figure 2: Example instance of baba+2 constructed from the earlier instance of
pcp5-2. Road objects are present on top of each lava and ice object, but are
hidden to allow the other objects on those tiles to be visible. All lava and
ice objects are right-facing. Note the positioning of the "hallway" at the
bottom right of the level.

In any baba+2 instance we create, there are five buttons that will be present,
which when pressed will perform an action equivalent to making a copy of one
of the tiles from the pcp5-2 instance.

Figure 3: Three components of the level: from left to right, a button gadget,
the timer gadget, and a duplication gadget. The duplication gadget corresponds
to the tile with $\alpha=1$, $\beta=10$ from the earlier instance of pcp5-2.
Important rules found elsewhere in the level are wall is stop, baba is you,
lava and ice on tile is move, bird is push, car is push, baba is push, lava
and ice is push, and dog is move.

(a) The gadgets from Figure 3 after the player moves up, duplicating the lava
and ice objects in the third image. Nothing in the timer gadget changes on
this timestep.

(b) The same gadgets after one additional move in any direction, including
waiting. Note that baba is pushed out of the first gadget, and the dog, lava,
and ice objects begin to move right.

Figure 4: If the player pushes up on the is text shown in the first image of
Figure 3, each of the gadgets takes the state shown in (a). After this, the
player’s moves do not matter, and the state in (b) will be reached no matter
what.

The button gadget displayed in the first image of Figure 3 is accessible to
the baba object (which the player has control of), so the player may push the
is text upwards. This is the only way the player may interact with the text
visible in the image. Doing so forms the rules ice on rubble is more, lava on
rubble is more, duplicating the lava and ice objects in the third image of
Figure 3, as seen in Figure 4(a). On the next time step, the new rule car and
bird is move causes the car in the second image to move to the right, breaking
the rule dog is not move and forming the rule baba is not you, as seen in
Figure 4(b). The bird will also move downwards, pushing baba out of the gadget
and resetting the gadget to the state it is in in the image above. This occurs
in the exact same way no matter what action the player takes, since the
player’s move processes first, and moving right, left, or up will have no
result.

In the following time steps, the dog in the second image will move all the way
to the right, forming the rule tree is empty if it has not yet been formed,
though on subsequent iterations where this gadget is activated, the dog will
still travel the same distance before turning around, bouncing off the rule it
previously formed without modifying it. The dog will eventually travel back to
the left, pushing the car back into place, reforming dog is not move, and
breaking baba is not you, returning to the player control of baba. While this
happens, the newly duplicated lava and ice objects will move to the right per
the rule lava and ice on tile is move until they reach the end of the strip of
tile objects depicted at the bottom of the level in the full-level image. Once
those objects reach the end of this strip, they will push other lava and ice
objects already present so that they are further to the right, and they will
stop just after the tile objects in the same left-to-right order as the order
in which they were produced.

Note that no objects are you during this entire process, so the player cannot
interfere in any way. The strip that the dog object must move across is
constructed to be at least as long as the strip of tile objects at the bottom
of the level, so that the player must wait more turns than it requires for the
lava and ice objects to move off of the tile objects before they may duplicate
any more objects. This stops the player from duplicating two sets of objects
in such a way that would allow them to add lava and ice objects in an order
other than one of the ten strings already present at the beginning of the
level.

We construct the arrangement of lava and ice objects in the third image of
Figure 3 from the tile in the pcp5-2 instance in the following fashion: we
read the top string (1) in order from left to right, adding a lava tile in the
top row for each 1 and an ice tile in the top row for each 0. We then read the
bottom string (10), placing an ice tile in the bottom row for each 1, and a
lava tile for each 0.

A copy of the gadgets shown in the first and third images of Figure 3 should
be made for each tile in the pcp5-2 instance, swapping the bird and rubble
objects and text for other objects and their corresponding texts. In the full
level image, the pairs are, in order, bird/rubble, bat/brick, cat/plank,
bug/track, bee/grass. Only one copy of the gadget with the dog is needed,
since only one of the buttons may be pressed at once, so the same gadget with
the dog may be used as a timer for all of the buttons.

###  3.2 Comparing strings

Figure 5: The gadget with which the player can interact when they have created
two matching strings. Pushing down on wall enables the player to win the game
if and only if they have produced strings of lava and ice in the top and
bottom row of the hallway that correspond to matching binary strings.
Additional relevant rules are lava is open, circle is push, tree is stop, and
level without lava and without ice is you and win.

We may now discuss the section of the level visible at the center right in the
image of the full level, or in Figure 5. The text wall is accessible to the
player. Because tree is stop, the player may not push the column of “wall
(circle) you push ice is” downwards. As seen earlier in the timer gadget,
however, once at least one of the buttons has been pressed once, the rule tree
is empty will be formed, removing the tree from this column and enabling the
player to push wall downwards, forming and breaking various rules. In order
for the player to push wall downards, the player must have control of baba,
which can only occur if all lava and ice objects at the bottom of the screen
have moved to the right off of the tiles. When the player pushes wall down,
the rules baba is you and lava and ice is push are broken, and the rules crab
is move, ice is shut, lava and ice is you, and lava and ice on road is wall
are formed. This relinquishes control of baba from the player, locking off
access from all of the button gadgets, and causes the crab to begin pushing
level downwards to form the rule level is sink. This rule takes priority over
any other actions, and renders the level unbeatable by deleting all objects
and text on the screen. This will occur in two turns and cannot be stopped or
delayed, meaning that after pushing wall downwards, the player must win on the
next turn or they will be unable to win.

The win condition for the level comes from level without lava and without ice
is you and win (no other win condition can be formed, since the win word is
inaccessible). The ice and lava objects present at the beginning of the level
are all stacked on top of road objects, meaning that when the rule lava and
ice on road is wall is formed, they will be deleted. The only lava and ice
objects remaining are then those which have been produced via the button
gadgets and aligned just to the right of the tile objects. There must be at
least one such lava or ice object, since as discussed earlier, the player may
only push wall downwards if at least one button has been pressed already,
meaning the player has duplicated at least one lava or ice object.

On the player’s next turn, if they take the wait action, nothing will happen
to the lava and ice tiles, and they will lose on the next turn no matter what.
Similarly, if the player takes the right or left action, they will move all
lava and ice tiles to the left or right, meaning they will still be present
and the level will not be won.111Due to a strange way the game processes
movement, it is necessary for the lava and ice is push rule to be broken for
this to function as intended–if the rule were still present then it would be
possible to annihilate ice and lava objects by moving left or right. However,
the rule is broken, so this does in fact work as intended. Thus, the only
option is for the player to move up or down.

In the case of moving down, the lava and ice objects in the bottom of the two
rows will fail to move since they are up against a wall, and the lava and ice
objects in the top row will move down into the lava and ice objects in the
bottom row. Moving up has the same effect, in which lava and ice objects in
the same column will collide. Since ice is shut and lava is open, any column
which contains one ice object and one lava object (in either order) will have
those two objects annihilate each other via the open/shut rule. Thus, if in
each column there is exactly one ice and one lava, then moving down or up will
lead to no ice and lava remaining in the level, and so the rule level without
lava and without ice is you and win takes effect and causes the player to win
the level. Alternatively, if there is a column which contains two ice, two
lava, or a column with exactly one object (e.g. a single ice object in the top
row with no matching object in the bottom row), then the objects will not be
annihilated so at least one object of ice or lava will remain in the level,
meaning the player will not win on that turn. Since the player will lose on
the next turn regardless of what action is taken, the player will be unable to
win.

###  3.3 Constructing the level

With the function of the individual components of the level clarified, we now
present a general scheme for constructing a level based off of a general
pcp5-2 instance. It should be noted that this procedure will not produce
levels with the exact same layout as the level in Figure 2, as that level in
particular has been rearranged to be more compact for ease of presentation.
Still, it should be clear how the level that the following procedure
constructs is equivalent to the level already presented.

Given an instance of pcp5-2, there are ten binary strings $\alpha_{1}$,
$\alpha_{2}$, $\alpha_{3}$, $\alpha_{4}$, $\alpha_{5}$, $\beta_{1}$,
$\beta_{2}$, $\beta_{3}$, $\beta_{4}$, and $\beta_{5}$. Define the quantity
$l$:

$l=\max\left\\{\sum_{i=1}^{5}|\alpha_{i}|,\sum_{i=1}^{5}|\beta_{i}|,33\right\\}$

where $|\alpha_{i}|$ denotes the length of the string $\alpha_{i}$. We
construct a level of width $l+6$ and height 25 beginning with the level
section seen in Figure 6 aligned to the top left corner of the level.
Subsequently, we construct the timer gadget of Figure 7 below the previous
part, but stretched out so that the left and right edges of the timer line up
with the left and right edges of the level.

Figure 6: The top section of every instance of baba+2 created. The contents of
this section are identical for any initial instance of pcp5-2. The right level
border need not be where it is shown here, though any additional space
remaining to the right of this will not be used. Figure 7: The timer gadget to
be constructed in each instance of baba+2. This should be modified to span the
full width of the level in order to ensure that the timer is sufficiently long
for each particular baba+2 instance.

Fill the fifth row from the bottom of the level with walls. Fill every space
in the second and third rows from the bottom with tile objects.

In the fourth row from the bottom, at the very left, add a wall. Then, for
each character in $\alpha_{1}$, working from left to right in that same fourth
row, add a stack of a road object, a rubble object, and a lava object if the
character is a 1 or an ice object if the character is a 0. Add another wall
after this, then do the same for $\alpha_{2}$ replacing rubble with brick, a
wall, the same for $\alpha_{3}$ replacing rubble with plank, a wall, the same
for $\alpha_{4}$ replacing rubble with track, a wall, and the same for
$\alpha_{5}$ replacing rubble with grass. Then, add walls from the end of this
row all the way to the right of the level. Do the same on the bottom row with
the $\beta$ strings, except exchanging lava and ice for each other. Finally,
extend the rows which are second and third from the bottom of the level to the
right past the level border, adding the arbitrarily long two-tile-high space
to the level specified in the description of baba+2. An example of how this
construction might appear is visible in Figure 8. This completes the
construction of the level.

Figure 8: The bottom five rows of the level. Unlike the two other main
components of the level, this area can appear quite different depending on the
particular instance of pcp5-2 from which the level is being produced, but this
is one example of how this section could appear.

###  3.4 Proof of reduction

We now demonstrate that the baba+2 decision problem constructed above has the
same answer as the pcp5-2 instance on which it is based.

First, assume that there exists a solution to the instance of pcp5-2. In this
case, there is some finite list of $n\geq 1$ integers each between one and
five $i_{1},i_{2},\cdots,i_{n}$ such that
$\alpha_{i_{1}}\alpha_{i_{2}}\cdots\alpha_{i_{n}}=\beta_{i_{1}}\beta_{i_{2}}\cdots\beta_{i_{n}}$.
In this case, the player can push up on the $i_{n}$’th is word, then the
$i_{n-1}$’th is, and so on until they have pushed the $i_{1}$’th is. This will
replicate the tiles at the bottom of the level in reverse order to the pcp5-2
solution. Since the first strings copied will end up the farthest to the
right, this means that the third to bottom row of the level, when read left to
right treating lava as 1 and ice as 0, will be the binary string
$\alpha_{i_{1}}\alpha_{i_{2}}\cdots\alpha_{i_{n}}$. Similarly, the binary
string reached by reading the row second from the bottom with ice as 1 and
lava as 0 will be $\beta_{i_{1}}\beta_{i_{2}}\cdots\beta_{i_{n}}$, which is
the same string by the definition of the sequence $i_{1},i_{2},\cdots,i_{n}$.
For these strings to be equal, there must be a lava object in the top row in
each column where there is an ice object in the bottom row, and an ice object
in the top row in any column where there is a lava object in the bottom row.
Thus, each row will have the same number of objects, with exactly one ice and
one lava object in each column. As a result, when the player pushes down on
wall, they can move down to eliminate all ice and lava objects and win the
level. Thus, if the pcp5-2 instance is a yes instance, then this baba+2
instance is also a yes instance.

The only ways in which the player may interact with the level up until pushing
wall down are the five button gadgets where they may push is up. There is no
way for the player to do anything but push these five buttons in some order
and then push wall down to win the level, since the rule level without lava
and without ice is win is the only way to win the level, and the only way to
remove the lava and ice tiles present at the beginning of the level is pushing
wall down.

Thus, the only actions the player can legally take that could possibly result
in winning the level are pushing up on the is text objects some number of
times (but at least once) in some order, followed by pushing down on wall,
then moving down or up once. Additionally, the moves taken between pressing
the is text up or pushing wall down cannot affect anything in the level, so
they can be ignored. Thus, if this level can be won, it is through some
sequence of moves that can be completely described by the order in which
various is’s are pushed up.

If the level is won after such a sequence of moves, then on the turn when the
player pushes wall down, the third row from the bottom consists of some
sequence of lava and ice tiles such that the second row from the bottom
contains lava in any column the other row contains ice, it contains ice in any
column in which the other row contains lava, and it is empty in any row in
which the other row is empty. In any other configuration, pushing wall down
and moving in any direction does not result in the level being won. Thus, the
sequence in which the player pushed the various is text objects up resulted in
a construction of a lava/ice string in the upper row that is exactly opposite
in every position to the lava/ice string in the lower row.

If we take the $\alpha$ words in the reverse order that the player pushed the
is objects up (e.g. if the player first pushes the fourth is up, then the
fifth, we would take the string $\alpha_{5}\alpha_{4}$), we must construct a
string which is the same string we would obtain from reading left to right in
the row third from the bottom of the level, writing 1 for every lava object
and 0 for every ice object. Similarly, carrying out the same process with the
$\beta$ words gives the same string we obtain from reading along the row
second from the bottom of the level, writing a 0 for every lava object and a 1
for every ice object. However, we have seen that in each position where the
lower row has an ice, and upper row has a lava, and vice versa. This means
that the binary strings corresponding to each row must be the same, so we have
found a solution to the instance of pcp5-2. Thus, the pcp5-2 instance is a yes
instance whenever baba+2 is a yes instance.

Combining these results, we find that the baba+2 instance is a yes instance if
and only if the pcp5-2 instance is a yes instance. The level’s size is
polynomial in the size of the pcp5-2 instance and so the level can be
constructed from the pcp5-2 instance in polynomial time. As a result, this is
a polynomial time reduction from pcp5-2 to baba+2, so since pcp5-2 is
undecidable, baba+2 is also undecidable.

##  4 Conclusion

We have demonstrated that the game Baba is You is undecidable, though this
proof required a generalization of the game with an arbitrarily long hallway
adjoined to one side of the level. In general, some modification to the game
is certainly necessary to reach this undecidability result, as the unmodified
game is decidable. It is likely that other similarly small modifications to
the rules of the game could also lead to this same undecidability result. In
particular, removing the cap of the number of copies of an object which may be
present on one tile should enable the construction of a counter machine for a
proof along the same lines as the proof that Braid is undecidable given in
[5].

## References

  * [1] Daniel Bali.  Cities: Skylines is turing complete, Jul 2019.  URL: https://medium.com/@balidani/cities-skylines-is-turing-complete-e5ccf75d1c3a.
  * [2] Alex Churchill, Stella Biderman, and Austin Herrick.  Magic: The gathering is turing complete.  CoRR, abs/1904.09828, 2019.  URL: http://arxiv.org/abs/1904.09828, arXiv:1904.09828.
  * [3] Devin Danko.  Baba is life v3: Real-time, 2020.  URL: https://www.youtube.com/watch?v=LveTdtv0xiQ.
  * [4] Jonathan Geller.  Baba is undecidable, 2022.  URL: https://www.youtube.com/playlist?list=PLE75TLHOnaOKrQsrhCUgOmuAX7l7dI66N.
  * [5] Linus Hamilton.  Braid is undecidable.  arXiv preprint arXiv:1412.0784, 2014.
  * [6] Robert A. Hearn and Erik D. Demaine.  Pspace-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation.  CoRR, cs.CC/0205005, 2002.  URL: https://arxiv.org/abs/cs/0205005.
  * [7] Turlough Neary.  Undecidability in Binary Tag Systems and the Post Correspondence Problem for Five Pairs of Words.  In Ernst W. Mayr and Nicolas Ollinger, editors, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015), volume 30 of Leibniz International Proceedings in Informatics (LIPIcs), pages 649–661, Dagstuhl, Germany, 2015. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.  URL: http://drops.dagstuhl.de/opus/volltexte/2015/4948, doi:10.4230/LIPIcs.STACS.2015.649.
  * [8] Andrew Taylor.  Conway’s game of life in baba is you, 2019.  URL: https://www.youtube.com/watch?v=YH0NR1kmMUo.
  * [9] Arvi Teikari.  Baba is you.  Game [PC].(March 2019). Hempuli Oy, Finland, 2019.