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

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

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

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

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

[bin]

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

Народ тут никак с МТ без оракулов разобраться не может.

Да уж, народ тут никак с задачами реального времени разобраться не может!

[_hum_]

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

Это не расширение, а всё то же стандартное понятие вычислимости. Расширение — это когда оракулы добавляются.

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

Задать алгоритм по Тьюрингу, значит предоставить такую схему вычислений. В этом случае множество исходных данных алгоритма - это множество начальных строк для схемы, конечные данные алгоритма - конечные результаты работы по схеме, неприменимость алгоритма к некоторому исходному данному - безрезультатная работа по схеме (отсутствие остановки машины/невозможность извлечения конечного результата)
см. Н.К. Верещагин, А.Шень. Лекции по математической логике и теории алгоритмов. Ч. 3. Вычислимые функции. Раздел 9.2 Машина Тьюринга: определение.

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

Если же вы допускаете, что исходными данными для работы конечного автомата в схеме Тьюринга могут быть и бесконечные строки, то, по идее, все результаты надо передоказывать (как передоказывалось для вещественных чисел то, что было доказано для рациональных). И более того, придется выполнить расширение и остальных моделей вычисления. Например, для доказательства того же результата об эквивалентности вычислимости по Тьюрингу и через рекурсивные функции потребуется аналогично расширить понятие вычислимой функции таким образом, чтобы они стали способны принимать в качестве аргумента (подобно бесконечным строкам в МТ) бесконечные последовательности натуральных чисел.
И такое расширение, действительно, имеется, см. выдержку из статьи В. А. Успенского в сообщении #612963
И даже Профессор Снейп согласился, что это расширение "школьного" понятия (хотя и ничего принципиально нового, с его точки зрения, не несущее) (сообщение #614237).

Ну, а раз так, то, получается, того, чему учат в "школе" недостаточно, чтобы говорить
"любая программа, в том числе интерактивная (работающая с бесконечными потоками), с точки зрения вычислительности равносильна некоторой схеме вычисления по Тьюрингу".
Требуется дополнительно изучить теорию, связанную с расширенным понятием вычислимости (вычислимость в схеме МТ на $\omega$-последователльностях(?), $f_0$ - вычислимость функций и т.п.), чтобы потом с полным правом делать заявления наподобие
"любая программа, в том числе интерактивная (работающая с бесконечными потоками), с точки зрения вычислительности равносильна обощенной схеме вычисления по Тьюрингу".


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

[Munin]

(Оффтоп)

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

Я думал, Вас интересуют вычислимые на МТ функции не только с бесконечными входами, но и с бесконечными выходами...

Вспоминается обсуждение многоголовых драконов и их пищеварительных трактов...

-- 04.09.2012 15:57:18 --

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

Да ну я на самом деле адресовал эту задачу Мунину не потому, что думал, будто он реально её решит.

Точно. Не решу.

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

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

Точно. Не решу.

Если проникнитесь условием, это уже будет способствовать некоторому продвижению в понимании

Задача, кстати, довольно простая... как, наверное, какая-нибудь лаба по физике, которую доктор физматнаук типа меня за месяц не осилит

[epros]

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

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

Ёлы-палы, _hum_, попробую ещё раз: Отказ от этого условия ничего не изменит в понятии вычислимости.

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

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

Ничё передоказывать не надо! См. Ваше условие (3): Если не остановился, то "результата нет". Значит в случае, когда "результат есть", МТ обработала конечное подмножество данных на ленте. Какая разница, что там было на остальной части ленты? Оно не изменилось. Если хотите, можете считать, что "входными данными" является бесконечное подмножество данных ленты. Всё равно, реально результат вычислений будет зависеть только от конечного подмножества оных "входных данных".

[_hum_]

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

Ничё передоказывать не надо! См. Ваше условие (3): Если не остановился, то "результата нет". Значит в случае, когда "результат есть", МТ обработала конечное подмножество данных на ленте. Какая разница, что там было на остальной части ленты? Оно не изменилось. Если хотите, можете считать, что "входными данными" является бесконечное подмножество данных ленты. Всё равно, реально результат вычислений будет зависеть только от конечного подмножества оных "входных данных".

Понял вашу мысль, попробую высказать свои сомнения по ее поводу.
Итак, вы говорите, что можно называть вычислимым все то, что можно получать с помощью схемы МТ, в которой, в том числе, на вход машине разрешается подавать и бесконечные строки. Окей.
Тогда давайте рассмотрим пример.
Пусть $s$ - строка, образованная упорядоченными в лексическом порядке программами (разделенными спец. символом) всех общерекурсивных функций. Для всякой рекурсивной функции, описываемой программой $p$, через $<p,s>$ обозначим строку, получившуюся добавлением в начало строки $s$ программы $p$ (со спец. символом в качестве разделителя).
С учетом введенных обозначений рассмотрим теперь задачу определения по программе любой рекурсивной функции, является эта функция общерекурсивной или нет. Из вашего допущения возможности бесконечных по размеру исходных данных вытекает, что такая задача подпадает под алгоритмически разрешимую по Тьюрингу. Действительно, соответствующую схему МТ нетрудно указать:
исходные данные о произвольной программе $p$ подаются в виде строки $<p,s>$, а машина затем, постепенно перебирая содержимое строки s и сравнивая с $p$, либо останавливается и выводит $1$, если совпадение найдено, либо $0$, если совпадений не найдено вплоть до программы, размер которой оказался больше, чем у исходной.
Но ведь это, насколько я знаю, не так.

[Munin]

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

Если проникнитесь условием

Я уже. Но мой интерес к вопросу, который я задал, был мимолётным, ответ я получил, так что углубляться я как-то не увлечён, извините. Конечность и вычислимость - пусть тут epros резвится. И пусть он наконец оставит тему про ОС в покое, где затрагиваются совсем другие вопросы.

[epros]

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

исходные данные о произвольной программе $p$ подаются в виде строки $<p,s>$, а машина затем, постепенно перебирая содержимое строки s и сравнивая с $p$, либо останавливается и выводит $1$, если совпадение найдено, либо $0$, если совпадений не найдено вплоть до программы, размер которой оказался больше, чем у исходной.

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

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

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

если некто выложил на ленту список всех общерекурсивных функций, то можно посредством общерекурсивной функции проверить общерекурсивность любой функции? Что ж, это верно.

На самом деле это неверно. Просто список не даст возможности получить отрицательный ответ за конечное время.

Зато даст возможность перечислять множество программ, вычисляющих всюду определённую функцию. То есть снизит арифметическую сложность множества таких программ с $\Pi^0_2$ до $\Sigma^0_1$. А если хотим иметь разрешимость, надо над списком поколдовать и составить его не абы как, а, например, в порядке возрастания длин программ

[epros]

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

Просто список не даст возможности получить отрицательный ответ за конечное время.

Насколько я понял, _hum_ рассматривает в качестве "исходных" только программы с конечным кодом. Соответственно, отрицательный ответ будет получен как только доберёмся

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

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

-- Ср сен 05, 2012 11:46:53 --

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

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

Да, да, вроде же это он и имел в виду

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

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

Да, да, вроде же это он и имел в виду

По моему, он там просто про список написал.

[_hum_]

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

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

epros, опять какое-то недопонимание. Изначально я спрашивал, можно ли в схеме МТ разрешать бесконечные исходные данные. Вы сказали "без проблем", см. сообщение #614708. По "школьному" определению проблема разрешима (по Тьюрингу), если она разрешается с помощью какой-нибудь из конкретно построенных схем МТ. Я ее вам привел - берем машину и на вход подаем данные в указанном формате $<p,s>$. Все! (Вопрос, как происходит это "подавание на вход", схемы Тьюринга никак не касается).

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

По моему, он там просто про список написал.

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

[epros]

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

берем машину и на вход подаем данные в указанном формате $<p,s>$. Все! (Вопрос, как происходит это "подавание на вход", схемы Тьюринга никак не касается).

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

[_hum_]

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

А если мы договоримся считать общерекурсивными функциями только программы с конечными аргументами и кодами (как обычно и считается)

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

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

то список всех общерекурсивных функций не удастся впихнуть ни в код, ни в аргумент ни одной из таких программ.

Вы наверное все-таки не уловили, в чем состоял мой замысел. А дело в следующем - в схеме Тьюринга есть произвол в выборе формата исходных данных: например, без разницы, как подавать натуральное число - хоть в двоичной, хоть в десятичной системах счисления, а хоть вообще в формате <само число, дата вашего рождения>. Главное, чтобы можно было из формата, с которым работает МТ, легко "доставать" само число. Вот я и предлагаю новый формат представления исходных данный для схемы МТ, а именно для всякой конечной строки p, образовать строку <p,s>. Она, конечно, получится бесконечной. Но вы ведь разрешили вводить в машину и бесконечные строки. (Подчеркиваю, я конечные исходные данные представляю в формате бесконечной строки). Ну и все, получается, что такая схема МТ способна разрешать проблему, которую не способна разрешать схема МТ в "школьном" определении (не допускающая бесконечных размеров исходных строк).