реализуем ли на машине Тьюринга событийный цикл?

[Joker_vD]

proger в сообщении #875105 писал(а):

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

Еще раз: пользователь — это часть МТ. Он не может произвольно изменить.

В конце концов, это неновая идея из практики реализации чистых функциональных языков: можно представлять программу как функцию типа World -> (a, World).

[arseniiv]

proger в сообщении #875120 писал(а):

Докажите это.

Ёмкость оперативной памяти, регистров и кэша процессора и всего остального в компьютере конечна.

[proger]

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

Он не может произвольно изменить

Я об этом и говорю, о чем Вы спорите. И да, ФП модель столь же неполноценна, у них с МТ одна и та же проблема.

-- 13.06.2014, 23:31 --

arseniiv в сообщении #875145 писал(а):

Ёмкость оперативной памяти, регистров и кэша процессора и всего остального в компьютере конечна.

Но не число состояний.

[Someone]

proger в сообщении #875120 писал(а):

Someone в сообщении #875109 писал(а):

Вы собираетесь "эмулировать" бесконечную ленту

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

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

proger в сообщении #875120 писал(а):

Someone в сообщении #875109 писал(а):

У реального компьютера число состояний конечно.

Докажите это.

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

proger в сообщении #875120 писал(а):

Someone в сообщении #875109 писал(а):

Тогда Вы должны предъявить вычислительный процесс

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

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

proger в сообщении #875120 писал(а):

Достаточно заглянуть на быдлопедию

Цитата:

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

И что? Тезис Чёрча действительно нельзя ни доказать, ни опровергнуть. Все попытки формализовать понятие вычислимости до сих пор давали эквивалентные результаты, а доказать что-либо за пределами формализованного понятия вычислимости нельзя. Интуиционизм (одно из конструктивных направлений в математике) считает тезис Чёрча неверным. Однако пока никто не смог предъявить явным образом нечто, что все признали бы вычислимым, а запрограммировать это вычисление для машины Тьюринга было бы нельзя.

[proger]

Someone в сообщении #875148 писал(а):

либо в его работу вмешиваются внешние по отношению к нему "прерывания", и тогда это всё к тезису Чёрча никакого отношения не имеет.

Имеет то отношение, что эту абстракцию невозможно выполнить (вычислить) на МТ.

Someone в сообщении #875148 писал(а):

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

Вы не учитываете те же прерывания, а также то, что комп - это цикл, он может выполняться бесконечно, если мы не выдернем вилку. Только не надо рассказывать про износ материи и про конец света.

Someone в сообщении #875148 писал(а):

предъявить явным образом нечто,

Я предьявил.:) Я, кстати, слышал, что Карл Хьюитт считает модель МТ и LC неадекватной.

[arseniiv]

proger в сообщении #875147 писал(а):

И да, ФП модель столь же неполноценна, у них с МТ одна и та же проблема.

Это предмет вашей веры?

[proger]

arseniiv в сообщении #875159 писал(а):

Это предмет вашей веры?

Я на данный момент так считаю. Это мое мнение, возможно не окончательное. Но пока вижу так.

[arseniiv]

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

[proger]

arseniiv
Это невозможно хотя бы потому, что нет начала этой модели, нет той отправной точки с которой можно начинать строить модель. Мы столкнемся с противоречием.

arseniiv в сообщении #875170 писал(а):

большущей машиной Тьюринга

А какое значение имеет размер?

-- 14.06.2014, 00:27 --

arseniiv

(Оффтоп)

Кстати, мне это почему то напомнило сюжет "Беги Лола беги". Не смотрели случайно?

-- 14.06.2014, 00:30 --

arseniiv
Ну да, кстати, мы бы тогда сами оказались "всезнающими", и отменили проблему останова

PS И еще кстати, это объясняет, в некоторой степени, интуитивно, почему мат модели (никакие) практически не работают в трейдинге.

[Joker_vD]

proger в сообщении #875175 писал(а):

Это невозможно хотя бы потому, что нет начала этой модели, нет той отправной точки с которой можно начинать строить модель. Мы столкнемся с противоречием.

Отнюдь Берем КТП, и численно интегрируем, благо времени и места у нас полно: http://xkcd.com/505/

Опять же, краем глаза я читал, что (потенциально бесконечный) входной поток данных можно моделировать с помощью концепции коданных, и бесконечно работающие МТ получают вместо унылого $\bot$ какую-то осмысленную семантику. Увы, подробнее не расскажу, т.к. читал пару лет назад и мимоходом.

[Someone]

proger в сообщении #875154 писал(а):

Имеет то отношение, что эту абстракцию невозможно выполнить (вычислить) на МТ.

И фиг с ними, с внешними прерываниями. Они по определению не являются вычислимыми, поэтому к тезису Тьюринга отношения не имеют.

proger в сообщении #875154 писал(а):

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

Господи, какие пустяки Вас заботят. Машина Тьюринга вовсе не обязана останавливаться. И даже вилку у неё выдернуть нельзя ввиду полного отсутствия оной.

proger в сообщении #875154 писал(а):

Я предьявил

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

[proger]

Someone в сообщении #875192 писал(а):

Машина Тьюринга вовсе не обязана останавливаться

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

[Someone]

proger в сообщении #875207 писал(а):

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

Да ерунда. МТ печатает себе на ленте и печатает, а Вы читайте и читайте. Без конца. И "внешний мир" тут ни при чём. Для МТ лента и есть "внешний мир".

[Sonic86]

(помещаю это в оффтоп, ибо для ТСа это не главная его ошибка)

proger в сообщении #875120 писал(а):

Sonic86 писал(а):

Вы либо не в курсе, либо врете.

Достаточно заглянуть на быдлопедию

Цитата:

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

Вы спрыгнули. Читаем медленно еще раз Ваш текст:

proger в сообщении #875049 писал(а):

Тезис -- это всего лишь тезис. Это утверждение, которое ни на чем не основано, просто он так сказал.

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

proger в сообщении #875120 писал(а):

Вы видимо не поняли. МТ -- это статика. Фактически -- функция. Вы подаете на вход фиксированную строку. далее, вы получаете результат, в сам процесс между подачей строки и получением результата Вы вмешаться не можете. МТ не может прервать процесс вычисления, и там, фактически нет процесса.

Короче, вот суть Вашей проблемы в понимании.
Есть реальные процессы, а есть теории, матмодели. Вопрос о том, как именно поставить в соответствие реальному процессу матмодель, не такой простой. Адекватных матмоделей для одного и того же реального процесса может быть несколько и они могут быть неочевидными и сильно разными. Никаких сильных ограничений тут, наверное, нельзя высказать. А Вы думаете, что если Вы пытаетесь описать какой-то матмоделью реальные вычислительные устройства, то этому вычислительному устройству обязательно должна соответствовать машина Тьюринга. А это не так. Эту ошибку Вы прекрасно сформулировали в Вашей теме topic85395.html . Примеры Вам приводили я и Joker_vD:

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

Система "пользователь+интерактивная программа" прекрасно описываются одной МТ.

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

proger в сообщении #875154 писал(а):

эту абстракцию невозможно выполнить (вычислить) на МТ.

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

[Toucan]

proger заблокирован как клон.