-
Notifications
You must be signed in to change notification settings - Fork 0
Formalization Encoding
This document is part of the eXtensible Binary Universal Protocol project documentation. Provides description of the used types of encoding and development of their formal approval.
As the basic encoding of the natural numbers for the protocol is used the SLRUB encoding. It is a variant of gamma encoding, so far known as recursive unary-binary encoding, resulting from applying the requirements of the characteristics of the code. The emergence of encoding is described in the number's encoding document. With the extension of the referred argumentation it should be possible to formalize this encoding as the most appropriate option technique of the natural numbers representation.
Following requirements which must complied for the proposed encoding have been established. …
Specified requirements:
- Encoding of the numbers of any big value - The basic requirement is to allow to encode any large number. Can not be considered only big enough reserved size, since the format would lose its universality.
This can be summarized in the following statement:
Statement: Universal protocol must allow to encoding any large finite number value
Contradiction: Assume that the format can encode any number to a maximum value of n. Then, the format can not encode number n+1, and therefore is not universal.
Use of the Unlimited large numbers has been implemented in several programming languages and their main disadvantage is the greater intensity on the computing performance, but in normal cases it may be possible to use the protocol limited to standard ranges of values. It is worth mentioning that there can be no real encoded decimal numbers with the never-ending fraction, because we can only store final memory space. It is possible to store such…
- Coding into sequence of bits - The data are coded into a potentially endless sequence of bits. The sequence of the two-state information units is selected because of its minimality. Store data to the sequences of different ranges is not essential encoding in terms data representation and therefore a the choice of more than two-state information has no logical background. This can be summarized in the following statement:
Statement: Coding into the sequence of bits is sufficient and minimal
Argumentation: According to Church thesis]] it is possible to encode any data using Turing machines]]. That is then possible to minimalize to the equivalent machine, where input is sequence of two-state values (alphabet of two characters).
It is easy to show that each of the final binary development corresponds exactly to one code. Evidence in the opposite direction is similar.
Statement: To any number with a final binary development there corresponds exactly one code in the UBReal encoding. The statement is valid in case that that the same is true for UBInteger encoding (without giving any evidence)
Argumentation: (contradiction) Assume that there are two different forms of the number corresponding to UBReal code. Then these codes differ:
a) In the Base value, or both: All bits of the Value must be present in the binary code of the value Base. Then, on the assumption that the encoding UBInteger encoding meets the same condition implies the equality of the Base code - contradiction b) In the value of Mantissa: The binary code is a sequence of bits of the Value which ends by bit 1 (invisible one) and all the lower bits has value 0. If the value has a different value of Mantissa, the bit has position at the indentation bit of the value which is different in both the entry numbers - contradiction.
The list of resources, literature and relevant links:
Church Thesis - https://en.wikipedia.org/wiki/Church_thesis
Turing Machine - https://en.wikipedia.org/wiki/Turing_machine