Здравствуйте, DarkGray, Вы писали:
G>>Чушь. Можно сделать такой специализированный вычислитель, и что?
DG>шаблоны C++ именно таким вычислителем и являются.
Они являются чуточку большим, чем "высичлитетем, спосбным сгенерить последостельность длины N".
DG>>шаблоны C++ именно таким вычислителем и являются. G>Они являются чуточку большим, чем "высичлитетем, спосбным сгенерить последостельность длины N".
И, кстати, с длиной N конкретно в вычислениях на типах в С++ — проблемы. Конкретно — со списками типов. Их длина, насколько я помню, наперед ограничена программистом.
Здравствуйте, DarkGray, Вы писали:
G>>Они являются чуточку большим, чем "высичлитетем, спосбным сгенерить последостельность длины N".
DG>бессмысленное утверждение.
Ну что вы. Бессмысленно было Ваше, зацитированное мной, утверждение. А мое вполне осмысленно.
Здравствуйте, Дмитрий Писаренко, Вы писали:
ДП>Что касается теоремы Бёма-Якопини, то она имеет применение. Если я хочу написать DSL, то эта теорема говорит мне о минимальном наборе конструкций, которые должны там быть.
Ну, вот уже это — неверный вывод. "Минимальный набор" подразумевает необходимость, теорема же о достаточности. Поэтому может стоит прислушаться к словам Gaperton-а? Они вполне себе о практике: он говорит о том, что таких минимальных наборов больше чем один. Вам есть из чего выбирать для своего DSL.
Здравствуйте, Gaperton, Вы писали:
G>Я не специалист по Хаскелю. Тем не менее, факт, что вычисления на типах (как-то — проверка физтческой размерности) там возможны — мне известен.
Тут такой вопрос возникает: понятно, что на тьюринг-полной системе можно делать любые вычисления. Но если некоторая система позволяет делать какие-то вычисления, это ведь еще не делает ее тьюринг-полной. Какие именно вычисления должна она уметь, чтобы быть полной?
Кое-какие вычисления на типах в хаскеле показывал thesz, но очень ограниченные (вроде сложения и умножения натуральных чисел) и работающие лишь на игрушечных примерах (на сложных компилятор падал). Достаточно ли сложения натуральных чисел для вычислительной полноты?
Здравствуйте, Gaperton, Вы писали:
G>Шаблоны С++ — они вычислительн полны?
Теоретически да, попадают под определение ЧРФ, фактически же компиляторы ограничивают вложенность (т.е. потенциальной рекурсии) совсем небольшой величиной.
Здравствуйте, D. Mon, Вы писали:
G>>Я не специалист по Хаскелю. Тем не менее, факт, что вычисления на типах (как-то — проверка физтческой размерности) там возможны — мне известен.
DM>Тут такой вопрос возникает: понятно, что на тьюринг-полной системе можно делать любые вычисления. Но если некоторая система позволяет делать какие-то вычисления, это ведь еще не делает ее тьюринг-полной. Какие именно вычисления должна она уметь, чтобы быть полной?
Система типов должна уметь зацикливаться на некоторых подстановках.
Т.е. должна иметь потенциально-бесконечную мощность.
Не знаю, возможно ли это для Хаскеля, но для шаблонов С++ это возможно, поэтому компиляторы имеют ограничение на глубину вложенности шаблонов.
Здравствуйте, D. Mon, Вы писали:
G>>Я не специалист по Хаскелю. Тем не менее, факт, что вычисления на типах (как-то — проверка физтческой размерности) там возможны — мне известен. DM>Тут такой вопрос возникает: понятно, что на тьюринг-полной системе можно делать любые вычисления. Но если некоторая система позволяет делать какие-то вычисления, это ведь еще не делает ее тьюринг-полной.
DM>Какие именно вычисления должна она уметь, чтобы быть полной?
На ней должна быть возможность написать машину Тьюринга. Или любую другую полную систему.
Говорить о каких-то особых вычислениях, которые должны быть, трудно, и это отлично показывает пример нормальных алгорифмов Маркова. "Программа" в данном случае — это упорядоченный набор текстовых замен. А состояние "программы" — это строка, над которой они производятся. И все. Нет там никаких вычислений в обычном понимании.
Второй пример — это модель kernel-stream. Это шейдерные вычисления в графускорителях, и map-reduce в NoSQL БД. Функции map и reduce описываются на полном языке (скажем, JavaScript), но сама модель вычислений такова, что в ней далеко не все выразимо.
DM>Кое-какие вычисления на типах в хаскеле показывал thesz, но очень ограниченные (вроде сложения и умножения натуральных чисел) и работающие лишь на игрушечных примерах (на сложных компилятор падал). Достаточно ли сложения натуральных чисел для вычислительной полноты?
Здравствуйте, D. Mon, Вы писали:
DM>Тут такой вопрос возникает: понятно, что на тьюринг-полной системе можно делать любые вычисления. Но если некоторая система позволяет делать какие-то вычисления, это ведь еще не делает ее тьюринг-полной. Какие именно вычисления должна она уметь, чтобы быть полной?
DM>Кое-какие вычисления на типах в хаскеле показывал thesz, но очень ограниченные (вроде сложения и умножения натуральных чисел) и работающие лишь на игрушечных примерах (на сложных компилятор падал). Достаточно ли сложения натуральных чисел для вычислительной полноты?
Или вот еще один великолепный пример. Всем знакомый, старый добрый SQL 92.
Сложение в нем есть. Он не является вычислительно полным. Но при этом, вне всякого сомнения, позволяет производить годные, полезные вычисления.
А вычислительно полные системы — они, крайне разнообразны и не похожи друг на друга, настолько, что в общем случае по доступным в них операциям однозначно определить полноту невозможно. Думаю, именно это нам и хотели показать преподаватели, дав примеры двух сильно непохожих полных систем.
Здравствуйте, vdimas, Вы писали:
V>Здравствуйте, D. Mon, Вы писали:
G>>>Я не специалист по Хаскелю. Тем не менее, факт, что вычисления на типах (как-то — проверка физтческой размерности) там возможны — мне известен.
DM>>Тут такой вопрос возникает: понятно, что на тьюринг-полной системе можно делать любые вычисления. Но если некоторая система позволяет делать какие-то вычисления, это ведь еще не делает ее тьюринг-полной. Какие именно вычисления должна она уметь, чтобы быть полной?
V>Система типов должна уметь зацикливаться на некоторых подстановках. V>Т.е. должна иметь потенциально-бесконечную мощность.
И это условие не является необходимым. Пример — язык программирования FP, в котором можно писать в комбинаторном стиле, без рекурсии и явного зацикливания. Примеры приводятся в книге Филда "Функциональное программирование".
Здравствуйте, Gaperton, Вы писали:
G>Или вот еще один великолепный пример. Всем знакомый, старый добрый SQL 92. G>Сложение в нем есть. Он не является вычислительно полным.
А кстати. Считая, что база данных не ограничена в размерах (мы же говорим про язык, не про реализацию), один шаг машины Тьюринга описать на SQL должно быть несложно (три таблички — лента, программа, текущие счетчики позиции и состояния). Будем выполнять такой запрос в цикле, и МТ готова. А зациклить запрос в SQL нельзя, случайно?
Здравствуйте, D. Mon, Вы писали:
G>>Или вот еще один великолепный пример. Всем знакомый, старый добрый SQL 92. G>>Сложение в нем есть. Он не является вычислительно полным.
DM>А кстати. Считая, что база данных не ограничена в размерах (мы же говорим про язык, не про реализацию), один шаг машины Тьюринга описать на SQL должно быть несложно (три таблички — лента, программа, текущие счетчики позиции и состояния). Будем выполнять такой запрос в цикле, и МТ готова. А зациклить запрос в SQL нельзя, случайно?
Прямолинейным образом — нельзя. Однако, можно попробовать как-нибудь через задний проход воспользоваться косвенной рекурсией на триггерах (пара триггеров, триггерящих друг друга), чтобы попытаться умутить что-нибудь тьюринг-полное. Например, какой-нибудь cyclic tag system (полнота этой хрени также доказана).
Не уверен, что это возможно, но с вычислительной полнотой никогда и ни в чем нельзя быть уверенным.
Здравствуйте, Дмитрий Писаренко, Вы писали:
ДП>Есть фундаментальный постулат: Если задача решается за конечное число шагов, то ее можно решить на любом языке программирования, в котором есть следующие конструкции: ДП>а) Последовательность (инструкции выполняются в определенной последовательности) ДП>б) Ветвление, развилки (конструкции if-else, switch) ДП>в) Повтор (циклы любого рода)
Для Тьюринг-полноты достаточно одного комбинатора iota.
Гипотеза, предполагающая, что Тьюринг-полноты достаточно для решения любой в принципе решаемой задачи — это тезис Чёрча — Тьюринга, который не доказан, но считается хорошо эмпирически подтверждённым (пока нет ни одного реального контрпримера, хотя некоторые продолжают проводить исследования в этом направлении).
Здравствуйте, Дмитрий Писаренко, Вы писали:
ДП>Здравствуйте!
ДП>Есть фундаментальный постулат: Если задача решается за конечное число шагов, то ее можно решить на любом языке программирования, в котором есть следующие конструкции:
ДП>а) Последовательность (инструкции выполняются в определенной последовательности) ДП>б) Ветвление, развилки (конструкции if-else, switch) ДП>в) Повтор (циклы любого рода)
ДП>Это означает: Язык программирования может быть каким угодно, но если в нем есть конструкции 3 указанных типов, то любую решаемую задачу на нем можно решить.
ДП>Подскажите, пожалуйста, как называется этот постулат и где можно найти его в развернутой форме (с формулами, блекджеком и культурологами).
ДП>Заранее благодарен
ДП>Дмитрий Писаренко
Это вы уже роскошно начинаете Необходимый и достаточный набор другой.
1. Операция присваивания нуля. Обнуление.
2. Прибавление 1. Следующий.
3. Переход по нулю. Ветвление.
Остальное можно получить из этого.
Здравствуйте, Gaperton, Вы писали:
G> Ибо (контрпример), ситема вроде нормальных алгорифмов Маркова является вычислительно полной, и там нет никаких ветвлений и развилок. Он предстваляет собой упорядоченный набор простых текстовых замен, и он вычислительно полон.
Вообще-то есть
В нормальном алгорифме выбор подстановки идёт сверху вниз до первой удовлетворяющей входной строке, что является if-then выбором, а сам по себе этот процесс цикличен.
Любая вычислительно полная логическая система включая самые экзотические (о Колмогоровских комплексах слышали? а они есть) так или иначе оперирует с ветвлениями&(циклами|рекурсией) просто иногда как в случе комбинаторной логики Карри это забито куда-нибудь вглубь "рекурсивного комбинатора" или "комбинатора суперпозиции" и т.п. но это всегда есть.
Здравствуйте, Дмитрий Писаренко, Вы писали:
ДП>Здравствуйте!
ДП>Есть фундаментальный постулат: Если задача решается за конечное число шагов, то ее можно решить на любом языке программирования, в котором есть следующие конструкции:
Еще малость подумал. Это не правильный постулат. Принципиальный вопрос в содержании самих шагов. Ведь они сами по себе могут быть не решаемы на машине тюринга, тем не менее алгоритм может быть и решаемый.
