Требование конечности исходных данных для машины Тьюринга

[epros]

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

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

Ну вот мы и добрались до излучения эквивалентности функций… Да будет Вам известно, что функции $f$ и $g$ эквивалентны, если $\forall x,y ~ f(x)=y \leftrightarrow g(x)=y$

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

Рассмотрим машину Тьюринга
$\Bar{\mathbb{A}} = \{\,'|',\,'e',\,'p',\,'r',\,'o',\,'s',\,'\sqcup '\}$
$S = \{s_0,s_1,s_2\}$, $ s_0$ - начальное, $s_2$ - конечное.
Таблица переходов:
//----------------------------------------------------
$('|', s_0) \rightarrow ('|', s_0, R)$
$('e', s_0) \rightarrow ('\sqcup ', s_0, R)$
$('p', s_0) \rightarrow ('\sqcup ', s_0, R)$
$('r', s_0) \rightarrow ('\sqcup ', s_0, R)$
$('o', s_0) \rightarrow ('\sqcup ', s_0, R)$
$('s', s_0) \rightarrow ('\sqcup ', s_0, R)$
$('\sqcup ', s_0) \rightarrow ('\sqcup ', s_1, L)$
//----------------------------------------------------
$('|', s_1) \rightarrow ('|', s_2, N)$
$('e', s_1) \rightarrow ('\sqcup ', s_0, R)$
$('p', s_1) \rightarrow ('\sqcup ', s_0, R)$
$('r', s_1) \rightarrow ('\sqcup ', s_0, R)$
$('o', s_1) \rightarrow ('\sqcup ', s_0, R)$
$('s', s_1) \rightarrow ('\sqcup ', s_0, R)$
$('\sqcup ', s_1) \rightarrow ('\sqcup ', s_1, L)$
//----------------------------------------------------
Допустим, я собираюсь помещать на ленту натуральные числа, закодированные в виде строк "$|||...|epros$" (состоящих из $n$ палочек и оканчивающихся строкой "$epros$"). Могу ли я считать считать, что данная машина Тьюринга может вычислять значения функции $f_{id}(n) = n$? Если да, то как это согласуется с тем, что, по-вашему, в аргумент функции должны включаться все данные, влияющие на результат вычисления МТ, а строка "$epros$" (несмотря на то, что не содержит никакой информации о натуральном числе) влияет на результат вычисления, и значит, должна всегда с необходимостью присутствовать в аргументе вычислимой функции?

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

[Munin]

epros в сообщении #616782 писал(а):

:shock: Ну вот мы и добрались до излучения эквивалентности функций… Да будет Вам известно, что функции $f$ и $g$ эквивалентны, если $\forall x,y ~ f(x)=y \leftrightarrow g(x)=y$

:shock: Я всю жизнь, с трёхлетнего возраста, думал, что это означает, что функции $f$ и $g$ равны.

[epros]

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

epros в сообщении #616782 писал(а):

Ну вот мы и добрались до излучения эквивалентности функций… Да будет Вам известно, что функции $f$ и $g$ эквивалентны, если $\forall x,y ~ f(x)=y \leftrightarrow g(x)=y$

Я всю жизнь, с трёхлетнего возраста, думал, что это означает, что функции $f$ и $g$ равны.

Ну в общем, наверное, это одно и то же.

[url=http://ru.wikipedia.org/wiki/Отношение_эквивалентности]Отношение эквивалентности[/url]

[_hum_]

(Оффтоп)

epros в сообщении #616782 писал(а):

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

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

Ну вот мы и добрались до излучения эквивалентности функций… Да будет Вам известно, что функции $f$ и $g$ эквивалентны, если $\forall x,y ~ f(x)=y \leftrightarrow g(x)=y$

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

epros в сообщении #616566 писал(а):

«вычислимая функция — это класс эквивалентности МТ»

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

epros в сообщении #616782 писал(а):

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

Едет обратно для того, чтобы

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

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

epros в сообщении #616782 писал(а):

Разумеется, она делает кучу лишних вещей, помимо подсчёта чёрточек.

Какое это отношение имеют к вопросу?

epros в сообщении #616782 писал(а):

Например, результатом может оказаться серия из нескольких строк чёрточек, разделённых пробелами. Как Вы собираетесь интерпретировать такие результаты, непонятно.

см. выше цитату о том, что считается результатом.

epros в сообщении #616782 писал(а):

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

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

И вообще, я задал вам конкретный вопрос, а вместо того, чтобы услышать "можно считать/нельзя считать, что данная МТ вычисляет $f_{id}$ " опять начались какие-то отговорки "как будете интерпретировать" и прочее, что лишний раз наводит на мысль о степени владения вами данным предметом.

[epros]

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

При чем тут функции? Речь об эквивалентности машин Тьюринга.

Этот детский сад уже конкретно напрягает… Вы знаете, что такое эквивалентность? Что кружка может быть эквивалентна миске в смысле объёмов, например? Или что 1/3 может быть эквивалентно 5/15, хотя строки разные?

Вот и две машины Тьюринга могут быть эквивалентны в смысле функций (отображений строк в строки), которые они реализуют.

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

Едет обратно для того, чтобы
_hum_ в сообщении #614674 писал(а):
2) в качестве результата берется конечная строка, над которой находится головка автомата после остановки.

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

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

Какое это отношение имеют к вопросу?

А какое отношение этот вопрос имеет к функции $f=n$? В качестве какого числа будет интерпретироваться строка типа «|| ||| | »?

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

см. выше цитату о том, что считается результатом

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

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

И вообще, я задал вам конкретный вопрос

А я Вам конкретно отвечаю, что ничего общего у Вашей МТ с функцией $f=n$ я не вижу.

И вообще, я Вам конкретно заявляю, что Вы уже 5 страниц пишете несусветную чушь. Я Вам пытался несколько раз объяснить как правильно, но, судя про всему, это бесполезно — в виду владения Вами логикой на уровне детского сада. Препираться с Вами у меня нет охоты. Если хотите слушать — я готов подсказать, а если нет, если Вы только пытаетесь меня своими дикими воззрениями кормить, тогда я лучше оставлю Вас наедине с Вашими воззрениями.

[_hum_]

epros

(Оффтоп)

epros в сообщении #616833 писал(а):

А я Вам конкретно отвечаю, что ничего общего у Вашей МТ с функцией $f=n$ я не вижу.

Вопросов больше не имею.
И разрешите на этом прекратить с вами дискуссию, оставшись при своих "диких воззрениях".

[Munin]

epros в сообщении #616796 писал(а):

Ну в общем, наверное, это одно и то же.

[url=http://ru.wikipedia.org/wiki/Отношение_эквивалентности]Отношение эквивалентности[/url]

Я всю жизнь, с трёхлетнего возраста, думал, что равенство - это эквивалентность, но эквивалентность - не равенство.

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

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

...равенство - это эквивалентность, но эквивалентность - не равенство.

Эквивалентность - не всегда равенство

[Munin]

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

Эквивалентность - не всегда равенство

Конкретная эквивалентность - не всегда равенство. Понятие эквивалентности не совпадает с понятием равенства.

[epros]

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

Понятие эквивалентности не совпадает с понятием равенства.

Угу. Эквивалентность МТ в смысле равенства реализуемых ими функций $String \to String$ не совпадает с понятием равенства МТ.

[Munin]

Не паясничайте. Вы говорили об эквивалентности функций.

[epros]

(Оффтоп)

По-моему, теме пора в пургаторий. Вон уже и Munin начал пургу нести. Да, я говорил про эквивалентность функций, и что? Чем Вам равенство функций — не эквивалентность?

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

[Munin]

epros в сообщении #616957 писал(а):

Да, я говорил про эквивалентность функций, и что? Чем Вам равенство функций — не эквивалентность?

Равенство функций - это, конечно, эквивалентность. Но определять эквивалентность, как это сделали вы, непозволительно.

-- 10.09.2012 13:35:01 --

epros в сообщении #616957 писал(а):

По-моему, теме пора в пургаторий... наверное, говорить больше не о чем.

Я в этой теме редкий случайный гость, на меня не стоит ориентироваться.