Функциональный апартеид

[metaclass]

http://udpn.livejournal.com/78084.html?style=mine
Обычно говорят, что нормальный порядок редукции нужен для того, чтобы bottom в аргументе не превращался в bottom в результате всегда, когда это возможно. Само по себе это никому не нужно. Дело именно в отложенном вычислении аргументов. Чтобы определить управляющие конструкции в языке с аппл. порядком редукции, нужно это делать явно, и их можно ввести только конечное число на этапе разработки языка. С нормальным порядком мы имеем возможность определять новые конструкции в любом количестве.

Всех, кто ничего не понял - отправить в индию и бангладеш, купаться в ганге и поклонятся коровам.

Comments

[akuklev.livejournal.com]

Реально достаточно. На агде и родственных языках заведомо определяются все функции для которых можно дать оценку сверху скорости выполнения, которая выразима в терминах обобщённых функций Гудштейна (http://en.wikipedia.org/wiki/Goodstein's_theorem). То есть любые алгоритмы даже со временем работы O(2^2^...^n) туда влезают. Влезают любые фукнции Акермана, стрелки Конвея и чёртзнаетчто. Я слышал лишь про одну тотальную функцию, которую так построить невозможно — функцию TREE Фридмана.

Цитирую Википедию (http://en.wikipedia.org/wiki/Kruskal%27s_tree_theorem): «The latter theorem ensures the existence of a rapidly growing function that Friedman called TREE, such that TREE(n) is the length of a longest sequence of n-labelled trees T1,...,Tm in which each Ti has at most i vertices, and no tree is embeddable into a later tree.
The TREE sequence begins TREE(1) = 1, TREE(2) = 3, then suddenly TREE(3) explodes to a value so enormously large that many other "large" combinatorial constants, such as Friedman's n(4), are extremely small by comparison. A lower bound for n(4), and hence an extremely weak lower bound for TREE(3), is A(A(...A(1)...)), where the number of A's is A(187196), and A() is a version of Ackermann's function: A(x) = 2↑↑...↑x with x-1 ↑s (Knuth up-arrows). Graham's number, for example, is approximately A^64(4) which is much smaller than the lower bound A^A(187196)(1).»

В общем, на практике больше не нать.

[jakobz.livejournal.com]

Всех, кто ничего не понял - отправить в индию и бангладеш, купаться в ганге и поклонятся коровам.