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

[Lukin]

_hum_

На мой взгляд, ситуация следующая.
Сначала Вы берете счетно-бесконечное множество всех строк $S_n (n \in N)$ являющихся схемами конечных МТ. Каждая такая строка $S_n$ конечна.
Затем доказываете, чистое существование в этом множестве подмножества $M$ конечных строк, являющихся теми МТ, которые всегда останавливаются, не предъявляя по понятным причинам алгоритма его построения.
Затем, доказываете, что полученное счетно-бесконечное множество $M$ упорядочивается в лексографическом порядке в $s$.
Затем подаете пару : $<S_n, s>$ на вход МТ* и приходите к выводу о разрешимости для каждого $S_n$ его принадлежности к $M$, т.е. по сути к алгоритмической (в новом смысле) вычислимости $M$.

Меня тут больше смущает не невычислимость в стандартном смысле $M$, а невычислимость в стандартном смысле самой МТ*, хотя и то и другое эквивалентно.
МТ* должна быть среди строк в бесконечном множестве $M$, но чтобы ее найти нужно уже иметь MT*, в стандартном смысле она невычислима.

Похоже на чистое существование саморазрешимого нестандартного алгоритма, который к тому же конечен. Проблема в том, что он нестандартный. Для нас это "вещь в себе". Занятно еще то, что их может быть много, фактически континуум.

[_hum_]

epros

(Оффтоп)

epros
Просьба. Не могли бы вы, в место отсылки к неизвестно где "написанному выше", создать отдельный пост, в котором все ваши мысли собраны в компактном и как можно более формальном виде?
Начиная с определений
- что такое, по-вашему, вычислимая функция (по Тьюрингу)
- что такое, по-вашему, аргумент вычислимой функции
- что такое, по-вашему, значение вычислимой функции

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

Lukin в сообщении #615805 писал(а):

Меня тут больше смущает не невычислимость в стандартном смысле $M$, а невычислимость в стандартном смысле самой МТ*, хотя и то и другое эквивалентно.
МТ* должна быть среди строк в бесконечном множестве $M$, но чтобы ее найти нужно уже иметь MT*, в стандартном смысле она невычислима.

Вы просто, как мне кажется, не совсем корректно используете понятия. Что вы имеете в виду под фразой "невычислимость самой МТ*". Невычислимой может быть функция. МТ* же (в вашем контексте) - это программа (таблица переходов) работы железной машины Тьюринга. Если ее использовать в "школьной" схеме МТ (то есть подавать на вход только конечные строки), то с ее помощью можно будет задавать некоторую вычислимую функцию. Если же ее использовать в epros-схеме МТ, то она станет способна задавать функцию, которая не является вычислимой в обычном смысле. Это сходно с тем, что одну и ту же машину используют в одном случае напрямую, а в другом разрешают обращаться к оракулу.

[epros]

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

Не могли бы вы, в место отсылки к неизвестно где "написанному выше", создать отдельный пост, в котором все ваши мысли собраны в компактном и как можно более формальном виде?

http://dxdy.ru/post615277.html#p615277

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

- что такое, по-вашему, вычислимая функция (по Тьюрингу)

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

МТ с бесконечной лентой, в любых ячейках которой могут быть любые символы конечного алфавита

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

- что такое, по-вашему, значение вычислимой функции

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

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

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

- что такое, по-вашему, аргумент вычислимой функции

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

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

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

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

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

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

[Lukin]

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

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

Я имею в виду, что эта таблица переходов - программа МТ*, является конечной строкой – одной из множества всех конечных программ $S$.
Ее невычислимость в стандартном смысле означает, что не существует стандартного алгоритма, способного определить, является ли данная конечная таблица переходов той самой MT* или нет.
Задача "построения" множества $M$ или $s$ из множества всех $S$ эквивалентна задаче распознавания среди всех конечных программ $S$ тех, которые являются МТ*.

[epros]

(Оффтоп)

Lukin в сообщении #615879 писал(а):

не существует стандартного алгоритма, способного определить, является ли данная конечная таблица переходов той самой MT* или нет

Ещё один бредогенератор подключился.

[_hum_]

(Оффтоп)

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

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

- что такое, по-вашему, вычислимая функция (по Тьюрингу)

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

МТ с бесконечной лентой, в любых ячейках которой могут быть любые символы конечного алфавита

Значит, вы вычислимую функцию отождествляете с конкретной машиной Тьюринга? Тогда, по-вашему, какой машине Тьюринга соответствует функция $f_{id}(n) = n$ (опишите схематично, какой алфавит у нее будет и примерно по какой программе она должна работать)?

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

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

- что такое, по-вашему, значение вычислимой функции

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

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

Вы можете дать четкое определение, что именно на ленте после остановки машины считаете значением функции (описать алгоритм извлечения рзультата с ленты)?

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

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

- что такое, по-вашему, аргумент вычислимой функции

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

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

Итак, по-вашему, аргументом вычислимой функции, которой отвечает данная МТ, нужно считать только тот фрагмент исходной строки, изменение которого с необходимостью вызывает изменение конечного результата работы машины?
Если да, то тогда, исходя из вашего определения, у тождественно постоянной функции $f_1(n) = 1$ вообще нет аргументов.


Lukin, вы, действительно, в сторону куда-то уходите.

[epros]

(Оффтоп)

_hum_, отвечу чуть позже, выходные начинаются… А что Вы в офтоп всё это запихали? Это же, вроде, всё вопросы про существу Вашей темы.

[_hum_]

(Оффтоп)

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

А что Вы в офтоп всё это запихали? Это же, вроде, всё вопросы про существу Вашей темы.

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

[Lukin]

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

Lukin, вы, действительно, в сторону куда-то уходите.

_hum_, ладно epros - "старый" конструктивист, но Вас то что не устраивает ?
Вот Вы говорите МТ и МТ* - это одно и тоже, одна и та же конечная таблица переходов:

Цитата:

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

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

Вы утверждаете, что МТ и МТ* не эквивалентны, epros не согласен. Он считает, что конечность работы машины и конечность выходного состояния ленты означает, что вся бесконечная входная лента никогда не используется. Если МТ останавливается, значит она проработала лишь конечное число итераций и соответственно переработала лишь конечное число ячеек входной ленты. По моему, тут все ясно.

Вы же считаете, что существуют такие бесконечные входные данные, которые позволяют за конечное число шагов МТ*, используя лишь конечный участок ленты, решать задачи, которые неразрешимы за то же конечное число шагов МТ, использующей тот же конечный участок ленты.
Как такое возможно ?
Я сделал единственно возможный, по моим понятиям, вывод - Вы с epros по разному понимаете конечность. Для Вас существуют нестандартные натуральные числа, которые соответствуют нестандартным таблицам переходов - т.е. МТ*.
Я просто изобразил, почему Вы не сможете привести явно ни одного нестандартного натурального числа (иже МТ*) – epros сразу разъяснит Вам, что оно обычное натуральное число. Вы можете лишь доказать чистое существование таких чисел (соответственно, таблиц переходов МТ*).

[epros]

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

Значит, вы вычислимую функцию отождествляете с конкретной машиной Тьюринга? Тогда, по-вашему, какой машине Тьюринга соответствует функция $f_{id}(n) = n$ (опишите схематично, какой алфавит у нее будет и примерно по какой программе она должна работать)?

Легко. Вариантов масса. Раз уж у нас вычислимая функция отображает строки в строки, то для начала нужно выбрать способ кодировки чисел строками. Самый древний способ, насколько я знаю, это представлять числа строками вертикальных чёрточек. Стало быть, берём алфавит из двух символов: пробела и чёрточки «|». Машина устроена простейшим образом: головка едет вправо до первого пробела, на котором и останавливается. Нетрудно убедиться, что и аргументом, и значением является строка из $n$ вертикальных чёрточек, заканчивающаяся пробелом.

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

Вы можете дать четкое определение, что именно на ленте после остановки машины считаете значением функции (описать алгоритм извлечения рзультата с ленты)?

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

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

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

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

Итак, по-вашему, аргументом вычислимой функции, которой отвечает данная МТ, нужно считать только тот фрагмент исходной строки, изменение которого с необходимостью вызывает изменение конечного результата работы машины?
Если да, то тогда, исходя из вашего определения, у тождественно постоянной функции $f_1(n) = 1$ вообще нет аргументов.

Угу, константу можно считать функцией без аргументов. Но вообще-то в моей процитированной выше фразе употреблено ключевое слово «можно». Это значит, что можно брать минимальную такую строку, а можно — и не самую минимальную. В последнем случае у функции будет такой аргумент, от которого значение не зависит: как Вы и хотели.

Главное, что нельзя считать за аргумент строку МЕНЬШЕ минимально допустимой: в этом заключается Ваша ошибка.

-- Сб сен 08, 2012 00:51:01 --

Lukin в сообщении #616016 писал(а):

Я сделал единственно возможный, по моим понятиям, вывод - Вы с epros по разному понимаете конечность. Для Вас существуют нестандартные натуральные числа, которые соответствуют нестандартным таблицам переходов - т.е. МТ*.

Это Вы через край хватили. Разумеется, нестандартная интерпретация количества шагов МТ до остановки влечёт нестандартную интерпретацию вычислимости. Однако _hum_-то просто-напросто в определении аргумента вычислимой функции ошибся.

[_hum_]

(Оффтоп)

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

Легко. Вариантов масса. Раз уж у нас вычислимая функция отображает строки в строки, то для начала нужно выбрать способ кодировки чисел строками. Самый древний способ, насколько я знаю, это представлять числа строками вертикальных чёрточек. Стало быть, берём алфавит из двух символов: пробела и чёрточки «|». Машина устроена простейшим образом: головка едет вправо до первого пробела, на котором и останавливается. Нетрудно убедиться, что и аргументом, и значением является строка из $n$ вертикальных чёрточек, заканчивающаяся пробелом.

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

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

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

- что такое, по-вашему, вычислимая функция (по Тьюрингу)

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

МТ с бесконечной лентой, в любых ячейках которой могут быть любые символы конечного алфавита

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

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

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

Опять бла-бла-бла, когда я просил у вас указания какого-нибудь конкретного алгоритма извлечения результата (чтобы потом на него опираться в рассуждениях, а не постоянно плавать в "сие не есть проблема").

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

Главное, что нельзя считать за аргумент строку МЕНЬШЕ минимально допустимой: в этом заключается Ваша ошибка.

Замечательно. Тогда рассмотрим машину Тьюринга, которая выполняет следующие действия: в строке, помещенной на ленту, просто удаляет все символы, отличные от символа '$ | $'.
Допустим, я помещаю на ленту натуральное число, закодированное в виде строки "$|||...|epros$" (состоящей из $n$ палочек и оканчивающейся строкой "$epros$"). Могу ли я считать считать, что данная машина Тьюринга может вычислять значения функции $f_{id}(n) = n$? Что считать аргументом?

[epros]

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

Сначала говорите, что вычислимая функция - это, по-вашему определению, в точности какая-то машина Тьюринга

Угу, в точности такая МТ, которая едет вправо до первого пробела и там останавливается.

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

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

Угу. А ещё числа можно записывать не чёрточками, а десятичными цифрами, а ещё можно — двоичными. А ещё можно записать вместо $f=n$, например, $f=n \times 1$ или $f=(n+n)/2$.

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

Поэтому еще раз возвращаемся к исходной унификации понятий: дайте точное непротиворечивое определение понятию вычислимой функции.

Включайте мозги и кончайте нести чушь. Я сказал, что МТ реализует вычислимую функцию — посредством отображения строки в строку. Я даже попытался на примере научить Вас тому, как с помощью МТ можно смоделировать функцию $\mathbb{N} \to \mathbb{N}$. Учить Вас базовым понятиям об эквивалентности и т.п. у меня уже нет охоты.

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

Опять бла-бла-бла, когда я просил у вас указания какого-нибудь конкретного алгоритма извлечения результата (чтобы потом на него опираться в рассуждениях, а не постоянно плавать в "сие не есть проблема").

Хватит нести пургу. Вникайте, там написано как извлечь результат.

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

Замечательно. Тогда рассмотрим машину Тьюринга, которая выполняет следующие действия: в строке, помещенной на ленту, просто удаляет все символы, отличные от символа '$ | $'.
Допустим, я помещаю на ленту натуральное число, закодированное в виде строки "$|||...|epros$" (состоящей из $n$ палочек и оканчивающейся строкой "$epros$"). Могу ли я считать считать, что данная машина Тьюринга может вычислять значения функции $f_{id}(n) = n$? Что считать аргументом?

А ключевое условие — сказать, когда МТ останавливается — где?

[_hum_]

(Оффтоп)

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

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

Сначала говорите, что вычислимая функция - это, по-вашему определению, в точности какая-то машина Тьюринга

Угу, в точности такая МТ, которая едет вправо до первого пробела и там останавливается.

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

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

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

Замечательно. Тогда рассмотрим машину Тьюринга, которая выполняет следующие действия: в строке, помещенной на ленту, просто удаляет все символы, отличные от символа '$ | $'.
Допустим, я помещаю на ленту натуральное число, закодированное в виде строки "$|||...|epros$" (состоящей из $n$ палочек и оканчивающейся строкой "$epros$"). Могу ли я считать считать, что данная машина Тьюринга может вычислять значения функции $f_{id}(n) = n$? Что считать аргументом?

А ключевое условие — сказать, когда МТ останавливается — где?

Останавливается тогда, когда удалит все символы, отличные от палочки.

[epros]

(Оффтоп)

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

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

Честно говоря, я долго думал, нужно ли отвечать на этот флуд. Но, имея привычку исходить из презумпции вменяемости собеседника, всё же отвечу. Раз Вас не устроили слова про то, что МТ «реализует вычислимую функцию», может быть Вас устроит формулировка: «вычислимая функция — это класс эквивалентности МТ»?

-- Вс сен 09, 2012 14:09:50 --

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

Останавливается тогда, когда удалит все символы, отличные от палочки.

Нет, презумпция вменяемости не работает. Каким образом, интересно, МТ узнает, что удалила ВСЕ символы, отличные от черточки?

[_hum_]

(Оффтоп)

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

может быть Вас устроит формулировка: «вычислимая функция — это класс эквивалентности МТ»?

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

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

Каким образом, интересно, МТ узнает, что удалила ВСЕ символы, отличные от черточки?

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

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

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

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

Угу [...]. Но вообще-то в моей процитированной выше фразе употреблено ключевое слово «можно». Это значит, что можно брать минимальную такую строку, а можно — и не самую минимальную. В последнем случае у функции будет такой аргумент, от которого значение не зависит: как Вы и хотели.

Главное, что нельзя считать за аргумент строку МЕНЬШЕ минимально допустимой: в этом заключается Ваша ошибка.

Рассмотрим машину Тьюринга
$\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$" (несмотря на то, что не содержит никакой информации о натуральном числе) влияет на результат вычисления, и значит, должна всегда с необходимостью присутствовать в аргументе вычислимой функции?