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

[proger]

Я думаю, так. МТ при каждом вводе из-вне начинает вычисления заново. Каждый ввод -- это новый цикл. Во время работы алгоритма не предусмотрено, что кто-то посторонний может писать на ленту. Значит, получается, что реализовать нельзя?

[Sonic86]

Содержательно: определение МТ устроено так, что, условно говоря, "никто ничего не пишет на ленту, кроме головки МТ". Для того, чтобы вопрос был осмысленный, Вам придется определить сначала все новые понятия так, чтобы они "расширяли" старое понятие и потом в рамках них уже ставить вопрос. Тем более, что формулировки явно пишутся из предметной области, не особо думая, а что там такого написали. Например:

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

Каждый ввод -- это новый цикл.

Это такая очень непонятная фраза, если вдуматься.

Формально, что такое "событийный цикл", что такое вообще "цикл", что такое "кто-то посторонний может писать на ленту"? Перед ответом посмотрите предварительно на определение МТ.

Т.е. пока вопрос не поставлен.

[proger]

Sonic86 в сообщении #874860 писал(а):

"никто ничего не пишет на ленту, кроме головки МТ

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

Sonic86 в сообщении #874860 писал(а):

Это такая очень непонятная фраза, если вдуматься

Что тут непонятного. Событийный цикл -- это новый текст, который подается на вход алгоритма.

[Sonic86]

Т.е. формулировать вопрос Вы не хотите, да? Ну тогда ждите телепатов из отпуска.

(жалкая попытка что-то объяснить)

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

Что тут непонятного. Событийный цикл -- это новый текст, который подается на вход алгоритма.

Ну вот смотрите. Ваш вопрос:

Цитата:

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

Ваше определение:

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

Событийный цикл -- это новый текст, который подается на вход алгоритма.

Соотв-но, вопрос имеет вид:
"реализуем ли на машине Тьюринга новый текст, который подается на вход алгоритма?"
И что это значит?

[proger]

Sonic86
Я не могу понять, что вам не ясно. МТ принимает на вход текст программы, выполняет алгоритм, останавливается. Машина реализующая событийный цикл: запускается, ждет на вход текст программы, выполняет ее, выводит на выход результат, ждет дальнейших инструкций. Причем, во время выполнения алгоритма она может получить новое задание(принять текст) и поставить его в очередь (в простом случае).

[Sonic86]

(Оффтоп)

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

Я не могу понять, что вам не ясно.

Вы определение МТ видели?

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

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

Ага, хорошо (правда, термин "Машина реализующая событийный цикл" придется считать бесструктурным, но пофиг). У МТ есть лента и функция переходов $\delta$. Не сильно понятно, что такое "программа", будем считать, что программа - это новое слово на чистой ленте и новая функция $\delta$. Время $\to$ номер шага. "Ждет" - это ничто (нет в МТ такого свойства).
Тогда эту ситуацию МТ напрямую вроде бы не описывает. Свойство "Ждет", например, прямо не описывается. Если пренебречь ожиданием и моментами выставления новых заданий, то данная ситуация может быть просто описано как последовательное вычисление разных программ, можно на разных МТ, можно на одной и той же (МТ делает 1-е вычисление, потом очищает ленту, переходит в новое множество состояний, делает 2-е вычисление и т.п.). Но так длина очереди, средний объем очереди, число заданий и т.п. теряется из рассмотрения.

Однако, можно извратиться и все это всунуть в МТ. Только букв будет много. Надо просто проэмулировать весь описываемый процесс (МТ и все вычисления, ввод задания, постановку его в очередь) на некоей другой абстрактной МТ $M_A$. Т.е., например, ленту $M_A$ разбить на $N$ частей (ячейки $b_k$ $j$-й части - это последовательность $a_{Nk+j}$ из $M_A$), в 1-й части писать ленту исходной МТ, во 2-й части - писать функцию $\delta$ из МТ, вычисление которой будет эмулироваться, закодированную каким-либо образом, в 3-й части - моменты времени, в которые вводят новые ленты и новые функции переходов, в 4-й - вводимые программы и т.п. Соотв-но, $M_A$ будет эмулировать на 1-й части вычисление с помощью функций переходов во 2-й части. Как только вычисление закончено - ленту стираем, программу стираем - если в 4-й части есть вводимые функции переходов и содержания ленты, то самые крайние функции переходов и ленты переписываем на 2-ю часть, а из 4-й - стираем. Если в 4-й части ничего нет - $M_A$ будет бегать туда-сюда - это и будет называться "МТ ждет". В 5-й части можно "инкрементно" считать время и сравнивать его после каждого шага вычисления исходной МТ с моментами времени в части 3. Если совпадают, то МТ ВНЕЗАПНО начинает из памяти (в смысле из состояний $M_A$) писать в 4-ю часть ленты $M_A$ новую ленту МТ и новую функцию переходов для нее - это назовем "постановкой новой программы в очередь". Можно вынести это также на 6-ю часть ленты и таким образом "постановкой новой программы в очередь" станет просто переписывание программы из 6-й части ленты в 4-ю часть. Как вариант.
Как-то так. Ясно, что $M_A$ в обычном смысле ничего не вычисляет, а по умолчанию зациклена.
Удовлетворяет?

Соотв-но, чтобы это описать, лучше сделать новую модель.
Делать мне ее лень - это несложно, потому Вы это сами должны делать, кроме того, Вы явно сидите в предметной области, которая мне неизвестна, из которую Вам надо (а может быть и не надо?) извлекать модель. Модель ведь нужна попроще, напридумывать моделей можно дофига

[proger]

Sonic86 в сообщении #874884 писал(а):

Свойство "Ждет", например, прямо не описывается

Оно никак не описывается.

Sonic86 в сообщении #874884 писал(а):

может быть просто описано как последовательное вычисление разных программ

Не может, потому что следующее вычисление может зависить от предыдущих.

Sonic86 в сообщении #874884 писал(а):

можно на разных МТ

У вас фантазия бурная. Разные МТ это не одна МТ.

Sonic86 в сообщении #874884 писал(а):

МТ делает 1-е вычисление, потом очищает ленту, переходит в новое множество состояний, делает 2-е вычисление и т.п.

Она не может перейти в другое [правильно будет -- вычисление], это не заложено в модели. То самое ожидание.

Sonic86 в сообщении #874884 писал(а):

Однако, можно извратиться и все это всунуть в МТ. Только букв будет много. Надо просто проэмулировать весь описываемый процесс (МТ и все вычисления, ввод задания, постановку его в очередь) на некоей другой абстрактной МТ $M_A$

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

[Sonic86]

(малосодержательные ответы)

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

Оно никак не описывается.

Это неверно, пример описания приведен ниже.

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

Она не может перейти в другое [правильно будет -- вычисление], это не заложено в модели. То самое ожидание.

Может. Я что хочу, то и закладываю в модель.

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

Все что вы описали в дальнейшем, это, во первых, не МТ

Выше описана именно МТ. Если Вам непонятно - Ваши проблемы.

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

Не может, потому что следующее вычисление может зависить от предыдущих.

В таком случае уточните описание. Сейчас из фразы

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

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

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

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

У вас фантазия бурная. Разные МТ это не одна МТ.

Я, к сожалению, когда писал, очень торопился, потому получился такой поток сознания, понять его можно только усилием. Там, например, под МТ, которая не $M_A$ понимается как раз машина, реализующая событийный цикл. Там, наверняка, еще куча ошибок и недомолвок.
Короче, суть там такая: процесс описан, потому по описанию может быть эмулирован на машине Тьюринга (на это нам намекает тезис Тьюринга). Т.е. все предметы и отношения нужно просто выразить на языке МТ и все. Выше - конкретная попытка выражения. Я не буду ее продолжать, ибо сильно лень и смысла не вижу - это Вам надо, а не мне. Модель здесь должна строиться от реальной задачи.

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

[Someone]

(Оффтоп)

proger, а Вы что, хотите Widows запустить на машине Тьюринга?

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

P.S. Физическое устройство, моделирующее машину Тьюринга — не машина Тьюринга, поскольку, в отличие от машины Тьюринга, является конечным устройством.

[proger]

Sonic86 в сообщении #875020 писал(а):

абстрактно

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

Sonic86 в сообщении #875020 писал(а):

на это нам намекает тезис Тьюринга

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

-- 13.06.2014, 20:40 --

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

Widows запустить на машине Тьюринга?

Не запустить, а выяснить, является ли абстракция реального компьютера (который мы можем оассматривать тоже как абстрактную машину) и МТ эквивалентными. С помощюю компьютера мы можем эмулировать МТ, а вот в обратном я не уверен.

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

Она с окружающим миром никак не взаимодействует

В этом и проблема. Этот окружающий мир может быть не обязательно реальным, он может быть абстрактным. И там его нет.

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

Вы должны и этот окружающий мир с временем и пространством описать в модели.

Тогда это будет не МТ. А я оспариваю претензию МТ на универсальность.

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

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

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

PS Я не считаю, что то, что Вы написали является офтопом, распакуйте.

[Joker_vD]

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

[proger]

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

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

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

[Someone]

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

С помощюю компьютера мы можем эмулировать МТ

И каким же образом Вы собираетесь "эмулировать" бесконечную ленту? МТ с конечной лентой — это не МТ, её вычислительные возможности гораздо скромнее.

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

А вот абстракция реальной машины как раз наоборот.

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

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

А я оспариваю претензию МТ на универсальность.

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

[Sonic86]

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

Цитата:

на это нам намекает тезис Тьюринга

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

Вы либо не в курсе, либо врете.
См. Мальцев Алгоритмы и рекурсивные функции.

[proger]

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

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

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

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

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

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

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

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

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

-- 13.06.2014, 23:04 --

Sonic86 в сообщении #875115 писал(а):

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

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

Цитата:

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