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

[epros]

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

Вот я и предлагаю новый формат представления исходных данный для схемы МТ, а именно для всякой конечной строки p, образовать строку <p,s>. Она, конечно, получится бесконечной. Но вы ведь разрешили вводить в машину и бесконечные строки.

Все проблемы, как всегда, зарыты в деталях определений. Каким именно образом Вы собираетесь определять строку s? Если Вы рассматриваете только программы с конечными аргументами и кодами, то никаких проблем. Но если Вы собираетесь рассматривать все возможные начальные состояния ленты МТ, то Вам их переписать на ленту (в виде бесконечной строки s) не удастся.

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

[_hum_]

:( Неужели я так плохо объясняю...
Итак, есть "школьная" схема МТ (определение смотрите в сообщении #614674"]). На основе этой схемы строится вся "школьная" теория вычислимости, в частности вводится
Опр 1. Функция называется вычислимой, если существует схема МТ, позволяющая по аргументам получать значения функции.
И в этой же теории устанавливается следующий результат.
Пусть
$f(p) =$
$1$, если $p$ - программа "железной" машины Тьюринга, которая ни при каких (конечных) исходных данных не приводит к зацикливанию работы машины;
$0$, иначе.

Утв 1. Функция $f $ невычислима.
Доказательство следует из известной неразрешимости проблемы определения незацикливаемости машины Тьюринга.

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

Где вам что не понравилось? Только, пожалуйста, указывайте конкретно место в моем рассуждении, к которому относится возражение.

[epros]

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

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

Как же мне ещё объяснять, чтобы до Вас дошёл смысл этого утверждения? Попытки «указать конкретное место в Вашем рассуждении» не сработали... Давайте я попробую так: Я сейчас изложу Вам вариант формализации понятия «вычислимая функция», в котором нет никаких требований к конечности записанного на ленту МТ, а Вы мне объясните, почему «множество функций, относящихся к вычислимым, изменится» сравнительно со «школьной» формализацией.

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

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

3) если автомат не останавливается, считается, что результата нет!

Что-нибудь изменилось из-за того, что мы разрешили стартовать с полностью чем-то заполненной ленты? Абсолютно ничего.

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

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

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

Вот мы стартуем с чем угодно заполненной ленты, а «результатами» всё равно оказываются конечные строки.

Теперь давайте подумаем, что имеет смысл считать «аргументом» вычислимой функции. Смотрим сюда:

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

1) на ленту перед началом работы подается произвольная конечная строка;

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

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

[_hum_]

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

[epros]

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

Ладно. Видимо у нас принципиально разное понимание вычислимости по Тьюрингу, и понять друг друга не дано.

Похоже, что у Вас просто никакого понимания нет.
Если хотите, разберите Ваш пример в рамках описанной мной выше формализации, т.е.:
- где там "аргумент"
- и где там "значение".

И убедитесть, что:
1) Разрешение забивать ленту бесконечной последовательностью не отменяет того факта, что вычислимая функция отображает конечную строку в конечную строку.
2) Описанная Вами функция не решает

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

задачу определения по программе любой рекурсивной функции, является эта функция общерекурсивной или нет

[Lukin]

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

[epros]

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

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

Он же сказал что делать:

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

3) если автомат не останавливается, считается, что результата нет!

Это - единственное существенное условие во всём этом "школьном" определении вычислимости. Ибо оно говорит о том, что вычислимость нужно понимать в стандартном смысле. А вот как только мы начинаем различать какие-то "решения" для тех МТ, которые не останавливаются (например, не останавливается, но заполняет ленту числами Фиббоначчи, или - не останавливается, но заполняет ленту цифрами десятичного представления числа $\pi$), так мы приходим к нестандартному пониманию вычислимости. Но сначала, конечно, нужно конкретно определить ЧЕМ они различаются.

[_hum_]

В качестве подведения итога.

Опр 1. Схема МТ ("школьная"):
0) машина Тьюринга
- конечный расширенный (включающий пробел) алфавит;
- конечное множество состояний с выделенными начальным и конечным
- конечная таблица переходов (программа);
1) договоренность о том, что исходные данные алгоритма подаются в виде конечной строки, начиная с первой ячейки ленты;
2) договоренность о том, что конечным результатом алгоритма является конечная строка, над которой находится головка машины в момент остановки.
3) договоренность, что во всех остальных случаях (машина не останавливается/останавливается не над строкой) результат отсутствует (алгоритм неприменим к исходному данному).

Опр 2. Функция называется вычислимой, если существует схема МТ, позволяющая по аргументам получать значения функции.

Выбросим, следуя epros, из условия 1) "школьной" схемы МТ требование конечности строк. Эту модифицированную схему назовем epros-схемой МТ.

Опр 3. Функция называется epros-вычислимой, если существует epros-схема МТ, позволяющая по аргументам получать значения функции.

Договоримся о каком-либо общем способе кодирования программ машин Тьюринга в виде конечных строк из некоторого конечного алфавита и рассмотрим функцию

\begin{align*} f(p) = \begin{cases} 1, \,\text{ если }p\text{ программа машины Тьюринга},\text{которая ни при каких (конечных) исходных данных } \\\quad\text{не приводит к зацикливанию работы машины},\\\phantom{0}\\ 0, \,\text{ иначе.} \end{cases} \end{align*}


Утв 1.
1) функция $f$ является невычислимой;
2) функция $f$ является epros-вычислимой.

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

Обозначим эту epros-схему МТ через epros-схема МТ*.
Далее, обозначим через $s$ строку, образованную упорядоченными в лексикографическом порядке программами (через символ разделителя) всех незацикливающихся программ машин Тьюринга. И рассмотрим функцию:

\begin{align*} g(p) = \begin{cases} 1, \,\text{ если epros-схема МТ* с поданной на вход строкой }<p,s>\text{ печатает } 1, \\ 0, \,\text{ если epros-схема МТ* с поданной на вход строкой }<p,s>\text{ печатает } 0, \end{cases} \end{align*}

где $<p,s>$ - строка, образованная объединением (через символ разделителя) строк $p$ и $s$.

Очевидно, функция $g(p)$ - epros-вычислима. С другой стороны, легко видеть, что $g(p) = f(p)$, а значит, $f(p)$ также epros-вычислима. Ч.т.д.

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

[epros]

Ёлы-палы, _hum_, я же просил Вас: Разберите Ваш пример в рамках описанной мной формализации,

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

- где там "аргумент"
- и где там "значение".

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

К тому же, вот это что такое:

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

Договоримся о каком-либо общем способе кодирования программ машин Тьюринга в виде конечных строк из некоторого конечного алфавита и рассмотрим функцию

Что это ещё за "программы машины Тьюринга", что ИМЕННО Вы понимаете под этим? В описанной мной формализации термин "программа" не используется. Есть сама МТ - конечный автомат с заданной логикой, который и реализует "вычислимую функцию", и есть запись на ленте, которая определяет только "аргумент" и "значение" функции.

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

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

Очевидно, функция $g(p)$ - epros-вычислима.

Нет никакой функции $g(p)$, ибо Вы её - не определили! А знаете почему? Потому что строка $p$ не подходит под понятие "аргумента". См. сюда:

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

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

.

[_hum_]

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

Разберите Ваш пример в рамках описанной мной формализации

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

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

Занимаетесь подтасовкой понятий (я никак иначе не могу это назвать), предлагая вместо этого свои непонятно откуда взятые замены понятиям аргумента и значения вычислимой функции.

с комментариями наподобие - вот у вас здесь такое-то понятие определяется так-то, а на самом деле оно определяется совсем по-другому, в подтверждение см. то-то и то-то.

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

Что это ещё за "программы машины Тьюринга", что ИМЕННО Вы понимаете под этим?

Вы невнимательно читаете:

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

- конечная таблица переходов (программа);

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

Нет никакой функции $g(p)$, ибо Вы её - не определили!

Извините, но это какая-то бессмыслица. Определить функцию - значит поставить в соответствие каждому аргументу $p$ определенное значение $g(p)$. Я вам явно указал, как определяется это соответствие (грубо говоря, даете мне $p$ я заворачиваю его в строку $s $ отдаю МТ*, получаю от нее результат и отдаю вам. Итого - дали мне $p$, получили от меня 0 или 1. Вот вам и заданная функция.)

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

А знаете почему? Потому что строка $p$ не подходит под понятие "аргумента".

Эту фразу и следующее за ней я вообще не понимаю.

[epros]

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

попрошу вас в первую очередь указывать на конкретные просчеты в моей формализации

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

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

Вы невнимательно читаете:

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

- конечная таблица переходов (программа);

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

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

Я вам явно указал, как определяется это соответствие

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

Вот такую же примерно чушь пытаетесь сейчас сконструировать и Вы. А знаете в чем ошибка? Да в том, что записанный на левую часть ленты номер - не есть аргумент вычислимой функции.

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

Эту фразу и следующее за ней я вообще не понимаю.

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

[_hum_]

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

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

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

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

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

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

А знаете в чем ошибка? Да в том, что записанный на левую часть ленты номер - не есть аргумент вычислимой функции.

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

Нельзя просто взять, и объявить произвольно выбранный Вами кусок ленты "аргументом".

Честно говоря, после таких высказываний у меня появляются сомнения в вашей компетентности в области теории вычислимости. Поскольку в противном случае вы бы не проявили непонимания того, что объекты, с коими работают алгоритмы (и их формализации), определены с точностью до эффективного перекодирования. А потому для доказательства вычислимости той или иной функции не обязательно, чтобы данные вносились в первоначальном неизменном виде на ленту. Никто не запрещает вам их прежде подвергнуть перекодированию (например, вместо самого натурального числа в десятичной записи помещать на ленту его двоичное представление). Грубо говоря, если у вас есть машина, способная вычислять функцию для аргументов, представленных в какой-то определенной кодировке, то это автоматически доказывает вычислимость функции. Сравните, для того, чтобы доказать, что функция $q(n) = [n/2]$ вычислима, достаточно доказать, что вычислима функция, которая всякой двоичной строке $b_kb_{k-1}\dots b_1b_0$, $b_i \in \{0,1\}$, ставит в соответствие строку $b_kb_{k-1}\dots b_1$, ибо это в точности соответствует делению на 2 для числа в двоичной кодировке.
С учетом этого, ваши претензии по поводу того, что на ленту я помещаю не саму программу $p$, а строку $<p,s>$ несостоятельны, так как $<p,s>$ можно рассматривать как кодировку для этой самой $p$.
(Попутно отмечу, что, по-хорошему, конечно же, нужно было бы уточнять, что такое эффективная кодировка для бесконечных объектов (бесконечных строк), но поскольку вы сами так свободно разрешили появиться в МТ этим бесконечным объектам, то, думаю, это излишне).

[epros]

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

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

Спасибо, конечно, что удостоили меня чести назвать «в честь меня» нечто. Но, право, не стоило тратить время на попытки доказать несоответствие одного Вашего определения другому Вашему же.

Напоминаю, что я здесь Вам изложил, как понятие вычислимости определяется через МТ без всяких упоминаний о заполнении ленты пробелами. Вы утверждали, что оно не соответствует стандартному. Вот и доказывайте ЭТО. А не хотите — так нечего было затевать эти пляски.

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

вы бы не проявили непонимания того, что объекты, с коими работают алгоритмы (и их формализации), определены с точностью до эффективного перекодирования

Вот давайте не будем про бузину в огороде. Причём тут перекодирование (возможность которого никто здесь не отрицал)? Просто перечитайте ещё раз (медленно) мой пример про то, как с помощью МТ дать ответы на все вопросы, которые возникнут в Вашей жизни, и поймёте, какую шизу Вы тут пытаетесь определить вместо вычислимой функции. Нет, _hum_, это не некомпетентность. Это полное отсутствие логики. На гране невменяемости.

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

[_hum_]

epros

(Оффтоп)

epros, честно говоря, у меня нет никакой мотивации разбираться в ваших рассуждениях, поскольку
a) они слишком неформальны (вы не дали ни одного четкого определения);
b) я сомневаюсь, что это не ваша собственная авторская версия, а подтверждений обратного в качестве ссылок вы не даете.
Потому, действительно, давайте договоримся, либо вы четко излагаете свою позицию (по аналогии с моей в формате - меньше слов, больше четких определений, утверждений, доказательств), либо на этом останавливаемся.

[epros]

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

a) они слишком неформальны (вы не дали ни одного четкого определения);

Чего Вам там нечётко? Там всего два существенных термина: «значение» и «аргумент» вычислимой функции. Сказано вполне однозначно. В конце концов, если что-то неясно, то можно спросить.

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

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

А какая Вам вообще разница? Ваша-то авторская версия уж точно бредовая. Я сказал почему: Потому что нельзя за аргумент принимать произвольно выбранный кусок ленты, имея в виду, что в других её местах, где побывает головка, может быть что угодно - вплоть до ответов на все вопросы (и бесконечность строк тут ни при чём). Вот ЭТО Вам хотя бы понятно?