Sunday, 5 June 2016

How to describe or represent an infinite object efficiently

There are many cases where you need to represent an infinite mathematical object on a way that you will be able to work on it. In other words, create a representation or a description of an infinite mathematical entity on a way that you can perform computations over it. In these cases just using a variable to denote the entity is not enough. You need a description of its structure and to be able to reproduce any part of the object using this description.
Usually these situations occur in theoretical studies but this does not rule out practical applications. An infinite object can be a number (real, irrational, transcendental etc.) or a sequence like an infinite binary sequence.
It is safe to consider a description that may be inputted in a Turing Machine (TM). It is a general purpose computational model and if you can build a TM that accepts as input your infinite object description then it is an efficient representation of your object, otherwise the description and the object itself are probably uncomputable.
Let’s see a few cases of infinite mathematical objects and how they may be represented in Turing Machines starting from trivial cases and moving on to more difficult ones.

Irrational numbers. Set Q of irrational numbers contains numbers of infinite decimal expansion like the number equal to 3/10. Despite this, it is very easy to describe any irrational number using the definition of infinite numbers. For each irrational number i stands that i = a / b, where a, b are natural numbers. On this way each i is easily described. Using this description we may perform computations between any two irrational numbers.

Algebraic numbers. The set A of algebraic numbers consists of computable numbers so each a of A is Turing computable and has a computable description. Using the definition of algebraic numbers we may construct a description. Each a is the root of some polynomial p so it may have infinite decimal expansion p however is of the form
hn xn+hn-1 xn-1+…+h1 x1+h0 x0
As a is computable p is also be computable, so it is of finite length. In order to represent p in a TM we introduce symbol “|” that substitutes the x^n factor so that p is represented on the tape of a TM as follows
hn | hn-1 | … | h1 | h0
Each p has a bounded number of roots. Let a be the i-th root of p then it may be represented in a TM as
hn | hn-1 | … | h1 | h0^i
by introducing symbol “^” in the alphabet of the TM.

Infinite strings. Each string may be encoded to a binary string so let’s talk about binary strings. Following Computer Science theory, infinite binary strings are either computable or uncomputable. About the uncomputable ones there is not much we can do, it’s clear that you cannot describe something that you can’t compute. The computability of the rest of binary strings implies that for each string s there is algorithm H that produces s. Each character of s may be produced by H so its operation describes it.
Of course H may be simulated in a Universal TM that accepts as input the description of H which is of finite length otherwise it wouldn’t be computable. As a result the description of H stands for a description of s.
Algorithm H is of finite length while s is infinite this directly implies that the structure of s follows some pattern that H iteratively produces while running on TM.

Transcendental numbers. These numbers have infinite decimal or binary expansions but for each one there are algorithms that may produce any part of its expansion. Following the same reasoning as with infinite strings, the description of any algorithm that generates the sequence of digits of the decimal or binary expansion of a transcendental number may stand for its description.

No comments:

Post a Comment