Сomputability theory на языке рекурсивных функций (?)

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

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

Вот и я спрашиваю, можно ли принципиально всю Computability theory перевести на "функциональный язык" (который избавлен от понятий машин и машинных тактов).

А я Вам и отвечаю, абсолютно по теме. Да, можно. Но не нужно, поскольку за деревьями не станет видно леса. Ровно то же самое, что переводить программы с языков высокого уровня на ассемблер. В связи с излишней элементарностью операций перестаёт быть виден смысл кода. И понять по тексту такой программы, всё ли в ней корректно, станет неимоверно сложной задачей.

Всё равно что если меня бабушка на остановке спросит, как пройти на почту, а я ей вместо указания общего направления начну объяснять, в какой последовательности ей при походе на почту следует переставлять ноги и делать вдохи-выдохи. А ведь она именно этим и будет заниматься, если пойдёт: передвигать ногами и дышать!

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

Итак, в приводимом мною ранее примере с объединением перечислимых множеств использовалось следующее определение:
множество называется перечислимым, если существует такая рекурсивная функция, которая на этом множестве всюду принимает значение 1, а в остальных точках она либо не определена, либо принимает значение 0.

Ок, замечательно. Что Вы теперь ходите доказывать: перечислимость объединения или перечислимость пересечения?

С пересечением Вы уже вроде как разобрались. А с объединением, увы, всё сложнее: придётся сначала доказывать, что перечислимое множество - это не только область определения, но и множество значений. Можно, конечно, попробовать поизвращаться, но... это будет примерно как разгружать весь день вагоны, чтобы получить пачку денег, чтобы потом голыми руками изловить в лесу оленя и жарить мясо на костре, а заработанными купюрами этот костёр разжигать. Если уж хочется поработать, не лучше ли будет на заработанные деньги купить готовый шашлык?

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

Стандартное доказательство выглядит так: при данном $x$ по очереди выполняем шаги вычисления первой и второй функций, ждём: как только вычислилось хотя бы одно значение, кричим "ура" и полагаем значение новой, определяемой специально для объединения функции равным $1$. А если ничего так никогда и не вычислится, то значит элемент, на котором мы пытаемся параллельно вычислять два значения, в объединение не попал и ничего вычислять на нём не надо! Всё Ок. Но вам не нравится делать шаги вычислений и ждать, Вы вообще считаете, что вычислений никаких в природе не бывает. Значит что?..

А ничё!!! Не получится тут нихрена, как не извращайся! По крайней мере, у меня фантазии не хватает! Да и желание заниматься маразмом как нахлынуло, так и пропало. Время, между прочим, 4 часа ночи!!!

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

[_hum_]

Замечательно. Итак, на вопрос

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

можно ли всю эту теорию [Computability theory] полностью перевести на языке рекурсивных функций, не привлекая машинных понятий типа инструкций и их потактового исполнения (не опираясь на понятия теории машин Тьюринга, RAM и проч.)?

То есть, можно ли на языке рекурсивных функций
1) дать определения всех понятий computability theory;
2) сформулировать все теоремы этой теории;
3) сформулировать все доказательства этих теорем.

от Профессор Снэйп был получен утвердительный ответ:

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

Да, можно.

-- Вс авг 26, 2012 02:16:55 --

(Оффтоп)

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

Но вам не нравится делать шаги вычислений и ждать, Вы вообще считаете, что вычислений никаких в природе не бывает. Значит что?..

А ничё!!! Не получится тут нихрена, как не извращайся! По крайней мере, у меня фантазии не хватает! Да и желание заниматься маразмом как нахлынуло, так и пропало. Время, между прочим, 4 часа ночи!!!

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

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

[_hum_]

(Оффтоп)

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

А ничё!!! Не получится тут нихрена, как не извращайся! По крайней мере, у меня фантазии не хватает! Да и желание заниматься маразмом как нахлынуло, так и пропало.

По-видимому, как-то оператор минимизации надо задействовать. Вот тут recursionclass/chap5.pdf говорится про какую-то используемую в теории рекурсивных функций технику dovetailing, возможно, это то, что нужно. Вникнуть не успел - пошел спать.

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

_hum_

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

По-видимому, как-то оператор минимизации надо задействовать.

А Вы хоть знаете, что это такое - минимизация? Или как с объединением: услышал звон, но не знает, где он?

Надо аналог теоремы Клини о нормальной форме доказывать, причём можно неравномерный. Одно из следствий теоремы Клини гласит, что для любой частично рекурсивной функции $f(\bar{x})$ существует примитивно рекурсивный предикат $P(\bar{x}, y, t)$, такой что $\exists t P(\bar{x}, y, t) \Leftrightarrow f(\bar{x}) = y$. Во всех человеческих учебниках этот предикат означает, что программа, вычисляющая функцию $f$, при входе $\bar{x}$ даёт на выходе $y$ не более чем за $t$ шагов работы. Однако, в принципе, существование абы какого примитивно рекурсивного $P$ с нужными свойствами можно доказать индукцией по определению функции $f$.

Честно говоря, я уже глубоко жалею, что начал метать бисер перед свиньями. Поглядел сегодня, за что в "Физике" народ банят: если там за гораздо меньшие провинности на две недели остынуть отправляют, то здесь, похоже, надо пожизненный бан выписывать за агрессивное невежество. БОльший маразм наблюдается только у ферманьяков, где люди с умным видом начинают рассуждать про эллиптические кривые и доказательство Уайлса, а сами при этом неспособны $x^n - z^n$ на $x-z$ правильно поделить или в кубическом уравнении от квадрата избавиться.

Я, пожалуй, даже рискну и предложу _hum_ элементарную проверку знаний. Пусть определит оператор минимизации. Что в точности означает выражение $f(\bar{x}) = \mu y(g(\bar{x}, y) = 0)$ для частично рекурсивной функции $g$? Книжки под руками, любая энциклопедия под руками, бери и переписывай... и всё равно процентов 50 вероятность, что лажу опять напорет! Проверим, а?

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

[Xaositect]

В книге Odifreddi, Classical recursion theory изложение в основном такое, какое требуется топикстартеру.

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

Xaositect в сообщении #610678 писал(а):

В книге Odifreddi, Classical recursion theory изложение в основном такое, какое требуется топикстартеру.

Бросьте, ему до Одифредди, как до Луны пешком

[_hum_]

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

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

Я, пожалуй, даже рискну и предложу _hum_ элементарную проверку знаний. Пусть определит оператор минимизации. Что в точности означает выражение $f(\bar{x}) = \mu y(g(\bar{x}, y) = 0)$ для частично рекурсивной функции $g$? Книжки под руками, любая энциклопедия под руками, бери и переписывай... и всё равно процентов 50 вероятность, что лажу опять напорет! Проверим, а?

Если говорить на машинном языке, то $f(\mathbf{x}) $ означает результат работы (включая неопределенный) следующего алгоритма:
$\_1\,$ для $y = 0,1,\dots$
$\_\quad 1.1$ вычислить $z := g(\mathbf{x},y)$
$\_\quad1.2$ если $z = 0$, то
$\_\quad\quad1.2.1$ печатать $y$
$\_\quad\quad1.2.2$ останов.
Если не на машинным языком, то это такое число $y^*$ (если оно существует), которое
1) является минимальным среди всех чисел, удовлетворяющих соответствующему уравнению;
2) для всех чисел $y \leq y*$, значение $g(\mathbf{x},y)$ определено.
С содержательной точки зрения - это вариант задания неявной функции.

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

Xaositect в сообщении #610678 писал(а):

В книге Odifreddi, Classical recursion theory изложение в основном такое, какое требуется топикстартеру.

Спасибо, попробую посмотреть.

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

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

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

А толку делиться знаниями, если я уже делюсь, а в ответ слышу, что знания мои не нужны и я всё равно хочу всё делать по своему? Да ещё и на слове пытаются ловить... Особенно не понравилось заявление насчёт того, что Вы, дескать, сказали, что без машин можно обойтись, значит я прав, а все аргументы в пользу машин мне глубоко до фени.

Про минимизацию Вы всё правильно написали, молодец (ругать уже ругал, пора и похвалить )! Вот только Вы её ведь не случайно начали описывать на "машинном" языке, да? А почему? А потому что её определение обычно кажется сложным и каким-то взятым с потолка, надуманным... если, конечно, не держать в голове тот факт, что оно было специально придумано для формализации одного из приёмов программирования. Обычно люди, избегающие машинной логики и рассуждений о машинах, заявляют, что $\mu y(g(x,y) = 0)$ - это минимальный $y$, для которого $g(x,y) = 0$. Что, конечно же, абсолютно неверно; обязательно следует добавлять, что $g(x,y')$ должна быть определена при всех $y' < y$. Я ожидал от Вас этой ошибки, а Вы её не сделали. Значит, Вы всё-таки держите машины в голове и представляете, как они работают, обрабатывая суперпозицию, минимизацию и примитивную рекурсию. И отлично понимаете, что неопределённость функции означает в точности то, что вычисляющая её машина уходит в бесконечный цикл и не останавливается

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

Докажите, что существует частично рекурсивная функция $g(x,y)$ такая, что функция $f(x) = \min \{ y : g(x,y) = 0 \}$ не частично рекурсивна. Имеется в виду не $\mu$-оператор, а обычный минимум, не учитывающий возможную неопределённость $g$ при меньших игреках.

[Munin]

(Оффтоп)

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

И отлично понимаете, что неопределённость функции означает в точности то, что вычисляющая её машина уходит в бесконечный цикл и не останавливается

Извините, почему обязательно в цикл? :-)

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

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

Извините, почему обязательно в цикл?

Ну как же. Программа состоит из конечного числа команд, а работает бесконечно долго, без остановки. Значит, одни и те же команды раз за разом исполняются снова и снова. Чем не цикл?

[Munin]

(Оффтоп)

Они могут исполняться в неповторяющемся порядке. Например, машина поехала по бесконечной ленте рисовать числа Фибоначчи.

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

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

Они могут исполняться в неповторяющемся порядке. Например, машина поехала по бесконечной ленте рисовать числа Фибоначчи.

А при чём здесь повторяющийся порядок?

x := 1;
repeat
  if (x is prime number) then A else B;
  inc(x)
until false

$A$ и $B$ - какие-нибудь различные команды. Неужели Вы отказываетесь считать эту конструкцию repeat ... until циклом?

[Munin]

Да, вы правы, пожалуй...

[_hum_]

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

Докажите, что существует частично рекурсивная функция $g(x,y)$ такая, что функция $f(x) = \min \{ y : g(x,y) = 0 \}$ не частично рекурсивна. Имеется в виду не $\mu$-оператор, а обычный минимум, не учитывающий возможную неопределённость $g$ при меньших игреках.

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

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

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

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

Докажите, что существует частично рекурсивная функция $g(x,y)$ такая, что функция $f(x) = \min \{ y : g(x,y) = 0 \}$ не частично рекурсивна. Имеется в виду не $\mu$-оператор, а обычный минимум, не учитывающий возможную неопределённость $g$ при меньших игреках.

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

Для каждого $x$ полагаем $g(x,1) = 0$ и начинаем вычислять $\varphi_x(x)$. Если окажется $\varphi_x(x) = 1$, то полагаем $g(x,0) = 0$, в противном случае оставляем $g(x,0)$ неопределённым. Вот и вся навскидка