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

[_hum_]

Mysterious Light, где все-таки из Вашего изложения видно, что формализация ОС вполне вкладывается в какую-либо известную математическую формализацию алгоритма (рекурсивные функции, алгорифмы Маркова, лямбда-исчисление, машины Тьюринга и т.п.)?

И да, как правильно заметил Joker_vD, не обязательно брать ОС (с ее обработкой "железа"), а достаточно взять любую интерактивную программу - тот же Блокнот (если считать, что вы никогда его не закрываете).

Joker_vD в сообщении #902901 писал(а):

и действительно, существуют денотационные семантики, которые последней программе сопоставляют не $\bot$, а что-то более интересное.

Так а как все-таки формализуются такие программы в теории алгоритмов?

[hazzo]

ОС не возможно формализовать одной единственной МТ, поскольку ОС - это множество МТ. Я бы даже сказал не множество МТ, а множество конечных автоматов, т.е. проще чем МТ. Каждая из этих автоматов, когда получает управление начинает свою работу и в нужный момент выдает свой результат. Среди этих машин есть те, что организуют работу других. Есть те, что работают резидентно, т.е. постоянно находятся в памяти и выполняют определенную работу. Например, следят за событиями и т.д.
Когда Вы включаете ваш компьютер, и ОС получает управление от, например BIOSа, то она начинает свою работу. На самом деле в этот момент какая-то или какие-то МТ (или КА) запускаются. Некоторые на время запускаются, делают определенную работу и завершаются;а другие остаются в памяти все время работы ОС. Резидентные МТ завершают свою работу по сигналу завершения ОС или ещё другим способом.
Любая программа - это описание одного или несколько алгоритмов на конкретном языке программирования. Каждый алгоритм - это, например, одна МТ. Но главное не забудьте о тезисе Тьюринга-Черча. Пока ещё никто не доказал его не состоятельность.

[cool_d]

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