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

[_hum_]

Я с *никсом непосредственно не знаком, потому спорить не буду. Высказывание же насчет его связи с потоками уточнял ранее в своем сообщении #610556"

[Xaositect]

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

Про файлы я не говорил, что они бесконечные. Все остальное может длиться бесконечно.

А зря, /dev/zero, например, настолько же бесконечен, насколько бесконечна работа ОС.

[epros]

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

Исторически ОС была первой программой, которая перестала подпадать под формализм обычной машины Тьюринга

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

[_hum_]

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

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

Исторически ОС была первой программой, которая перестала подпадать под формализм обычной машины Тьюринга

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

А аргументы к своему высказыванию и контраргументы к сказанному мною ранее будут? (Не хотелось бы "начинать песню сначала").

[epros]

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

А аргументы к своему высказыванию и контраргументы к сказанному мною ранее будут? (Не хотелось бы "начинать песню сначала").

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

Контраргументы к сказанному Вами хотите? Насколько я понял, Вы что-то пытались сказать про "бесконечность" каких-то потоков данных на входе ОС? Так вот, никаких бесконечных потоков на входе в ОС не бывает, всяк поток данных - конечен, после чего ОС переходит в режим ожидания. Эдак рассуждая, Вы могли бы "обосновать" и то, что любая программа, обрабатывающая строки, якобы "не подпадает под формализм машины Тьюринга": Можно ведь ей по очереди подавать на вход любое количество строк, так что получится "бесконечный поток входных данных", а программа в итоге "никогда не остановится". Б-рррр.

[_hum_]

Видимо, вы все-таки не совсем внимательно читали.

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

Профессор Снэйп в сообщении #608547 писал(а):

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

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

А вот программа для машины Тьюринга, вычисляющая универсальную функцию, чем не операционная система?

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

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

Esp_ в сообщении #609173 писал(а):

Но на ленте уже все написано заранее.

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

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

Wiki:Turing_machine:
"One way in which Turing machines are a poor model for programs is that many real programs, such as operating systems and word processors, are written to receive unbounded input over time, and therefore do not halt. Turing machines do not model such ongoing computation well (but can still model portions of it, such as individual procedures)."

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

Насколько я понял, Вы что-то пытались сказать про "бесконечность" каких-то потоков данных на входе ОС? Так вот, никаких бесконечных потоков на входе в ОС не бывает, всяк поток данных - конечен, после чего ОС переходит в режим ожидания.

См. дискуссию на это счет ранее в ветке.

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

Эдак рассуждая, Вы могли бы "обосновать" и то, что любая программа, обрабатывающая строки, якобы "не подпадает под формализм машины Тьюринга": Можно ведь ей по очереди подавать на вход любое количество строк, так что получится "бесконечный поток входных данных", а программа в итоге "никогда не остановится".

Ответ:

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

На мой взгляд, ситуация такова. Исторически ОС была первой программой, которая перестала подпадать под формализм обычной машины Тьюринга, потому сейчас в качестве примера подобного класса программ она и упоминается первой. Но она не единственная (если опять же говорить в контексте того вопроса, который привел к появлению данной ветки)! С тех пор появилась уйма подобных программ - тех, для которых бесконечная работа которых имеет смысл. Это и ваш торрент, и службы TCP/IP, http, и даже обычный Word. Общим для них всех является то, что они способны "результативно" обрабатывать бесконечный поток данных.

[Munin]

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

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

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

-- 30.08.2012 17:06:56 --

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

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

Этого ещё недостаточно.

[epros]

_hum_, простите, но это всё - тема для какого-то анекдота. Я, конечно, всё это ранее прочитал и нашёл смехотворным. Нет никакой "возможности менять сторонним наблюдателем содержимого ленты в процессе работы машины". И "службы TCP/IP, http, и даже обычный Word" на это тоже не способны. Есть конечные исходные данные, после обработки которых программа заканчивает работу. Вся "интерактивность" заключается в возможности подачи на вход программы новой порции данных. Вот и всё. Не надо навешивать на это фиг знает что.

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

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

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

Этого ещё недостаточно.

Недостаточно для чего?

[Xaositect]

Я, пожалуй, тоже как-то более по теме выскажусь.

Интерактивные программы, и современные ОС как частный случай, не покрываются понятием вычислимой функции. Потому что они получают вход и выдают результат не "в одно действие".
Однако если отвлечься от некоторых деталей, их можно описать в рамках формализма теории рекурсии, в частности, формализма машин Тьюринга.

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

Во-вторых, если это удобно, то можно дать отдельное определение в духе интерактивной МТ. Например, так:
Имеется алфавит состояний машины $Q$, алфавит ленты $A$, алфавит входных воздействий $I$, алфавит выходных воздействий $O$. У машины имеется головка с состоянием $q\in Q$, лента с ячейками с состояниями $a_i\in A$, регистр входа с состоянием $i\in I$
Программа - это последовательность команд вида $(i, a, q) \mapsto (q', c)$, $i\in I$, $a\in A$, $q\in Q$, $c\in A\cup O\cup \{L, R\}$.
Действия $L, R$ двигают головку ленты, действия из $A$ печатают символ на текущей позиции, как обычно. Если же действие $c$ было из алфавита $O$, то она выдает некоторое выходное воздействие и принимает новое входное, которое записывается в регистр.
Добавив еще немного очевидных формальностей, можно определить, каким образом программа для такой машины реализует функцию $I^{*}\to O^{*}$ или $I^{\omega}\to O^{\omega}$, т.е. переводит последовательности (сколь угодно длинные или бесконечные, как нам больше нравится) входных воздействий в последовательности выходных.

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

-- Чт авг 30, 2012 18:07:28 --

Если хочется подчеркнуть интерактивность, то даже лучше рассматривать не $I^{\omega}\to O^{\omega}$, а $(O^{*}\to I)\to O^{\omega}$

[epros]

Честно говоря, понимая вот это:

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

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

я не вижу, как можно разумно интерпретировать вот это:

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

Интерактивные программы, и современные ОС как частный случай, не покрываются понятием вычислимой функции.

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

[Munin]

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

Недостаточно для чего?

Для утверждения, что ОС моделируется машиной Тьюринга.

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

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

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

[epros]

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

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

Все «внешние условия» описываются как аргумент на входе вычислимой функции.

[Профессор Снэйп]

В теории вычислимости есть такое понятие - сводимость по перечислимости. Пишем $A \leqslant_e B$, если существует машина Тьюринга, которая, получая на вход элементы множества $B$ (в произвольном порядке), перечисляет элементы множества $A$. Один из весьма популярных объектов!

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

-- Пт авг 31, 2012 10:59:39 --

А ещё есть массовые проблемы и решётка Медведева!

[Munin]

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

Все «внешние условия» описываются как аргумент на входе вычислимой функции.

В граничной задаче можно заменить краевые условия начальными?

[epros]

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

В граничной задаче можно заменить краевые условия начальными?

Никакая граничная задача здесь ни при чём. Любой вычислительный процесс на компе устроен таким образом, чтобы выдавать результат или, в крайнем случае, завершаться прерыванием по таймауту. Иначе это не комп, а фиг знает что. Даже если Вы будете периодически искусственно прерывать вычислительный процесс и портить данные, с которыми он работает (хотя это не то, что обычно понимается под "интерактивностью"), то это ничего по-сути не изменит: Как только Вам надоедят эти непонятные издевательства над вычислительной техникой и Вы оставите её в покое, так вычислительный процесс неуклонно устремится к своему завершению.