# Convergaptor

Paradigm(s) Unknown Hakerh400 2020 Unknown Unimplemented `.txt`

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 `1`s 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 `y`s. If `start` is larger than `end`, then returns `0`
• `prod<x, start, end>(y)` - Similar to `sum`, but returns the product of all `y`s. 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 `1`s, 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(
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>(
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.

Unknown.

## Interpreters

No interpreters exist yet.