Алгоритм vs компьютерная программа

[_hum_]

Alexu007 в сообщении #901795 писал(а):

Есть такой алгоритм: бесконечный цикл. Все программы, интерактивно работающие с человеком (и ОС в том числе), на этом алгоритме построены: 1. Проверяем, не было ли событий мыши. 2. Проверяем, не было ли событий клавиатуры. 3. Goto 1.

Время компьютера - это число импульсов, пришедших с входящего в его состав физического устройства - тактового генератора.

Не понимаю, о чем тут можно спорить?

Суть в том, что обычный алгоритм можно соотнести с некоторой функцией $f = f(x)$, которой на вход дается значение $x$, а на выходе либо получается результат работы алгоритма $y$, либо ничего не получается (значение функции оказывается для данного аргумента не определено).
Так вот работа ОС и того алгоритма, что вы описали, не вкладывается в этот формализм - там вычисление никогда не завершается результатом.

[arseniiv]

Незавершение — тот же $\bot$, вид сбоку.

[_hum_]

arseniiv в сообщении #901939 писал(а):

Незавершение — тот же $\bot$, вид сбоку.

что вы хотели сказать этим комментарием? что можно доопределить частично-вычислимую функцию до всюду определенной путем введения этого символа? но тогда полученная функция не будет вычислимой.
да и все равно это проблемы с определением соответствующей функции для ОС не решит.

[arseniiv]

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

-- Сб авг 30, 2014 04:14:50 --

_hum_ в сообщении #901940 писал(а):

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

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

[_hum_]

arseniiv в сообщении #901943 писал(а):

другой недоопределённости

какой другой? я знаю только одно понятие недоопределнности функции.

arseniiv в сообщении #901943 писал(а):

нормально на рекурсивные функции отображается

???

-- Сб авг 30, 2014 02:17:14 --

arseniiv, ну, пожалуйста, приведите тогда мат. определение, соответствующее ОС
хотелось бы услышать что-то наподобие, если говорить про формализацию обычной программы:

всякой программе, которая при запуске принимает на вход некий аргумент $a$ и либо выдает для него конкретный результат, либо зависает, поставим в соответствие функцию $f = f(a)$, которая определена для всех значений $a$, для которых программа дает конкретный результат (и для них совпадает со значением $f(a)$), и не определена для остальных.

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

[arseniiv]

_hum_ в сообщении #901946 писал(а):

какой другой? я знаю только одно понятие недоопределнности функции.

Ну вот оно одно и достаточно. Функция, которая не знает, что делать, если её второй аргумент меньше первого, «таким же образом» не определена на таких парах аргументов, как и функция, которая получена из программы for (i = arg1; i == arg2; i++); return 0;.

_hum_ в сообщении #901946 писал(а):

arseniiv, ну, пожалуйста, приведите тогда мат. определение, соответствующее ОС
хотелось бы услышать что-то наподобие, если говорить про формализацию обычной программы:

Пополните список функций $O, S, I_m^n$ (частичной) функцией $U\colon\mathbb N\to\mathbb N$, которой передаётся код списка, в начале которого находится параметр, с которым «вызовется» пользователь, а дальше — все предыдущие переданные параметры, и которая возвращает ответ пользователя. Например.

Частично-рекурсивная-функция-по-такому-определению ничем не хуже «нормальной», принимающей код $U$.

[_hum_]

arseniiv, мне как человеку, не настроенному на вашу волну, понять эти фрагментарные высказывания достаточно тяжело. можно вас попросить излагаться яснее, с соблюдением формальностей наподобие "прежде чем употребить термин, следует его предварительно определить/ввести" и проч.?


и еще раз, я прошу математически формализовать работу ОС, а именно, у меня эта программа работает на компе безостановочно, обрабатывая пакеты интернет-трафика, рассчитывая для меня утром, сколько будет 2+2, а вечером показывая фильмы и проигрывая музыкальные файлы. и все это безостановочно! никогда нельзя сказать, что ОС завершила работу, и вот результат этой работы (как бывает для обычных программ), и в то же время нельзя сказать, что ОС - это зависшая программа, потому как зависшие программы не дают никакого результата, а я от работы ОС получаю много результатов (см. выше).

[Mysterious Light]

_hum_, ок, давайте посмотрим на ОС, как на некую абстрактную штуковину, работающая как алгоритм на вычислителе.
Что должна делать система? Реагировать на внешние действия в соответствии со внутренней логикой, так? Т.е. имеются внешние действия, опишем их множеством $\rm{Time}\to \rm{NetInput}\times\rm{MouseInput}\times\rm{KeyboardInput}\times\ldots$ функций, которые моменту времени сопоставляет совокупность уже пришедшего в комп сигнала (из сети, клавы, мыши и т.п.).
ОС как обычно работает: сканирует входные команды, реагирует на них и так по циклу. Стало быть, работа ОС на конкретном вычислителе эквивалента функции $\rm{State}\to\rm{State}\times\rm{ScreenOutput}\times\rm{NetOutput}\times\ldots$, которая меняется состояние вычислителя и что-то посылает вовне.
Наконец, система может быть охарактеризована совокупностью элементарных функций, которые работают за ед. времени.
Всё, модель готова.

Глобально ОС выглядит как функция $(\rm{Time}\to \rm{NetInput}\times\rm{MouseInput}\times\ldots) \to (\rm{ScreenOutput}\times\rm{NetOutput}\times\ldots)$, локально — как композиция эл. функций $\rm{State}\times\rm{Time}\to\rm{State}\times\rm{ScreenOutput}\times\rm{NetOutput}\times\ldots$. Слова «глобально» и «локально» понимаются так: машина Тьюринга глобально представляется функцией $\rm{String}\to\rm{String}$, локально — набор правил перехода.

Посмотрите на машину Тьюринга: там есть считывающая головка, которая находится на определённой позиции. Сама модель контролирует положение головки, алгоритм (отдельные действия) лишь косвенно влияет на её положение. Предлагается Вам лишь добавить к вычислителю счётчик времени и много-много дополнительных источников информация: не одна только лента, но сеть, мышь, клава и т.п., так и выходы приделать. Если Вы смеете МТ заменять функцией $f: in \mapsto out$, то на ОС Вы можете смотреть как на $(\rm{Time}\to In) \to (\rm{Time}\to Out)$.

[Skeptic]

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

[Skeptic]

Пример терминального алгоритма. Ферма написал на полях: "Недостаточно места для доказательства".
Пример вечной программы. Физические законы - программа движения вселенной. Проверить конец вселенной невозможно, значит она вечна.

[Alexu007]

_hum_ в сообщении #901848 писал(а):

Так вот работа ОС и того алгоритма, что вы описали, не вкладывается в этот формализм - там вычисление никогда не завершается результатом.

Результат работы ОС - не число или массив чисел. Вы сели за компьютер, хорошо поработали (денег заработали) или поиграли, или музыку послушали, фильм посмотрели - в результате получили удовольствие, это и есть результат. Если алгоритм ОС удачный - вы получите удовольствие. Если неудачный - тормозит, глючит и виснет - не получите. Зачем сводить всё к математике?

[Toucan]

Alexu007 в сообщении #902562 писал(а):

Если алгоритм ОС удачный - вы получите удовольствие.

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

[Joker_vD]

(Оффтоп)

Alexu007 в сообщении #901795 писал(а):

Все программы, интерактивно работающие с человеком (и ОС в том числе), на этом алгоритме построены: 1. Проверяем, не было ли событий мыши. 2. Проверяем, не было ли событий клавиатуры. 3. Goto 1.

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

$$P=(mouse?x \to processMouse(x) \to P)\mathbin{\,\Box\,} (keyboard?x \to processKeyboard(x) \to P)$$

[Skeptic]

(Оффтоп)

Процессор не ждёт прерываний от внешних устройств. Внешние устройства по собственной инициативе прерывают работу процессора, переключая его на обработку прерываний.

[Joker_vD]

(Оффтоп)

Как правило. Однако, во-первых, прерывания можно замаскировать, и тогда никто работу процессора не прервет, а во-вторых, есть такие замечательные инструкции как HLT для x86 и WFI для ARM.

В любом случае, разница между while(true); ($\mathbf{STOP}$) и while(true) { int x = read(input); write(output, x * x); } ($\mu A {.\,} input?x\to output!(x^2) \to A$) существенная, и действительно, существуют денотационные семантики, которые последней программе сопоставляют не $\bot$, а что-то более интересное.