# Attempt Towards Stress Transfer in Speech-to-Speech Machine Translation

Sai Akarsh, Vamshi Raghusimha, Anindita Mondal, Anil Vuppala
LTRC, International Institute of Information Technology - Hyderabad
{sai.akarsh, narasinga.vamshi<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

The language diversity in India’s education sector poses a significant
challenge, hindering inclusivity. Despite the democratization of knowledge
through online educational content, the dominance of English, as the
internet’s lingua franca, limits accessibility, emphasizing the crucial need
for translation into Indian languages. Despite existing Speech-to-Speech
Machine Translation (SSMT) technologies, the lack of intonation in these
systems gives monotonous translations, leading to a loss of audience interest
and disengagement from the content. To address this, our paper introduces a
dataset with stress annotations in Indian English and also a Text-to-Speech
(TTS) architecture capable of incorporating stress into synthesized speech.
This dataset is used for training a stress detection model, which is then used
in the SSMT system for detecting stress in the source speech and transferring
it into the target language speech. The TTS architecture is based on FastPitch
and can modify the variances based on stressed words given. We present an
Indian English-to-Hindi SSMT system that can transfer stress and aim to
enhance the overall quality and engagement of educational content.

###### Index Terms:

speech-to-speech machine translation, stress detection, text-to-speech, speech
synthesis

##  I Introduction

SSMT stands at the forefront of linguistic innovation, aiming to bridge
communication gaps by offering real-time translation of spoken language. In a
globalized society, effective communication across diverse linguistic
boundaries is indispensable. SSMT, as a cutting-edge technology, emerges as a
pivotal solution and is composed of three primary components: Automatic Speech
Recognition (ASR), Machine Translation (MT), and Text-to-Speech synthesis
(TTS). These components involve language and prosodic understanding and hence,
there are several challenges, stemming from the complex nature of spoken
language and the intricacies involved in real-time translation.

Prosody encompasses elements such as stress, rhythm, and intonation, which
play a crucial role in conveying the emotional and expressive aspects of
spoken language. Ensuring the faithful transfer of prosody from the source to
the target language is essential for producing natural and human-like
translations. Prosody often varies based on the context of the conversation,
such as asking a question, making a statement, or expressing surprise. The
inability to transfer prosodic features accurately results in robotic or
unnatural-sounding translations, affecting the overall intelligibility and
expressiveness of the translated speech.

Traditional speech translation systems overlook paralinguistic cues, but there
has been a recent focus on systems that transfer linguistic content along with
emphasis information. In contrast to conventional SSMT systems [7, 6, 8],
proposed methods to translate paralinguistic information, focusing
specifically on stress/emphasis where source speech was English and target
speech was Japanese. Utilizing DNN-HMM ASR, Statistical Machine Translation,
and an HSMM-based TTS model, the approach in [7] involves the use of linear-
regression hidden semi-Markov models (LRHSMMs). These models estimate a
sequence of real-numbered emphasis values for each word in an utterance.

Numerous studies have been conducted within the linguistic domains of Spanish,
English, and Catalan such as [1],[12] reflecting a comprehensive exploration
of prosody transfer techniques between these languages. Moreover, recent
research initiatives have broadened their focus to incorporate the intricate
linguistic environment prevalent in the Indian context [16]. While existing
speech datasets offer valuable resources for speech processing and synthesis
research, they often lack annotations for aspects like prosodic emphasis,
particularly in domains such as educational settings. To address this gap,
this paper undertook an in-depth exploration of an Indian English dataset
[11], meticulously annotated the gathered data, devised a stress detection
model, and subsequently formulated a methodology to integrate this model into
TTS systems which can generate target language speech in Hindi enriched with
stress patterns for enhanced naturalness and expressiveness.

##  II Proposed Methodology

The fidelity of SSMT hinges not just on semantic accuracy, but also on
capturing the speaker’s intent conveyed through subtle prosodic cues like
stress. While existing systems excel at translating meaning, they often
stumble when replicating the emotional weight and emphasis embedded in the
source speech. In this section, we discuss in detail the methodology for
bridging this gap.

###  II-A Stress Dataset

Recognizing the limitations of existing speech datasets in capturing the
subtleties of stress, especially within the distinct domain of Indian English
video lectures, we sought to build a resource tailored to this specific niche.
We leveraged the existing strengths of the IED-IIITH dataset [11], which
features high-quality speech recordings from the NPTEL educational lectures.
This dataset was chosen as it contains a wide variety of speakers and speaking
styles, and also captures common disfluencies that occur in spoken speech.
This is important as our stress detection model which is set in the context of
spoken speech in educational lectures needs to be robust against disfluencies
and shouldn’t necessarily classify them as stress regions.

In the context of lectures, the lecturer naturally incorporates stress while
explaining specific topics, emphasizing certain words to add meaning and
subtlety. Such stress patterns often occur at the beginning or ending of
sentences, and feature prolonged duration, with potential pauses. This dataset
was manually annotated by trained annotators who identified the stressed
regions, relying on both acoustic cues like pitch and duration and indicators
like waveform and the above-explained reasoning.

Figure 1: Sample from the annotated dataset that contains a stress region
(orange)

Label Studio [20], an open-source data labelling platform, was used to perform
stress region annotation and generate the timestamps for each audio file as
shown in Figure 1 (with the transcript for reference). An audio file may have
multiple stressed regions or none at all. The audio data was distributed among
ten annotators in such a way that every audio sample had labels from at least
3 different annotators. This was done to address the subjective nature of
stress and emphasis as everyone has a different perception of such nuances. We
use Fleiss Kappa inter-annotator agreement [9] to aggregate multiple
annotations to get the final labels. This effort resulted in a unique stress-
annotated dataset specifically tailored to Indian English (NPTEL) video
lectures, advancing the availability of resources for stress detection.

###  II-B Stress Detection Models

Stress detection in speech is achieved by training classifiers on several
acoustic features calculated from the data collected. The classifier is
trained to predict a stress label for each frame indicating if a frame is
stressed or not. The model uses features from a window of frames rather than
one frame for more contextual information. In speech, the stressed regions
occupy a small region when compared to the non-stressed regions, hence the
labels given to the classifier are usually skewed giving rise to more false
positives and need to be balanced.

A post-processing technique is employed, where the word alignments with speech
are calculated using an ASR system. With these alignments, the frame-level
predictions are converted to word-level predictions. A word is classified as
stressed if the region containing the word has a majority of frames predicted
as stress. This technique not only filters out a considerable amount of false
positives but also gives stress detection on the word level which is used in
SSMT.

For every detected stress word, additional information, indicating how the
pitch and energy variances change in that stressed region with respect to the
rest of the speech, is denoted as a scaling factor and is quite useful in SSMT
as a metric for the TTS system to modify variances in order to introduce
stress in the target speech.

###  II-C TTS

Once the stressed words are known, a way of incorporating stress in
synthesized speech is presented based on FastPitch [15] which is a two-stage
TTS architecture. The first stage is comprised of a Transformer-based [21]
text encoder, and a CNN-based pitch and duration variance predictor. The
second stage combines the text encoding with pitch embeddings and duplicates
it based on the predicted duration, which is then sent to another Transformer
to finally give the mel spectrogram.

In the proposed TTS system, several changes were made to the base FastPitch
architecture to condition the synthesized speech on stress cues. First, both
text and stress cues are taken as input, where the text is handled as
character tokens and stress cues are given as stressed word and scale factor
pairs that were generated using the stress detection model. Second, an energy
prediction block is added since stressed words have a strong correlation with
energy and can be seen in Figure 2 (a). Third, a Pitch-Duration-Energy (PDE)
Modifier block as shown in Figure 2 (b) is introduced, which modifies the
predicted variances using the stress cues. Such modifications enable the
training of the TTS on neutral speech-text datasets which are already
available. Since TTS requires very high-quality clean speech data, procuring
such amounts of stressed data is not trivial and we overcome this issue by
using the PDE Modifier block only during inference.

(a) Proposed TTS architecture

(b) PDE Modifier

Figure 2: Architecture for proposed TTS follows FastPitch [15]. The predicted
variances are modified by the PDE Modifier based on the stress cues to
introduce stress in the synthesized speech.

Let $x$ be input character tokens and $s$ be input stress cues. The token
embeddings for the text are generated using an embedding layer and are passed
to a feed-forward Transformer (FFT) encoder stack that produces the hidden
representation $h=\text{FFT}_{e}\text{(Embedding}(x))$. This hidden
representation is then used to predict each input character token’s duration
$\hat{d}$, pitch $\hat{p}$ and energy $\hat{e}$ using a CNN stack. The pitch,
duration and energy values are then sent to the PDE Modifier block, where each
of the variances is modified based on the stressed word region and the scaling
factors provided. This is done by scaling the predicted variances of every
input token corresponding to a stressed word using the scaling factors.

Next, the modified pitch $p_{m}$ and energy $e_{m}$ are projected to match the
dimensionality of the hidden representation $h$ using an embedding layer and
are then added to $h$. The resulting sum $g$ which is at the resolution of
input character tokens is then discretely upsampled using the modified
durations $d_{m}$ to give $f$ which is at the resolution of output frames. $f$
is then passed to an FFT decoder stack to produce the output mel-spectrogram
sequence.

The output mel-spectrogram $\hat{y}$ is generated using the modified variances
from the PDE Modifier block, thus incorporating stress in the synthesized
speech. Since the PDE Modifier block is used only during inference, the
training loss is based on mean-square error (MSE), similar to that of
FastPitch.

Figure 3: The overall architecture for the proposed SSMT pipeline. The MT
Aligner takes English stress words, generates the English-Hindi word
alignments and converts them into stress cues: Hindi stress words along with
scaling factors

##  III Experimental Setup

In this section, we discuss the datasets, features and models that were used
for the experiments.

###  III-A Stress Dataset

The stress dataset consists of nearly 10 hours of spoken speech in the context
of educational video lectures from [11]. It features recordings from 60
speakers (30 male and 30 female), where each speaker has around 10 minutes of
speech. These 10-minute recordings are further split into smaller audio files
of 8 to 12 seconds, with a sampling rate of 16000 Hz. The dataset comprises
3329 audio files where each audio file is identified using a unique ID and has
information about the speaker and the stressed region labels. Each audio
sample can have multiple stressed regions or none at all. There are a total of
3807 occurrences of stressed regions with an average duration of about 0.53
seconds.

Features | Models | Window Size = 3 | Window Size = 5 | Window Size = 7
---|---|---|---|---
Accuracy | F1 | Post Accuracy | Accuracy | F1 | Post Accuracy | Accuracy | F1 | Post Accuracy
F0 and Energy | LPA | 60.6 | 60.45 | 71.11 | 68.9 | 68.77 | 81.85 | 75.3 | 75.16 | 86.18
| RFC | 58.2 | 58.06 | 69.52 | 68.6 | 67.59 | 76.75 | 72.8 | 71.79 | 82
| SVC | 61.1 | 60.5 | 73.35 | 67.2 | 66.11 | 80.3 | 71.5 | 70.46 | 83.83
F0, Energy, MFCC, SDC | LPA | 63.1 | 61.09 | 75.28 | 62.2 | 58.52 | 74.57 | 82.3 | 80.77 | 90.36
| RFC | 64.3 | 63.28 | 77.37 | 71.1 | 70.3 | 81.22 | 78.3 | 78.27 | 85.29
| SVC | 66.8 | 66.79 | 78.42 | 70.1 | 70.09 | 80.12 | 79.2 | 79.2 | 83.82
TABLE I: Evaluation of stress detection model with different features and
varying window sizes.

###  III-B Feature Extraction and Stress Detection Models

Several acoustic features such as F0 [10], energy [14], Mel Frequency Cepstral
Coefficients (MFCC) and Shifted Delta Coefficients (SDC) [11] were used for
the task of stress detection. 13 MFCC features were extracted by taking a
frame length of 1024 and hop length of 256. 52 SDC features were calculated
using $d=1,p=5,k=3$ as they gave better results. The F0 and energy contours
were averaged to get frame-level features. All the features were then mean-
variance normalized, and different subsets of features were considered to get
the best performance. We combine different features on the frame level and
then stack up those features from frames before and after to give wider
contextual information.

The data imbalance needs to be tackled as the frames corresponding to stressed
regions are much fewer than that of non-stressed regions. This would lead the
model to be biased and hence not desirable. We used SMOTE (Synthetic Minority
Oversampling Technique) [4] based oversampling on the data while training each
model.

Using the features extracted above, various classifiers were trained to
perform the task of stress detection. The following three classifiers were
chosen to be tabulated as they gave better results: Label Propagation
Algorithm (LPA) [22] with radial basis function kernel and 7 neighbours,
Random Forest Classifier (RFC) with 100 trees in the ensemble and Support
Vector Classifier (SVC) with a radial basis function kernel and penalty factor
of 0.8. Due to the limited availability of data, a DNN-based model was not
deemed suitable to achieve the desired level of accuracy.

###  III-C SSMT Pipeline

ASR: WhisperX [3] ASR model was used to process the source speech in Indian
English to give both the transcript and word alignments. The ASR is built upon
a pre-trained Whisper [17] English large-v2 model and delivers accurate word-
level transcriptions with high confidence scores. Word-level alignments in
post-processing boost stress detection model accuracy and reliability. They
also aid in identifying stressed words in the target language by mapping them
to their equivalents in the source language.

MT and Aligner: English-Hindi MT model was taken from the open source Helsinki
OPUS MT[19] project. This is used to convert the English transcript from ASR
into a Hindi transcript. MT word aligner from simalign [13] was used to map
the translated Hindi words to their corresponding English words. It uses a
pre-trained mBERT [5] multilingual language model to achieve this mapping.

TTS: To train the TTS model, we have used the latest version of the Hindi Male
speaker’s database from the ULCA Bhashini IndicTTS [2] which has nearly 10
hours of recorded and transcribed speech at a sampling rate of 22050 Hz. The
utterances of more than 15 seconds were ignored. The TTS model used an FFT
stack of 6 layers and a pre-trained Tacotron2 [18] model for calculating the
durations of ground truth [15]. It was trained for 2000 epochs on a single
NVIDIA A100 80GB Tensor Core GPU with a batch size of 128.

##  IV Results

The performance of the stress detection models is shown in Table I based on
the classification of frame-level stress labels. The experiments were carried
out on two feature sets: (F0, Energy) and (F0, Energy, MFCC, SDC) using
different classifiers. From Table I, it can be seen that LPA having a window
size of 7 with the addition of the post-processing stage improves the accuracy
and f1 score for both feature sets with an absolute improvement of around
2-4%. RFC gave better results compared to LPA and SVC in the case of all
features when the window size is 5 with an absolute improvement of around 5%.
SVC gave better results compared to LPA and RFC in both cases when the window
size is 3 with an absolute improvement of around 2-3%.

| MOS
---|---
TTS Model | Without Stress | With Stress
Pitch | 4.25 | 3.95
Pitch and Energy | 4.36 | 4.21
TABLE II: Evaluation of TTS models in SSMT using Mean Opinion Score (MOS)

Due to the lack of automated evaluation metrics for SSMT, we rely on
subjective evaluation through a survey where 30 participants, fluent in both
English and Hindi were asked to give performance metrics. Every participant
was given 15 samples111https://sativus04.github.io/, each containing the
original English speech, translated Hindi speech with and without stress. They
gave two performance metrics, the first is the quality of the synthesized
Hindi speech for both with and without stress as seen in Table II. A score
between 0 and 5 is given, where 0 is very bad and 5 is very good. The Mean
Opinion Score (MOS) is derived by averaging all the scores. Notably, TTS
without stress outperforms its stressed counterpart due to potential
instability in spectrogram generation when directly altering variances. The
model with both Pitch and Energy exhibits enhanced flexibility in speech
generation.

SSMT | st-MOS
---|---
Pitch | 3.73
Pitch and Energy | 4.09
TABLE III: Evaluation of SSMT models using st-MOS (Stress Transfer MOS)

The second performance metric is the measure of how well the stress has been
incorporated as seen in Table III. The participant uses the original speech
and synthesized speech without stress as a reference to gauge how well the
stress has been added to the synthesized speech with stress. This is used to
calculate the st-MOS (stress transfer MOS) score, where 0 means that no stress
was transferred and 5 means that all the stress regions were transferred. The
average score of 3.96 indicates effective stress integration, particularly
with both pitch and energy, underlining the significance of energy in stress
modelling. These results serve as the baseline for this task, given the
absence of a baseline setup.

##  V Conclusion

SSMT systems keep improving with rapid strides. We curated a dataset with
stress annotations for Indian English and trained stress detection models
using it. We modified an existing TTS architecture for the addition of stress
in synthesized speech using existing speech corpora. Evaluation was done on
the stress detection models, TTS and SSMT systems and the best configurations
were identified. Several directions of work can be seen from here: other TTS
models need to be compared in this task, preserving the speaker’s voice in
target speech, and designing better subjective and objective metrics for such
tasks in SSMT. We aim to address some of these issues in future works and
bridge the gap between the source and target speech in SSMT.

## Acknowledgment

We thank the reviewers for their insightful comments. This undertaking is
funded by the Ministry of Electronics and Information Technology, Government
of India , as evidenced by the Sanction Order:
11(1)/2022-HCC(TDIL)-Part(2)/A/B/C and the Administrative Approval:
11(1)/2022-HCC(TDIL)- Part(2).

## References

  * [1] P.D. Aguero, J. Adell and A. Bonafonte  “Prosody Generation for Speech-to-Speech Translation”  In _2006 IEEE International Conference on Acoustics Speech and Signal Processing Proceedings_ 1, 2006, pp. I–I  DOI: 10.1109/ICASSP.2006.1660081
  * [2] Arun Baby, Anju Thomas, Nishanthi L and TTS Consortium  “Resources for Indian languages”, 2016
  * [3] Max Bain, Jaesung Huh, Tengda Han and Andrew Zisserman  “WhisperX: Time-Accurate Speech Transcription of Long-Form Audio”  In _INTERSPEECH 2023_ , 2023
  * [4] N.. Chawla, K.. Bowyer, L.. Hall and W.. Kegelmeyer  “SMOTE: Synthetic Minority Over-sampling Technique”  In _Journal of Artificial Intelligence Research_ 16 AI Access Foundation, 2002, pp. 321–357  DOI: 10.1613/jair.953
  * [5] Jacob Devlin, Ming-Wei Chang, Kenton Lee and Kristina Toutanova  “BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding”, 2019  arXiv:1810.04805 [cs.CL]
  * [6] Quoc Truong Do, Sakriani Sakti and Satoshi Nakamura  “Sequence-to-Sequence Models for Emphasis Speech Translation”  In _IEEE/ACM Transactions on Audio, Speech, and Language Processing_ 26.10, 2018, pp. 1873–1883  DOI: 10.1109/TASLP.2018.2846402
  * [7] Quoc Truong Do et al.  “Preserving Word-Level Emphasis in Speech-to-Speech Translation”  In _IEEE/ACM Transactions on Audio, Speech, and Language Processing_ 25.3, 2017, pp. 544–556  DOI: 10.1109/TASLP.2016.2643280
  * [8] Quoc Truong Do, Sakriani Sakti, Graham Neubig and Satoshi Nakamura  “Transferring Emphasis in Speech Translation Using Hard-Attentional Neural Network Models”  In _Proc. Interspeech 2016_
  * [9] JL Fleiss  “Measuring nominal scale agreement among many raters”  In _Psychological bulletin_
  * [10] Hiroya Fujisaki  “Information, prosody, and modeling-with emphasis on tonal features of speech”  In _Scientific Programming - SP_ , 2004
  * [11] Sparsh Garg, Utkarsh Mehrotra, Gurugubelli Krishna and Anil Kumar Vuppala  “Towards a Database For Detection of Multiple Speech Disfluencies in Indian English”  In _2021 National Conference on Communications (NCC)_ , 2021, pp. 1–6  DOI: 10.1109/NCC52529.2021.9530043
  * [12] Wen-Chin Huang et al.  “A Holistic Cascade System, benchmark, and Human Evaluation Protocol for Expressive Speech-to-Speech Translation”, 2023  arXiv:2301.10606 [cs.CL]
  * [13] Masoud Jalili Sabet, Philipp Dufter, Francois Yvon and Hinrich Schutze  “SimAlign: High Quality Word Alignments without Parallel Training Data using Static and Contextualized Embeddings”  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: Findings_ Association for Computational Linguistics
  * [14] Takatomo Kano and Sakriani Sakti  “A method for translation of paralinguistic information”  In _Proceedings of the 9th International Workshop on Spoken Language Translation: Papers_ , 2012, pp. 158–163
  * [15] Adrian Łańcucki  “Fastpitch: Parallel Text-to-Speech with Pitch Prediction”  In _ICASSP 2021 - 2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , 2021, pp. 6588–6592  DOI: 10.1109/ICASSP39728.2021.9413889
  * [16] Shivam Mhaskar et al.  “VAKTA-SETU: A Speech-to-Speech Machine Translation Service in Select Indic Languages”, 2023  arXiv:2305.12518 [cs.CL]
  * [17] Alec Radford et al.  “Robust Speech Recognition via Large-Scale Weak Supervision”, 2022  arXiv:2212.04356 [eess.AS]
  * [18] Jonathan Shen et al.  “Natural TTS Synthesis by Conditioning WaveNet on Mel Spectrogram Predictions”, 2018  arXiv:1712.05884 [cs.CL]
  * [19] Jörg Tiedemann and Santhosh Thottingal  “OPUS-MT — Building open translation services for the World”  In _Proceedings of the 22nd Annual Conferenec of the European Association for Machine Translation (EAMT)_ , 2020
  * [20] Maxim Tkachenko, Mikhail Malyuk, Andrey Holmanyuk and Nikolai Liubimov  “Label Studio: Data labeling software” Open source software available from https://github.com/heartexlabs/label-studio, 2022  URL: https://github.com/heartexlabs/label-studio
  * [21] Ashish Vaswani et al.  “Attention Is All You Need”, 2023  arXiv:1706.03762 [cs.CL]
  * [22] Dengyong Zhou et al.  “Learning with Local and Global Consistency”  In _Advances in Neural Information Processing Systems_ 16 MIT Press, 2003


# Computability in Dynamical Systems

Michael Burr  and  Christian Wolf  Michael Burr, School of Mathematical and
Statistical Sciences, Clemson University<EMAIL_ADDRESS>Christian Wolf,
Department of Mathematics, The CUNY Graduate Center, NY, NY<EMAIL_ADDRESS>
###### Abstract.

In this paper we present an introduction to the area of computability in
dynamical systems. This is a fairly new field which has received quite some
attention in recent years. One of the central questions in this area is if
relevant dynamical objects can be algorithmically presented by a Turing
machine. After providing an overview of the relevant objects we discuss recent
results concerning the computability of the entropy for symbolic systems and
the computability of Julia sets as well as their Brolin-Lyubich measures.

Burr was partially supported by grants from the National Science Foundation
(CCF-1527193 and DMS-1913119).

Wolf was partially supported by grants from the Simons Foundation (#637594 to
Christian Wolf) and PSC-CUNY (TRADB-51-63715 to Christian Wolf).

##  1\. Introduction

In [16], Milnor poses the question of whether an algorithm exists to
approximate the entropy of a dynamical system up to a specified error. Such an
algorithm does not exist in the most general setting, but this nonexistence
leads to the following question:

For which classes of dynamical systems and invariants can these invariants be
algorithmically approximated to any specified precision?

In dynamics and the sciences, computational experiments are often used to gain
insight into the behavior of dynamical systems. For invariants which cannot be
algorithmically approximated, the results of such computational experiments
may be meaningless. We approach the generalization of Milnor’s question from
the point of view of computability theory.

We begin with the computational model for computability theory. From a
theoretical standpoint, we may study a dynamical system $f:X\rightarrow X$
defined by an infinite amount of data. From an algorithmic standpoint,
however, only a finite amount of data may be provided as input. Therefore, by
necessity, we replace the dynamical system $f:X\rightarrow X$ by a convergent
sequence of approximations $f_{i}:X_{i}\rightarrow X_{i}$, each of which may
be described by a finite amount of data. Milnor’s question then leads to the
question

Do computations with a sequence of approximations $f_{i}:X_{i}\rightarrow
X_{i}$ provide insight into the properties of the original dynamical system
$f:X\rightarrow X$?

We apply computability theory to three case studies from dynamical systems
which yield both positive and negative results.

###  1.1. Dynamical Systems

A dynamical system consists of a state space $X$ (the set of attainable
states) and a time evolution law

$(\Phi_{t})_{t\in T}:X\to X,$

where $T$ denotes the set of times when the state of the system can be
observed. In other words, if the system is in state $x_{0}$ at time $t=0$,
then it is in state $\Phi_{t}(x_{0})$ at time $t$. We focus on discrete
dynamical systems where $T={\mathbb{N}}_{0}$. We assume that $\Phi_{0}={\rm
id}_{X}$ and that $\Phi_{n+m}=\Phi_{n}\circ\Phi_{m}$ for all
$n,m\in{\mathbb{N}}$. Hence

$\Phi_{n}(x_{0})=\underbrace{\Phi_{1}\circ\ldots\circ\Phi_{1}}_{n-{\rm
times}}(x_{0})=\vcentcolon\Phi_{1}^{n}(x_{0}).$

Consequently, such a dynamical system is given by the iteration of a map
$f\vcentcolon=\Phi_{1}:X\rightarrow X$.

We consider discrete dynamical systems given by continuous maps $f:X\to X$
where $(X,d)$ is a compact metric space. Given $x\in X$ we call
$\mathcal{O}(x)\vcentcolon=\mathcal{O}^{+}(x)\vcentcolon=\\{x,f(x),f^{2}(x),\ldots\\}$
the (forward) orbit of $x$. If $f$ is invertible, we analogously define the
backward orbit $\mathcal{O}^{-}(x)$ by iterating $f^{-1}$. When $f^{n}(x)=x$
for some finite positive $n$, we say that $x$ is periodic and define the
period of $x$ to be the cardinality of the orbit, i.e., a periodic point of
period $n$ has orbit $\mathcal{O}(x)=\\{x,f(x),\dots,f^{n-1}(x)\\}$, where
each $f^{i}(x)$ is distinct for $0\leq i<n$ and $x=f^{n}(x)$. We denote the
set of periodic points of $f$ with period $n$ by ${\rm Per}_{n}(f)$ and the
set of periodic points of $f$ by ${\rm Per}(f)=\bigcup_{n}{\rm Per}_{n}(f)$.

In dynamics, it is a central goal to understand the asymptotic behavior of the
orbits of $f:X\to X$ for a large class of points in $X$. For instance, in
ergodic theory, large often means a set of full measure for an $f$-invariant
probability measure.

To motivate some of the challenges in studying families of dynamical systems
computationally, the following example illustrates one of the pitfalls in the
computational study of a single dynamical system.

######  Example 1.1.

Consider the $2x$-mod-$1$ dynamical system where $X=[0,1)$ and $f:X\rightarrow
X$ takes $x$ to the fractional part of $2x$. It is straightforward to show
that some iterate of $x$ is periodic if and only if $x$ is rational. Moreover,
every dyadic rational is eventually mapped onto the fixed point $0$.
Conversely, the closure of the orbit of an irrational point is either a Cantor
set or $X$ itself.

One challenge in studying this dynamical system computationally is that the
orbits of rational points are not representative of a typical orbit, even
though the rationals are dense in $X$. Also, the most common number types on a
computer are dyadic rationals, which exhibit even more atypical behavior. This
example illustrates that care must be taken with both the selection of
representative points and how conclusions are drawn from computational
experiments.

###  1.2. Computability theory

The main technique in computability theory is to replace a single mathematical
object by a convergent sequence, and to use the convergent sequence to study
the original object, see [4, 20].

######  Definition 1.2.

An oracle approximation of a real number $\alpha$ is a function $\psi$ such
that for any $n\in\mathbb{N}$, $\psi(n)$ is a rational number such that
$|\alpha-\psi(n)|<2^{-n}$. A real number $\alpha$ is computable if there
exists a Turing machine which is an oracle approximation for $\alpha.$

For most purposes, it is sufficient to think of a Turing machine as an
algorithm. Since every Turing machine is represented by a finite string of
characters from a finite alphabet, we conclude that the computable numbers
form a countable dense subset of the real numbers. This conclusion immediately
implies that noncomputable real numbers exist.

The error estimates in the definition of a computable real number are quite
strong. In some cases, there is a Turing machine that approximates $\alpha$
without an estimate on the convergence rate.

######  Definition 1.3.

A real number $\alpha$ is computable from above (respectively, from below) if
there exists a Turing machine $\psi$ such that on input $n$, $\psi(n)$ is a
rational number such that the sequence $(\psi(n))_{n\in\mathbb{N}}$ is a
decreasing (an increasing) sequence converging to $\alpha$.

We observe that computability is equivalent to simultaneous computability from
above and below. The ideas from computability theory can be extended to
functions as well as to many other settings.

######  Definition 1.4.

A function $f:{\mathbb{R}}\rightarrow{\mathbb{R}}$ is a computable function if
there exists a Turing machine $\phi$ with the following property: For any
$\alpha\in{\mathbb{R}}$ and oracle approximation $\psi$ for $\alpha$, on input
$(\psi,n)$, $\phi(\psi,n)$ is a rational number such that
$|f(\alpha)-\phi(\psi,n)|<2^{-n}$.

The Turing machine $\phi$ must be able to accept every oracle approximation
for any $\alpha$ (not merely Turing machines) and produce meaningful results.
Computable functions are necessarily continuous, and there are analogous
notions of computability from above and below for computable functions.

We introduce the concept of a computable metric space and refer the reader to
[13] for more details.

######  Definition 1.5.

Let $(X,d_{X})$ be a separable metric space and let
$\mathcal{S}_{X}=(s_{i})_{i\in\mathbb{N}}$ be a dense sequence of points in
$X$. We say that $(X,d_{X},\mathcal{S}_{X})$ is a computable metric space if
there is a Turing machine
$\chi:\mathbb{N}^{2}\times\mathbb{N}\rightarrow\mathbb{Q}$ such that
$|\chi(i,j,n)-d_{X}(s_{i},s_{j})|<2^{-n}$.

The definition for a computable metric space is equivalent to the
computability of the function $(i,j)\mapsto d_{X}(s_{i},s_{j})$. Importantly
the approximation is uniform, that is, the same Turing machine $\chi$ is used
for every $i$ and $j$ in $\mathbb{N}$. The definitions of computable numbers
and functions generalize to computable metric spaces by replacing the output
of Turing machines by an index $i\in\mathbb{N}$ of a point in
$\mathcal{S}_{X}$.

##  2\. Computability of Entropy

Arguably, the most important invariant of a dynamical system $f$ is its
topological entropy $H_{\rm top}(f)$. The topological entropy measures the
complexity of the dynamical system $f$, and it is invariant under topological
conjugation. Roughly, $H_{\rm top}(f)$ measures the exponential growth rate of
the number of orbit segments that can be distinguished up to an error of
$\varepsilon$. Specifically, for $n\in{\mathbb{N}}$ and $\varepsilon>0$, a
finite set $F\subset X$ is $(n,\varepsilon)$-separated if
$\max_{k=0,\ldots,n-1}d(f^{k}(x),f^{k}(y))\geq\varepsilon$ for distinct points
$x,y\in F$. Let $F_{n}(\varepsilon)$ denote the largest cardinality of an
$(n,\varepsilon)$-separated set. The topological entropy of $f$ is

(1) $H_{\rm top}(f)\vcentcolon=\lim_{\varepsilon\to
0}\limsup_{n\to\infty}\frac{1}{n}\log F_{n}(\varepsilon).$

From a computability standpoint, the limits in the formula for the topological
entropy make its calculation difficult. Even if $F_{n}(\varepsilon)$ can be
approximated for $n$ and $\varepsilon$, a computation cannot decide without
additional theory whether $\varepsilon$ is small enough and $n$ is large
enough for $F_{n}(\varepsilon)$ to approximate the limit.

We say that $f$ is expansive with expansivity constant $2\varepsilon_{0}$ if
for distinct $x,y\in X$, there is some $n$ such that
$d(f^{n}(x),f^{n}(y))>2\varepsilon_{0}$. In this case, we can omit the limit
on $\varepsilon$ and compute the $\limsup$ for $\varepsilon_{0}$. Then
sequence $(h_{n})_{n}$ defined by

(2) $h_{n}\vcentcolon=\min_{k\leq n}\frac{1}{k}\log F_{k}(\varepsilon_{0})$

is non-increasing and converges to $H_{\rm top}(f)$.

######  Corollary 2.1.

Let $f:X\to X$ be an expansive dynamical system with expansivity constant
$2\varepsilon_{0}$ that is given by an oracle $\chi$. If there exists a Turing
machine that takes $\chi$ and $n\in{\mathbb{N}}$ as input and computes
$F_{n}(\varepsilon_{0})$, then $H_{\rm top}(f)$ is upper semi-computable.

###  2.1. Symbolic dynamical systems

The class of symbolic systems form a rich family of discrete dynamical
systems. These systems provide good test cases for many theories as they can
be studied in a hands-on way, but have enough variability to provide
challenging examples. We review the relevant material from symbolic dynamics,
see [15].

Let $\mathcal{A}=\\{0,\dots,d-1\\}$ be a finite set called the alphabet. Let
${\mathcal{A}}^{\ast}$ denote the set of all finite words in ${\mathcal{A}}$.
The full shift $\Sigma$ with alphabet $\mathcal{A}$ is the set of bi-infinite
sequences $(x_{k})_{k\in{\mathbb{Z}}}$ of elements of ${\mathcal{A}}$. With
the Tychonov product topology, which coincides with the topology generated by
the metric

$d(x,y)\vcentcolon=2^{-\min\\{|k|\;:\;x_{k}\neq y_{k}\\}},$

$\Sigma$ is a compact metrizable topological space.

The (left) shift map $f:\Sigma\to\Sigma$ is defined by $f(x)_{k}=x_{k+1}$, and
we note that $f$ is a homeomorphism. We call a closed shift-invariant set
$X\subset\Sigma$ a shift space, and we say that $f:X\to X$ is a subshift.

For a fixed subshift $X$, let $\mathcal{L}(X,n)$ be the set of length-$n$
words which occur in some element of $X$. Moreover, we call
$\mathcal{L}=\bigcup_{n\in{\mathbb{N}}}\mathcal{L}(X,n)$ the language of $X$.
Languages and shift spaces are equivalent objects.

For a shift map $f:X\to X$, the entropy formula in Definition (1) reduces to

(3) $H_{\rm
top}(f|_{X})\vcentcolon=\lim_{n\rightarrow\infty}\frac{1}{n}\log\\#\mathcal{L}(X,n).$

Moreover, this limit converges from above.

An oracle $\chi$ of the language $\mathcal{L}(X)$ is a function such that
$\chi(n)$ is a list of the words of the language of length $n$. In light of
the simplicity of the entropy of a subshift $X$ and Corollary 2.1, one might
suspect that if the language of shift space is given by an oracle, then the
entropy $H_{\rm top}(f|_{X})$ is computable. This statement, however, is not
true.

The following theorem uses the notion of computability at a point, which is a
computable version of continuity at a point, see [8] for more details.

######  Theorem 2.2 ([6]).

The generalized entropy map $X\mapsto H(f|_{X})$ is computable at a nonempty
shift space $X_{0}$ if and only if $X_{0}$ has zero entropy. Moreover, there
is one Turing machine that uniformly computes the topological entropy at all
shift spaces with zero entropy.

This fact is proved by noting that the entropy is nonnegative, and, for any
value of ${\mathcal{L}}(X,n)$, there is a zero-entropy shift space
$X^{\prime}$ which has the same language as $X$ up to length $n$. For example,
$X^{\prime}$ can be a union of orbits of points whose forward and backward
tails are periodic. Thus, given only the language, the only possible lower
bound on the entropy is zero.

###  2.2. SFTs of finite type and Sofic shifts

Subshifts of finite type and Sofic shifts are among the shifts for which the
computability of their dynamics is best understood. Both of these shifts can
be described in terms of finite data.

Let $\mathcal{F}\subset\mathcal{A}^{\ast}$ be called a forbidden set. Then
$X_{\mathcal{F}}$ is defined to be the largest shift space such that no point
$x\in X_{\mathcal{F}}$ contains any of the words in $\mathcal{F}$.

######  Definition 2.3.

A shift space $X$ is a subshift of finite type (SFT) if $X=X_{\mathcal{F}}$
for some finite set of words $\mathcal{F}$.

The set $\mathcal{F}$ in this definition is not unique. A set $\mathcal{F}$ is
a minimal forbidden set for an SFT $X$ if for every word in ${\mathcal{F}}$,
all of its proper subwords appear in the language of $X$. It follows that
there is only one minimal forbidden set for an SFT. One less than the length
of the largest word in the minimal forbidden set is called the step size of
the SFT. Every SFT $X=X_{\mathcal{F}}$ is topologically conjugate to a one-
step SFT $X^{\prime}=X^{\prime}_{\mathcal{F^{\prime}}}$ on a possibly larger
alphabet $\mathcal{A^{\prime}}$. Moreover, given $\mathcal{F}$, the forbidden
set $\mathcal{F^{\prime}}$ can be computed by a Turing machine. Thus, it
suffices to study one-step SFTs. One-step SFTs can also be described via a
transition matrix, as follows: Let $A=(a_{i,j})$ be an
${\mathcal{A}}\times{\mathcal{A}}$ zero-one matrix. Then

(4) $X_{A}\vcentcolon=\\{(x_{k})_{k}:a_{x_{i},x_{i+1}}=1\\}$

is a one-step SFT. Moreover, every one-step SFT can be written this way.
Additionally, the entropy $H(f|_{X_{A}})$ of the SFT $X_{A}$ is the logarithm
of the spectral radius of the matrix $A$. Since there are algorithms that
compute the spectral radius of $A$ at any given precision, we obtain the
following result.

######  Proposition 2.4.

There is a Turing machine that computes the topological entropy of any SFT
given by either a finite forbidden set or a transition matrix.

######  Definition 2.5.

Let $\mathcal{T}=(G,E,L)$ be a finite labeled directed graph, where $G$ is a
graph with directed edge set $E$ and labeling function
$L:E\rightarrow\mathcal{A}$, which assigns a label $L(e)$ from the finite
alphabet $\mathcal{A}$ to each edge $e\in E$. Let $\xi=\cdots
e_{-1}e_{0}e_{1}\cdots$ be a bi-infinite path on $G$. The label of the path
$\xi$ is

$L(\xi)\vcentcolon=\cdots
L(e_{-1})L(e_{0})L(e_{1})\cdots\in\mathcal{A}^{\mathbb{Z}}.$

The set of all bi-infinite labels of paths is denoted by
$X_{\mathcal{T}}=\\{L(\xi):\xi\in G\\}$. A subset $X$ of the full shift is a
Sofic shift if $X=X_{\mathcal{T}}$ for a finite labeled graph $\mathcal{T}$.

A shift space $X$ is Sofic if and only if $X$ is a (finite-to-one) factor of
some SFT $Y$. In particular, every SFT is Sofic, but the converse is not true.
Moreover, there is a Turing machine that takes, as input, a finite labeled
directed graph $\mathcal{T}$ and outputs a transition matrix $A$ such that the
Sofic shift $X_{\mathcal{T}}$ is a factor of the SFT $X_{A}$. Since finite-to-
one factors preserve entropy, we obtain the following result.

######  Proposition 2.6.

There exists a Turing machine that computes the topological entropy of any
Sofic shift that is given by a finite labeled directed graph.

###  2.3. Invariant measures

There is a natural connection between topological and measure-theoretic
entropies, and we are interested in the computability properties of the
measure-theoretic entropy. A probability measure $\mu$ is said to be
$f$-invariant if $\mu(A)=\mu(f^{-1}(A))$ for all Borel sets $A$. For example,
if $x\in{\rm Per}_{n}(f)$ then
$\mu_{x}=\frac{1}{n}\sum_{k=0}^{n-1}\delta_{f^{k}(x)}$ is the unique invariant
measure supported on $\mathcal{O}(x)$, where $\delta_{f^{k}(x)}$ denotes the
Dirac measure on $f^{k}(x)$. Let $\mathcal{M}_{f}$ denote the space of all
$f$-invariant Borel probability measures on $X$ endowed with the weak∗
topology. With this topology, $\mathcal{M}_{f}$ is a compact convex metrizable
topological space. The extreme points in this convex space are denoted by
$\mathcal{M}_{f,E}$. These measures are precisely the ergodic measures, where
an $f$-invariant measure is ergodic if every $f$-invariant set has either
measure zero or one.

######  Example 2.7.

Let $X=[0,1)$ and $\alpha\in[0,\infty).$ Let $f:X\rightarrow X$ be a
translation by $\alpha$, i.e., $f(x)$ is the fractional part of $x+\alpha$. If
$\alpha\in{\mathbb{Q}}$, then every point in $X$ is periodic and
$\mathcal{M}_{f,E}=\\{\mu_{x}:x\in X\\}\cup\\{\lambda\\}$, where $\lambda$
denotes the Lebesgue measure. On the other hand, if
$\alpha\in{\mathbb{R}}^{+}\setminus{\mathbb{Q}}$ then
$\mathcal{M}_{f}=\mathcal{M}_{f,E}=\\{\lambda\\}.$

Let $H_{\mu}(f)$ denote the measure-theoretic entropy of $f$ with respect to
$\mu$. Roughly, $h_{\mu}(f)$ is similar to the topological entropy, but
ignores sets of measure zero, see Section 4 for details. The relationship
between the topological and measure-theoretic entropies is the variational
principle for the entropy, see Equation (5).

###  2.4. General and coded shifts

The computability properties of more general classes of shifts are more
complicated. One reason why these spaces are more challenging to study is that
their descriptions may be given in terms of infinite amounts of data. By
Corollary 2.1, if the language is given by an oracle, then the topological
entropy is upper semi-computable. Thus, we are interested in identifying when
the entropy is also lower semi-computable.

We approach this problem by using a sequence $\\{X_{m}\\}_{m\in{\mathbb{N}}}$
of Sofic shifts which “exhausts” $X$ in the sense that the entropy of these
$X_{m}$’s approaches that of $X$ from below. The challenge with this approach
is that the generalized entropy function $X\mapsto H_{\rm top}(f|_{X})$ might
not be continuous. Whenever such an approximation exists, one calls such a
shift an almost Sofic shift, see [19]. In most cases, the language itself is
not enough to compute such an approximation, we, therefore, focus on the case
where $X$ is generated from concatenations of a countable set of finite words,
that is $X$ is a coded shift.

To emphasize the generality of the class of coded shifts, we note that every
shift space $X$ can be expressed as the closure of the set of bi-infinite
paths on a countable directed labeled graph, called a representation of $X$,
see [15]. Coded shifts are precisely those shift spaces which have a
representation by an irreducible countable directed labeled graph. Many
classes of shifts spaces are coded shifts, including Sofic shifts, S-gap, and
Beta-shifts.

######  Definition 2.8.

A two-sided shift space $X$ over a finite alphabet
${\mathcal{A}}=\\{0,\dots,d-1\\}$ is coded if there exists a generating set
${\mathcal{G}}=\\{g_{i}\\}_{i\in{\mathbb{N}}}\subset{\mathcal{A}}^{\ast}$,
such that $X=X({\mathcal{G}})$ is the smallest shift space that contains all
bi-infinite concatenations of generators, i.e.,

$X_{\rm seq}{\vcentcolon=}\\{\cdots
g_{i_{-2}}g_{i_{-1}}g_{i_{0}}g_{i_{1}}g_{i_{2}}\cdots:i_{j}\in{\mathbb{N}},j\in{\mathbb{Z}}\\}.$

In other words, $X$ is the topological closure of $X_{\text{seq}}$, for more
details, see [3, 15].

Let $X_{m}\vcentcolon=X(\\{g_{1},\dots,g_{m}\\})$ be the coded shift generated
by the first $m$ generators in ${\mathcal{G}}$. Since each $X_{m}$ is a Sofic
shift, its entropy is computable. We observe that
$\\{X_{m}\\}_{m\in{\mathbb{N}}}$ is an increasing sequence of shift spaces in
$X_{\rm seq}$. In order to establish computability results for the entropy of
coded shifts, we study when the entropy of $\\{X_{m}\\}_{m\in{\mathbb{N}}}$
converges to the entropy of $X$. For this convergence to hold, we show that
the entropy on $X$ cannot be “concentrated” on $X\setminus\bigcup_{m}X_{m}$.

To make these notions more precise, we introduce the following two
definitions:

######  Definition 2.9.

[[6]] We say that $X$ has full sequential entropy if

$H_{\rm top}(f|_{X})=\sup_{\mu\in\mathcal{M}}\\{H_{\mu}(f):\mu(X_{\rm
seq})=1\\}.$

We say that $X$ has strict full sequential entropy if

$\sup_{\mu\in\mathcal{M}}\\{H_{\mu}(f):\mu(X_{\rm
seq})=1\\}>\sup_{\mu\in\mathcal{M}}\\{H_{\mu}(f):\mu(X\setminus X_{\rm
seq})=1\\}.$

We observe that strict full sequential entropy implies full sequential
entropy.

######  Definition 2.10 (cf [18]).

A unique representation of a coded shift $X$ is a generating set
${\mathcal{G}}$ of $X$ such that each $x\in X_{\rm seq}({\mathcal{G}})$ can be
uniquely written as an infinite concatenation of elements of ${\mathcal{G}}$.

The manuscript [1] includes a proof that all coded shifts have a unique
representation.

######  Theorem 2.11 ([6]).

Let $X$ be a coded shift with unique representation ${\mathcal{G}}$.

  1. (i)

If $X$ has strict full sequential entropy then $H_{\rm
top}(f|_{X})=\lim_{m\to\infty}H_{\rm top}(f|_{X_{m}})$.

  2. (ii)

Suppose $X$ has strict full sequential entropy. There exists a Turing machine,
independent of $X$, that computes $H_{\rm top}(f|_{X})$ from oracles for the
language and generating set ${\mathcal{G}}$ of $X$. In particular, $H_{\rm
top}(f|_{X})$ is computable; and

  3. (iii)

If $X$ does not have full sequential entropy, then the entropy is not
continuous at $X$ and hence is not computable at $X$.

Since the entropy is not continuous as a function of the shift space, the main
challenge in the proof of Statement (ii) of this theorem is to show that the
sequence of entropies for $X_{m}$ converges to that of $X$. In the proof of
Statement (iii), it is shown that the entropy for subshifts $X_{m}$ does not
converge to the entropy of $f$ on $X$. We refer to [6, 19] for examples of
coded shifts without full sequential entropy. In particular, there are coded
shifts for which the topological entropy is not computable.

###  2.5. Classification of entropies

An alternative to computing the entropy of a dynamical system is to classify
the computability properties of entropies of dynamical systems. For instance,
by Proposition 2.4, the entropies of all SFTs are not only computable, but
also are rational logarithms of Perron numbers, where a Perron number is a
real zero of an integer polynomial such that the zero is greater than one and
is the zero of largest magnitude. The converse of this statement also holds,
i.e., every rational logarithm of a Perron number is the entropy of some
mixing SFT, see [14].

A natural generalization of one-dimensional SFTs are multidimensional SFTs
which are finite type ${\mathbb{Z}}^{d}$-actions. In this case, the set of
possible entropies coincides with the set of positive upper computable numbers
[12]. Since there are upper computable numbers which are not computable, there
exist symbolic systems whose entropy is not a computable number. On the other
hand, the entropy of strongly irreducible higher dimensional SFTs is
computable.

In more generality, for computable dynamical systems, see the definition in
[10], the entropy is always a supremum of a computable sequence of upper-
computable numbers [10]. Moreover, for every positive such number, there is a
dynamical system over $\\{0,1\\}^{\mathbb{N}}$ which has this entropy and for
which the time evolution function is computable.

##  3\. Computability of Julia sets

Computer generated pictures of the Mandelbrot set and Julia sets can be quite
striking, but computability theory raises the question of whether the
underlying sample used to generate these sets accurately represents their true
shape. Julia sets are prototypes of fractals consisting of the points with
unpredictable dynamics. Since the dynamical behavior of nearby points can
differ, computations with sample points may not correctly capture the
dynamical behavior.

Let $\overline{{\mathbb{C}}}=\mathbb{C}\cup\\{\infty\\}$ be the Riemann Sphere
endowed with the spherical metric $d_{\overline{{\mathbb{C}}}}$. Let

$f_{c}(z)=z^{d}+c_{d-2}z^{d-2}+\dots+c_{0}$

be a polynomial of degree $d$, where
$c=(c_{d-2},\dots,c_{0})\in\mathbb{C}^{d-1}$. We denote the space of
polynomials of this form by $\operatorname{Pol}(d)$.

Fatou and Julia introduced a partition of $\overline{{\mathbb{C}}}$ into two
completely invariant sets, $F_{f}$ and $J_{f}$, called the Fatou and Julia
sets, respectively. The Fatou set $F_{f}$ is the set of points
$z\in\overline{{\mathbb{C}}}$ where the family of iterates of $f$ is
equicontinuous in a neighborhood of $z$. The Julia set $J_{f}$ is the
complement of $F_{f}$ in the Riemann sphere, and thus, the Fatou set is open,
while the Julia set is compact. In particular, $z\in F_{f}$ if and only if for
all $\varepsilon>0$ there exists $\delta>0$ such that
$d_{\overline{{\mathbb{C}}}}(z,w)<\delta$ implies
$d_{\overline{{\mathbb{C}}}}(f^{n}(z),f^{n}(w))<\varepsilon$ for all
$n\in{\mathbb{N}}$. In other words, the Fatou set is the set of points whose
orbits are Lyapunov stable. The Julia set is the set of points whose orbits
have sensitive dependence on the initial conditions, i.e., chaotic dynamics.

When $d=2$, the polynomials are of the form $f_{c}(z)=z^{2}+c$. The Julia set
of a quadratic polynomial is either connected or totally disconnected. The
connectivity-locus

$\mathcal{M}=\\{c\in\mathbb{C}:J_{c}\,\,\text{is connected}\\}$

is the famous Mandelbrot set. The filled-in Julia set of $f$ is defined by

$K_{f}=\\{z\in{\mathbb{C}}:\\{f^{n}(z):n\in{\mathbb{N}}_{0}\\}\,\,\text{is
bounded}\\}.$

The iterates of the points in $U_{f}=\overline{{\mathbb{C}}}\setminus K_{f}$
converge to $\infty$. Moreover,

$J_{f}=\partial K_{f}=\partial
U_{f}\,\,\text{and}\,\,F_{f}=U_{f}\cup\operatorname{int}K_{f}.$

The sensitivity to the initial conditions makes computing the Julia set
particularly challenging.

Figure 1. Examples of (filled-in) Julia sets for $z^{2}+c$: (a)
$c\not\in\mathcal{M}$, totally disconnected Julia set (b) $c\in{\rm
int}\mathcal{M}$, $f$ is hyperbolic (c) $c\in\partial\mathcal{M}$, Julia set
is a dendrite (d) $c\in\partial\mathcal{M}$, $0$ is parabolic fixed point. In
all these examples the Julia set is computable. These images were created with
Mathematica.

###  3.1. Computability of sets

######  Definition 3.1.

Let $S\subset{\mathbb{R}}^{m}$ be an open set. $S$ is a recursively open set
(also called a semi-decidable set or a lower-computable set) if there exists a
Turing machine $\psi$ that produces a (possibly infinite) sequence of pairs
$(z_{i},n_{i})$ so that $z_{i}\in{\mathbb{Q}}^{m}$ is a rational vector and
$n_{i}\in{\mathbb{Z}}$ so that $S=\cup_{i}B(z_{i},2^{-n_{i}})$

There is a Turing machine, whose input is $\psi$, that terminates if $s\in S$,
but may fail to terminate if $s\not\in S$.

######  Definition 3.2.

Let $S,T\subset{\mathbb{R}}^{m}$ be compact sets. The Hausdorff distance
between $S$ and $T$ is

$d_{H}(S,T)\vcentcolon=\max\\{\max_{s\in S}\min_{t\in T}d(s,t),\max_{t\in
T}\min_{s\in S}d(s,t)\\}.$

######  Definition 3.3.

Let $S\subset{\mathbb{R}}^{m}$ be compact. $S$ is computable if there exists a
Turing machine $\psi$ such that on input $n$, $\psi(n)$ is a finite collection
of pairs ${(q_{i},l_{i})}$ where $q_{i}\in{\mathbb{Q}}^{m}$ and
$l_{i}\in{\mathbb{Z}}$ such that
$d_{H}(\cup_{i}\overline{B}(q_{k_{i}},2^{-l_{i}}),S)<2^{-n}$

There is a Turing machine, whose input is $\psi$, that terminates if $s\not\in
S$, but may fail to terminate if $s\in S$.

###  3.2. Properties of periodic points

By a theorem of Fatou and Julia, the Julia set is the closure of the set of
repelling periodic orbits. A periodic point $\alpha\in{\rm Per}_{k}(f)$ is
repelling (respectively, attracting) if $|(f^{k})^{\prime}(\alpha)|>1$ (if
$|(f^{k})^{\prime}(\alpha)|<1$). A periodic point $\alpha\in{\rm Per}_{k}(f)$
is neutral if $|(f^{k})^{\prime}(\alpha)|=1$.

For a neutral periodic point, we replace $f$ by its $k$-th iterate so that
$\alpha$ is a fixed point. We write $f^{\prime}(\alpha)=e^{2\pi i\theta}.$ We
say that $\alpha$ is parabolic if $f^{\prime}(\alpha)$ is a root of unity,
i.e., $\theta\in{\mathbb{Q}}$. In this case, $\alpha\in J$ and the dynamics
near $\alpha$ is given by the Leau-Fatou Flower theorem, i.e., alternating
attracting and repelling petals [17].

We say that $\alpha$ is a Siegel point if the dynamics near $\alpha$ is
conjugate to the linear map $L_{\alpha}(z)=f^{\prime}(\alpha)z$. Then
$\alpha\in F_{f}$ and the connected component $U\subset F_{f}$ containing
$\alpha$ is a Siegel disk, i.e., there exists a conformal map $\varphi$ from
$U$ to the unit disk $D$ such that $f(z)=\varphi^{-1}\circ
L_{\alpha}\circ\varphi(z)$ for all $z\in U$.

By Bryuno’s Theorem, $\alpha$ is Siegel if $\theta$ is a Bryuno number, that
is,

$\sum_{n}\frac{\log(q_{n+1})}{q_{n}}<\infty,$

where $q_{n}$ is the denominator of the $n$-th continued fraction expansion of
$\theta$. Moreover, the Bryuno numbers have full Lebesgue measure. We denote
the set of degree $d$ polynomials with a Siegel disk by ${\rm Pol}_{\rm
Sie}(d)$.

###  3.3. Noncomputability of Julia sets

The map $c\mapsto J_{c}$ is not continuous at $c$ if $f_{c}$ has either a
parabolic or a Siegel point, see [5]. In particular, the map $c\mapsto J_{c}$
is not computable on ${\rm Pol}(d)$. Furthermore, for each non-computable real
number $c$, the Julia set $J_{c}$ is not computable without oracle access to
$c$.

Braverman and Yampolsky show that $c\mapsto J_{c}$ is computable on ${\rm
Pol}(d)\setminus{\rm Pol}_{\rm Sie}(d)$ by one Turing machine once some non-
uniform information about each parabolic point $\alpha$ of $f_{c}$ is
provided. This shows that the computability of the Juila set is problematic
only for polynomials with Siegel disks. For example, consider the quadratic
family

$f_{\theta}(z)=z^{2}+e^{2\pi i\theta}z,\quad\theta\in[0,1),$

which has a neutral fixed point at $0$. If $\theta$ is Bryuno, then
$f_{\theta}$ has a Siegel disk centered at $0$. In particular, $f_{\theta}$
has a Siegel disk at the origin for $\theta$-values in a set of full Lebesgue
measure. It is natural to conjecture that the non-computability of Siegel
Julia sets $J_{\theta}$ stems from the non-computability of $\theta$ –
surprisingly, this is not the case.

Braverman and Yampolsky also construct an explicit algorithm that computes
$\theta$-values with a Siegel disk at the origin. In particular, there exist
computable $\theta$ values with a noncomputable Julia set $J_{\theta}$. The
idea of this proof is to show that the Julia set $J_{\theta}$ is computable if
and only if the conformal radius $r(\theta)$ of its Siegel disk is computable.
In addition, they show that there are computable $\theta$’s such that
$r(\theta)$ is not computable. This shows that it is impossible to compute the
Julia set from $\theta$ alone since then $r(\theta)$ could be computed from
$\theta$, which is not possible.

###  3.4. Computability of filled Julia sets

For the filled-in Julia set the situation is better.

######  Theorem 3.4 ([5]).

For any $c$, there is a Turing machine that produces a $2^{-n}$-approximation
of the filled-in Julia set $K_{c}$ from an oracle for $c$ and
$n\in{\mathbb{N}}$.

The proof of Theorem 3.4 describes a pair of Turing machines, one which
terminates on points further than $2^{-n}$ from the filled-in Julia set, and a
second which terminates on points which are near the filled-in Julia set. The
second Turing machine classifies the behavior of points, e.g., near the Julia
set or an iterate in the interior of a Siegel disk.

This result does not imply that $c\mapsto K_{c}$ is computable on ${\rm
Pol}(d)$ since there would need to be one Turing machine that computes $K_{c}$
for all $c\in{\rm Pol}(d)$.

There are other recent results that discuss the computability of dynamically
defined sets, e.g., the computability of Lorenz attractors [11] and the
computability of generalized rotation sets [7].

##  4\. Computability of measures of maximal entropy

Let $f:X\to X$ be a continuous map on a compact metric space $(X,d)$. As in
Section 2.3, there is the notion of the measure-theoretic entropy $H_{\mu}(f)$
of an invariant measure $\mu$, see Section 4.1 for the definition. A measure
which maximizes $H_{\mu}(f)$ is called a measure of maximal entropy.

Roughly, $\mu$ is a measure of maximal entropy if the set of its typical
points carries the full topological complexity in terms of entropy. A
dynamical system might not have a measure of maximal entropy, or, when such a
measure exists, it might not be unique.

For several classes of dynamical systems, there exists a unique measure of
maximal entropy, e.g., transitive SFTs and sofic shifts. If
$f:\overline{{\mathbb{C}}}\to\overline{{\mathbb{C}}}$ is a polynomial of
degree $d\geq 2$, then $f$ has a unique measure of maximal entropy, called the
Brolin-Lyubich (B-L) measure $\lambda_{f}$. The measure of maximal entropy
$\lambda_{f}$ is fully supported on the Julia set $J_{f}$.

One might suspect that since there are non-computable Julia sets, the B-L
measure is also not computable. Surprisingly, this is not the case, and the
B-L measure is computable.

###  4.1. Measure-theoretic entropy

Using a result of Katok and Brin, we provide an intuitive description of
$H_{\mu}(f)$ as a measure-theoretic notion of complexity.

For $n\in{\mathbb{N}}$, define the Bowen $d_{n}$-metric on $X$ by

$d_{n}(x,y)=\max_{k=0,\dots,n-1}d(f^{k}(x),f^{k}(y)).$

We observe that $d_{n}$ induces the same topology on $X$ as $d$. Let
$B_{n}(x,\varepsilon)$ denote the Bowen-ball of radius $\varepsilon$ with
center $x$ in the $d_{n}$-metric.

######  Theorem 4.1 (Katok-Brin).

Let $\mu\in\mathcal{M}_{f}$. Then

$H_{\mu}(x)\vcentcolon=\lim_{\varepsilon\to
0}\lim_{n\to\infty}-\frac{\log(\mu(B_{n}(x,\varepsilon))}{n}$

exists for $\mu$ for almost every $x\in X$ and $H_{\mu}(\cdot)$ is
$\mu$-measurable. Moreover, if $\mu$ is ergodic, then $H_{\mu}(\cdot)$ is
constant almost everywhere.

The quantity $H_{\mu}(x)$ is called the point-wise entropy of $\mu$ at $x$,
and we define

$H_{\mu}(f)=\int_{X}H_{\mu}(x)\,d\mu(x).$

For $H_{\mu}(x)$ to be positive, the measure of the Bowen balls must decay
exponentially to zero in $n$. Since Bowen balls are sets of points that stay
close together under iteration, one infers that $H_{\mu}(f)>0$ implies that
$\mu$ must be “concentrated” on sets whose points are pushed apart under
iteration. Thus, $\mu$ is concentrated on sets where a small change in the
initial condition results in different dynamical behavior.

Bowen also defines the topology entropy $H_{\rm top}(Y)$ for arbitrary sets
$Y\subset X$. If $\mu$ is ergodic, then $H_{\mu}(f)=H_{\rm
top}({\mathbb{G}}_{\mu}),$ where ${\mathbb{G}}_{\mu}$ denotes the set of
$\mu$-generic points of $\mu$, where a point $x$ is $\mu$-generic if its orbit
distribution coincides with the measure $\mu$, i.e.,

$\lim_{n\to\infty}\frac{1}{n}\sum_{k=0}^{n-1}\delta_{f^{k}(x)}=\mu,$

in the weak∗ topology. As a consequence of Birkhoff’s Ergodic theorem, for
every ergodic measure $\mu$, the set of $\mu$-generic points has full
$\mu$-measure. The topological and measure-theoretic entropies are related by
the variational principle for the entropy:

(5) $H_{\rm top}(f)=\sup_{\mu\in\mathcal{M}_{f}}H_{\mu}(f).$

###  4.2. Properties of B-L measures

The B-L measure $\lambda$ is characterized by the following equivalent
properties, see e.g. [2]:

  1. (1)

$H_{\lambda}(f)=\log d=H_{\rm top}(f);$

  2. (2)

$\lambda(f(A))=d\cdot\lambda(A)$ for all measurable sets $A$ on which $f$ is
injective;

  3. (3)

$\lim_{n\to\infty}\frac{1}{d^{n}}\sum_{w\in f^{-n}(z)}\delta_{w}=\lambda$ for
all but finitely many $z\in{\mathbb{C}}$ in the weak∗ topology;

  4. (4)

$\lambda$ is the harmonic measure at infinity of the filled-in Julia set
$K_{f}$.

###  4.3. Computability of measures

Let $\mathcal{M}(\overline{{\mathbb{C}}})$ denote that space of Borel
probability measures on $\overline{{\mathbb{C}}}$ endowed with the weak∗
topology. We endow $\mathcal{M}(\overline{{\mathbb{C}}})$ with the
Wasserstein-Kantorovich metric defined by

$W_{1}(\mu,\nu)\vcentcolon=\sup_{\phi\in 1-{\rm
Lip}(\overline{{\mathbb{C}}})}\left|\int\phi\,d\mu-\int\phi\,d\nu\right|,$

where $1{\rm-Lip}(\overline{{\mathbb{C}}})$ is the space of real-valued
Lipschitz functions on $\overline{{\mathbb{C}}}$ with Lipschitz constant $1$.
Let ${\mathbb{D}}$ denote the set of probability measures on
$\overline{{\mathbb{C}}}$ that are finite rational convex combinations of
Dirac measures supported on points in ${\mathbb{C}}$ with rational
coordinates. Then $(\mathcal{M}(\overline{{\mathbb{C}}}),W_{1},{\mathbb{D}})$
is a computable metric space.

###  4.4. Computability of B-L measures

We address the computability of the map ${\rm Pol}(d)\ni c\mapsto\lambda_{c}$
from polynomials to B-L measures.

######  Definition 4.2.

The function $c\mapsto\lambda_{c}$ is computable if there exists a Turing
machine $\phi$ with the following property: For any $c\in{\rm Pol}(d)$ and any
oracle approximation of $\psi$ of $c$, on input $\psi$ and $n$, $\phi(\psi,n)$
is a measure in ${\mathbb{D}}$ with $W_{1}(\phi(\psi,n),\lambda_{c})<2^{-n}$.

######  Theorem 4.3 ([2]).

Let $d\geq 2$. Then $c\mapsto\lambda_{c}$ is computable.

The proof of Theorem 4.3 follows from general statements about the
computability of measures in $\mathcal{M}(\overline{{\mathbb{C}}})$ and from
the characterization of the B-L measure in Property 2 of Section 4.2.

We note that Theorem 4.3 is surprising for parameters with non-computable
Julia sets. To see this consider a (non-exceptional) point
$z_{0}\in{\mathbb{C}}$. For any given $n\in{\mathbb{N}}$, the pre-images
$f_{c}^{-n}(z_{0})$ can be calculated at any pre-described accuracy. Moreover,

(6) $f_{c}^{-n}(z_{0})\quad\longrightarrow\quad J_{c}$

in the Hausdorff metric. If $c$ is a parameter for which $J_{c}$ is not
computable, then the accuracy of the convergence in Equation (6) can not be
controlled by a Turing machine, but the convergence of

(7) $\frac{1}{d^{n}}\sum_{w\in
f_{c}^{-n}(z_{0})}\delta_{w}\quad\longrightarrow\quad\lambda_{c}$

in the weak∗ topology can be computed at any prescribed accuracy. Since the
support of the B-L measure is the entire Julia set, we interpret the
convergence in Equation (7) as covering most of the Julia set at a prescribed
rate which is sufficient to compute the B-L measure.

There are additional results in the literature concerning the computability
and non-computability of other dynamically relevant measures including
physical measures, e.g. [9].

## References

  * [1] M.P. Béal, D. Perrin, and A. Restivo.  Unambiguously coded systems.  2021\.  https://arxiv.org/abs/2103.01012.
  * [2] I. Binder, M. Braverman, C. Rojas, and M. Yampolsky.  Computability of Brolin-Lyubich measure.  Comm. Math. Phys., 308, 2011.
  * [3] F. Blanchard and G. Hansel.  Systèmes codés.  Theoret. Comput. Sci., 44:17–49, 1986.
  * [4] V. Brattka, P. Hertling, and K. Weihrauch.  A tutorial on computable analysis.  In S.C. Barry, B. Löwe, and A. Sorbi, editors, New Computational Paradigms: Changing Conceptions of What is Computable, pages 425–491. Springer, New York, 2008.
  * [5] M. Braverman and M. Yampolsky.  Computability of Julia sets.  Mosc. Math. J., pages 185–231, 2008.
  * [6] M. Burr, S. Das, C. Wolf, and Y. Yang.  Computability of topological pressure on compact shift spaces beyond finite type.  Nonlinearity, 35:4250–4282, 2022.
  * [7] M. Burr, M. Schmoll, and C. Wolf.  On the computability of rotation sets and their entropies.  Ergodic Theory Dynam. Systems, 40:367–401, 2020.
  * [8] M. Burr and C. Wolf.  Computability at zero temperature.  Nonlinearity, 33:6157––6175, 2020.
  * [9] S. Galatolo, M. Hoyrup, and C. Rojas.  Dynamics and abstract computability: computing invariant measures.  Discrete Contin. Dyn. Syst., 29:193–212, 2011.
  * [10] S. Gangloff, A. Herrera, C. Rojas, and M. Sablik.  Computability of topological entropy: from general systems to transformations on Cantor sets and the interval.  Discrete Contin. Dyn. Syst., 40:4259–4286, 2020.
  * [11] D. S. Graça, C. Rojas, and N. Zhong.  Computing geometric Lorenz attractors with arbitrary precision.  Trans. Amer. Math. Soc., 370:2955–2970, 2018.
  * [12] M. Hochman and T. Meyerovitch.  A characterization of the entropies of multidimensional shifts of finite type.  Annals of Mathematics, 171:2011–2038, 2010.
  * [13] Mathieu Hoyrup and Cristóbal Rojas.  Computability of probability measures and Martin-Löf randomness over metric spaces.  Inform. and Comput., 207:830–847, 2009.
  * [14] D. A. Lind.  The entropies of topological Markov shifts and a related class of algebraic integers.  Ergodic Theory Dynam. Systems, 4:283–300, 1984.
  * [15] Douglas Lind and Brian Marcus.  An introduction to symbolic dynamics and coding.  Cambridge University Press, Cambridge, 1995.
  * [16] John Milnor.  Is entropy effectively computable?  http://www.math.stonybrook.edu/~jack/comp-ent.pdf, 2002.
  * [17] John Milnor.  Dynamics in one complex variable, volume 160 of Annals of Mathematics Studies.  Princeton University Press, Princeton, NJ, third edition, 2006.
  * [18] R. Pavlov.  On entropy and intrinsic ergodicity of coded subshifts.  Proc. Amer. Math. Soc., 148:4717–4731, 2020.
  * [19] Karl Petersen.  Chains, entropy, coding.  Ergodic Theory and Dynamical Systems, 6(3):415–448, 1986.
  * [20] Cristóbal Rojas and Michael Yampolsky.  Computable geometric complex analysis and complex dynamics.  In Handbook of computability and complexity in analysis, Theory Appl. Comput., pages 143–172. Springer, Cham, 2021.