Тьюринг-полон ли данный язык

[kotenok gav]

GCD(int1, int2) {
    r_i = car(int1); //знаки int1 и int2 не важны для вычисления GCD
    r_i1 = car(int2);
    whilene (r_i1) {
        copy = r_i;
        r_i = r_i1;
        r_i1 = car(divideIntegers(cons(copy, []), cons(r_i1, [])));
    }
    return r_i;
}

А, еще забыл: сделать import надо.

-- 24 мар 2020, 01:27 --

arseniiv в сообщении #1446555 писал(а):

Ну кто первый напишем, реализацию того и будем критиковать.

Ничто не мешает сделать два интерпретатора и две библиотеки работы с числами

-- 24 мар 2020, 01:27 --

Реализацию рациональных напишу чуть позже.

-- 24 мар 2020, 01:30 --

Жаль только, что операции с нашими числами в унарной системе занимают ОЧЕНЬ много времени. Но, с другой стороны, мы сможем измерить его на практике!

-- 24 мар 2020, 01:33 --

Кстати, было бы интересно придумать более быстрые алгоритмы. Сомнительно, что тут подойдут "классические".

[_Ivana]

kotenok gav в сообщении #1446557 писал(а):

Кстати, было бы интересно придумать более быстрые алгоритмы.

Воспользуйтесь волшебным изоморфизмом - переводите в нормальные (в общечеловеческом смысле этого слова) числа, проводите операции с ними и переводите обратно.

[kotenok gav]

И как реализовывать "нормальные" числа в терминах множеств?

-- 24 мар 2020, 02:07 --

arseniiv
Ваши нормализованные представления очень напоминают мои ($(n,0)$ и $(0,-n)$ vs $(n,0)$ и $(-n, 1)$). Ваши функции в каком-то смысле проще, мои в каком-то смысле быстрее. Кмк, оба варианта заслуживают отделения в отдельную библиотеку работы с числами.

[_Ivana]

Руками, набирая код на клавиатуре.

[kotenok gav]

Не надо хамить, пожалуйста. Я не вижу способа реализовать это (кроме как создать большой кортеж с двоичными цифрами числа, что огромное извращение. Но даже в этом случае оно все равно займет много времени, потому что оно происходит не на аппаратном уровне, как в обычных языках). Мой вопрос был не об этом, а об алгоритмах именно в нашей унарной системе.

[_Ivana]

Не надо тупить, пожалуйста. Мой ответ соответствовал вашему вопросу. Впрочем, не смею отвлекать от собственных попыток.

[kotenok gav]

Не хамите. Хорошо, я уточнил теперь вопрос.

[arseniiv]

kotenok gav в сообщении #1446557 писал(а):

Ничто не мешает сделать два интерпретатора и две библиотеки работы с числами

Да, конечно.

-- Пн мар 23, 2020 21:15:43 --

kotenok gav в сообщении #1446557 писал(а):

Кстати, было бы интересно придумать более быстрые алгоритмы. Сомнительно, что тут подойдут "классические".

Можно двоичные ввести. Есть «бесконечный дополнительный код», где сначала идёт «знак на бесконечности», обозначающий префикс ...000000 или ...111111, а потом конечный набор других цифр числа. Строго говоря это будет вложение целых чисел в 2-адические числа, но достаточно простое, потому что не позволяются произвольные разряды влево до бесконечности. Ну и есть просто способ взять какой-то набор разрядов и приписать знак, опять же. Кажется, сложность сравнения, вычитания, сложения, умножения примерно одинаковы для тех и тех.

_Ivana в сообщении #1446566 писал(а):

переводите в нормальные (в общечеловеческом смысле этого слова) числа, проводите операции с ними и переводите обратно

Я вот тоже не понял, какие нормальные числа тут имеются в виду. Язык изначально оперирует только наследственно конечными множествами by design. Это вообще его основная черта, всё остальное можно перекроить.

[_Ivana]

arseniiv в сообщении #1446584 писал(а):

Язык изначально оперирует

Но речь то зашла не о семантике, а об оптимальной реализации. И в этом смысле никто не мешает языку отдать часть реализаций своих операций на аутсорс черному ящику, ассемблеру, или кому угодно. А какие внутренние операции будут производиться для получения результата, языку фиолетово, это вообще не его головная боль, так что основные черты не страдают. Разумеется, при сохранении семантики, которое гарантируется изоморфными преобразованиями.

Возьмем простое нетипизированное лямбда-исчисление, или хоть SK. Есть нумералы Черча, есть комбинаторы арифметических операций, все теоретически доказано и работает, семантика чиста как слеза. Но в реализации редуктора никто не мешает преобразовать термовые представления чисел и операций в любые другие, получить результат и выполнить обратные преобразования. Если вас смущает вопрос распознавания термов, то на помощь придет нотация де-Брейна.

[arseniiv]

_Ivana в сообщении #1446609 писал(а):

Но речь то зашла не о семантике, а об оптимальной реализации.

Оптимальной реализации не вообще, а в условиях выбранного набора примитивов. Да, это может казаться праздным вопросом, но вот люди такими вопросами задаются всё равно.

-- Вт мар 24, 2020 00:55:06 --

Кстати говоря если думать об оптимальности, есть ещё такой способ: есть код для библиотеки целых чисел, но он не используется, потому что при компиляции все вызовы функций из этой библиотеки заменяются на другие, которые оперируют действительно чем угодно. Но это всё мимо задачи выражения одного в терминах другого, в которой тут самый интерес и стоит. Вполне серьёзные вопросы например есть о том, за сколько можно транслировать представление в одной модели вычислений в представление в другой, и зависимость размера этого представления от того, или скорость интерпретации, рассчитываемую в шагах выполнения той модели вычислений, которая интерпретирует. В этой области есть неожиданные результаты, что оказывается всё-таки не все модели одинаково полезны, и есть такие, которые переводятся в некоторые другие только с экспоненциальным (или больше) увеличением представления или замедлением. Ссылки не помню, но поплавав в эзотерическом сообществе я это узнал. Это всё не обязательно относится к этой теме, но не обесценивает то, что заинтересовался делать kotenok gav, до нуля.

-- Вт мар 24, 2020 00:56:54 --

Кстати я не понял, почему предлагаются λ-исчисление и иже с ним, имплементация на которых операций с числами будет вообще вряд ли быстрее в каком-то смысле (в редукциях ли, в секундах ли выполнения какой-то реализации на железе) чем тут. Сразу GMP я бы тогда брал.

[_Ivana]

Не, я сам люблю праздные вопросы. Типа чтобы только топором, без единого гвоздя. Просто в таких вопросах допустимый набор инструментов надо четко озвучивать, в нем же вся соль.

-- 23.03.2020, 23:01 --

arseniiv в сообщении #1446674 писал(а):

почему предлагаются λ-исчисление

Исключительно в качестве наглядного примера концепции возможности отдачи неэффективных операций на аутсорс

-- 23.03.2020, 23:04 --

arseniiv в сообщении #1446674 писал(а):

есть ещё такой способ:

Собственно, это и есть то что я имел в виду

[kotenok gav]

_Ivana в сообщении #1446609 писал(а):

Но речь то зашла не о семантике, а об оптимальной реализации.

Речь зашла об оптимальных алгоритмах в заданной реализации.

-- 24 мар 2020, 20:41 --

Рациональные числа мы представляем как (целое, положительное целое).

canonicForm(rat) {
    int1 = car(rat);
    int2 = cdr(rat);
    gcd = GCD(int1, int2);
    newInt1 = cdr(divideIntegers(int1, gcd));
    newInt2 = cdr(divideIntegers(int2, gcd));
    return cons(newInt1, newInt2);
}

-- 24 мар 2020, 20:49 --

addRationals(rat1, rat2) {
    int11 = car(rat1);
    int12 = cdr(rat1);
    int21 = car(rat2);
    int22 = cdr(rat2);
    int1 = addIntegers(multiplyIntegers(int11, int22), multiplyIntegers(int12, int21));
    int2 = multiplyIntegers(int12, int22);
    return canonicForm(cons(int1, int2));
}

substractRationals(rat1, rat2) {
    num21 = car(car(rat2));
    signInt21 = cdr(car(rat2));
    int22 = cdr(rat2);
    return addRationals(rat1, cons(cons(num21, signInt21 ~ [[]]), int22));
}

-- 24 мар 2020, 20:59 --

multiplyRationals(rat1, rat2) {
    int11 = car(rat1);
    int12 = cdr(rat1);
    int21 = car(rat2);
    int22 = cdr(rat2);
    int1 = multiplyIntegers(int11, int21);
    int2 = multiplyIntegers(int12, int22);
    return canonicForm(cons(int1, int2));
}

divideRationals(rat1, rat2) {
    num21 = car(car(rat2));
    signInt21 = cdr(car(rat2));
    num22 = car(cdr(rat2));
    signInt22 = cdr(cdr(rat2)) ~ signInt21;
    newInt21 = cons(num22, signInt22);
    newInt22 = cons(num21, []);
    return multiplyRationals(rat1, cons(newInt21, newInt22));
}

-- 24 мар 2020, 21:03 --

Теперь попробуем реализовать корни...

-- 24 мар 2020, 21:13 --

По методу Ньютона у нас есть итерационный алгоритм $x_{i+1}=\frac{(n-1)x_i+\frac{\alpha}{x_i^{n-1}}}n$.

[kotenok gav]

reciprocalRational(rat) {
    num1 = car(car(rat));
    signInt1 = cdr(car(rat));
    num2 = car(cdr(rat));
    signInt2 = cdr(cdr(rat)) ~ signInt1;
    newInt1 = cons(num2, signInt2);
    newInt2 = cons(num1, []);
    return cons(newInt1, newInt2);
}

divideRationals(rat1, rat2) {
    return multiplyRationals(rat1, reciprocalRational(rat2));
}

naturalPowerOfRational(rat1, num2) {
    ans = cons(cons([[]], []), cons([[]], []));
    count = [];
    whilene ([count] * num2) {
        count = nextNumber(count);
        ans = multiplyRationals(ans, rat1);
    }
    return ans;
}

integerPowerOfRational(rat1, int2) {
     num2 = car(int2);
     signInt2 = cdr(int2);
     power = naturalPowerOfRational(rat1, num2);
     ife (signInt2) {
         return power;
     }
     ifne (signInt2) {
         return reciprocalRational(power);
    }
}

Кстати, хорошо бы еще добавить оператор const, которым будут помечаться неизменяемые и видимые из всех функций константы, типа 1 или 0.

-- 24 мар 2020, 21:58 --

naturalRootOfRational(rat1, num2, iter = /* тут должна быть простыня, содержащая число 10 */) {
    ans = cons(cons([[]], []), cons([[]], []));
    count = [];
    whilene ([count] * iter) {
        a = substractIntegers(cons(num2, []), cons([[]], []));
        b = multiplyRationals(cons(a, cons([[]], [])), ans);
        c = divideRationals(rat1, integerPowerOfRational(ans, a));
        ans = divideRationals(addRationals(b, c), cons(cons(num2, []), cons([[]], [])));
    }
    return ans;
}

Кстати, я только что понял. В моей форме записи натуральных чисел невозможно записывать числа больше какого-то не очень большого предела...

[arseniiv]

kotenok gav в сообщении #1446792 писал(а):

В моей форме записи натуральных чисел невозможно записывать числа больше какого-то не очень большого предела...

Кстати да. Если считать, что множество $\{a_1,\ldots,a_n\}$ занимает в памяти не менее* $S\{a_1,\ldots,a_n\} = 1 + n + Sa_1 + \ldots + Sa_n$ места, то для кодировки фон Неймана $S(0) = 1$ и $S(n+1) := 2 + n + S(0) + \ldots + S(n) = 1 + 2S(n)$, итого $S(n) = 2^{n+1} - 1$. Контрастно этому, наивный способ $n + 1 := \{n\}$ даёт $S(n+1) := 2 + S(n)$, итого $S(n) = 2n - 1 = O(n)$, оптимально для унарного представления. Зато у вас порядок вычисляется за $O(1)$, этого не отнять, а для наивного представления время линейно от размера аргументов. Вот для двоичных представлений можно достичь логарифмического времени и одновременно экономии памяти.

* Учтём, что в реалистичной реализации разные множества могут ссылаться как на элементы на одно и то же множество, например s1 = [s0]; s2 = [s0]; может занять дополнительно лишь дважды столько места, сколько требуется для нового множества плюс на список ссылок на элементы плюс на ссылку на s0, которое сидит в памяти в единственном экземпляре.

[kotenok gav]

Ну, в любом случае, менять реализацию чисел нетрудно - достаточно сменить nextNumber и [num1] * num2 (его стоит тоже тогда в отдельную функцию отделить).