Что такое операционная система

[Munin]

epros в сообщении #612944 писал(а):

Никакая граничная задача здесь ни при чём.

То есть, вы аналогии не поняли?

epros в сообщении #612944 писал(а):

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

Ну поздравляю, у вас на столе фиг знает что.

Надеялся на более содержательное обсуждение.

[_hum_]

Возможно, вот это формализация подойдет.

В. А. Успенский, А. Л. Семёнов, А. Х. Шень. Может ли (индивидуальная) последовательность нулей и единиц быть случайной?

Цитата:

параграф 3.1 Вычислимые отображения

Дадим определение понятия вычислимого отображения множества $\Sigma$ конечных и бесконечных последовательностей нулей и единиц в себя. Естественный путь сделать это состоит в применении общих конструкций теории $f_0$-пространств в смысле Ю.Л.Ершова [Ерш 72]; см. об этом [Шень 84]. Мы, однако, приведем определение вычислимости лишь для отображений пространства $\Sigma$. [...]
Введем на $\Sigma$ порядок, считая, что $x \leqslant y$, если последовательность $x$ является началом последовательности $y$. Будем говорить, что $x$ и $y$ сравнимы, если $x \leqslant y$ или $y \leqslant x$. Для каждой конечной последовательности $x$ через $\Sigma_x$ обозначим множество всех ее (конечных или бесконечных) продолжений.[...]. рассматривая семейство $\Sigma_x$ как базу топологии, мы превращаем $\Sigma$ в топологическое пространство. Отметим, что пространство $\Sigma$ не является хаусдорфовым ($T_2$ - пространством); оно не является даже $T_1$ - пространством, а является всего лишь $T_0$ - пространством. Вычислимое отображение $\Sigma$ в себя будем искать среди всюду определенных непрерывных в указанной топологии функций. Легко проверить, что непрерывность всюду определенного отображения $f: \Sigma \rightarrow \Sigma$ равносильна выполнению двух условий:
(а) если $x, y \in \Sigma$, $x \leqslant y$, то $f(x) \leqslant f(y)$;
(б) значение $f$ на бесконечной последовательности равно минимальному продолжению значений $f$ на всех конечных ее началах: $f(x) = \sup \{f(x_0) \,| \,x_0 \text{ конечно}, x_0 \leqslant x \}$. (Отметим, что условие (а) гарантирует, что точная верхняя грань в (б) существует). Таким образом, всякое непрерывное отображение $f $ пространства $\Sigma$ в себя задается своими значениями на конечных последовательностях. Свяжем с ним множество $F$ тех пар конечных последовательностей $\langle p,q \rangle$, для которых $q \leqslant f(p)$. По этому множеству, очевидно, однозначно восстанавливается $f$: именно,

$$f(x) = \sup \{q\,|\, p \leqslant x \text{ и } \langle p,q \rangle \in F \}.$$

Соответствующие друг другу $F$ и $f$ будем называть сопряженными. Легко проверить, что отношение сопряжения является взаимно-однозначным соответствием между семейством всех непрерывных всюду определенных отображений $\Sigma$ в себя и семейством всех подмножеств $F\subset \Xi \times \Xi$, обладающих такими свойствами $(p,q,p',q',q_1,q_2 \in \Xi)$:
(1) $\langle p,\Lambda \rangle \in F\text{ для всех }p\in \Xi$;
(2) $\langle p,q \rangle \in F, p'\geqslant p, q' \leqslant q \Rightarrow \langle p',q' \rangle \in F$;
(3) $\langle p,q_1 \rangle \in F, \langle p,q_2 \rangle \in F \Rightarrow q_1 \text{ и } q_2 \text{ сравнимы }$.

Вычислимыми мы будем называть те непрерывные всюду определенные отображения $\Sigma$ в себя, для которых сопряженное множество пар перечислимо.[...]
Подчеркнем, что согласно этому определению вычислимые отображения являются всюду определенными; аналогом ситуации "$f(x)$ не определено" служит ситуация "$f(x)$ - пустая последовательность".
Можно дать и другое, возможно, более наглядное определение вычислимого отображения пространства $\Sigma$ в себя. Представим себе вычислительную машину, имеющую вход и выход. На вход можно подавать нули и единицы (например, нажимая одну из клавиш "$0$" и "$1$"), на выходе машина может выдавать (например, печатать на ленте) также только нули и единицы. Таким образом, работа машины состоит в получении на входе некоторой конечной или бесконечной последовательности нулей и единиц и выдаче на выходе некоторой конечной или бесконечной последовательности нулей и единиц. (Отметим, что в нашем понимании процесс работы машины продолжается неограниченно во во времени. При этом машина может проводить вычисления и печатать символы на выходе параллельно с ожиданием очередного символа на входе.)
Вообще говоря, последовательность нулей и единиц, появляющаяся на входе данной машины, может зависеть не только от входной последовательности, но и от того, в какие моменты времени были поданы на вход ее символы. Мы, однако, будем рассматривать только те машины, в которых выходная последовательность зависит только от входной последовательности. Если машина такова, то ей соответствует некоторое отображение $\Sigma$ в себя (сопоставляющее с каждой входной последовательностью соответствующую выходную). Такие отображения и будут вычислимыми отображениями $\Sigma$ в $\Sigma$.
Например, машина может игнорировать вход и печатать на выходе знаки двоичного разложения числа $\pi$. Это означает, что постоянное отображение, значение которого на любой последовательности равно двоичному разложению $\pi$, является вычислимым. (Вообще постоянное отображение вычислимо тогда и только тогда, когда его значением является вычислимая последовательность нулей и единиц.) Другой пример вычислимого отображения - тождественно: соответствующая машина копирует входную последовательность на выход.
Использованные в приведенном только что определении машины являются разновидностью "машин с оракулом" (см. [Родж 72б параграф 9.2]).

Только не совсем понятно, почему независимость от времени подачи на ленту оговаривается отдельно. Разве ее нельзя охватить, просто в сами данные "зашивая" время их поступления, и тем самым сводя зависимость к независимости?
И, я так понимаю, это все же не сама машина с оракулом (а только напоминающая ее разновидность), ибо исходными данными для нее является и "сам оракул". При этом еще накладываются ограничения на порядок вычисления. Так?

(Оффтоп)

Как в тесте табуляцию делать?

[epros]

Munin в сообщении #612957 писал(а):

То есть, вы аналогии не поняли?

Аналогия неуместна. Вот, допустим, есть у Вас программа вычисления факториала - примитивная рекурсия, конечное количество операций умножения. В чём заключается нормальное понимание интерактивности на примере этой процедуры? В том, что можно подавать новые и новые аргументы на вход и получать новые и новые результаты на выходе. Отменяет это понятие рекурсивности для данной процедуры? Ни в коем случае. Хорошо, допустим Вы скажете, что для некоторых аргументов программа будет считаться слишком долго - мы не захотим дожидаться результата предыдущего расчёта и подадим на вход процедуры новый аргумент. Можно ли так сделать? Пожалуйста, для этого есть понятие многопотоковости. Порождается новый экземпляр процедуры, который вычисляет свой результат параллельно с предыдущим экземпляром. Отменяет это понятие рекурсивности? Ни в коем случае. Любое конечное количество экземпляров процедуры описывается как рекурсивная функция.

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

[Munin]

epros в сообщении #612968 писал(а):

Аналогия неуместна. Вот, допустим, есть у Вас программа вычисления факториала

Я не спорю, что для программы вычисления факториала аналогия неуместна. Я говорю о других программах. И все вокруг, кроме вас. Или вы не считаете Word или Windows программами?

[bin]

Xaositect в сообщении #612631 писал(а):

если это удобно, то можно дать отдельное определение в духе интерактивной МТ

Такая машина уже не будет классической МТ, поэтому не лучше ли назвать ее Машиной Xaositect'а (МХ) и обсуждать в отдельной теме связь ОС и МХ?

-- Пт авг 31, 2012 16:03:08 --

epros в сообщении #612968 писал(а):

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

Ну вот уже и регистры появились. Сколько регистров у МТ?

-- Пт авг 31, 2012 16:07:15 --

Munin в сообщении #612957 писал(а):

Ну поздравляю, у вас на столе фиг знает что.

Верно! На наших столах (а у кого и под столом) "фиг знает что"(ФЗЧ) и это ФЗЧ только частично можно моделировать МТ. Я уже писал об этом ранее:

-- Пт авг 31, 2012 16:08:22 --

bin в сообщении #610761 писал(а):

для моделирования системы автоматического управления (САУ) в реальном времени ощущается недостаток "железа" у МТ

-- Пт авг 31, 2012 16:09:22 --

bin в сообщении #610761 писал(а):

Вопрос не праздный, т.к. моделируя САУ, мы можем ставить цель смоделировать конфликтные ситуации, типа гонок, взаимной блокировки и т.д.

-- Пт авг 31, 2012 16:10:10 --

bin в сообщении #610761 писал(а):

При параллельных вычислениях может наблюдаться недетерминированность

-- Пт авг 31, 2012 16:17:24 --

Далее:

epros в сообщении #612968 писал(а):

Хорошо, допустим Вы скажете, что для некоторых аргументов программа будет считаться слишком долго - мы не захотим дожидаться результата предыдущего расчёта и подадим на вход процедуры новый аргумент. Можно ли так сделать? Пожалуйста, для этого есть понятие многопотоковости. Порождается новый экземпляр процедуры, который вычисляет свой результат параллельно с предыдущим экземпляром.

Это тривиальный случай двух независимых процессов. А как быть с перемножением двух матриц по широко известным параллельным алгоритмам, где потоки нужно хорошо синхронизировать внутри одного процесса? Где оптимальное количество потоков определяется архитектурой машины (прога сама должна это делать, т.е. порождать оптимальное кол-во потоков)?

[epros]

Munin в сообщении #612976 писал(а):

Я не спорю, что для программы вычисления факториала аналогия неуместна. Я говорю о других программах. И все вокруг, кроме вас. Или вы не считаете Word или Windows программами?

А что нового в понятие вычислимой функции вносят другие программы? То, что они обрабатывают не натуральные числа, а некие другие объекты? А какая разница, если это всего лишь вопрос формы представления входных / выходных данных? Преобразуйте их в числа и получите те же самые рекурсивные функции. И далее повторяете все те же рассуждения про интерактивность.

-- Пт авг 31, 2012 18:12:55 --

bin в сообщении #612983 писал(а):

Это тривиальный случай двух независимых процессов. А как быть с перемножением двух матриц по широко известным параллельным алгоритмам, где потоки нужно хорошо синхронизировать внутри одного процесса? Где оптимальное количество потоков определяется архитектурой машины (прога сама должна это делать, т.е. порождать оптимальное кол-во потоков)?

Поверьте, ничего нового к понятию рекурсивной функции это не добавляет. Скажу Вам по секрету: любой реальный компьютер - это нечто даже меньшее, чем машина Тьюринга, это - конечный автомат.

Увы, никакие заклинания про интерактивность, многопотоковость и т.п. из компьютера оракул не сделают.

[Munin]

epros в сообщении #613010 писал(а):

А что нового в понятие вычислимой функции вносят другие программы?

Вам уже сказали, что. Ходить по кругу не вижу смысла.

epros в сообщении #613010 писал(а):

То, что они обрабатывают не натуральные числа, а некие другие объекты?

Нет, не то, что они обрабатывают, а то, как и когда они это обрабатывают. Я не понимаю, вы кривляетесь?

epros в сообщении #613010 писал(а):

Увы, никакие заклинания про интерактивность, многопотоковость и т.п. из компьютера оракул не сделают.

А об оракуле и речи нет!!! Вы совсем перепутали предмет обсуждения.

[bin]

epros в сообщении #613010 писал(а):

Поверьте, ничего нового к понятию рекурсивной функции это не добавляет. Скажу Вам по секрету: любой реальный компьютер - это нечто даже меньшее, чем машина Тьюринга, это - конечный автомат.Увы, никакие заклинания про интерактивность, многопотоковость и т.п. из компьютера оракул не сделают.

Скажу и Вам по секрету: не так все просто, как Вы говорите! Вот инфо для размышления (Википедия; при желании можно найти более строгие источники, но, пока, и этот достаточен; выделил ключевые слова, где "заклинания" - не мои!):

Цитата:

Отталкиваясь от работ Гильберта Гёдель впервые описал класс так называемых рекурсивных функций, с помощью которой доказал свои знаменитые теоремы о неполноте. Впоследствии был введён ряд других формализмов, таких как машина Тьюринга, λ-исчисление, оказавшихся эквивалентными рекурсивным функциям. В настоящее время, каждый из них считается формальным эквивалентом интуитивного понятия вычислимой функции. Эта эквивалентность постулируется тезисом Чёрча.

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

Интуитивно понятно, что чем сложнее и выразительнее теория, тем больше шансов, что она окажется неразрешимой. Поэтому, грубо говоря, «неразрешимая теория» — синоним к «сложная теория». (Алгоритмическая разрешимость)

Первые модели вычислений (например, машина Тьюринга, машина Поста, лямбда-исчисление и т.д.) были основаны на математике и использовали понятие глобального состояния, чтобы определить шаг вычисления (позднее эти понятия обобщены в работах [McCarthy and Hayes 1969] и [Dijkstra 1976]). Каждый шаг вычисления шёл от одного глобального состояния вычислений до следующего. Глобальный подход к состоянию был продолжен в теории автоматов для конечных автоматов и машин со стеком, в том числе их недетерминированные версии. Такие недетерминированные автоматы имеют свойство ограниченного индетерминизма. То есть, если машина всегда стоит перед тем, как она переходит в исходное состояние, то имеется ограничение на число состояний, в которых она может находиться.

Эдсгер Дейкстра развил дальше подход с недетерминированными глобальными состояниями. Модель Дейкстры породила споры о неограниченном индетерминизме. Неограниченный индетерминизм (называемый также неограниченным недетерминизмом) является свойством совпадающих вычислений, при котором величина задержки в обслуживании запроса может стать неограниченной в результате арбитражного соперничества за общие ресурсы, в то же время гарантируется, что запрос в конечном итоге будет обслужен. Хьюитт утверждает, что модель акторов должна обеспечить гарантии на предоставление услуги. Хотя в модели Дейкстры не может быть неограниченного количества времени между выполнением последовательных операций на компьютере, параллельно выполняемая программа, которая начала свою работу в строго определённом состоянии, может быть прервана лишь в ограниченном числе состояний [Dijkstra 1976]. Следовательно, модель Дейкстры не может обеспечить гарантии предоставления услуги. Дейкстра утверждал, что невозможно осуществить неограниченный индетерминизм.

Хьюитт утверждал иное: не существует ограничения на время, которое затрачивается на работу участка вычислений, называемого арбитром для урегулирования конфликтов. Арбитры имеют дело с разрешением таких ситуаций. Часы компьютера работают асинхронно с внешними входами: вводом с клавиатуры, доступом к диску, сетевым входом и т.д. Так что для получения сообщения, отправленного на компьютер, может пройти неограниченное время, и за это время компьютер может пройти через неограниченное количество состояний.

Неограниченный индетерминизм является характерной чертой модели акторов, в которой используется математическая модель Билла Клингера, основанная на теории доменов.[2] В модели акторов не существует глобального состояния. (Модель акторов)

-- Пт авг 31, 2012 21:49:28 --

epros в сообщении #613010 писал(а):

из компьютера оракул не сделают

Отдельный вопрос. Не понял, что значит "сделать из компа оракул"?:

-- Пт авг 31, 2012 22:06:39 --

Цитата:

В теории вычислений и теории сложности Машиной с оракулом называют абстрактную машину, предназначенную для решения какой-либо проблемы разрешимости. Такая машина может быть представлена как машина Тьюринга, дополненная оракулом с неизвестным внутренним устройством. Постулируется, что оракул способен решить определенные проблемы разрешимости за один такт машины Тьюринга.(Википедия, Вычисления с оракулом)

Проблема разрешимости — вопрос, сформулированный в рамках какой-либо формальной системы, требующий ответа «да» или «нет», возможно, зависящего от значений некоторых входных параметров.

Например, проблема «дано два числа x и y, делится ли x на у?» является проблемой разрешимости. Ответ может быть дан либо «да» либо «нет» и зависит от значений x и y. Метод решения проблемы разрешимости, представленный в форме алгоритма, называется разрешающей процедурой для этой проблемы. Так, разрешающая процедура для проблемы разрешимости «дано два числа x и y, делится ли нацело x на у?» должна определять совокупность действий, которые следует предпринять для проверки делимости нацело x на у для данных x и y. Один из таких алгоритмов деление столбиком изучается в начальной школе. Остаток равный нулю означает ответ «да», иначе «нет». Проблема разрешимости, для которой существует разрешающая процедура, называется разрешимой.(Википедия, Проблема разрешимости)

Поставлю на PC эмулятор МТ, задам очень низкую тактовую частоту этой МТ и подключу прогу с именем "оракул", которая будет пытаться разделить два целых числа одно на другое. Вот и сделаю "из компа оракул" (т.е. "МТ с оракулом")

PS Еще одна цитата (отметил сугубое):

Цитата:

Существует теорема, гласящая, что «Любой недетерминированный конечный автомат может быть преобразован в детерминированный так, чтобы их языки совпадали» (такие автоматы называются эквивалентными). Однако, поскольку количество состояний в эквивалентном ДКА в худшем случае растёт экспоненциально с ростом количества состояний исходного НКА, на практике подобная детерминизация не всегда возможна. Кроме того, конечные автоматы с выходом в общем случае не поддаются детерминизации. (Вики, Конечный автомат)

[epros]

Munin в сообщении #613092 писал(а):

А об оракуле и речи нет!!! Вы совсем перепутали предмет обсуждения.

Munin, это Вы с binом что-то напутали по жизни, ибо берётесь комментировать то, что не только не понимаете, но даже толком не прочитали. Так вот, то, что не выражается вычислимой функцией (т.е. не моделируется машиной Тьюринга), это и есть оракул.

[Munin]

epros в сообщении #613250 писал(а):

Так вот, то, что не выражается вычислимой функцией (т.е. не моделируется машиной Тьюринга), это и есть оракул.

Ну-у-у, как всё запущено. Яблоко выражается вычислимой функцией? Оно - оракул?

[bin]

epros в сообщении #613250 писал(а):

Munin в сообщении #613092 писал(а):

А об оракуле и речи нет!!! Вы совсем перепутали предмет обсуждения.

Munin, это Вы с binом что-то напутали по жизни, ибо берётесь комментировать то, что не только не понимаете, но даже толком не прочитали. Так вот, то, что не выражается вычислимой функцией (т.е. не моделируется машиной Тьюринга), это и есть оракул.

Глубокоуважаемый epros! Позвольте спросить: откуда у Вас такая уверенность, что только Вы обладаете истинным пониманием? Из приведенных мной выше цитат следует, например, что Дейкстра и Хьюитт тоже друг друга не понимали. Используя Ваш "подход", можно сделать аналогичное высказывание: как один из них, напутав что-то по жизни, посмел комментировать... (выглядеть такое высказывание будет более чем забавно, не находите? ) Далее Вы утверждаете, что:

Цитата:

то, что не выражается вычислимой функцией (т.е. не моделируется машиной Тьюринга), это и есть оракул

Откуда такое определение? Сами придумали или ссылку на источник приведете? Если хотите участвовать в обсуждении, то, пожалуйста, разъясняйте, аргументируйте свою точку зрения, убеждайте в ее правильности, вместо бездоказательных обвинений, что Ваши оппоненты "что-то напутали по жизни". Такое никого в Вашей правоте убедить не сможет, даже постороннего наблюдателя не убедит. Это же самоочевидно на уровне элементарной культуры спора.

[epros]

Munin в сообщении #613357 писал(а):

Яблоко выражается вычислимой функцией? Оно - оракул?

Munin, чё Вы несёте? В философы решили податься? Комп реализует некие функции, т.е. отображает некие входы в некие выходы. Функции бывают вычислимые и невычислимые. Причём тут, на фиг, какие-то яблоки?

bin в сообщении #613382 писал(а):

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

Вообще-то я не мотивирован Вас в чём-то убеждать. Имеете полное право остаться при своих ошибочных убеждениях. Определение оракула можете почерпнуть хотя бы из википедии. Правда Вы уже достали откуда-то цитату про него, которую явно не поняли. Хорошо тогда вот Вам такая линейка вопросов для обдумывания:
1) Вычислима ли процедура проверки равенства между рациональными числами?
2) Вычислима ли процедура проверки равенства между пределами фундаментальных последовательностей рациональных чисел ?
3) В каком из двух указанных выше случаев для решения потребуется оракул?

[Munin]

epros в сообщении #613414 писал(а):

Munin, чё Вы несёте? В философы решили податься?

Нет, просто показываю бредовость вашего обобщения.

epros в сообщении #613414 писал(а):

Комп реализует некие функции, т.е. отображает некие входы в некие выходы.

Э нет. Посмотрите внимательно на ваш комп. И сравните его с тем, что вы вообразили: машина, в которую в один конец скармливается заранее приготовленная входная перфолента, а с другого конца вылезает выходная.

epros в сообщении #613414 писал(а):

Имеете полное право остаться при своих ошибочных убеждениях.

Пожалуйста, но буянить в чужой теме зачем?

[bin]

epros в сообщении #613414 писал(а):

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

Вы подменили вопрос! Я спросил не про какое-то определение, а про то, которое Вы дали. Откуда оно? Предположим, что я могу чего-то не понимать, но сличить побуквенно два утверждения (Ваше и Вики) я могу?

[epros]

bin в сообщении #613442 писал(а):

Предположим, что я могу чего-то не понимать, но сличить побуквенно два утверждения (Ваше и Вики) я могу?

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

-- Сб сен 01, 2012 19:16:27 --

Munin в сообщении #613428 писал(а):

Посмотрите внимательно на ваш комп. И сравните его с тем, что вы вообразили: машина, в которую в один конец скармливается заранее приготовленная входная перфолента, а с другого конца вылезает выходная.

О, ну канэчно же! Магическая Связь со Всемирной Паутиной и неописуемые ни на каком формальном языке загадочные Человеко-Машинные Интерфейсы — это же совсем другое дело!