DRAKON.SU

И это не "псевдоакадемическая чушь" - а истина. К коей я пытаюсь по мере сил стремиться.
Отличия эти вполне принципиальны, на что указывал еще сам Тьюринг, описавший "машину выбора"

Семантика управляющего алгоритма реального времени не может адекватно быть описана без часов.

Но почему же нет разницы?

Да, фактически, можно сказать, что имеющаяся в литературе (или в IT в целом) классификация алгоритмики и есть уточнение частных случаев общей формулы, вами ранее указанной: S[n+1]=f(X[n],S[n]).

Однако, к примеру, выше Владимир Шелехов представил свою статью о классификации программ.

он же первично глобально выделяет или разделяет программирование на логическое и прочее

Подавляющее большинство реальных задач невозможно решить методами логического программирования.

Конечно, можно "придраться" и указать на то, что логические декларации трансформируются в императивные для машины вывода, и "нет никакой разницы"

должна же быть какая-то наука об алгоритмизации...

И базовая операция "ожидание" есть основа для пунктов выше (вне зависимости от природы исполнителя и реализации операции).

Попробуйте воспринять конструктивно - а не переходя на личности оборотами вроде "детский сад"

Время - не просто "еще один аргумент в векторе входных параметров". ПРОЦЕСС - это не "мгновенно, вне времени" вычисляемая ФУНКЦИЯ.

это ... истина.

Семантика управляющего алгоритма реального времени не может адекватно быть описана без часов.

Семантика управляющего алгоритма вообще не может адекватно быть описана с помощью функций.

располагает формат: текстовые сообщения.

Что ж, победителем спора выходит Alexey_Donskoy

Все равно она останется истиной.

Вот еще бы чОткую инструкцию приложили, как разрабатывать программы-функции, и как управляющие )

Вот тоже хорошая иллюстрация к теме.
Да, невозможно.
А почему?
Академист может сказать, что из-за принципиального различия.
Различия чего? Теории?
Фиг.
Различие только в исполнителе.
Ну, кривой исполнитель в логическом программировании. Заточенный на узкий круг задач и непригодный к решению других.

Истина в том, что вычислительный алгоритм есть вырожденный частный случай управляющего.
Истина в том, что время входит во входной вектор X в обобщённой формуле S[n+1]=f(X[n],S[n]).

Истина также в том, что введение времени в вектор X существенно затрудняет анализ алгоритма формальными методами по сравнению с вырожденным частным случаем.
Однако это не повод называть разницу между вычислительными и интерактивными алгоритмами принципиальной.

Да. Это семантика.
Но ожидание не аксиоматически существует в базисе, а реализуется строго теми же базовыми примитивами императивного программирования.

Да пожалуйста.
Только обсуждение в моей старой теме "Что же такое алгоритм?" так и не привело к консенсусу, что этим алгоритмом следует считать, а что нет.
Предлагаете по пятому кругу обсуждение вести?
Тогда вопросы: следует ли считать алгоритмом любую функцию f(X[n],S[n])?
Следует ли считать данные X[n], подаваемые на вход логической машины, программой?
Я на оба вопроса отвечаю утвердительно, кстати.

7.5. Алгоритмика процессов и управляющие структуры

Процесс, состояние, событие, действие. От описания структуры
системы произвольной природы перейдем теперь к изучению структур
разнообразных процессов, происходящих в системе и ее объектах на
разных иерархических уровнях, к построению структурных моделей
процессов и других характеристик динамической системы. В наиболее
общем виде понятие процесса определяется как упорядоченная во
времени последовательность состояний, событий, действий,
взаимообусловленных причинными и целевыми связями прообъектов системы
и внешнего окружения. Последовательность есть линейно
упорядоченное множество прообъектов, которые можно занумеровать целыми или
натуральными числами в соответствии с текущими моментами времени
так, что если номер п> т, то время tn >= tm. Понятие состояния
уточним чуть позже, а событие понимается как ощутимое, выше порога
различимости, изменение состояний, скажем, |S1 — S2| > delta(Sr), которое
можно привязать к определенному моменту или интервалу
времени, либо достижение системой целевого, либо выделенного состояния
S0 = S(t), иначе, событие есть совместное бытие S и S0.
В психологии, в бихевиористике, в технике действие есть
проявление какой-либо активности, силы, энергии со стороны человека,
машины или природных сил, поступок, шаг предопределенного
процесса. В физике действие есть произведение разности кинетической
и потенциальной энергии на время действия. В системологии
понятие действия трактуется весьма широко как элементарный или более
укрупненный составной шаг целенаправленного поведения активного
субъекта, человека или машины, вызывающий изменения состояний
системы.
Приведенные рассуждения показывают, что исходным понятием
в определении процесса является состояние. В системологии понятие
состояния стоит в ряду базисных категорий вместе с такими понятиями
как различимость, прообъект, система, процесс. Прежде всего,
представление о состоянии чего-либо ассоциируется с выражением в
определенных значениях каких-то постоянных или переменных парамет-
ров системы. При формализации системы в ней выделяют известные
и неизвестные объекты и связи между ними, их различимые и
неразличимые свойства, неизменные и меняющиеся объекты, их
характеристики, соответственно части системы разделяются на постоянные
и переменные. Последние включают статичные объекты,
неподвижные, но изменяющиеся по свойствам и связям, и потоковые,
подвижные объекты, образующие материальные и информационные
потоки прообъектов, называемых транзактами. Потоки, как и отдельные
объекты в потоке, характеризуются наборами числовых и нечисловых
параметров, объединенных в сигнаты, S-объекты, которые и описывают
потенциально изменчивые состояния системы.
Итак, описание состояния системы — это описание свойств ее
объектов и связей между ними в виде набора констант и
переменных, их значений, т.е. параметров, характеристик, количественных
и качественных признаков, принимающих определенные или размытые
значения в некоторый момент времени t. Чаще всего состояние системы
описывается сигнатными переменными, S-объектами, но в общем слу-
чае переменные, выражающие состояния, могут быть и функциональ-
ными и реляционными переменными, F-объектами и R-объектами из
соответствующих классов — доменов этих переменных. Переменные,
описывающие изменчивые состояния, могут быть известными либо
неизвестными, элементарными, базисными из FSR-базиса, либо
составными в виде набора, вектора переменных или структуры. В системах
с постоянной структурой, наиболее изученных, имеющих развитый
математический аппарат, функциональные и реляционные состояния
остаются неизменными, а если изменяются, то эти изменения соответ-
ствующим образом параметризуются, и определенные таким способом
параметры включаются в S-объекты, тогда полное состояние — статус
системы — представлен набором S-объектов, и процессы в системе
представляются сигнатными процессами — функциями преобразования
состояний, зависящих от времени. В системах с переменной структурой
возникают дискретно-непрерывные процессы структурных
преобразовании реляционных и функциональных объектов.

История, поведение, алгоритм процесса. Последовательность во
времени состояний системы, зависящих от внешних и внутренних
воздействий, называется поведением системы или траекторией, фа-
зовой траекторией и выражает историческое описание или историю
процесса или системы. Состояние системы и состояние внешней сре-
ды в определенный момент времени определяют текущую ситуацию,
а последовательность ситуаций есть история надсистемы. Другое
название ситуации — сцена, а история надсистемы есть сценарий,
описывающий последовательность ситуаций в определенном временном
интервале. Историческое описание процесса может быть полным либо
частичным. Избыточное описание процесса можно сократить без
потери точности и подробности характеризации процесса, представить его
в «свернутом» виде, используя функциональные связи и естественную
причинную ориентацию. Подобное представление процесса называется
алгоритмом процесса, по нему можно получить развернутое описание
в виде истории системы либо в виде траектории состояний объектов
в полном фазовом пространстве системы и надсистемы.
Представляя функционирование информационно-материальных систем
различной природы, выделяют объектные и операционные
истории. Объектная история характеризует последовательность
возникновения в системе (генерации) FSR-объектов, изменения их состояний,
движения в виде транзактов, начиная с появления на входных полюсах
системы и кончая выходом из системы через соответствующие
выходные полюса системы либо исчезновением, гибелью, аннигиляцией,
стиранием из памяти, «разбором» на составные компоненты внутри
системы, размазыванием и т.п. Операционная история описывает
последовательности преобразовании объектов системы и их состояний,
начиная с генерации, рождения и последующих превращений, преоб-
разований, гибели или удаления из системы. Операционная история
определяет последовательности работы F-объектов системы и являет-
ся функциональным описанием алгоритма процесса в виде линейно
или частично упорядоченных этапов реализации процесса. Для
процессов, происходящих в системах с постоянной структурой, с
неизменными функциональными и реляционными объектами,
операционная история выражает последовательности преобразований S-объектов
s -> s' = f(s). В системах с переменной структурой операционная
история описывает процессы возникновения и всевозможные превращения
FSR-объектов в виде взаимообратных переходов s <-> f, s <-> r, f <-> r,
f -> f', r -> r', s -> s'. Наличие тех или иных типов преобразований
определяет и тип процесса в целом.

Классификация процессов. [...]

Траектории состояний. Математический и технологический
алгоритм процесса. Модели и характеристики процессов весьма
разнообразны по форме задания, степени абстрагирования и полноты
описания. Чтобы определить процесс, необходимо задать не только
систему, но и законы изменения состояний во времени от внутренних
и внешних воздействий (источников и стоков), вычислить
промежуточные и финишные состояния, определить обобщенные характеристики
процесса. Мы ограничимся двумя видами представления произвольно-
го информационно-материального процесса: свернутым представлением
в виде алгоритма процесса и развернутым представлением в виде
траектории системы в пространстве состояний, которая выше была
названа историей системы или процессов в ней.
Описание процесса в виде последовательности преобразований,
линейной либо разветвленной (для параллельного процесса), не является
алгоритмом. Основное семантическое различие истории и алгоритма
процесса состоит в различии описательной, декларативной формы
информации, содержащейся в истории, и конструктивной
императивной формы представления алгоритма. Это различие нашло отражение
в теоретическом программировании в виде формального
представления декларативной и процедурной (функциональной, императивной)
семантики. В других областях науки и техники императивная
функция информации была формализована понятием управления, его мы
рассмотрим чуть позже. Алгоритм реализации процесса по существу
совпадает с понятием алгоритма функционирования системы. Понятие
алгоритма возникло в математике как способ однозначного описания
преобразований математических объектов. С развитием кибернетики-
информатики абстрактное понятие алгоритма наполнилось более
конкретным и более широким содержанием, которое охватило помимо
математических систем и процессов всю человеческую деятельность,
поддающуюся формализации и строгому знаковому описанию. В связи
с этим математическое понятие алгоритма должно быть уточнено при
переходе к произвольным системам и процессам.
В теории алгоритмов понятие математического алгоритма
отождествляется с понятием рекурсивной или эффективно вычислимой
функции, определенной в классе конструктивных объектов, а само
определение алгоритма формулируется так: «точное предписание,
которое задает вычислительный процесс (называемый в этом случае
алгоритмическим), начинающийся с произвольного исходного данного (из
некоторой совокупности возможных для данного алгоритма исходных
данных) и направленный на получение полностью определяемого этим
исходным данным результата» [84]. Это и подобные ему определения
считаются априори понятными математическому субъекту на уровне
интуиции, и при углубленном анализе понятие алгоритма в конечном
счете математики относят к неопределенным базисным понятиям,
таким как множество или число. В теоретической информатике,
напротив, стараются заменить не вполне ясную математическую интуицию
внешними по отношению к формализованному (объективированному)
субъекту конструктивными объектами и процессами.
При подобном переходе и расширении семантики понятие
математического алгоритма заменяется произвольным технологическим
(информационно-материальным) алгоритмом, в котором описаны не
только знаковые, информационные процессоры и преобразуемые
объекты, но и материальные преобразователи, системы, процессы в них,
и описание отсылает систему, реализующую
материально-информационный процесс, к внутренним дентам и контам соответствующих
знаков и понятий, внешним, материальным дентам, сенсорам, рефорам
и эффекторам, связанным с материальными объектами и процессами.
Итак, технологический алгоритм задается в
материально-информационном FSR-базисе, содержащем конечное число допустимых
материальных и информационных объектов. Так, S-базис содержит перечень
допустимых статусных (сигнатных) объектов и форм их представления:
вещества, детали, изделия, виды энергии, сигналы, базы данных и
другие знаки; функциональный базис содержит перечень станков,
технологического оборудования, информационных процессоров; реляционный
базис определяет типы R-объектов: условия, ограничения, требования,
связи и т. п. Математический алгоритм материально-информационного
процесса есть приближенная абстрактная модель технологического ал-
горитма.
Чтобы отделить технологические алгоритмы, частичные или всюду
определенные в заданном классе объектов предметики, от квазиал-
горитмов, необходимо фиксировать FSR-базис и систему, в которой
этот базис реализуется, а также определить алгоритмический или,
точнее сказать, технологический язык алгоритмики — язык
реализации информационных и материальных процессов и технологий, на
котором будет определено управление реализацией алгоритмического
процесса в заданном базисе. На технологическом языке по строго
формализованным правилам задается последовательность шагов
процесса с указанием FSR-объектов для каждого этапа процесса, входные
и выходные объекты, данные F-объекта, предусловия и постусловия
и действия при их нарушении, что и составляет программу процесса,
т. е. точную инструкцию на технологическом языке без предположений
о «догадливой, изобретательной и умной» системе, которая сама решит,
домыслит, что делать, если описание алгоритма неполное.
Реализацию математического алгоритма, записанного на логико-
математическом языке, выполняет математический процессор
объективированного субъекта. Реализация технологического алгоритма может
быть выполнена в информационно-материальной системе —
технологическом процессоре, если он имеет в своем составе все
необходимые функциональные объекты, правильно воспринимающие команды
технологического алгоритма и способные обеспечить информационный
процесс контроля и управления ходом протекания воплощаемого
информационно-материального технологического процесса, поэтому в
открытых системах важную функцию несет подсистема управления.
[...]

Конечно, нет. Для чего это тривиальное утверждение?
Функция используется для преобразования процессов.

Графы - да, но они отнюдь не сводятся к сетям Петри и даже к конечным автоматам.
Например, графами описываются дифференциальные уравнения, которые в управляющих алгоритмах играют отнюдь не последнюю роль.
...

Не хотите замечать, что я всё время говорю о процессах и только о процессах - и о том, как функцию применить к управлению этими процессами? А ведь я все возможные варианты подробно расписал в этой задаче!

Теория как раз и формирует "репертуар" исполнителя.

А в целом, исполнители Пролог-подобного "pattern matching"-а отнюдь не кривые, позволяют реализовать произвольную императивщину.

Это та семантика, которая не может быть внутри вычислительного алгоритма.

указывает в базисе управляющего алгоритма две операции: "ожидание" и "действие"

Процитирую ключевые моменты (громоздко, но вся терминология как раз в данную тему форума, кому-то может пригодиться) -- из "Зверев Г.Н. Теоретическая информатика и ее основания."

Всё-таки, не все варианты (как минимум, входные данные откуда-то берутся, же).

Если функция понимается как математическая -- подразумевается вычислительный алгоритм

Пожалуй, в характеристиках вычислительных и реагирующих алгоритмов есть важное отличие: реагирующий/управляющий алгоритм может исполняться бесконечно (пока существует системный объект), что не есть нарушение правильности, вычислительный же -- обязательно конечный.

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

Другими словами, если действие и условный переход составляют базис императивного исполнителя, то ожидание туда не входит - оно может являться там банальным макроопределением

Алексей Донской, признайте свое поражение в споре

- Вычислительный алгоритм есть вырожденный частный случай управляющего.
- Время входит во входной вектор X в обобщённой формуле S[n+1]=f(X[n],S[n]).

Введение времени в вектор X (наряду с другими сигналами из внешнего мира) существенно затрудняет анализ алгоритма формальными методами по сравнению с вырожденным частным случаем.
Однако это не повод называть разницу между вычислительными и управляющими (интерактивными) алгоритмами принципиальной.

Алексей Донской, признайте свое поражение в споре

- Вычислительный алгоритм есть вырожденный частный случай управляющего.

Уже частично признал

Между дубиной и пулемётом принципиальной разницы тоже нет. Это разные виды оружия. Но ТТХ пулемёта другие...

У нас в датацентре в январе произошёл сбой. Разбор полётов показал: причина в ошибке в программе, которая мониторит сервера.
Виновный программист, скорее всего, даже не знал, что пишет алгоритм управления. Поэтому у него не было шансов с самого начала.
Если бы тот программист понимал, что разрабатывает "программу-процесс", то он бы (по Шелехову) применил бы соответствующие "методы программной инженерии". Но он не знал и не применил. Итог печален.

Всё вроде правильно изложено, да.

Да пожалуйста, сколько угодно.
Но пользы-то именно от этой классификации немного.
И там, и там, действия выполняются одними и теми же командами исполнителя.
Наложите ряд ограничений на тактику использования команд - получите "вычислительный алгоритм".
Вопрос - зачем?

Повторно обращаю внимание, что ожидание не обязано быть в базисе ИСПОЛНИТЕЛЯ. Оно реализуется при помощи тех же действий.
Другими словами, если действие и условный переход составляют базис императивного исполнителя, то ожидание туда не входит - оно может являться там банальным макроопределением.

Однако же юмор всей ситуации в том, что хотя рассмотрение всего этого многообразия действительно полезно, всё это описанное многообразие не выходит за рамки обобщённого S[n+1]=f(X[n],S[n]) !

Возьмём общее определение алгоритма: S[n+1]=f(X[n],S[n]), где S - пространство состояний исполнителя, X - вектор входных данных, f - собственно алгоритм как функция преобразования пространства состояний.
Имеем следующие частные случаи:

1) X - пустое множество. Тогда алгоритм можно назвать чисто вычислительным - он что-то считает по определённым правилам из предопределённого в нём же самом исходного пространства состояний. Например, осуществляет полный перебор шахматной задачи, или вычисляет корни трансцендентного уравнения с заданными коэффициентами, или рисует картинку на экране и т.п.

2) X - const. Тогда алгоритм однократно принимает исходные данные и заданным образом их преобразует. Например, анализирует введённую шахматную позицию, или вычисляет корни уравнения по введённым коэффициентам, или трансформирует заданный графический файл и т.п.

3) X=X(t), то есть меняется во времени. Это уже из той области, что выше названо "управляющим алгоритмом" - процесс в реальном (или модельном, неважно) времени и в меняющейся внешней среде. Например, игра в шахматы с человеком, или автоматическое управление технологическим процессом, или динамическое управление детализацией рендеринга в шутере (не говоря уж об игровых персонажах), и т.д. и т.п.

Ну и где принципиальная-то разница?
Зато характерные частные случаи налицо (вплоть до полностью вырожденного).

Вот этого не понял. Какая разница, откуда они берутся, если перечислены все возможные варианты их свойств: процессы, константы, отсутствие.

Очень хорошо, если теперь можно говорить на одном языке, надеюсь.

В данном случае речь о математических формализмах, а не о реализации технологического алгоритма.

Формализм алгоритма процесса обязан иметь средства для выражения "упорядоченной во времени последовательности состояний, событий, действий".

Ключевое не в том, как именно реализуются операции "ожидания" и "действия".

Итак, f - математическая функция, которая не имеет права выполнять "действие"

выше в теме указано, почему

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

функция и процесс -- различные математические формализмы