2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

 
 
 
 Re: Алгоритм vs компьютерная программа
Сообщение10.07.2014, 17:29 
Компютерные программы - это алгоритмы с заданными источниками данных. Дайте машине Тьюринга счётчик секунд по фиксированному адресу и она тоже будет иметь время.

tenmin в сообщении #886060 писал(а):
Но может тогда есть компьютерная программа, которая решает проблему останова?


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

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

 
 
 
 Re: Алгоритм vs компьютерная программа
Сообщение10.07.2014, 21:52 
Что такое "источник данных", "счётчик секунд по фиксированному адресу"?
Teletranslator в сообщении #886245 писал(а):
Дайте программе источик данных о наличиях остановов в работе всех МТ

Что значит "источик данных о наличиях остановов в работе всех МТ" и что значит "дайте"?
Teletranslator в сообщении #886245 писал(а):
Вас не смущает то, что МТ оперирует фиксированными исходными данными?

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

 
 
 
 Re: Алгоритм vs компьютерная программа
Сообщение10.07.2014, 23:03 
Отличие программ в лющем случае от МТ в том, что они имеют ичтосник данных в дополнение к тем, которые в них заложены.

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

 
 
 
 Re: Алгоритм vs компьютерная программа
Сообщение11.07.2014, 10:32 
Аватара пользователя
tenmin
tenmin в сообщении #886060 писал(а):
Все знают, что нет алгоритма, который бы решал проблему останова.

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

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

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

tenmin в сообщении #886060 писал(а):
Получается, что есть компьютерные программы, которым не соответствует никакой алгоритм.

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

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

 
 
 
 Re: Алгоритм vs компьютерная программа
Сообщение28.08.2014, 19:25 
Достаточно засунуть весь компьютер целиком в МТ, и всё прояснится.

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

 
 
 
 Re: Алгоритм vs компьютерная программа
Сообщение28.08.2014, 19:38 
Аватара пользователя
tenmin в сообщении #886060 писал(а):
Я правильно понимаю, что, например, процедуру, которая возвращает текущее время, нельзя никакой машиной Тьюринга представить?
Что такое «текущее время» и как его можно возвратить?
tenmin в сообщении #886060 писал(а):
Получается, что есть компьютерные программы, которым не соответствует никакой алгоритм.
Все знают, что нет алгоритма, который бы решал проблему останова. Но может тогда есть компьютерная программа, которая решает проблему останова?
Дайте определения в т.ч. «компьютерной программе» и «алгоритм».
Мне известные определения этих фраз предполагают полную непересекаемость, как, например, понятия «человек» и «мысль».
_hum_ в сообщении #901338 писал(а):
как-то пытался поднять тут схожий вопрос:
обычные программы (дал на вход данные, получил на выходе результат или бесконечное зависание) - суть алгоритмы
а вот как быть с операционными системами. ведь это получается подобие "зависнувшего, но при этом перерабатывающего и выдающего на выход частичные результаты, алгоритма". то есть, под прямой формализм алгоритма вроде не подпадает.

(gramar nazi)

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

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

 
 
 
 Re: Алгоритм vs компьютерная программа
Сообщение28.08.2014, 19:50 
Pavia в сообщении #886497 писал(а):
Другими словами это запись алгоритма в программном коде.
А если это программа на декларативном языке?

 
 
 
 Re: Алгоритм vs компьютерная программа
Сообщение28.08.2014, 19:54 
Аватара пользователя
tenmin в сообщении #886060 писал(а):
Я правильно понимаю, что, например, процедуру, которая возвращает текущее время, нельзя никакой машиной Тьюринга представить?

Можно представить машиной Тьюринга с оракулом сообщающим текущее время.
tenmin в сообщении #886060 писал(а):
Все знают, что нет алгоритма, который бы решал проблему останова. Но может тогда есть компьютерная программа, которая решает проблему останова?

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

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

 
 
 
 Re: Алгоритм vs компьютерная программа
Сообщение28.08.2014, 19:54 
Mysterious Light в сообщении #901392 писал(а):
Есть ещё т.н. генераторы, которые формализуются итеративной функцией $X\to A\times X$, где $X$ — пространство скрытых состояний. Например, генератор псевдослучайных чисел. Это обобщается до понятия копрограмм.


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

Mysterious Light в сообщении #901392 писал(а):
Кстати, нормальная работа ОС предполагает терминальность.

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

 
 
 
 Re: Алгоритм vs компьютерная программа
Сообщение28.08.2014, 20:23 
Аватара пользователя
_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 писал(а):
Кстати, нормальная работа ОС предполагает терминальность.

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

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

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

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

 
 
 
 Re: Алгоритм vs компьютерная программа
Сообщение29.08.2014, 09:01 
Аватара пользователя
_hum_ в сообщении #901537 писал(а):
кхм...странный аргумент. по этой логике, и алгоритма поиска максимального среди 10^(10^10000000000000) чисел числа тоже не существует, потому как ни один комп за реальное время не сможет так долго поработать, чтобы его вычислить и не попасть под сбой питания или поломку.

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

(Оффтоп)

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

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

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

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

 
 
 [ Сообщений: 33 ]  На страницу 1, 2, 3  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group