Convergaptor

Convergaptor is a programming language which performs computation by searching for bit patterns in the decimal expansion of the real number defined by the source code.
== Overview ==
Input and output are sequences of bits. Source code represents a methematical formula that defines a real number in interval [0, 1). If the number evaluates to something outside this interval, or is not a real number, or does not converge, then spin in an infinite loop.
Then the obtained real number is written in binary (base 2) and the decimal digits (bits) after the decimal point are extracted to form an infinite sequence of bits.
That sequence is then interpretted as follows. We split the sequence into subsequences such that each subsequence:
* has odd length
* ends with 0
* has 1s on each even position in the subsequence (0-indexed), except the last bit (which is 0)
For example, if the source code defines number 1 / 7, the decimal expansion is
 0.00100100100100100100...
and the subsequences are
 0 0 100 100 100 100 100 100 ...
Now drop all bits at even positions in each subsequence:
 _ _ 0 0 0 0 0 0 ...
We represent empty sequences by _. Then we consider consecutive pairs of subsequences (the first two, the second two, and so on)
 [_ _] [0 0] [0 0] [0 0] ...
Each pair contains two sequences (we call them x and y respectively). If there are multiple pairs with the same x, then keep only the first pair of them and drop the others. In this example, we obtain
 [_ _] [0 0]
We dropped all other pairs that have 0 as the x parameter, so we are left with exactly two pairs. If there is a pair whose x is equal to the input, then output y of that pair. Otherwise spin in an infinite loop.
In this example, if the input is an empty sequence, the program outputs nothing and halts. If the input is a single 0, then the program outputs 0 and halts. In all other cases, it spins in an infinite loop.
== Syntax ==
Source code consists of one or more mathematical function definitions. Definition looks like this:
 f(x, y) = pow(add(pow(x, 2), pow(y, 2)), div(1, 2));
For example, this function named f takes two arguments x and y and returns the Euclidean distance between the points (0, 0) and (x, y) in the plane (assuming x and y are real numbers).
Function definition consists of left side and right side separated by = and ends with ;. On the left side we have function name followed by parentheses in which we have formal argument names separated by commas. The number of arguments is called function arity. When called, it must be called with the exact number of arguments that matches its arity. In case of zero arity (constant function) the parentheses can be omitted, both in the definition and/or when calling the function.
On the right side of the equals sign, we have either a constant (zero-arity function) or a function call. A function call is represented by function name followed by parentheses and arguments. Each argument is either a constant or another function call. In the above example, we call function pow with arguments add(pow(x, 2), pow(y, 2)) and div(1, 2). All arguments and return values (for any function) are complex numbers of unlimited precision.
There are predefined (native) and user-defined functions. The main function is the first function that appers in the source code and its arity must be zero. Its return value is the real number whose decimal expansion we examine.
Any user-defined function may call other user-defined functions or native functions, but recursion is not allowed (neither direct or indirect).
=== Native functions ===
The following functions are predefined:
* 0, 1, 2, ... - Literal integers (can be arbitrary large) are constant functions that return the value obtained by parsing the integer in base 10
* add(x, y) - Adds x and y
* sub(x, y) - Subtracts y from x
* mul(x, y) - Multiplies x with y
* div(x, y) - Divides x by y
* pow(x, y) - Raises x to the power of y
* log(x, y) - Returns the logarithm of y with base x
* floor(x) - Rounds x down
* ceil(x) - Rounds x up
* re(x) - Real part of x
* im(x) - Imaginary part of x
There are some compare functons:
* eq(x, y, a, b) - If x = y then returns a, otherwise returns b
* lt(x, y, a, b) - If x < y then returns a, otherwise returns b
* gt(x, y, a, b) - If x > y then returns a, otherwise returns b
* le(x, y, a, b) - If x <= y then returns a, otherwise returns b
* ge(x, y, a, b) - If x >= y then returns a, otherwise returns b
And also iterating functons:
* sum<x, start, end>(y) - Iterates x from start to end (inclusively) and for each x evaluates y (substitutes x in it with the current value of x) and returns the sum of all ys. If start is larger than end, then returns 0
* prod<x, start, end>(y) - Similar to sum, but returns the product of all ys. In case of start > end returns 1 instead of 0
* lim<x, y>(z) - Evaluates z when x approaches y
* liminf<x>(y) - Evaluates y when x approaches positive infinity
Note that <> is a special part of the syntax.
== Examples ==
=== Truth-machine ===
 main = div(18879, pow(2, 15));
We cannot output infinitely many 1s, but this program outputs 0 if the input is 0 and outputs 111 if the input is 1. Here is how the computation goes (each line prepresents a step that is taken, as explained in the overview paragraph):
 0.1001001101111110000000...
 100 100 110 1111110 0 0 0 0 0 0 ...
 0 0 1 111 _ _ _ _ _ _ ...
 [0 0] [1 111] [_ _] [_ _] [_ _] ...
 [0 0] [1 111] [_ _]
Now we can see that on input 0 it outputs 0 and on input 1 it outputs 111. It also halts on empty string.
=== Cat ===
 main = div(
 add(
 generate(0),
 generate(1)
 ),
 4
 );
 
 generate(x) = liminf<inf>(
 sum<n, 2, inf>(
 div(prepare(n), pow(
 2,
 sub(
 mul(sum<k, 2, n>(
 calc(k)
 ), 2),
 mul(calc(n), x)
 )
 ))
 )
 );
 
 encapsulate(x) = liminf<inf>(
 mul(sum<n, 0, inf>(
 add(
 mul(getBit(x, n), pow(2, mul(n, 2))),
 ge(x, pow(2, n), pow(2, add(mul(n, 2), 1)), 0)
 )
 ), 2)
 );
 
 prepare(x) = dropFirstTwoBits(encapsulate(x));
 calc(x) = sub(digitsNum(encapsulate(x)), 2);
 dropFirstTwoBits(x) = mod(x, pow(2, sub(digitsNum(x), 2)));
 digitsNum(x) = ceil(log(2, x));
 getBit(x, i) = mod(divf(x, pow(2, i)), 2);
 mod(a, b) = sub(a, mul(divf(a, b), b));
 divf(a, b) = floor(div(a, b));
It uses a modified version of Champernowne formula and produces the following real number (in base 2):
 0.00100100110110101001010010110101101110011100111101111010101001010100101011010101101011100101110010
 1111010111101110100111010011101101110110111110011111001111110111111010101010010101010010101011010101
 0110101011100101011100101011110101011110101110100101110100101110110101110110101111100101111100101111
 1101011111101110101001110101001110101101110101101110111001110111001110111101110111101111101001111101
 0011111011011111011011111110011111110011111111011111111010101010100101010101001010101011010101010110
 1010101110010101011100101010111101010101111010101110100101011101001010111011010101110110101011111001
 0101111100101011111101010111111010111010100101110101001011101011010111010110101110111001011101110010
 1110111101011101111010111110100101111101001011111011010111110110101111111001011111110010111111110101
 1111111011101010100111010101001110101011011101010110111010111001110101110011101011110111010111101110
 1110100111011101001110111011011101110110111011111001110111110011101111110111011111101111101010011...
Extracting the subsequences and obtaining input-output pairs gives the following:
 --->
 0 ---> 0
 1 ---> 1
 00 ---> 00
 01 ---> 01
 10 ---> 10
 11 ---> 11
 000 ---> 000
 001 ---> 001
 010 ---> 010
 011 ---> 011
 100 ---> 100
 101 ---> 101
 110 ---> 110
 111 ---> 111
 0000 ---> 0000
 0001 ---> 0001
 0010 ---> 0010
 0011 ---> 0011
 0100 ---> 0100
 0101 ---> 0101
 0110 ---> 0110
 0111 ---> 0111
 1000 ---> 1000
 1001 ---> 1001
 1010 ---> 1010
 1011 ---> 1011
 1100 ---> 1100
 1101 ---> 1101
 1110 ---> 1110
 1111 ---> 1111
 00000 ---> 00000
 00001 ---> 00001
 00010 ---> 00010
 00011 ---> 00011
 00100 ---> 00100
 00101 ---> 00101
 00110 ---> 00110
 00111 ---> 00111
 01000 ---> 01000
 01001 ---> 01001
 01010 ---> 01010
 01011 ---> 01011
 01100 ---> 01100
 01101 ---> 01101
 01110 ---> 01110
 01111 ---> 01111
 10000 ---> 10000
 10001 ---> 10001
 10010 ---> 10010
 10011 ---> 10011
 10100 ---> 10100
 10101 ---> 10101
 10110 ---> 10110
 10111 ---> 10111
 ...
As can be seen, each input maps to the exactly same output.
== Computational class ==
Unknown.
== Interpreters ==
No interpreters exist yet.
== References ==
Category:Languages
Category:Unknown_computational_class
Category:Unimplemented
Category:2020