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

[epros]

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

Но никакой компьютер не сможет предугадать, какой второй ход сделает человек

Может Вы не читали то, что я отвечал binу в этой теме, поэтому повторю: Не надо путать предсказуемость с вычислимостью. Разумеется, если аргумент вычислимой функции неизвестен, то её значение — непредсказуемо. Но здесь обсуждалась вычислимость, а не предсказуемость! Мой первый коммент в этой теме был к заявлению _hum_ о моделируемости машиной Тьюринга (т.е. о вычислимости — вычислимость так определяется, понимаете?), а не о предсказуемости. И зачем Вы влезли со своими замечаниями про непредсказуемость, непонятно.

[Munin]

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

данная тема ИМХО очень показательна.

Только к догматизму в науке она ни малейшего отношения не имеет.

-- 04.09.2012 15:45:41 --

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

Может Вы не читали то, что я отвечал binу в этой теме

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

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

поэтому повторю: Не надо путать предсказуемость с вычислимостью.

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

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

Но здесь обсуждалась вычислимость, а не предсказуемость!

Вашим попыткам самочинно решать, что здесь решалось - незачот! Здесь обсуждались, напоминаю, ОС и их возможность быть описанными абстракцией МТ. А то, что лично вы всё умеете воспринимать только через призму вычислимости, это лично ваш заскок в мозгах, и не надо его проецировать на окружающих.

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

о моделируемости машиной Тьюринга (т.е. о вычислимости — вычислимость так определяется, понимаете?)

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

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

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

Я не "влез", я в этой теме был раньше вас, и с моего приятного разговора с Профессором Снэйпом она и началась. Может быть, не только моего. Но вас там точно не стояло. Если уж кто и "влез", то именно вы. И трамвайное хамство разводить тут тоже начали именно вы.

[_hum_]

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

Нет. Я думаю, они вообще к computability theory не относятся. А относятся к кибернетике. Как только вы начинаете впихивать их в прокрустово ложе computability theory, то естественно, они сводятся к чему-то уже известному, но при этом с них отстригается именно то существенное, что их отличало от неинтерактивных.

Так если не ограничиваться рамками формализма computability theory, то тогда непонятно, что подразумевается под "моделирование интерактивной программы посредством МТ ". И можно все что угодно предлагать, самое естественное из чего то, что уже предлагали epros и Профессор Снэйп:
рассматриваете работу МТ на ленте. В четные ячейки заносятся данные от пользователя, в нечетных хранятся промежуточные данные (в том числе те, что выводятся для пользователя).
Вот и все. И нет никаких оснований возражать, что это противоречит формализму МТ, ибо формализм МТ находится в рамках computability theory, а вы от нее отказались.

[bin]

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

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

данная тема ИМХО очень показательна.

Только к догматизму в науке она ни малейшего отношения не имеет.

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

(Оффтоп)

В 1980-х мне пришлось в МВТУ им Баумана участвовать в курсах повышения квалификации преподов кафедры высшей математики - компьютерной грамоте их учить. Вот там я насмотрелся на женщин предпенсионного возраста: всю жизнь матан читала в объеме Фихтенгольца с Демидовичем, но задача найти на клаве пробел такой не по силам: не интересно ей это и не нужно. По 20 раз объяснять приходилось, а на 21-й опять та же проблема...

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

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

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

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

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

Есть ещё, правда, квантовые компьютеры, но я в них не разобрался, ибо там физика, а я её ни асилил

Кстати, хоть и считается, что PTIME и EXPTIME - достаточно приближенные к практике вещи, они обладают многими признаками сферических коней в вакууме. Вот, допустим, есть два алгоритма вычисления $f(x)$: один считает это значение за $x^{100}$ шагов, а другой - за $x^{\ln \ln x}$ шагов. Какой из алгоритмов с практической точки зрения лучше?

[epros]

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

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

Просто Вы не понимаете, чем отличается computability (которая здесь обсуждалась) от complexity.

(Munin)

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

-- Вт сен 04, 2012 17:18:59 --

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

Вот, допустим, есть два алгоритма вычисления $f(x)$: один считает это значение за $x^{100}$ шагов, а другой - за $x^{\ln \ln x}$ шагов. Какой из алгоритмов с практической точки зрения лучше?

Интересный вопрос. Я полагаю, что при $x < e^{e^{100}}$ второй алгоритм с практической точки зрения лучше.

[bin]

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

Какой из алгоритмов с практической точки зрения лучше?

Сейчас в смежной теме как раз пример подобной практической проблемы:

Cubic в сообщении #614224 писал(а):

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

Далее:

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

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

И в нашей теме речь не об абсолютных величинах тактовой частоты (1 Гц или 1 ГГц), а об относительных: во сколько раз тактовая частота МТ больше/меньше тактовой частоты Профессора с фломастером. Причем и тут не нужно точной цифры - достаточно "во много раз меньше/больше" или "примерно одинакова".

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

машина Тьюринга является достаточно адекватной моделью вычислительного устройства

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

Если объяснять предельно популярно "на пальцах", то это можно сделать, например, так. Возьмем две МТ с одинаковой частотой и будем суммировать на них пары чисел методом цифра за цифрой, как на бумажке. Пусть за один такт суммируется один разряд с учетом переноса. Какая из двух МТ остановится первой? Видимо, та, где было меньше разрядов в данных на входе. Если мы захотим перемножать на параллельных МТ матрицы, то необходимо устройство синхронизации этих МТ, это будет радикальным изменением модели МТ: есть принципиальная разница между подключением черных ящиков к каждой МТ (в этом случае МТ останутся изолированными друг от друга) и подключением одного черного ящика ко всем МТ сразу - получим принципиально иную модель вычислительного кластера на МТ. На такой черный ящик ляжет нетривиальная задача разрешения конфликтных ситуаций, и чтобы решить эту задачу алгоритмически, придется заглянуть в этот ящик...

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

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

речь не об абсолютных величинах тактовой частоты (1 Гц или 1 ГГц), а об относительных: во сколько раз тактовая частота МТ больше/меньше тактовой частоты Профессора с фломастером.

Ну, МТ всегда может, сделав шаг, остановиться и подождать, пока профессор фломастер помусолит

[Munin]

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

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

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

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

Ну, МТ всегда может, сделав шаг, остановиться и подождать, пока профессор фломастер помусолит

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

[_hum_]

Munin

(Оффтоп)

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

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

Извините, Munin, но вы, по-моему, перегибаете палку. Как раз вся эта проблематика начиналась с вопроса об описании ОС в рамках computability theory:

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

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

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

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

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

[Munin]

(Оффтоп)

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

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

Выслушивать неинтересные мне замечания мне неинтересно.

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

[bin]

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

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

речь не об абсолютных величинах тактовой частоты (1 Гц или 1 ГГц), а об относительных: во сколько раз тактовая частота МТ больше/меньше тактовой частоты Профессора с фломастером.

Ну, МТ всегда может, сделав шаг, остановиться и подождать, пока профессор фломастер помусолит

Т.е. профессор после каждого шага МТ должен что-то записать на ленту (нпр., знак пробела, если нет новых данных) да еще и пуск нажать. А современной ОС никто ничего не должен: пришло прерывание хорошо - она его обработает, а не пришло, тоже хорошо - ОС продолжит работу. Почувствуйте разницу!

-- Вт сен 04, 2012 17:30:51 --

_hum_

(Оффтоп)

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

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

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

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

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

Т.е. профессор после каждого шага МТ должен что-то записать на ленту (нпр., знак пробела, если нет новых данных) да еще и пуск нажать. А современной ОС никто ничего не должен: пришло прерывание хорошо - она его обработает, а не пришло, тоже хорошо - ОС продолжит работу. Почувствуйте разницу!

Ну, принципиальной разницы-то нет! То, что профессор будет по полчаса мусолить фломастер и в лишь в $\varepsilon$ случаях что-то реально менять на ленте, никого не волнует

(Оффтоп)

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

Мне тоже трудно слушать epros: почти каждую реплику он начинает с "глупость", "вы ничего не понимаете", "профаны" и т.д.

Конструктивней будет просто игнорировать некоторых... клинических случаев

-- Вт сен 04, 2012 23:04:05 --

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

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

Эт смотря какую конструкцию мы зададим. Xaositect тут где-то давал интересную ссылку

[Munin]

(Оффтоп)

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

Эт смотря какую конструкцию мы зададим. Xaositect тут где-то давал интересную ссылку

И вы согласились, насколько я помню, что с обычной МТ она не совпадает, а является всё-таки каким-то другим понятием.

[bin]

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

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

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

И как быть, если к одной машине нужно подключить несколько "профессоров"? Они ведь подерутся (пример наша тема, но замолкаю )