Программирование только с помощью for

[_hum_]

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

Ваши разворачивания процесса "сверху вниз" и "итеративно" как раз и означают, что время $t$ , о котором говорил Профессор Снэйп там есть

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

И если уж на то пошло, давайте по-честному - дайте математическое определение понятия времени $t$, о котором вы все говорите. Вот тогда и будем дальше вести речь.

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

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

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

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

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

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

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

Каверзный вопрос. Хотел сначала сказать "нет", потом "да" ... м-да. Думаю хоть какой-то вывод должен быть у этой программы, пусть не ввод, но вывод - обязательно. Тогда пожалуй - да, наверно может.

Тут, конечно, всё зависит от того, что понимать под словами "операционная система".

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

-- Чт авг 23, 2012 11:01:26 --

А насчёт вывода... Ну стоит человек, смотрит на ленту, пока машина работает. Чем не вывод?

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

-- Чт авг 23, 2012 11:06:09 --

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

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

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

_hum_ я ничего объяснять не буду и спорить с ним не буду, ибо бесполезно. Но если кто-нибудь из других участников темы спросит меня, почему хум не прав, я ему с удовольствием объясню.

[Esp_]

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

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

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

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

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

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

Вы говорите не корректно: операционная система - это программа, она имеет конечный текст, а значит задается машиной тьюринга.

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

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

Вы говорите не корректно: операционная система - это программа, она имеет конечный текст, а значит задается машиной тьюринга.

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

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

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

[_hum_]

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

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

_hum_ я ничего объяснять не буду и спорить с ним не буду, ибо бесполезно. Но если кто-нибудь из других участников темы спросит меня, почему хум не прав, я ему с удовольствием объясню.

Ого.
Я был о вас лучшего мнения. Повесить ярлык "альта" и заткнуть рот безо всяких четких аргументов - это очень достойно специалиста

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

-- Чт авг 23, 2012 14:16:20 --

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)."

[Munin]

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

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

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

-- 23.08.2012 15:51:58 --

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

[_hum_]

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

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

Не совсем.
Если интерактивная система работает только конечное время, то ее работу (с токи зрения computability theory) спокойно можно подвести под обычную машину Тьюринга. Для этого достаточно в исходные данные этой машины заложить все данные, полученные интерактивной системой от пользователя в процессе их ограниченного во времени общения (Аналог - все, что вы делали при работе с Word до его выключения, все эти действия можно запомнить и отдать другой "неинтерактивной" программе, которая, эмулируя работу Word с известными данными от вас, за конечное время в точности воспроизведет результат вашего общения с Word. Но обратите внимание, такое возможно только из-за того, что есть условие ограниченности работы с Word. Как только вы его опустите, то есть, начнете считать, что Word никогда не выключается, ничего подобного сделать уже не удастся).

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

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

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

Готова, не готова - кто её спрашивать будет?

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

Первого и последнего этапов достаточно для интерактивности или интерактивность должна в любой момент проявляться?

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

В любом случае всё, что нужно, давно описано и формализовано.

[Tod Leben]

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

А насчёт вывода... Ну стоит человек, смотрит на ленту, пока машина работает. Чем не вывод?

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

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

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

Вот так вот кинет кого-нибудь не правильно на очередную порцию бит, приедут, отобьют ему оперативную память,
поломают внешние носители, и будет он отрабатывать аж до самого резета. Контроль приоритета. В данном случае процессор сам "выступает" в качестве операционной системы, да плюс внутренняя логика, внутренний контроль, исключения и всё такое.
И кому нужен процессор без I/O? Цена такому процу как камушку на пляже. Хотя некоторые контроллеры так и стОят.

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

Как-то мы далеко ушли от темы! Обсуждение понятия "операционная система" не имеет ничего общего с исходным вопросом. Давайте новую тему заведём!

-- Чт авг 23, 2012 19:10:58 --

(Оффтоп)

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

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

Кэш отобьют, на прерывание по таймеру поставят... :-)

-- Чт авг 23, 2012 19:24:03 --

Завёл тему. Предлагаю обсуждение операционной системы перенести туда.

[Munin]

Ответил в новой теме, _hum_ и Профессор Снэйп, ищите мой ответ там.

[_hum_]

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

Э нет. Данные, полученные от пользователя, сами могут зависеть от того, что интерактивная система выдала раньше. Рассмотрите, например, компьютерную игру, "стрелялку" или "сапёра". С этой точки зрения, пользователь для машины чёрный ящик.

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

Можно. Но смысла в этом будет немного. Примерно столько же, сколько в киноплёнке, на которой заранее записан финал фильма. Это же будет уже другая программа, не Word.

Я же специально оговаривал, что речь идет о вопросе формализации интерактивной системы в рамках computability theory, которая, согласно вики, "deals primarily with the question of the extent to which a problem is solvable on a computer" [см. расположение этой теории в генеалогическом дереве общей теории вычислений тут: wiki/Theory_of_computation]. С ее точки зрения неважно, как интересно вам было играть, и какие вы способности проявили. Главное, что если это продолжалось конечное время, то найдется такая машина Тьюринга, которая в точности воспроизведет результат работы интерактивной программы-игры (например, все те же визуальные изображения, которые вам довелось увидеть во время игры). Другими словами, машина Тьюринга обладает той же вычислительной способностью, что и вы вдвоем с интерактивной системой при условии ограниченности работы во времени (способна решить любую задачу, которую может решить интерактивная система с вашим участием). А вот если снять требование ограниченности работы интерактивной системы по времени, то уже так сделать не удастся. И встает вопрос: с помощью чего же тогда в computability theory формализовывать подобную систему, чтобы можно было аналогично исследовать ее вычислительные способности (например, какие задачи она решает, а какие для нее неразрешимы; какие системы равносильны с точки зрения вычислительной способности и т.п.).
Что-то про варианты решения написано тут:wiki/Interactive_computation.


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