{'fraction_non_alphanumeric': 0.04193871229090216, 'fraction_numerical': 0.012438640804460754, 'mean_word_length': 4.203074634267295, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Computability of entropy and information in classical Hamiltonian systems

We consider the computability of entropy and information in classical Hamiltonian systems. We define the information part and total information capacity part of entropy in classical Hamiltonian systems using relative information under a computable discrete partition. Using a recursively enumerable nonrecursive set it is shown that even though the initial probability distribution, entropy, Hamiltonian and its partial derivatives are computable under a computable partition, the time evolution of its information capacity under the original partition can grow faster than any recursive function. This implies that even though the probability measure and information are conserved in classical Hamiltonian time evolution we might not actually compute the information with respect to the original computable partition.


Introduction
In statistical mechanics, entropy is one of the most important concept. Entropy is the measure of uncertainty, and statistical mechanics can be viewed as the best theory we can get with the constraint of uncertainty or partial information [1,2]. Even though the Hamiltonian time evolution conserves the probability and probability measure, the second law of thermodynamics states the entropy is nondecreasing in time. From the information theoretical perspective this may imply that information is lost during the computation of Hamiltonian time evolution. With rapid advances of numerical computation of physical systems, up to which extent we can actually compute the entropy and keep the information during its time evolution became an important and interesting problem.
Computability means that there is an algorithm of calculating a quantity with a Turing machine up to arbitrary precision. Originally this algorithm issue is related to the Hilbert's plan to prove or disprove all statements derived from axiomatic systems in a systematic way. But in 1930s, Gödel showed that in an axiomatic system which is strong enough to express natural numbers there exist unprovable statements [3]. Turing applied this to the programs and showed there exist problems which are not solvable by algorithms [4].
With the advances of algorithmic information theory, G. Chaitin showed that in a formal system with n bits of axioms it is impossible to prove that a particular binary string is of Kolmogorov complexity greater than n + c [5].
In analysis and differential equations what kind of quantities can be computed is also researched [6]. In the wave equations and ordinary differential equations Pour-El, I. Richards and Zong showed that a computable initial condition may evolve to a noncomputable solution at the later time [7,8,9], and discussed how these phenomena would be related to the actual computation with Turing machine [10]. The undecidability and computability in physical systems are also studied [11,12]. C. Moore showed a Hamiltonian system can be mapped into a Turing machine, and where the trajectories are passing can be mapped into the Halting problem. Z. Xia [13] showed that a gravitational system may have non-collision singularity which makes the system not computable. Noncomputability of topological entropy in various systems are also researched [14,15]. Recently D. Graça et.al. [16,17] showed that an ordinary differential equation can be mapped into a Turing machine.
In this article we apply computability approach [18,19] to the entropy and information of a probability distribution in classical Hamiltonian systems. We define the entropy of a continuous probability distribution through a discrete computable partition in the phase space. This entropy we define are divided as two parts, one representing information and the other representing information capacity. We show that even though the initial entropy and Hamiltonian is computable the time evolution of entropy may not be computable.

Entropy, information and information capacity
Let us first define entropy and information for the discrete probabilities and probability distributions. We follow Shannon's definition [20]. Shanonn entropy for discrete probabilities P 1 , ..., P n , ... is If we take the base of the logarithm as 2 then the unit of entropy is bits. This entropy is a measure of uncertainty or the ability to store information. If we have an unknown digit X which can be either 0 or 1 with probability 1/2 each, we have 1 bit of entropy. The system has one bit of uncertainty or the capacity to store one bit of information. If the unknown digit X is identified as 0, the probability for 0 is 1 and probability for 1 is 0. From Eq. (1) entropy becomes 0 ( 0 log 0 is considered 0 as the limit value) and we say we gain 1 bit of information and entropy is reduced to 0 bit.
Let us apply Eq. (1) for continuous probability distribution inside a phase space Ω given by the momenta and coordinates (p, q). Consider the probability distribution function ρ(p, q, t) of a particle in the phase space, which satisfies Liouville's equation. Suppose that ρ(p, q, t) has a finite support. To define probabilities and actually compute them continuous phase space and the probability distribution are discretized. Suppose that we discretize the phase space by countable number of cells with the same volume µ. The probability distribution is also discretized by where the integral at RHS of Eq. (2) is over the ith cell. ρ i and µ satisfies the relation Using Shannon's definition, the entropy of the system S(ρ, µ) is whereρ i = ρα andμ = µ/α. The scaling constant α is inserted to make the argument of log dimensionless. As the cell size µ becomes smaller and smaller, the first term in RHS (right hand side) of Eq. (4) converges to the phase space integral − i ρ i log(ρ i α)µ → − dΩ ρ log(ρα) if the integral exists. The second term diverges as log(α/µ). These terms can be interpreted as follows.
If α is chosen as the volume of probability distribution's support, the first part in Eq. (4) is always nonpositive. This term is called negative of so-called relative entropy or Kullback-Leibler divergence [21]. In general the Kullback-Leibler divergence is defined for two probability distributions P (x) and Q(x) as D KL (P ||Q) = P (x) log(P (x)/Q(x))dx and always nonnegative. For our choice of α the first term in integral limit is always nonpositive and becomes zero only when the probability distribution is uniformly distributed on its support. Since the negative entropy decreases uncertainty it can be interpreted as the information we gain for the probability distribution ρ with respect to the uniform distribution 1/α. This term is also referred as 'physical entropy [22]' or 'coarse-grained entropy' over measure [23]. In the integral limit (often setting α = 1) dΩρ log(1/ρ) is called a 'differential entropy'. The second term is the total information capacity, which is positive when α/µ > 1. This term depends on how fine the measures are. The information is minimum when ρ is uniform distribution 1/α on the support α. In descrete case the information is maximum log N when ρ is discrete delta (ρ = N for one cell and zero for all others), and diverges as the distribution goes to the Dirac delta distribution. This coincides with the fact that in general infinite digits are needed to specify a real number. The entropy and information we defined in Eq. (4) are subjective. First they depend on the chosen partition, in this case discrete grid size µ which determines the coarse grained precision. Second they depend on the scale α, which determines how the we divide the information part and information capacity part.
With this definition of entropy and information we consider the entropy of probability distribution with Hamiltonian time evolution with respect to the initial discrete partition. Since it is a classical Hamiltonian system, as time changes the probability density moves like an incompressible fluid in phase space, i.e. if one follows the time evolution of a point in phase space the density at the representation point remains constant and the measure is conserved. In actual computation of time evolution of initial probability distribution, one first discretize the probability density and evolve this discretized probability density with time (in most cases the probability distribution at later times can be only known numerically).
Suppose that at time t = 0 we make a discrete partition of phase space. This discrete partition divides the phase space with countable number of cells. Let us call the initial ith discretized probability density and ith partitioning cell as ρ i (0) and C i (0), like in Eq. (2). Then we compute the time evolved, discretized probability density. In most cases the exact analytic form of ρ(t) is not known, so the discretized probability in time t is obtained by the time evolution of ρ i (t), which is the discretized probability density at t = 0. As time passes the original cell C i (0) deforms to C i (t), but the discretized probability distribution inside the deformed cell is still ρ i (0). The deformed cell C i (t) will be spread over the original discretized partition. If our computing precision is fixed, then the new discretized probability density is computed by the same discretized cells at t = 0. Let us write the new discretized probability distribution within the initial ith cell as ρ i (t) (see Fig. 1). We have where a ij (t) is given by This probability distribution averaging (coarse graining) is the place where the information is lost due to the finite information capacity.
From Eq. (6) we have the relation After one time step, the new entropy S(t) computed with P i (t) using fixed precision C i (0) is where Eq. (3) and Eq. (7) is used. Since the function f (x) = x log(λx) with λ > 0 is a convex function and the convex function satisfies Jensen's inequality we have We see that the information capacity part of S(t) in Eq. (8) is the same, but the negative entropy (information) part of S(t) is always greater or equal than the information part of S(t). This means that the information is always same or lost due to the coarse graining. One way to avoid the information loss is using finer partition. If the entropy is calculated for each fractional probabilities of P ij (t) = a ij (t)ρ j (0)μ, we have The first term in RHS of Eq. (11) is information, which is the same as before. But the total information capacity is increased by where − j a ij (t) log a ij (t), which is always nonnegative since a ij (t) ≥ 0, represents the entropy increase (information capacity increase) due to the finer partition or resolution. For example in baker transformation this term is log 2 = 1 bit for each discrete time step.
Now we ask the question of computation of entropy and its time evolution. As stated before, the total entropy is a subjective quantity which depends on the partition we choose. Given the computable partition and computable initial conditions, can we compute the information and the total information capacity needed to keep the information during time evolution? To answer this question, we first need definitions about computability.

Computability preliminaries
The following definitions, theorems and examples are from the book of M. B. Pour-El and J. I. Richards [18]. Here the term recursive function means it can be implemented and calculated by a Turing machine. N denotes the set of non-negative integers. We now define computable functions. For simplicity we first consider the case where the function f is defined on a closed bounded rectangle I q in R q . Specifically (ii) f is effectively uniformly continuous , i.e. there is a recursive function d : N → N such that for all x, y ∈ I q and all N: Now the function in R q is considered.
Definition 5 A sequence of functions f n : R q → R is computable if: (i) for any computable sequence of points x k ∈ R q , the double sequence of reals {f n (x k )} is computable; (ii) there exists a recursive function d : N × N × N → N such that for all M, n, N : Theorems about computability of integrals of functions.
Theorem 1 Let I q be a computable rectangle in R q , and let f n : I q → R be a computable sequence of functions. Then the definite integrals v n = ... Now we define the recursively enumerable nonrecursive set.
A set A ⊆ N is called recursively enumerable if A = ∅ or A is the range of a recursive function a. In other words, we can compute a(0), a(1), a(2)... step by step using a Turing machine.
A set A ⊆ N is called recursive if both A and its complement N − A are recursively enumerable.

A fundamental and important theorem of logic is that
Theorem 3 There exists a set A ⊆ N which is recursively enumerable but not recursive.
If a set A is recursively enumerable but nonrecursive, then we have a recursive (or computable) procedure to get the elements a(0), a(1), a(2), ... sequentially, but we have no recursive (or computable) procedure to tell an arbitrary number α ∈ N belongs to A or not. We do not know how long we should compute the sequence to see α appears. This is expressed in the following lemma.
Lemma 1 (Waiting lemma). Let a : N → N be a one to one recursive function generating a recursively enumerable nonrecursive set A. Let w(n) denote the "waiting time" w(n) = max{m : a(m) ≤ n}.
Then there is no recursive function c such that w(n) ≤ c(n) for all n.
One example of recursively enumerable nonrecursive set is the set of Halting programs.
Next theorem is about the convergence of sequence of functions. The proof is in [18].
Theorem 4 (Closure under effective uniform convergence) Let f nk : I q → R be a computable double sequence of functions such that f nk → f n as k → ∞, uniformly in x, effectively in k and n. Then {f n } is a computable sequence of functions. Now we show an example of a function which is not bounded by any recursive function, which will be used later in section 4.
Example Let a : N → N be a one to one recursive function generating a recursively enumerable nonrecursive set A. We assume 0 / ∈ A. Then the function f (z) = ∞ m=0 z m /a(m) m is an entire function but not bounded by any recursive function.
In this example, the sequence of Taylor Hence f (2n) > w(n) and w(n) is not bounded by any recursive function, so f (z) is not bounded by any recursive function.
With these preliminaries, next section we construct an example in which the time evolution of entropy is not computable.

Computability of time evolution of entropy
In this section we construct a Hamiltonian system, in which the Hamiltonian and its partial derivatives, initial probability distribution and information are computable under a computable partition but the time evolution of entropy under the original partition grows faster than any recursive function.
To construct our Hamiltonian and probability distribution we first define a pulse function 0. otherwise (14) This function is in C ∞ and has the support [−1, 1] (Fig. 2). We define the normalization constant of φ(x) as N φ = 1/ 1 −1 φ(x)dx = 0.828569... . N φ is computable, since it is an integral of computable function under a bounded interval by theorem 1.
We define another pulse function where φ int (x) is given by φ int (x) is 0 for x < −1, increases smoothly (C ∞ way) from 0 to 1 for −1 ≤ x ≤ 1 and 1 for 1 ≤ x. This is a computable function by theorem 2. The shape of ψ(x) is shown in Fig. 3. It is a C ∞ function, which increases from 0 to 1 in C ∞ way on the interval (−3/8, −1/4), constant value 1 between −1/4 and 1/4, and decreases from 1 to 0 in C ∞ way on the interval (1/4, 3/8). Otherwise it is 0. Both φ(x) and ψ(x) are computable functions.

The Hamiltonian is constructed by
where H m is defined as Since each support of H m are in m − 3/8 ≤ q 3 ≤ m + 3/8 (none of them overlap), for any computable point (p, q) we can make a ball centered at that point with radius 2 −N and for sufficiently large N this ball contains at most one H m , which is a computable function. With this fact and definition 5 we see that H is a computable function in R 6 . Also all ∂Hm ∂p i and ∂Hm ∂q i are computable and we can choose a neighborhood of computable point which contains at most one nonzero derivatives of H m . By the same logic all ∂H ∂p i and ∂H ∂q i are computable.
Again, each ρ mn is computable and none of the supports of ρ mn overlap. For any computable point if we choose radius 2 −N sized ball centered at that point with large enough N it overlaps at most one nonzero ρ mn which is a computable function. From definition 5 ρ(p, q) is computable. N ρ is the normalization constant, which makes ρ(p, q)dpdq = 1. N ρ is also a computable number since the sum m,n dpdqρ mn = m,n 2 −12n−2m−3 /a(n) n converges faster than a geometric series.
Next we compute the information and entropy of initial probability distribution. In Eq. (4), the entropy is defined through the probabilities with a computable partition. Here computable partition means that boundaries of the partition are made with computable functions and any computable finite area can be covered by increasing the number of partitions in a recursive way. Let us choose the original partition as p i = k2 −np and q i = k2 −np surfaces (i = 1, 2, 3. n p is a (possibly large) natural number. k = 0, 1, 2, ...). Then the smallest cell in this partition is 6 dimensional hypercube with each side 2 −np and volume µ = 2 −6np . For a given scale α which defines the unit volume, − log(µ/α) is the precision one can get for the volume and − log(2 −np /α) is the precision for each coordinate. For now let us choose the scale α as 1.
Under this partition, for any natural number n p , the information part is − iρiμi logρ i < (6n+ m)2 −6n−m for each ρ mn pulse. The total ρ the information part is dominated by m,n (6n+m)2 −6n−m which is effectively convergent, so the initial information under this partition is computable. The information capacity part is − logμ and also computable.
Now we consider the time evolution of probability distribution and its entropy and information under the original partition. Since the Hamiltonian time evolution is measure preserving, the term − iρiμi logρ i is conserved during the time evolution if we make finer partition. But the information capacity term, which depends on the finer partition and ability to resolve the probability distribution with original partition , increases with time as the second term in RHS of Eq. (11) shows.
This solution shows exponential of exponential squeezing and stretching in p 1 and q 1 directions. For example a rectangle in p 1 q 1 space with side lengths δp 1 and δq 1 at t = 0 is stretched to a rectangle with side lengths δp 1 exp(−e nt+p 2 (0) + e p 2 (0) ) and δq 1 exp(e nt+p 2 (0) − e p 2 (0) ).
If the partition in p 1 q 1 space is made with δp 1 δq 1 cells, then the time evolution of one cell is stretched and overlaps at least N s = [exp(e nt+p 2 (0) − e p 2 (0) )] number of other cells in q 1 direction. ([x] means the largest integer not larger than x.) In p 1 direction N s number of partial cells are squeezed into one cell and at least log N s bits of resolution is needed to distinguish the thin strips of cells in the original one cell.
In view of the information capacity term iρi (0)μ − j a ji (t) log a ji (t) , for theρ i (0) which is in n − 1/4 ≤ q 3 ≤ n + 1/4 each a ji (t) is around 1/N s and it is summed over N s terms. So − Ns j=1 a ji (t) log a ji (t) ≈ log N s .
From Eq. (4), 0 ≤ p 2 (0) ≤ 1 for all ρ mn and exp(e nt ) < exp(e nt+p 2 (0) − e p 2 (0) ) < exp(e 2nt ) (24) for t ≥ 2. If we consider the whole 6 domensional space the number of overlapping cells are larger due to the exponential stretching in q 2 direction. So for each ρ i µ segment which is in n − 1/4 ≤ q 3 ≤ n + 1/4 the term − a ji (t) log a ji (t) is bounded by for t ≥ 2. Considering all ρ mn pulses for fixed n, the information capacity increase in n − 1/4 ≤ q 3 ≤ n + 1/4 is bounded by Like the example at the end of section 3, we see that the information capacity increase in time t = 0, 1, 2, 3, ... are finite but not bounded by any recursive function, for any µ. The information capacity is related to the ability to describe how far a cell is stretched or how many other cells are squeezed into an original cell for probability pulses in µ accuracy. But this grows faster than any recursive function and we cannot find a recursive way to compute information within the original computable partition.
bounded by any recursive function. Its total entropy, which is defined through a computable discrete partition, is originally computable but its time evolution grows faster than any recursive function. This total entropy is related to the precision required to compute the information, so the time evolution of information is not computable within the original computable discrete partition. Even though the information is a conserved quantity in the Hamiltonian time evolution, the result shows that we might not actually compute it.