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

[arseniiv]

(Если кто-нибудь не знает про эзотерические языки программирования (с эзотерикой они мало общего имеют), можно почитать в Википедии: ru, en.)
Не могу додуматься, является ли придуманный мной ЯП из числа таких, который имеет лишь значения типа множество и немного операторов и операций, Тьюринг-полным. Он описан тут: http://forum.sources.ru/index.php?showt ... try2667587, но я могу всё пересказать, если кто-нибудь захочет.

[Xaositect]

Давайте построим все част-рек ф-и, что ли.
Нуль есть, инкремент есть (return [x]), проекции есть.
Суперпозиция есть.
На равенство два множества протестировать можно, буду писать if (a == b)
Примитивную рекурсию( h(x,0) = f(x) и h(x, y+1) = g(x, y, h(x, y))) сделать можно:

h(x,y)
{
  return iter(x, y, 0, f(x));
}

iter(x, y, v, r)
{
  if (y == v)
    return r;
  else
    return iter(x, y, [v], g(x, v, r));
}

(Проверьте, спал вчера мало, могу тупить :)

Мю ($\mu x (f(x,y) = 0)$) тоже можно подобным образом, даже проще, наверное.

mu(y)
{
  return iter(0, y)
}

iter(x, y)
{
  ife (f(x, y))
    return x;
  else
    return iter([x], y);
}

[arseniiv]

(О, скажите, пожалуйста, что почитать про связь примитивно-рекурсивных функций и Тьюринг-полноты, а то не знаю.) А код вроде верный. Тогда получается, что функцию для булеана можно переписать без select?

-- Ср авг 25, 2010 01:49:26 --

Т. к. в реализации всего, что понадобилось, он не использовался.

-- Ср авг 25, 2010 02:02:32 --

Ага, надумал. Если можно сконструировать все конечные множества, select можно построить так:

select(&set) {
  t = 0;
  el = 0;
  do {
    t = set * [el];
    ifne (t) {
      set -= t;
      return el;
    }
    el = nextSet(el);
  } whilee (0);
}

где nextSet(s) выдаёт следующее за s множество из последовательности, которая включает все конечные множества — например, упорядоченную по рангам. В принципе, она (функция) вроде должна быть вычислимой (в наивном смысле, поскольку более точно пока не умею).

[Xaositect]

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

(О, скаж́ите, пожалуйста, что почитать про связь примитивно-рекурсивных функций и Тьюринг-полноты, а то не знаю.) А к

Я уж не помню, где это есть, где нет. У меня под рукой сейчас только брошюрка Верещагина-Шеня "Вычислимые функции". Там в самом конце теоремы 76-77 о равносильности машин Тьюринга и част-рек ф-й. В Роджерсе тоже, скорее всего, есть.

Целочисленную функцию $n\mapsto 2^n$ можно написать, это следует из моего док-ва.

select можно написать, перебирая все множества и смотря, принадлежит ли оно нам.
Мы можем сопоставить числу 1 $\varnothing$, а числу $2^{i_1}3^{i_2}\dots p_n^{i_n}$ - мн-во $\{I_1, I_2,\dots, I_n\}$, где $I_k$ соответствует $i_k$. Тогда любое множество соотсветствует какому-то нат. числу (не обязательно одному), и перебирая все числа, мы сможем перебирать все наследственно-конечные множества.

-- Вт авг 24, 2010 23:09:45 --

Ну вот, Вы уже сами успели :)

[arseniiv]

И если эти конструкции окажутся правильными, то останется только для пущей радости найти код для nextSet. А если неправильными, надо будет по-другому делать select, раз язык Тьюринг-полный (упс, а вы ни слова о полноте же не сказали ещё, это мои домыслы ).

О, вы подтвердили мои идеи! То, что я там надобавлял к сообщению.

-- Ср авг 25, 2010 02:11:16 --

Значит, буду искать nextSet.

[Xaositect]

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

Значит, буду искать nextSet.

Ну я описал словами один вариант

[arseniiv]

Завтра утром почитаю внимательно и пойму.

[arseniiv]

Xaositect в сообщении #346949 писал(а):

где $I_k$ соответствует $i_k$

За $I_k$ можно взять $\underbrace {\{ \{ \cdots \{ }_n\varnothing \} \cdots \} \} $?

-- Ср авг 25, 2010 12:08:17 --

Ага, нельзя. Вы, верно, имели ввиду запоминание всех предыдущих сгенерированных множеств и использование их в рекурсии. Надо подумать, как можно это расписать…

[Circiter]

2arseniiv
Очень интересная идея. Вот только не совсем понятно, где такой язык можно использовать. :)

Есть две мыслишки. Во-первых, этой язык можно приспособить для исследования (в первую очередь для демонстрации) различных парадоксов теории множеств; во-вторых, можно придумать какую-нибудь основанную на множествах нереляционную БД, использующую ваш язык для управления ею.

Как может выглядеть теор-множественная БД я точно не знаю... Слышал о подходе, в котором метрическое пространство, суть сама БД, моделируется булеаном над некоторым множеством, при этом хранимые объекты соответсвенно являются элементами этого булеана, а метрика вводится как мощность пересечения объектов.

Кстати, в случае с базами данных эзотеричность языка может даже на пользу пойти. Возьмем к примеру БД redis (aka редиска), представляющую собой простое хранилище ключ-значение, отличающееся от РСУБД огромной скоростью работы и хорошей горизонтальной масштабируемостью. Грубо говоря, весь язык редиски сводится к паре команд get/set, причем команда get позволяет только узнать значение данного ключа, но не наоборот. Например, команда set some_key 100 присвоит значение 100 ключу some_key; узнать значение ключа можно командой get some_key, но чтобы произвести поиск ключа по значению, придется предварительно создать ключ, содержащий искомое значение прямо в своем имени, что-то вроде set 100 some_key, после чего для поиска можно будет использовать get 100. Примерно так... Скорее всего такой язык не является полным по Тьюрингу. :)

Ещё ваш язык вроде-бы неплохо дружит с графовыми структурами. Действительно, множество ребер есть всего лишь подмножество декартового квадрата множества вершин. Вот только не понятно как решать практические задачки с такими графами. Например, как найти кратчайший путь в графе на этом языке?

Не менее интересно было-бы попробовать условные переходы и рекурсию выразить через "базовые" операции... Возможен ли язык, в котором есть только макросы и самое необходимое для работы с множествами (объединение, пересечение, ну и сами множества)? Ах да, для программирования достаточно самих макросов (имитация лямбда или комбинаторной логики), но все-равно интересно. :)

Извините, если не в тему. :)

[arseniiv]

В тему! Это интересный обзор. Не знаю как для "серьёзных" вычислений, но для иллюстрации разных конечно-множественных вещей может подходить. Например, можно было бы показывать, как строятся натуральные числа, целые, рациональные (а действительные, конечно, не выйдет)… Графы действительно легко можно хранить в этом языке, но не знаю, как с обработкой. Скорее всего, реализация алгоритмов будет проще, а вот выполнение, учитывая реализацию языка (множества можно хранить в виде ордеревьев, листьями будут $\varnothing$, а ветками — отношения $\in$), — медленней.

Если всё будет хорошо, может, напишу интерпретатор. Грамматику в BNF описал, реализация всего этого вроде ничего мне неизвестного не содержит. А пока хочу другой язык написать, который inspired by K-Forth (решил сделать массивы, а потом решил использовать их как куски кода тоже, аннулируя ужасные, по моему мнению, в Forth слова if-then-else). Если что-нибудь из этого завершится успехом, наверно, напишу. А пока снова подкрался университет…

[Circiter]

2arseniiv

Цитата:

множества можно хранить в виде ордеревьев

Для начала могут сгодиться и паскалевские множества (битовые строки)... Скорость будет приличной. Да и распараллеливаемость у программулек на вашем языке должна быть хорошей.

[arseniiv]

Они же не сойдут! Смотрите:

1. []                     (0) 
2. [[]]                 (1) 
3. [[[]]]             (2) 
4. [[], [[]]] 
5. [[[[]]]]         (3) 
6. [[], [[[]]]] 
7. [[[]], [[[]]]] 
8. [[], [[]], [[[]]]] 
9. [[[], [[]]]] 
10. [[], [[], [[]]]] 
11. [[[]], [[], [[]]]] 
12. [[], [[]], [[], [[]]]] 
13. [[[[]]], [[], [[]]]] 
14. [[], [[[]]], [[], [[]]]] 
15. [[[]], [[[]]], [[], [[]]]] 
16. [[], [[]], [[[]]], [[], [[]]]] 

— вот все множества ранга не больше 3. Не думаю, что будет удобно с ними управляться при помощи битовой шкалы/строки.

[Circiter]

2arseniiv
Не знаю, слышали ли вы о языке setl, но на всякий случай: An Invitation to SETL, оф.сайт здесь.

[arseniiv]

Интересно!

[Circiter]

А мне вот не понравилось, что там нет поддержки бесконечных множеств. Вроде бы, технически это возможно ведь реализовать (я просто провожу аналогию с бесконечными объектами в некоторых функциональных языках типа хаскеля)...