2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

 
 
 
 Re: Тьюринг-полон ли данный язык
Сообщение24.08.2010, 22:40 
Аватара пользователя
Давайте построим все част-рек ф-и, что ли.
Нуль есть, инкремент есть (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);
}

 
 
 
 Re: Тьюринг-полон ли данный язык
Сообщение24.08.2010, 22:47 
(О, скажите, пожалуйста, что почитать про связь примитивно-рекурсивных функций и Тьюринг-полноты, а то не знаю.) А код вроде верный. Тогда получается, что функцию для булеана можно переписать без 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 множество из последовательности, которая включает все конечные множества — например, упорядоченную по рангам. В принципе, она (функция) вроде должна быть вычислимой (в наивном смысле, поскольку более точно пока не умею).

 
 
 
 Re: Тьюринг-полон ли данный язык
Сообщение24.08.2010, 23:08 
Аватара пользователя
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 --

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

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

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

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

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

 
 
 
 Re: Тьюринг-полон ли данный язык
Сообщение24.08.2010, 23:13 
Аватара пользователя
arseniiv в сообщении #346950 писал(а):
Значит, буду искать nextSet.
Ну я описал словами один вариант

 
 
 
 Re: Тьюринг-полон ли данный язык
Сообщение24.08.2010, 23:13 
Завтра утром почитаю внимательно и пойму. :-)

 
 
 
 Re: Тьюринг-полон ли данный язык
Сообщение25.08.2010, 09:01 
Xaositect в сообщении #346949 писал(а):
где $I_k$ соответствует $i_k$
За $I_k$ можно взять $\underbrace {\{ \{  \cdots \{ }_n\varnothing \}  \cdots \} \} $?

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

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

 
 
 
 Re: Тьюринг-полон ли данный язык
Сообщение02.09.2010, 00:19 
2arseniiv
Очень интересная идея. Вот только не совсем понятно, где такой язык можно использовать. :)

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

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

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

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

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

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

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

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

 
 
 
 Re: Тьюринг-полон ли данный язык
Сообщение04.09.2010, 00:08 
2arseniiv
Цитата:
множества можно хранить в виде ордеревьев

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

 
 
 
 Re: Тьюринг-полон ли данный язык
Сообщение04.09.2010, 15:57 
Они же не сойдут! Смотрите:
код: [ скачать ] [ спрятать ]
  1. []                     (0) 
  2. [[]]                 (1) 
  3. [[[]]]             (2) 
  4. [[], [[]]] 
  5. [[[[]]]]         (3) 
  6. [[], [[[]]]] 
  7. [[[]], [[[]]]] 
  8. [[], [[]], [[[]]]] 
  9. [[[], [[]]]] 
  10. [[], [[], [[]]]] 
  11. [[[]], [[], [[]]]] 
  12. [[], [[]], [[], [[]]]] 
  13. [[[[]]], [[], [[]]]] 
  14. [[], [[[]]], [[], [[]]]] 
  15. [[[]], [[[]]], [[], [[]]]] 
  16. [[], [[]], [[[]]], [[], [[]]]] 
— вот все множества ранга не больше 3. Не думаю, что будет удобно с ними управляться при помощи битовой шкалы/строки. :-)

 
 
 
 Re: Тьюринг-полон ли данный язык
Сообщение06.08.2011, 18:36 
2arseniiv
Не знаю, слышали ли вы о языке setl, но на всякий случай: An Invitation to SETL, оф.сайт здесь.

 
 
 
 Re: Тьюринг-полон ли данный язык
Сообщение06.08.2011, 22:21 
Интересно!

 
 
 
 Re: Тьюринг-полон ли данный язык
Сообщение07.08.2011, 00:07 
А мне вот не понравилось, что там нет поддержки бесконечных множеств. Вроде бы, технически это возможно ведь реализовать (я просто провожу аналогию с бесконечными объектами в некоторых функциональных языках типа хаскеля)...

 
 
 [ Сообщений: 160 ]  На страницу 1, 2, 3, 4, 5 ... 11  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group