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

[tenmin]

Я правильно понимаю, что, например, процедуру, которая возвращает текущее время, нельзя никакой машиной Тьюринга представить? Еще есть I/O, рандом. Хотя НМТ эквивалентна МТ, т.е. рандом отпадает.
Получается, что есть компьютерные программы, которым не соответствует никакой алгоритм.
Все знают, что нет алгоритма, который бы решал проблему останова. Но может тогда есть компьютерная программа, которая решает проблему останова?

[Teletranslator]

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

tenmin в сообщении #886060 писал(а):

Но может тогда есть компьютерная программа, которая решает проблему останова?

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

Вас не смущает то, что МТ оперирует фиксированными исходными данными?

[tenmin]

Что такое "источник данных", "счётчик секунд по фиксированному адресу"?

Teletranslator в сообщении #886245 писал(а):

Дайте программе источик данных о наличиях остановов в работе всех МТ

Что значит "источик данных о наличиях остановов в работе всех МТ" и что значит "дайте"?

Teletranslator в сообщении #886245 писал(а):

Вас не смущает то, что МТ оперирует фиксированными исходными данными?

Почему меня должно это смущать?

[Teletranslator]

Отличие программ в лющем случае от МТ в том, что они имеют ичтосник данных в дополнение к тем, которые в них заложены.

Программы - это алгоритмы.

[Pavia]

tenmin

tenmin в сообщении #886060 писал(а):

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

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

tenmin в сообщении #886060 писал(а):

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

Представить можно. Делаете счётчик который увеличивается за фиксированное число команд это и будет время.
Или можно ещё проще представить, что некто,нечто пишет на ленте время. А машина копирует это время в нужное место ленты.

tenmin в сообщении #886060 писал(а):

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

По ГОСТ ГОСТ 19781—90 программа это - "Данные, предназначенные для управления конкретными компонентами системы обработки информации в целях реализации определенного алгоритма". Другими словами это запись алгоритма в программном коде.

[_hum_]

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

[arseniiv]

Достаточно засунуть весь компьютер целиком в МТ, и всё прояснится.

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

[Mysterious Light]

tenmin в сообщении #886060 писал(а):

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

Что такое «текущее время» и как его можно возвратить?

tenmin в сообщении #886060 писал(а):

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

Дайте определения в т.ч. «компьютерной программе» и «алгоритм».
Мне известные определения этих фраз предполагают полную непересекаемость, как, например, понятия «человек» и «мысль».

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

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

(gramar nazi)

дефис лишний, пунктуация странная

Есть ещё т.н. генераторы, которые формализуются итеративной функцией $X\to A\times X$, где $X$ — пространство скрытых состояний. Например, генератор псевдослучайных чисел. Это обобщается до понятия копрограмм.
Кстати, нормальная работа ОС предполагает терминальность.

[Pphantom]

Pavia в сообщении #886497 писал(а):

Другими словами это запись алгоритма в программном коде.

А если это программа на декларативном языке?

[whitefox]

tenmin в сообщении #886060 писал(а):

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

Можно представить машиной Тьюринга с оракулом сообщающим текущее время.

tenmin в сообщении #886060 писал(а):

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

МТ с оракулом отвечающим на соответствующий вопрос.

О теории относительной вычислимости можно, например, почитать здесь, глава 7

[_hum_]

Mysterious Light в сообщении #901392 писал(а):

Есть ещё т.н. генераторы, которые формализуются итеративной функцией $X\to A\times X$, где $X$ — пространство скрытых состояний. Например, генератор псевдослучайных чисел. Это обобщается до понятия копрограмм.

Можно какую-нибудь ссылку на ликбез по теме?

Mysterious Light в сообщении #901392 писал(а):

Кстати, нормальная работа ОС предполагает терминальность.

С чего вы взяли?

[Mysterious Light]

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

Mysterious Light в сообщении #901392 писал(а):

Есть ещё т.н. генераторы, которые формализуются итеративной функцией $X\to A\times X$, где $X$ — пространство скрытых состояний. Например, генератор псевдослучайных чисел. Это обобщается до понятия копрограмм.

Можно какую-нибудь ссылку на ликбез по теме?

Хорошими ссылками не располагаю. Мне вот недавно посоветовали B. Jacobs, J. Rutten "A Tutorial on (Co)Algebras and (Co)Induction", но можно просто обратить внимание на то обстоятельство, что во многих современных языках программирования вводятся операторы yield (напр, C# и Python), а в некоторых (Haskell etc) это встроено просто за счёт встроенной ленивости.
На хабре несколько месяцев назад был ажиотаж, связанный с генераторами на JS.

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

Mysterious Light в сообщении #901392 писал(а):

Кстати, нормальная работа ОС предполагает терминальность.

С чего вы взяли?

Потому что вечно работающих компьютеров ещё не изобрели, а значит система обязана либо завершиться нормально, либо неким ненормальным образом (например, из-за отключение притания), что не берётся во внимание как плохая практика :)

[_hum_]

Ааа, наверное операционные системы можно подогнать под формализм продолжений монотонных вычислимых отображений на бесконечные последовательности, как определяется у Шеня в его работах по теории алгоритмической сложности...(кому интересно: http://bookfi.org/book/1514827)

Mysterious Light в сообщении #901413 писал(а):

Потому что вечно работающих компьютеров ещё не изобрели, а значит система обязана либо завершиться нормально, либо неким ненормальным образом (например, из-за отключение притания), что не берётся во внимание как плохая практика :)

кхм...странный аргумент. по этой логике, и алгоритма поиска максимального среди 10^(10^10000000000000) чисел числа тоже не существует, потому как ни один комп за реальное время не сможет так долго поработать, чтобы его вычислить и не попасть под сбой питания или поломку.

[Mysterious Light]

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

кхм...странный аргумент. по этой логике, и алгоритма поиска максимального среди 10^(10^10000000000000) чисел числа тоже не существует, потому как ни один комп за реальное время не сможет так долго поработать, чтобы его вычислить и не попасть под сбой питания или поломку.

По моему мнению, алгоритм существует, а вот соответствующая программа — нет.

(Оффтоп)

Не могу сослаться на конкретную литературу, но я уже многократно встречался с такой точкой зрения, что нужно различать формальную модель и реальность, в которой модель может быть применима, а может и не быть. К этому же относятся те утверждения, что задачи «выигрывают ли белые в шахматах» и расшифровка симметричных шифров (в последнем не уверен) в теории являются разрешимыми (и даже за O(1)), а на практике — нет.

[Alexu007]

Есть такой алгоритм: бесконечный цикл. Все программы, интерактивно работающие с человеком (и ОС в том числе), на этом алгоритме построены: 1. Проверяем, не было ли событий мыши. 2. Проверяем, не было ли событий клавиатуры. 3. Goto 1.

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

Не понимаю, о чем тут можно спорить?