Есть фундаментальный постулат: Если задача решается за конечное число шагов, то ее можно решить на любом языке программирования, в котором есть следующие конструкции:
а) Последовательность (инструкции выполняются в определенной последовательности)
б) Ветвление, развилки (конструкции 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 (в частности, последовательность натуральных чисел).
Чушь. Можно сделать такой специализированный вычислитель, и что?
Вычислительно полные схемы зело разнообразны. И циклы — ни разу не являются необхогдимостью. Компбинаторные языки вычилистельно полны, шняга вроде алгорифмов Марова полна, функциональные с рекурсией языки полны. И все выражаются друг через друга (т.е. эквивалентны).
Но вы пытайтесь. Может быть, премию тьюирнга за годное определение вычислимости получите.
.
