{'fraction_non_alphanumeric': 0.03453416149068323, 'fraction_numerical': 0.009093167701863355, 'mean_word_length': 4.550468836183122, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 0, 'https://': 1, '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}}
On Function Description

The main result is that: function descriptions are not made equal, and they can be categorised in at least two categories using various computational methods for function evaluation. The result affects Kolmogorov complexity and Random Oracle Model notions. More precisely, the idea that the size of an object and the size of the smallest computer program defining that object is a ratio that represents the object complexity needs additional definitions to hold its original assertions.


Introduction
An introduction to Kolmogorov complexity could start with Chaitin's short story [1]: Suppose you have a friend who is visiting a planet in another galaxy, and that sending him telegrams is very expensive. He forgot to take along his tables of trigonometric functions, and he has asked you to supply them. You could simply translate the numbers into an appropriate code (such as the binary numbers) and transmit them directly, but even the most modest tables of the six functions have a few thousand digits, so that the cost would be high. A much cheaper way to convey the same information would be to transmit instructions for calculating the tables from the underlying trigonometric formulas, such as Euler's equation e ix = cosx + isinx. Such a message could be relatively brief, yet inherent in it is all the information contained in even the largest tables.
The Kolmogorov complexity deals with objects and computer programs outputting it. If the computer program is more compact than the object as an output, the complexity of the object in question is considered less complicated. The Kolmogorov complexity can apply to any object. In our case, it will deal with mathematical functions. Function description is a computer program which will define an object; in our case domain, co-domain and their mappings. Figure 1 shows the tables of some trigonometric functions and are represented as a string s. Implementation of Euler's equation is an example of trigonometric functions description and also a description of the string d(s). Then Kolmogorov complexity K of string s is stated as: where |d(s)| is a length of a program, in our case the length of the program implementing Euler's equation. There is also relation between K(s) and the length of a string |s|: ∀s.K(s) ≤ |s| + c where c is a constant. From Chaitin's short story it becomes obvious that Euler's equation is a way shorter than Figure 1: To some extent, the concept of Kolmogorov complexity was used for argumentation in the negative result of the random oracle model. A random oracle is a black box which on a given inquiry, replies with a random answer. A fictional story explains the concept quickly. In the black box lives a gnome with some dice and a blank notebook. Anyone can submit a question (an input q) to the black box. When q is submitted, the gnome checks whether the input q is already in the notebook. If it is there the gnome will respond with result r from the notebook. If q is not in the notebook, the gnome will throw its dice and the result r will be recorded to the notebook as a mapping from the query. That result r returns to the submitter. The notebook entries may look like Table 1 where q and r are sorted for easier searching. The availability of a random oracle serves as a security assumption during the design and development of various cryptographic protocols. For example, most of RSA (a well known public-key cryptography method) signing and encryption are shown to be secure under the Random Oracle Model (ROM) [2]. The problem starts when we wish to implement the fictional random oracle with a real algorithm on modern computers. The paper "The Random Oracle Methodology, Revisited"(ROMR) [3] shows that a random oracle is unreplaceable by any function (generally hash function) and that proofs based on ROM are unsound. Informal arguments are: An obvious failure. We first comment that an obvious maximalistic definition, which amount to adopting the pseudorandom requirement of [4], fails poorly. That is, we cannot require that an (efficient) algorithm that is given the description of the function cannot distinguish its inputoutput behavior from the one of a random function, because the function description determines its input-output behavior.
Informal Theorem 1.1 There exist no correlation intractable function ensembles. ... The proof of the above negative result relies on the fact that the description of the function is shorter than its input.
Resolving the random oracle is a significant and challenging endeavour. Shai's (one of the authors [3]) view is: Another possible explanation is that the random oracle methodology works for the currently published schemes, due to some specific features of these schemes that we are yet to identify. That is, maybe it is possible to identify interesting classes of schemes, for which security in the Random Oracle Model implies the existence of a secure implementation. Identifying such interesting classes, and proving the above implication, is an important and seemingly hard research direction.
This work sheds light on the random oracle controversy by defining function descriptions. It puts a function description of a program into two categories. Each category has a different rank depending on what computational methods are available to each category.

Function Description, a Mathematical Approach
The trigonometrical functions have been major engineering tools for a long, long time. Figure 1 shows pre-calculated values of various trigonometrical constructs including sine function. Figure 2 shows the sine description.
The sine function deals with angles of a right triangle. The sine of such an angle Θ is the ratio of the opposite side and hypotenuse. More formal definition via complex analysis is here: http://us.metamath.org/mpegif/df-sin.html From a computational view, an evaluation of sin function can be done in handful ways. Those ways we will call rankings.

Rank 1
Rank 1; It is an ability to compute an output providing a input via computer program. The example of Rank 1 is the C language sin implementation (given by Blindy: https://stackoverflow.com/questions/2284860/how-does-c-computesin-and-other-math-functions) Figure 3 shows an implementation.
; } r e t u r n r e s ; } The description length |d(s)| is Figure 3 implementation size and it is in tens of KBytes region |d(s)| ≈ 20KB. This particular sin function defines inputs and outputs as 32 bit decimal values, then size of domain-range mapings is |s| = 2 * 2 32 bits. Therefore we have an indication of low sin complexity.

Rank 2
Rank 2; A look-up table is used to evaluate input-output enquiries.
If the function description has Rank 1, it automatically can obtain Rank 2 by creating a look-up table (for example Table 2). For trigonometrical functions in game development, the look-up table is the preferred method. The reason is the spatial nature of some games and needs too many geometry calculations. Another advantage of the table is that they can be searched either by input or by output.
For example, the question is what angle (x) produces 0.829 (sin(x) = 0.829)? A searching algorithm will search for 0.829 through Sine column and will output 56 Degrees (

Rank 3
The quoted story from the beginning could continue with another twist. The communication with Earth and the faraway planet is lost. Your friend received function for calculating sin, but he needs to calculate angle when the sin value is known. Essentially knowing y, pair it with corresponding x. With tables, that is an easy task, but they are forgotten. One way to solve that problem is to guess x and run sin(x) and see if the y in question match. That exercise might be expensive because that search is exhaustive. Since sin have mathematical structure, simple binary search saves the day. If the function definition includes some input-output structure, to inverse that function the efficient search method suffices. This method is universal because searching does not depend on a function description. The requirement is that a input-output pairs are in correlation, which is generally assumed, because function description is smaller than its input-output (|d(s)| < |s|) (ROMR [3]). The efficiency of this approach is less than using Rank 4 function but is still efficient enough because the binary searching cost is logarithmic by nature (O(log 2 n)).

Rank 4
Rank 4; Using inverse function to match output to the corresponding input. Instead using Rank 2 or 3 approach you can use calculator because almost every scientific calculator has sin −1 function which is inverse of sin (See Figure 4 for example).   TSP starts with list of cities and their distances (Table 3), where cities are enumerated as 0, 1, 2, 3, 4.
The path is the list of cities, one permutation of that list. The number of permutations p is permutations with no repetitions p = n! where n is a number of cities. One path permutation is shown in Figure 5.
Given the distances and a specific path, the distance can be calculated by Figure 6 program.  Table 3 and path from Figure 5 the arguments for function get-TravelingDistance are:
However gTD size |d(s)| and the list of all input-output mappings |s| are in different relation than sin (Equation 6) because number of the possible travel paths permutations (inputs) rises exponentially |s| = n! (where n is number of cities) while gTD size |d(s)| remains constant.

Rank 2
If Rank 1 exists, then Rank 2 is given because mappings can be pre-calculated and evaluated via a look-up table. In the travelling distance case, that approach is impractical because of the exponential table dependence on input.

Rank 3 and 4
There is a similar connection between Rank 3 and Rank 4 as is in Rank 1-2. If a function has some mathematical structure, there is a good chance to find an inverse function as well (for example, sin and sin −1 ). sin Rank 3 depends on the ordered structure of input-output pairs. Regarding gTD sorting, there is an immediate problem because gTD path instances do not have clear criteria of how to do a meaningful sort on path permutations. Table 4 shows a couple of gTD calculated distances sorted by the distance in ascending order.  It starts to resemble the random oracle Table 1 where only one column is sorted. There is a possibility that path permutation column (Table 4) has some meaningful distribution after all. That eventuality leads to solving all N P complete problems efficiently (O(logn)), which is believed unlikely ( [5] and [6]).
The essence of Rank 3 approach is to search for mappings in the Table as it happens in Rank 2 but not creating the complete Table. Instead, it calculates only needed mappings according to the table pattern. In gTD case, if we need to know short distances and their paths, search for them will calculate permutations in the top table region. Since search algorithm cost is in O(logn) range, despite the exponential amount of inputs (n!), the overall cost is still polynomial.
The Rank 4 approach for the same sort of questions will match particular permutation with desired distance and again as in Rank 3 solve TSP.

Rank 3 Discussion
Straight forward candidate for a computer program having only Rank 1 and 2 ability is Blum Blum Shub (BBS). It is a secure pseudo-random generator, and it is interesting because its security is tied to the hard problem (in this case, factoring [7]). Practically, if a pseudo-random stream (an output) created by BBS is presented, then finding matching seed (an input) leaves you with either exhaustive search or factoring large composite number which is known to be a hard problem (N P ).
Since factoring is not NP-complete problem and also there is a quantum computer algorithm for solving factoring in P [8], stronger evidence for ranking categorisation is needed. The possible next step is to show how NP-complete problems relate to ranking categorisation. We can use TSP to show if it has Rank 3 implementation, then searching for the mappings of interest will be very efficient (O(log 2 n)).
The Branching Theorem could be considered as an even stronger argument for ranking categorisation. The argumentation starting point is Cyclomatic Complexity (CYC) [9].

Preliminaries
Every source code could have a decision point where a program can decide which way execution might go. The Table 5 first column is an example of a program with one branching where vertex 2 is that decision point. Depending on the program arguments, the execution of it can happen in two ways (second and third column). With added edge (dotted), the control graphs can be discussed in cyclic graph terms [10]. A graph with n vertices and a single cycle going through them all is called a cycle graph C n [10]. The control graph from Table 5 have two-cycle graphs (Cycle 1 and Cycle 2). McCabe showed that every decision point in the graph (program flow control) doubles the number of cycle graphs [9].
To simplify definitions, the source code and its flow control graph in our discussion will be a programming function pf .

Definition 1. Programming function (pf ).
pf is a process which performs a some desired task. It accepts an input and returns an output (y = pf (x)), thus mimicking mathematical notion of function y = f (x) where x is input and y is output. An example of pf is the C language sin implementations ( Figure 3). The same is valid for getT ravelingDistance function ( Figure 6). Both have set of arguments which are input to the function float sin(float x) and return value which is actually output.

float sin(float x)
Another pf requirement is: the function execution flow has to have a single entry and exit point. It enables the treatment of pf in graph cycle terms. Examples of flow controls can be seen in Table 5 where the blue vertex means entry point and red one exit point.

Definition 2. Redirected programming function (rf ).
rf is essentially pf and differs from pf in only one detail. Instead outputting prescribed output as pf would do a rf will return a execution path of pf (a cycle). For example, co-domain Y of the now redirected program (rf ) from Table 5 will be Y = {Cycle1, Cycle2}. Note that some functions as our sin implementations (Figure 3) have only one output cycle (execution path).

Branching Argument
The rf redirected functions share the same domain X and the same function description (plus output redirection) with the programming functions pf . The cardinality of RF (set of all rf ) is exactly the same as of P F (set of all rf ) .
Now we can ask what is Ranking 3 status of rf : X → Y ? Theorem 1. Branching Theorem. There exists at least one rf : X → Y mapping not satisfying Ranking 3 requirement.
Proof. We can assume opposite, that every rf : X → Y has a Ranking 3 attribute. In that case, a mapping search from any cycle (output) from some flow control graph, to the corresponding input is efficient one (O(log 2 n)). On first glance, that is a reasonable statement because when pf is properly specified every case (cycle) behaviour should be fully defined. On the other hand, there are at least two problems with all rf having Ranking 3 status: • pf are not always made with a purpose. The program could be written with arbitrarily many branching statements positioned in a program everywhere. If it compiles, it will run, but output behaviour will be undefined.
3x+1 iterations [11] can illustrate (not prove) the point. Take any positive integer x and if it is even divide it with 2 else multiply it with 3 and add 1. Iterate this procedure until the outputs start to repeat itself 1 . One iteration step formula is: To paraphrase Lagarias [12], 3x + 1 transformation appears to be without any mathematical structure and every arbitrarily chosen iteration (branching decision) behave like a fairly flipped coin.
• If every rf has Ranking 3 implementation then branching algorithmic structure is redundant. We will know the partition of inputs and their corresponding execution paths cycles, because there is some structure, which allows binary searches, in every rf mapping. Practically, we will know which path to execute for some input in advance without the need to test the branching statement. Therefore, we can write any rf (and consequently any pf ) without if /else alike statements. That situation will make programming endeavour very interesting because branching is one of the algorithm essentials. Note, Böhm-Jacopini theorem [13] shows that the operations and structure of only three statements (sequence, selection and iteration) is a Turing-equivalent system of computation.

Conclusions
For the discussion Rank 4 is not essential. We could assume that if some function does not have Rank 3 it probably does not have Rank 4. If the Theorem 1 holds then we have Category 2 (C2) type of functions. C2 functions have only one option to do the inverse, and that is by look-up table (Rank 2 ). In the case when domain X is large, making pre-computation prohibitive, the only option left to evaluate function is to calculate a single instance of it. The same phenomena as C2 function called computational irreducibility were investigated by [14] and [15]. The quote is from Computational Irreducibility [16]   The principle of computational irreducibility says that the only way to determine the answer to a computationally irreducible question is to perform, or simulate, the computation.
The computational irreducibly was often associated with cellular automaton. The chaos theory provides another source of C2 functions. For example, n body problem does not have a practical mathematical solution. The only way to predict the future configuration after an extended time of moving bodies is to do simulation.
In practice, whenever the C2 functions are evaluated, the outcome shall be unexpected. There is a line of argumentation that puts C2 functions and random oracle (RO) in the same basket. C2 has capabilities as RO because it will produce an identical answer (output y) from the same inquires (input x). Every new inquiry, C2 will answer with surprising output y. If y is somehow expected, then the particular function will have Rank 3 implementation and in some way ordered outputs. Essentially, Rank 3 means input/output correlation and C1. No Rank 3 means randomness and C2.

Kolmogorov Complexity; Additional Definitions
As we saw in previous sections, some problems such as TSP are straightforward to state indicating low complexity; please see Subsection 3.1 and Equation 7. On the other hand, TSP mapping and its behaviour are undefined. To find some details such as the shortest path is believed to be hard and only exhaustive search method exists.
The way around this discrepancy is to treat the TSP problem as a partially defined function. The fully described program should include a look-up table description as well. Table 1 is an example where entries are sorted by input and output. In that way, an algorithm could find the required details efficiently (O(log 2 n)). In the TSP case, table size will rise exponentially with many cities impacting the size of the program and its complexity. Therefore, program size d(s) and look-up table size T are approximately the same as the size of all mappings |s| . |d(s)| + |T | ≈ |s| (10) In that way, Kolmogorov Complexity will be high for TSP as should be (because TSP is NP-complete problem).

Random Oracle Adjustment
In similar vain as Kolmogorov Complexity, RO concept needs adjustment. In RO, full function description plays the main role. Negative result is argued by ratio of function description |d(s)| and size of the mappings |s|.
|d(s)| << |s| (11) where shorter program must define behaviour of large function mappings size (in cryptography, modern hash output size is 256 − 512 bits). That assertion does not work for partially defined functions( C2) which allows evaluation of single input without the need of whole mapping behaviours via exponentially sized look-up tables. This phenomenon enables trivial construction of one-way function [17] (easy evaluation and exhaustive search for inverting).