On finitistic addition

By a finite alphabet encoding of a set X, such as the real numbers, I mean a one-to-one function ψ from X to countably infinite sequences s₀s₁... taken from some finite alphabet. For instance, standard decimal encoding, with a decision whether to have infinite sequences of trailing nines or not, is a finite alphabet encoding of the reals, with the alphabet consisting of ten digits, a decimal point and a sign. Write ψ_k(x) for the kth symbol in the encoding ψ(x) of x.

A function f from Rⁿ to R is finitistic with respect to a finite alphabet encoding ψ provided that there is a function h from the natural numbers to the natural numbers such that the value of ψ_k(f(x₁,...,x_n)) depends only on the first h(k) symbols in each of ψ(x₁), ..., ψ(x_n).

This concept is related to concepts in “real computation”, but I am not requiring that the finite dependences be all implemented by the same Turing machine.

Theorem: Let X be any infinite divisible commutative group. Then addition on X is not finitistic with respect to any finite alphabet encoding.

A divisible group X is one where for every x ∈ X there is a y such that ny = x. The real numbers under addition are divisible. So are the rationals. So is the set of all rotations in the plane.

This has a somewhat unhappy consequence for Information Processing Finitism. If reality encodes real numbers in a discrete way consistent with IPF, we should not expect each real number to have a uniquely specified encoding.

Proof of Theorem: Suppose addition is finitistic with respect to ψ. Let F be the algebra on X generated by the sets of the form {x : ψ_k(x) = α}. If addition is finitistic, then for any A ∈ F, there is a finite sequence of pairs (A₁,B₁), ..., (A_N,B_N) of sets in F such that

1. {(x,y) : x + y ∈ A} = ⋃_i(A_i×B_i).

Therefore:

2. x + y ∈ A if and only if x ∈ ⋃{A_i : y ∈ B_i}.

Thus:

3.  − y + A =  ∪ {A_i : y ∈ B_i}.

Now as y varies over the members of X, there are at most 2^N different sets generated by the right hand side. Thus,  − y + A can take on only finitely many values. Hence, A has only finitely many translates.

But this is impossible. Let Z be the set of x such that x + A = A. This is an additive subgroup of X. Note that x + Z = y + Z iff x − y ∈ Z iff (x−y) + A = A iff x + A = y + A. Thus, if there are only finitely many x + A, there are finitely many x + Z. Hence X/Z is a finite group. Let n be its order. Then n[x] = 0 for every coset [x] = x + Z in R/Z. For any x ∈ X choose y such that ny = x. Then n[y] = 0, and so [x] = 0, thus Z = X. It follows that A is invariant under every translation, so it must be either ⌀ or X. Hence |F| ≤ 2, which is absurd since F is infinite as X is infinite and ψ is one-to-one.

(I got the main idea for this proof from the answer here.)

Information Processing Finitism

When I was trying to work out my intuitions about causal paradoxes of infinity, which eventually led to my formulating the thesis of causal finitism (CF)—that nothing can have an infinite causal history—I toyed with views that involved information. I ended up largely abandoning that approach, partly because of my qualms about the concept of information and perhaps partly because of worries about physics that I will discuss below.

But I still think the alternative, which one might call information processing finitism, is something someone should work out in more detail.

• [IPF] Nothing with finite informational content can essentially causally depend on anything with infinite informational content.

Here, informational content is by definition contingent. The “essentially” excludes cases where finite informational content depends on a finite part of something with infinite informational content. How exactly the “essentially” is spelled out is one thing I am not clear on as yet.

The main difficulty with IPF is that our physics seems to violate it. The exact current temperature in Waco depends on the exact temperature, pressure and other facts around the world yesterday. Each of the latter facts involves infinite information—temperature is quantified with a real number, and a real number contains infinite information. Note that here IPF and CF may diverge. An advocate of CF can say that the exact current temperature in Waco depends on a finite number of past events such as “yesterday particle n has parameters P”, even if the parameters P involve real numbers that have infinite energy.

One way to escape this difficulty is to assume that our fundamental physics is actually discrete, and the real numbers in our equations are just an approximation. But I don’t want to stick my neck out so far.

Let’s see if we can make IPF work out with a continuous dynamics. We can suppose that metaphysically speaking, an entity’s having a real-valued parameter is constituted by the entity’s having an infinite sequence of discrete parameters, which parameters are more ontologically fundamental than the real-valued parameter.

For instance, by a one-to-one mapping we can assume our real number is strictly between zero and one, and then define it as an infinite decimal sequence 0.b₁b₂..., specified by an infinite sequence of digits. Unfortunately, then, we have some severe restrictions on what kind of dynamics we can have if we require that each digit of the output depend only on a finite number of digits of the input. For instance, multiplication by 3/4 cannot be defined, because to know whether f(x) starts with 0.24 or 0.25, you’d have to know whether x < 1/3 or x ≥ 1/3, and if the input is 0.333..., then you can’t tell from a finite number of digits which is the case. This kind of problem will occur with any other base.

It would be really nice to find some way of encoding a real number as an infinite sequence of discrete parameters each of which takes on a fixed finite range that escapes this kind of a problem. I am pretty sure this is impossible, but am too tired to prove it right now.

But there is another approach. We can have non-unique (many-to-one) encodings of reals. Here is one such approach, probably not the most natural one. Consider sequences of natural numbers n₁, n₂, ... such that for all k we have n_k ≤ 2k and there exists a real number x between 0 and 1 inclusive with the property that |x−n_k/2k| ≤ 1/k. Say that such a sequence encodes the real number x. In general, there will be more than one sequence encoding x by this rule.

Then if f is a function from [0,1] to [0,1], if we have a sequence n₁, n₂, ... encoding the real number x, to generate an acceptable kth term in a sequence encoding f(x), it suffices to know f(x) to within precision 1/2k, and if f is continuous, then we can do that by knowing a finite number of terms in a sequence encoding x (this is because every continuos function on [0,1] is uniformly continuous).

So any continuous dynamics from [0,1] to [0,1] can be handled in this way. The cost is that fundamental reality has degrees of freedom that are unimportant physically—for fundamental reality distinguishes between different sequences encoding the same real x, but the difference has no physical significance.

I don’t know if there is a way to do this with a unique encoding.