2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу Пред.  1, 2, 3  След.
 
 Re: Сomputability theory на языке рекурсивных функций (?)
Сообщение26.08.2012, 00:07 
Аватара пользователя
_hum_ в сообщении #610538 писал(а):
Вот и я спрашиваю, можно ли принципиально всю Computability theory перевести на "функциональный язык" (который избавлен от понятий машин и машинных тактов).

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

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

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

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

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

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

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

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

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

 
 
 
 Re: Сomputability theory на языке рекурсивных функций (?)
Сообщение26.08.2012, 01:08 
Замечательно. Итак, на вопрос
_hum_ в сообщении #610071 писал(а):
можно ли всю эту теорию [Computability theory] полностью перевести на языке рекурсивных функций, не привлекая машинных понятий типа инструкций и их потактового исполнения (не опираясь на понятия теории машин Тьюринга, RAM и проч.)?

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

от Профессор Снэйп был получен утвердительный ответ:
Профессор Снэйп в сообщении #610548 писал(а):
Да, можно.


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

(Оффтоп)

Профессор Снэйп в сообщении #610548 писал(а):
Но вам не нравится делать шаги вычислений и ждать, Вы вообще считаете, что вычислений никаких в природе не бывает. Значит что?..

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

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

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

 
 
 
 Re: Сomputability theory на языке рекурсивных функций (?)
Сообщение26.08.2012, 02:24 

(Оффтоп)

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

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

 
 
 
 Re: Сomputability theory на языке рекурсивных функций (?)
Сообщение26.08.2012, 03:14 
Аватара пользователя
_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_ эту ветку читает. Может, кому-то мои ответы действительно пользу принесут :?

 
 
 
 Re: Сomputability theory на языке рекурсивных функций (?)
Сообщение26.08.2012, 14:06 
Аватара пользователя
В книге Odifreddi, Classical recursion theory изложение в основном такое, какое требуется топикстартеру.

 
 
 
 Re: Сomputability theory на языке рекурсивных функций (?)
Сообщение26.08.2012, 15:10 
Аватара пользователя
Xaositect в сообщении #610678 писал(а):
В книге Odifreddi, Classical recursion theory изложение в основном такое, какое требуется топикстартеру.

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

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

Профессор Снэйп в сообщении #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 изложение в основном такое, какое требуется топикстартеру.

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

 
 
 
 Re: Сomputability theory на языке рекурсивных функций (?)
Сообщение26.08.2012, 20:54 
Аватара пользователя
_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$ при меньших игреках.

 
 
 
 Re: Сomputability theory на языке рекурсивных функций (?)
Сообщение26.08.2012, 21:11 
Аватара пользователя

(Оффтоп)

Профессор Снэйп в сообщении #610839 писал(а):
И отлично понимаете, что неопределённость функции означает в точности то, что вычисляющая её машина уходит в бесконечный цикл и не останавливается

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

 
 
 
 Re: Сomputability theory на языке рекурсивных функций (?)
Сообщение26.08.2012, 21:19 
Аватара пользователя
Munin в сообщении #610847 писал(а):
Извините, почему обязательно в цикл? :-)

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

 
 
 
 Re: Сomputability theory на языке рекурсивных функций (?)
Сообщение26.08.2012, 21:27 
Аватара пользователя

(Оффтоп)

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

 
 
 
 Re: Сomputability theory на языке рекурсивных функций (?)
Сообщение26.08.2012, 21:41 
Аватара пользователя
Munin в сообщении #610855 писал(а):
Они могут исполняться в неповторяющемся порядке. Например, машина поехала по бесконечной ленте рисовать числа Фибоначчи.

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

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


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

 
 
 
 Re: Сomputability theory на языке рекурсивных функций (?)
Сообщение26.08.2012, 21:59 
Аватара пользователя
Да, вы правы, пожалуй...

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

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

 
 
 
 Re: Сomputability theory на языке рекурсивных функций (?)
Сообщение28.08.2012, 03:37 
Аватара пользователя
_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)$ неопределённым. Вот и вся навскидка :-)

 
 
 [ Сообщений: 31 ]  На страницу Пред.  1, 2, 3  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group