Есть фундаментальный постулат: Если задача решается за конечное число шагов, то ее можно решить на любом языке программирования, в котором есть следующие конструкции:
а) Последовательность (инструкции выполняются в определенной последовательности)
б) Ветвление, развилки (конструкции if-else, switch)
в) Повтор (циклы любого рода)
Это означает: Язык программирования может быть каким угодно, но если в нем есть конструкции 3 указанных типов, то любую решаемую задачу на нем можно решить.
Подскажите, пожалуйста, как называется этот постулат и где можно найти его в развернутой форме (с формулами, блекджеком и культурологами).
Здравствуйте, Дмитрий Писаренко, Вы писали:
ДП>... ДП>Подскажите, пожалуйста, как называется этот постулат и где можно найти его в развернутой форме (с формулами, блекджеком и культурологами).
Уж не про тьюринг-полноту ли идет речь?
Здравствуйте, Дмитрий Писаренко, Вы писали:
ДП>Здравствуйте! ДП>Есть фундаментальный постулат: Если задача решается за конечное число шагов, то ее можно решить на любом языке программирования, в котором есть следующие конструкции: ДП>а) Последовательность (инструкции выполняются в определенной последовательности) ДП>б) Ветвление, развилки (конструкции if-else, switch) ДП>в) Повтор (циклы любого рода) ДП>Подскажите, пожалуйста, как называется этот постулат и где можно найти его в развернутой форме (с формулами, блекджеком и культурологами).
Теорема Бёма — Якопини (нашёл по "Теории алгоритмов" Матроса и Поднебесовой, там, по-моему, переврали транскрипцию фамилий "Бома — Джакопини", хотя с Corrado Böhm непонятно, как будет правильно)
ДП>Подскажите, пожалуйста, как называется этот постулат
если к приведенному набору конструкций добавить бесконечную память и конструкции для работы с ней, то принцип называется Полнота по Тьюрингу
В теории вычислимости исполнитель (множество вычисляющих элементов) называется тьюринг-полным, если на нём можно реализовать любую вычислимую функцию.
Достаточное(и необходимое) условие для тьюринг-полноты — возможность реализовать на данном исполнителе машину-тьюринга с бесконечной лентой.
In computability theory, a system of data-manipulation rules (such as an instruction set, a programming language, or a cellular automaton) is said to be Turing complete or computationally universal if and only if it can be used to simulate any single-taped Turing machine and thus in principle any computer.
бесконечная память плюс последовательность инструкций, ветвление, цикл являются тьюринг-полными, т.к. с помощью них можно реализовать машину тьюринга с бесконечной лентой
если к приведенному набору конструкций добавить конечную память, ввод-вывод и конструкции для работы с памятью и вводом-выводом, то используется, что любая реально-исполняемая программа может быть представима как детерминированный конечный автомат, и что данных конструкций достаточно для построения произвольного конечного автомата.
All real computing devices in existence today can be modeled as a finite state machine, as all real computers operate on finite resources. Such a machine has a set of states, and a set of state transitions which are affected by the input stream.
Здравствуйте, Дмитрий Писаренко, Вы писали:
ДП>Есть фундаментальный постулат: Если задача решается за конечное число шагов, то ее можно решить на любом языке программирования, в котором есть следующие конструкции:
"Фундаментальный постулат" называется "вычислимость по Черчу", или вычислительной полнотой. http://ru.wikipedia.org/wiki/Тезис_Чёрча_—_Тьюринга
И его невозможно ни доказать, ни опровергнуть. Звучит он, разумеется, не так, как у тебя.
ДП>а) Последовательность (инструкции выполняются в определенной последовательности) ДП>б) Ветвление, развилки (конструкции if-else, switch) ДП>в) Повтор (циклы любого рода)
ДП>Это означает:
Это не означает ровным счетом ничего. Ибо (контрпример), ситема вроде нормальных алгорифмов Маркова является вычислительно полной, и там нет никаких ветвлений и развилок. Он предстваляет собой упорядоченный набор простых текстовых замен, и он вычислительно полон.
И этот факт доказан. Первый курс университета, по специальности ВМиК, между делом так.
Здравствуйте, Gaperton, Вы писали:
G>Здравствуйте, Дмитрий Писаренко, Вы писали:
...
ДП>>Это означает:
G>Это не означает ровным счетом ничего. Ибо (контрпример), ситема вроде нормальных алгорифмов Маркова является вычислительно полной, и там нет никаких ветвлений и развилок. Он предстваляет собой упорядоченный набор простых текстовых замен, и он вычислительно полон.
G>И этот факт доказан. Первый курс университета, по специальности ВМиК, между делом так.
Влад, ликбез устраивать, конечно, полезно, но теорема Бома-Якопини ничего не утверждает о том, могут ли быть построены системы вычисления, не включающие описаные выше элементы (последовательность, ветвление и цикл).
Здравствуйте, Курилка, Вы писали:
G>>И этот факт доказан. Первый курс университета, по специальности ВМиК, между делом так.
К>Влад, ликбез устраивать, конечно, полезно, но теорема Бома-Якопини ничего не утверждает о том, могут ли быть построены системы вычисления, не включающие описаные выше элементы (последовательность, ветвление и цикл).
Есть маленькая проблема. Указанная тобой теорема — о преобразовани уже готового алгоритма к структурному виду (любой исполняемый алгоритм...), а не о решении "любой проблемы, решаемой за окнечное количество шагов".
Автор же, судя по формулировке вопроса, смешивает само понятие вычислимости со структурным программированием. Это неверно.
G>Автор же, судя по формулировке вопроса, смешивает само понятие вычислимости со структурным программированием. Это неверно.
Хотя, впрочем, это частное высказывание — действительно верно. То есть — такие языки (в сочетании с деструктивным присваиванием, которое не было упомянуто) действительно вычислительно полны.
Но оно не особо полезно. Так как, вычислительно полны бывают самые неожиданные системы. В том числе, и те, в которых нет ни присваиваний, ни циклов, ни функций с рекурсиями.
Здравствуйте, Gaperton, Вы писали:
G>О! Минус за ликбез о теории вычислимости — зачетен .
Минус за грубость (тыканье) и ненужное теоретизирование.
Ваши знания, которыми Вы так гордитесь, не имеют абсолютно никакого значения для практики.
Вам хоть раз эти тьюринговые штучки понадобились при решении практических задач?
Если нет, то зачем их изучать?
* * *
Что касается теоремы Бёма-Якопини, то она имеет применение. Если я хочу написать DSL, то эта теорема говорит мне о минимальном наборе конструкций, которые должны там быть.
Здравствуйте, Дмитрий Писаренко, Вы писали:
G>>О! Минус за ликбез о теории вычислимости — зачетен . ДП>Минус за грубость (тыканье) и ненужное теоретизирование.
"Тыкание" допускается интернет-этикой, это не деловая переписка. Впрочем, здесь я не настаиваю.
А "ненужное теоретизирование" Вы сами начали, задав вопрос по теории алгоритмов.
ДП>Ваши знания, которыми Вы так гордитесь, не имеют абсолютно никакого значения для практики.
О как. Чем точно не стоит гордится — так это отсутствием фундаментальных знаний, которые положено знать первокурснику. Так как я уж как 15 лет как защитил диплом — этим мне гордится несколько поздно. Есть другие поводы.
А то, насколько они полезны — может судить только тот, кто ими обладает, не так ли?
ДП>Вам хоть раз эти тьюринговые штучки понадобились при решении практических задач? ДП>Если нет, то зачем их изучать?
О, вопрос расширяется. Зачем вообще нужно фундаментальное знание? Ну, может, затем, чтобы не задавать глупых вопросов?
ДП>* * *
ДП>Что касается теоремы Бёма-Якопини, то она имеет применение. Если я хочу написать DSL, то эта теорема говорит мне о минимальном наборе конструкций, которые должны там быть.
Удивительное рядом. А кто вам сказал, что ваш DSL должен обязательно быть вычислительно полон?
Здравствуйте, Дмитрий Писаренко, Вы писали:
ДП>Что касается теоремы Бёма-Якопини, то она имеет применение. Если я хочу написать DSL, то эта теорема говорит мне о минимальном наборе конструкций, которые должны там быть.
По-моему, делать DSL Тьюринг-полным далеко не обязательно, если не вредно.
ДП>>Вам хоть раз эти тьюринговые штучки понадобились при решении практических задач? ДП>>Если нет, то зачем их изучать?
G>О, вопрос расширяется. Зачем вообще нужно фундаментальное знание? Ну, может, затем, чтобы не задавать глупых вопросов?
Или вот возьмем элементарные, практические примеры. Сильно непохожие на то, с чем ты (Вы) привык иметь дело.
Шаблоны С++ — они вычислительн полны?
Ситема типов Хаскеля — вычислительно полна?
Понятное дело, большинству не надо иметь дело с теорией. А вот Александреску, имея фундаментальное образование, смог показать, что практически полезное можно делать с шаблонами С++. Ибо, они таки _почти_ вычислительно полны.
ДП>>Что касается теоремы Бёма-Якопини, то она имеет применение. Если я хочу написать DSL, то эта теорема говорит мне о минимальном наборе конструкций, которые должны там быть.
G>Удивительное рядом. А кто вам сказал, что ваш DSL должен обязательно быть вычислительно полон?
awk.
sed.
lexx.
yacc.
Весьма успешные DSL. Част из них вычислительно полны, но не в твоем понимании. То есть, твоего понимания не хватит, чтобы доказать полноту.
Здравствуйте, Gaperton, Вы писали:
G>Ситема типов Хаскеля — вычислительно полна?
Не должна бы. Те, кто заботится о завершимости алгоритмов типизации (не хочет, чтобы компилятор вис), обычно стараются не делать систему типов тьюринг-полной. Кажися, в стандартном хаскеле это так, а вот со всеми расширениями и примочками GHC уже не знаю.
Здравствуйте, D. Mon, Вы писали:
DM>Не должна бы. Те, кто заботится о завершимости алгоритмов типизации (не хочет, чтобы компилятор вис), обычно стараются не делать систему типов тьюринг-полной. Кажися, в стандартном хаскеле это так, а вот со всеми расширениями и примочками GHC уже не знаю.
Я не специалист по Хаскелю. Тем не менее, факт, что вычисления на типах (как-то — проверка физтческой размерности) там возможны — мне известен.
G>>Ситема типов Хаскеля — вычислительно полна?
DM>Не должна бы. Те, кто заботится о завершимости алгоритмов типизации (не хочет, чтобы компилятор вис), обычно стараются не делать систему типов тьюринг-полной. Кажися, в стандартном хаскеле это так, а вот со всеми расширениями и примочками GHC уже не знаю.
здесь можно зайти с другой стороны:
любой "N-конечный алгоритм" можно реализовать на вычислителе без циклов, если у вычислителя есть возможность сгенерить последовательность длины N (в частности, последовательность натуральных чисел).
"N-конечным алгоритмом" назовем алгоритм, для которого известно, что он заведомо завершается за число шагов меньше N (или N(s), где s — конкретный набор входных данных алгоритма)
также помогает, что для большинства стандартных алгоритмов (сортировка, поиск, фильтрация, обработка графов и т.д.) известна верхняя оценка кол-ва шагов.
Здравствуйте, DarkGray, Вы писали:
DG>любой "N-конечный алгоритм" можно реализовать на вычислителе без циклов, если у вычислителя есть возможность сгенерить последовательность длины N (в частности, последовательность натуральных чисел).
Чушь. Можно сделать такой специализированный вычислитель, и что?
Вычислительно полные схемы зело разнообразны. И циклы — ни разу не являются необхогдимостью. Компбинаторные языки вычилистельно полны, шняга вроде алгорифмов Марова полна, функциональные с рекурсией языки полны. И все выражаются друг через друга (т.е. эквивалентны).
Но вы пытайтесь. Может быть, премию тьюирнга за годное определение вычислимости получите.
Здравствуйте, 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 выбором, а сам по себе этот процесс цикличен.
Любая вычислительно полная логическая система включая самые экзотические (о Колмогоровских комплексах слышали? а они есть) так или иначе оперирует с ветвлениями&(циклами|рекурсией) просто иногда как в случе комбинаторной логики Карри это забито куда-нибудь вглубь "рекурсивного комбинатора" или "комбинатора суперпозиции" и т.п. но это всегда есть.
Здравствуйте, Дмитрий Писаренко, Вы писали:
ДП>Здравствуйте!
ДП>Есть фундаментальный постулат: Если задача решается за конечное число шагов, то ее можно решить на любом языке программирования, в котором есть следующие конструкции:
Еще малость подумал. Это не правильный постулат. Принципиальный вопрос в содержании самих шагов. Ведь они сами по себе могут быть не решаемы на машине тюринга, тем не менее алгоритм может быть и решаемый.
.
