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

[Munin]

Кажется, только что про ОС наделал :-)

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

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

Кажется, только что про ОС наделал

В ОС я сам плохо разбираюсь, иначе тему бы не заводил

[Tod Leben]

Цитата:

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

С.О.С. 2 - е издание. Э. Таненбаум.

(Оффтоп)

Большой полосатый МУХ - это пчёл, а ОС - это на чём вертится земля.

[Xaositect]

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

С первым он, возможно, и справится, со вторым скорее всего нет. Если, конечно, не заговорит об этапах перечисления, о шагах... короче, о том самом времени, которое он столь яростно отрицает!

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

[bin]

Tod Leben в сообщении #609750 писал(а):

Цитата:

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

Как же далека бывает теория от практики! Для очень многих практиков важно, чтобы 1) ОС была послушной 2) надежной 3) легко восстанавливаемой (откатываемой к предыдущим конфигурациям), и т.д. - много подобных трудно формализуемых свойств. Про такие спорные, как plug and play, тут лучше вообще промолчать

-- Сб авг 25, 2012 03:41:47 --

PS Я понимаю, что к машине Тьюринга plug and play, видимо, не имеют отношения, равно как и большинство других опций современных ОС

PPS Еще одна идея: в сетке масса эмуляторов машины Тьюринга, скачивайте и ставьте на свой комп. В принципе такой эмулятор можно назвать ОС, а если он еще и режим вывода промежуточных результатов (трассу) поддерживает и дамп памяти-ленты машины Тьюринга (для отладки проги), то чем не ОС?

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

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

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

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

В совсем простых случаях можно. Но лучше этого не делать.

Нет, серьёзно, вот простое утверждение: если $A_0, A_1$ рекурсивно перечислимы и $A_0 \cap A_1 = \varnothing$, то $A_0 \cup A_1 \equiv_T A_0 \oplus A_1$. Для доказательства нужно показать $A_i \leqslant_T A_0 \cup A_1$, остальное совсем очевидно. Сводим так: для каждого $x$ сначала проверяем $x \in A_0 \cup A_1$, если $x \not\in A_0 \cup A_1$, то сразу говорим, что $x \not\in A_i$. Если же $x \in A_0 \cup A_1$, то параллельно перечисляем оба множества $A_0, A_1$ и смотрим, в какое из них попадёт $x$...

Совсем простое рассуждение! И как его теперь "без времени" оформить? А в теории вычислимости много таких! Вся классика, которая начинается с 1950-ых годов, в основном такая.

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

$$ K = \{ x : \text{машина с номером }x \text{ останавливается, получив на вход } x \} $$

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

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

P. S. У меня шеф уже который год читает в курсе матлогики теоремы о неполноте без всяких машин и алгоритмов. Чисто через $\Sigma$-определимость. И каждый год студенты с круглыми шарами спрашивают: что, почему, как, откуда? Приходится каждый раз вздыхать и начинать объяснять: ну, давайте рассмотрим машину Тьюринга, которая работает по шагам и, перебирая все возможные формальные доказательства, перечисляет следствия данной разрешимой теории...

P. P. S. Помню, в студенческие годы был у нас один товарисч, который конструктивных рассуждений вообще не признавал. Если ему показывали доказательство, в котором объект с нужными свойствами явно строился, он начинал психовать и кричал: ерунда, это не настоящая математика, не верю я в ваши построения, покажите мне, как утверждение о несуществовании объекта приводит к противоречию!

[_hum_]

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

А так, ОС характеризуется:
- интерактивностью (способностью в процессе своего исполнения взаимодействовать с пользователем/аппаратным обеспечением (из-за чего результат работы ОС становится не детерминированным исходными данными),
- [для компьютеров общего назначения] универсальностью (способностью реализовывать универсальный алгоритм);

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

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

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

А так, ОС характеризуется:
- интерактивностью (способностью в процессе своего исполнения взаимодействовать с пользователем/аппаратным обеспечением (из-за чего результат работы ОС становится не детерминированным исходными данными),
- [для компьютеров общего назначения] универсальностью (способностью реализовывать универсальный алгоритм);

Ну вот опять Вы неправы. Откуда Вы всю эту ерунду берёте про бесконечные потоки? Если с теорией вычислимости я ещё могу Вас извинить, предполагая тот факт, что Вам просто плохой учебник в руки попался или преподаватель молодой-неопытный, то здесь... Где, в каких книгах написано про бесконечные потоки данных, кто и когда про это говорил? Декстра об этом писал? Вирт писал? Кнут писал? Фон Нейман? Или Вы это сами сейчас сочинили?

И что за бред про "недетерминированность исходными данными"? Винда, конечно, иной раз недетерминированно работает, но это исключительно по причине корявых микрософтовских ручонок, а не потому, что так изначально было задумано Человек, допустим, да, недетерминирован, но вот он-то в процессе топтания клавы как раз и вводит исходные данные. А получив от человека данные, компутер делает с ними ровно то, что предписано программой, абсолютно детерминированным образом. Если какая-то недетерминированность в системе компутер/хуманс и наблюдается, то она вся сосредоточена во втором компоненте

[longstreet]

(Оффтоп)

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

P. P. S. Помню, в студенческие годы был у нас один товарисч, который конструктивных рассуждений вообще не признавал. Если ему показывали доказательство, в котором объект с нужными свойствами явно строился, он начинал психовать и кричал: ерунда, это не настоящая математика, не верю я в ваши построения, покажите мне, как утверждение о несуществовании объекта приводит к противоречию!

Брат Гротендика?

[_hum_]

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

Ну вот опять Вы неправы. Откуда Вы всю эту ерунду берёте про бесконечные потоки?

Вот знаете, что меня удивляет, что вы даже не можете допустить, что чего-то не знаете. А ведь computer science настолько быстро развивается, что успеть за всем уследить вряд ли можно. Да и вы, насколько я понимаю, больше имеете дело с чистой теорией, чем с прикладными аспектами.
Потоки данных являются одним из базовых понятий в программировании. А Юникс, насколько я знаю, так и вообще их в свою основу положила.

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

И что за бред про "недетерминированность исходными данными"?

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

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

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

А Юникс, насколько я знаю, так и вообще их в свою основу положила.

Что она в основу положила? Бесконечные потоки, "состоящие из цифр разложения неконструктивного иррационального числа"?

[_hum_]

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

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

А Юникс, насколько я знаю, так и вообще их в свою основу положила.

Что она в основу положила? Бесконечные потоки, "состоящие из цифр разложения неконструктивного иррационального числа"?

PETER VAN ROY, SEIF HARIDI Concepts, Techniques, and Models of Computer Programming, part 4.3 Streams. писал(а):

The most useful technique for concurrent programming in the declarative concurrent model is using streams to communicate between threads. A stream is a potentially unbounded list of messages [...]

Stream programming is a quite general approach that can be applied in many domains. It is the concept underlying Unix pipes.

[Tod Leben]

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

В принципе такой эмулятор можно назвать ОС

Долго не мог понять а потом "пробило", - да! Сама МТ и есть ОС. Любая ОС походу виртуальная машина, и МТ в том числе. У меня их три(эмулятора). Современные компьютеры представляют собой работу виртуальной машины, в виртуальной машине виртуальной машины... А МТ сама давно уже концепция "вырубленная в камне" этих машин. И камни у них виртуальные

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

PS Я понимаю, что к машине Тьюринга plug and play, видимо, не имеют отношения, равно как и большинство других опций современных ОС

повторю цитату:

Tod Leben в сообщении #609750 писал(а):

расширение возможностей машины

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

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

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

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

[_hum_]

Tod Leben, насколько я понимаю, вопрос изначальный был не в том, какие специфические свойства имеет ОС с точки зрения приложений, а в том, что ее с теоретических позиций отличает от других программ (посмотрите изначально откуда вопрос возник).

[Xaositect]

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

Ну вот опять Вы неправы. Откуда Вы всю эту ерунду берёте про бесконечные потоки? Если с теорией вычислимости я ещё могу Вас извинить, предполагая тот факт, что Вам просто плохой учебник в руки попался или преподаватель молодой-неопытный, то здесь... Где, в каких книгах написано про бесконечные потоки данных, кто и когда про это говорил? Декстра об этом писал? Вирт писал? Кнут писал? Фон Нейман? Или Вы это сами сейчас сочинили?

Профессор Снэйп, потоки и коданные это известный концепт в функциональном программировании. Скажем, Уодлер и Coquand (не знаю транскрипции общепринятой с французского) писали об этом.

-- Вс авг 26, 2012 14:49:35 --

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

Совсем простое рассуждение! И как его теперь "без времени" оформить?

Да очень просто. Множества $A$ и $B$ рекурсивно перечислимы, значит, они являются проекциями рекурсивных, т.е. $x\in A\equiv \exists z R_A(x, z)$ и аналогично для $B$. Если есть оракул для объединения $U(x)\equiv x\in A\cup B$, то $x\in A\equiv U(x)\pmb{\&}R_A(x, \mu z(R_A(x, z)\vee R_B(x, z)))$ --- задается тотальной рекрсивной функцией (здесь $\pmb{\&}$ --- "ленивая" конъюнкция, равна 0, если первый аргумент равен 0, а второй расходится).
Таким образом, $A$ (и аналогично $B$) рекурсивны относительно $U$, а значит, $A\oplus B$ тоже.

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