Слабость функциональной парадигмы

[goodbigbeer]

aa_dav в сообщении #1083929 писал(а):

По вашему невозможно изучить ФП по книжке типа SICP, где не даётся лямбда-исчисление?

Мне как то странно слышать всегда, когда SICP связывают с ФП. Там действительно, в первых трех главах даются примеры только в пределах подстановочной модели, но не более того. Да, для понимания основ необходимо хотя бы общее понимание LC.

[aa_dav]

goodbigbeer в сообщении #1083933 писал(а):

Мне как то странно слышать всегда, когда SICP связывают с ФП.

С таким уровнем троллизма можно и внимание модератора

(Оффтоп)

опять

привлечь. SICP очень много внимания уделяет ФП.

[goodbigbeer]

aa_dav в сообщении #1083934 писал(а):

SICP очень много внимания уделяет ФП

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

[aa_dav]

goodbigbeer в сообщении #1083935 писал(а):

Действительно много.

Более чем достаточно.

[arseniiv]

goodbigbeer в сообщении #1083917 писал(а):

во-вторых, она опровергнута Карлом Хьюиттом, который доказал, что существуют алгоритмы нереализуемые на машине тьюринга, в том числе НМТ

Ссылочку, что ли, дали бы.

-- Вс дек 20, 2015 17:33:10 --

goodbigbeer в сообщении #1083935 писал(а):

Но я повторяю, чтобы рассуждать, нужны не просто примеры на ФП, но понимание модели.

А вы — мерило понимания ФП собеседниками, правильно угадал?

[goodbigbeer]

arseniiv в сообщении #1083939 писал(а):

Ссылочку, что ли, дали бы.

http://arxiv.org/pdf/1008.1459v38.pdf
стр 40

-- 20.12.2015, 16:41 --

arseniiv
То есть, на основании того, что человек знает реализацию различного рода рекурсивных факториалов и фибоначчи, которые рассматриваются в первых трех главах SICP, мы должны сделать вывод о том, что a) человек знает ФП, б) SICP -- книга о ФП?

Я не отрицаю, что SICP касается вопросов ФП, как и любое приличное издание, рассматривающее различные приемы/аспекты/парадигмы программирования. Только не стоит из этого делать далеко идущих выводов.

[Toucan]

goodbigbeer блокируется как злостный клон.

[arseniiv]

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

Цитата:

Theorem. There are nondeterministic computable functions on integers that cannot be implemented by a nondeterministic Turing machine.
Proof. The above Actor system implements a nondeterministic function i that cannot be implemented by a nondeterministic Turing machine.

Пруф какой-то не пруф. Вот машина над алфавитом $\{1,e\}$, начинает со строки $eee\ldots$ в состоянии $s$ с правилами $s\to1Rs$, $s\to t$ и допускающим состоянием $t$. Машина останавливается со строкой $1^n, n\in0..\infty$. Это контрпример — притом тут даже НКА справится.

[aa_dav]

arseniiv в сообщении #1083949 писал(а):

Это контрпример

Если я правильно понял, он там сразу же обсуждается ниже и ему "вменяется в вину" то, что он может никогда не остановится.
Но если честно я не смог понять аргументацию почему код с акторами ведет себя иначе. Надо сперва понять что это такое вообще судя по всему.

[gbb]

arseniiv
Я более чем уверен, что Ваше знание английского находится на хорошем уровне, и причина Вашего непонимания заключается не в том, что вы переводили автопереводчиком, а в том, что невнимательно прочитали. Я переведу это для Вас.

Цитата:

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

arseniiv в сообщении #1083949 писал(а):

Вот машина над

Сути Вы, к сожалению, тоже не поняли. МТ не гарантирует останов. Иными словами, нам нужно недетерминированное число менее бесконечности

-- 20.12.2015, 17:13 --

aa_dav в сообщении #1083955 писал(а):

почему код с акторами ведет себя иначе

Потому что сообщение Stop будет рано или поздно получено

[aa_dav]

gbb в сообщении #1083956 писал(а):

Потому что сообщение Stop будет рано или поздно получено

Я не понимаю как можно в железе реализовать то, что результат ничем не ограничен, при том что stop рано или поздно будет получен.

[gbb]

aa_dav
Утверждается что можно. Есть реальные физические примеры, например, квантовый индетерминизм, метастабильность в электронике.

[aa_dav]

Ну, в любом случае, недетерминированные машины не имеют отношения к поднятому вопросу.

[Karan]

gbb забанен как злостный клон.

[arseniiv]

aa_dav в сообщении #1083955 писал(а):

Если я правильно понял, он там сразу же обсуждается ниже и ему "вменяется в вину" то, что он может никогда не остановится.
Но если честно я не смог понять аргументацию почему код с акторами ведет себя иначе. Надо сперва понять что это такое вообще судя по всему.

А, я дальше не смотрел что-то. В таком случае, да, как-то не верится. Акторы не должны быть сильнее перед halting problem.

gbb в сообщении #1083956 писал(а):

Сути Вы, к сожалению, тоже не поняли. МТ не гарантирует останов. Иными словами, нам нужно недетерминированное число менее бесконечности

Вот не надо. Всё я так понял. $0..\infty$ означает $\{n : n\in\mathbb Z\wedge 0\leqslant n\}$.

gbb в сообщении #1083956 писал(а):

Потому что сообщение Stop будет рано или поздно получено

Это вилами по воде писано.

gbb в сообщении #1083961 писал(а):

Есть реальные физические примеры, например, квантовый индетерминизм, метастабильность в электронике.

С ненулевыми вероятностями не давать ответа дольше каждого наперёд заданного времени.