За что не любят Common Lisp?

Разве что только аксиоматически, придумав виртуальную машину, которая эту функцию может выполнять.

http://ru.wikipedia.org/wiki/Рекурсивная_функция_(теория_вычислимости)#.D0.A7...

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

P.S. В догонку о формальной системе: http://ru.wikipedia.org/wiki/Теорема_Гёделя_о_неполноте

Это русская википедия? Ты слово «неформально» не захватил. Там же:

в нерусской тоже самое. говорю-же, пусть математики придумывают новый термин, или не ругаются, если я использую слово «алгоритм» в «неформальном» смысле. Почему им можно, а мне нельзя?

часто задача _быстрее_ решается недетерминированным «алгоритмом»

Так уж и часто? Огромное количество используемых процедур вполне однозначны и завершимы.

К сожалению - очень часто. Тот же метод численного интегрирования Монте-Карло работает лучше во всех случаях, кроме самых примитивных, когда число степеней свободы == 1. IRL системы имеют Over9000 степеней свободы, и аналитические методы можно хоронить. Математики даже задачу для трёх тел сфэйлили, что их слушать-то? Приходится думать самостоятельно, по ходу дела придумывая новые термины, и вкладывая новые значения в старые.

ЗЫЖ можно того же Кнута почитать - в большинстве случаев он не смог найти полного математического анализа для большинства алгоритмов. Впрочем, с т.з. математиков, у него и алгоритмов-то выходит и нету...

Что совсем не мешает им меж собой обзывать стохастические алгоритмы именно _алгоритмами_

Именно «вероятностные алгоритмы» => «алгоритмы» в последующем контексте. Это те же вычисления, но с более слабыми свойствами, нежели у обычных алгоритмов.

вероятность вычисления за 1000 лет, IRL не так уж и мала

Ну и что (я не знаю какая там вероятность для 1000 лет)? O(n) с большим коэффициентом тоже может быть хуже чем O(n^2) с хорошим на всех практически нужных аргументах. Это не отменяет асимптотики, как и того что та вероятностная сортировка с проверкой это алгоритм в строгом смысле.

Пусть это таких теоретиков как ты греет.

Как по мне, твои отсылки к «IRL» не менее теоретизированы, точнее не к месту. Есть фундаментальная разница между математической функцией вообще и разрешимым алгоритмом, просто потому что классы сложности отличаются. Приравнять их - это случится такой «маленький» математический апокалипсис (начать хотя бы с теорем Гёделя). Разумеется, если перестать путать классы сложности, можно уже говорить и про конкретные численные ограничения сверху на время в рамках конкретных классов.

дабы предупредить у вас инфаркт миокарда

Молодой человек, уверяю вас, если бы каждый препод падал с инфарктом от первого попавшегося Митрофанушки - в мире бы не осталось бы ВУЗов. ;) По остальным вопросам вас вроде бы уже просветили коллеги (не могу сказать, что успешно - впрочем, все равно спасибо им за сей, увы, неблагодарный труд).

В этих конторах работают индусы, азиаты и прочие русские (на визах), женщины (отпуск по беременности бОльше) и белые мужчины предпенсионного возраста (401k, бонусы, страховка). Молодые белые мужчины работают в стартапах, во все руки используют всякую экзотику.

Только IBM и Oracle десятилетиями возглавляют топ-листы Fortune, а из стартапов едва выживает каждый десятый. А так все зашибись! Пускай венчурное бабло про**ано, зато мы не такие как все, бунтари и нонконформисты, юзаем экзотику и презираем мейнстрим! Молодые белые хипсторы. :)

Но всё равно смысла не распарсил...

Если проще, то я утверждаю, что подмножество декартового произведения (счётного) множества всех программ на множество 2 = {завершима, зависла} будет функцией - во-первых, всякой программе найдётся пара в этом подмножестве (это данность, то есть мы так хотим), и, во-вторых, для всякой программы foo в этом подмножестве будет либо пара (foo, завершима), либо пара (foo, зависла), то есть любая программа либо всегда зависает, либо всегда завершается. Это заставляет отказаться от рассмотрения IO (если нам нужна не аппроксимация, а точно эта функция).

Кстати,

индусы, азиаты и прочие русские (на визах), женщины (отпуск по беременности бОльше) и белые мужчины предпенсионного возраста

Ну бред же. Виталь, ты б сходил разок на JavaOne. Гарантирую, будешь приятно удивлен. А еще лучше - на внутреннюю конференцию Oracle. Правда, без меня тебя туда не пустят ;) Ты там, кстати, не на Калифорнийщине обитаешь часом?

Приводить корпорации и их выбор языков в качестве примера - это пример или неосведомлённости, или неадекватности.

А ориентироваться на стартапыв духе «смотрите-я-хипстер-купи-меня-гугль» - это типа дофига осведомленно и адекватно, ага ;)

http://ru.wikipedia.org/wiki/Рекурсивная_функция_(теория_вычислимости)#.D0.A7...

не. http://ru.wikipedia.org/wiki/Рекурсивная_функция_(теория_вычислимости)#.D0.9E...

для Ъ

Общерекурсивная функция — частично рекурсивная функция, определённая для всех значений аргументов. Задача определения того, является ли частично рекурсивная функция с данным описанием общерекурсивной или нет, алгоритмически неразрешима.

Это тоже самое, вообще говоря (базовые операторы примитивной рекурсии, минимизации и суперпозиции остаются). Там разница то только в области определения.

Только IBM и Oracle десятилетиями возглавляют топ-листы Fortune, а из стартапов едва выживает каждый десятый. А так все зашибись! Пускай венчурное бабло про**ано, зато мы не такие как все, бунтари и нонконформисты, юзаем экзотику и презираем мейнстрим! Молодые белые хипсторы. :)

И? Все конторы когда-то были стартапами.

Ну бред же. Виталь, ты б сходил разок на JavaOne. Гарантирую, будешь приятно удивлен. А еще лучше - на внутреннюю конференцию Oracle.

Причём здесь конференции? Конференции о составе контор ничего не скажут. Надо смотреть в их столовых в обеденное время.

Правда, без меня тебя туда не пустят ;) Ты там, кстати, не на Калифорнийщине обитаешь часом?

Нет, в MA.

Именно «вероятностные алгоритмы» => «алгоритмы» в последующем контексте. Это те же вычисления, но с более слабыми свойствами, нежели у обычных алгоритмов.

ну я и говорю: те же _алгоритмы_, только более обобщённые. Ваши «чистые» алгоритмы - частный случай более общего класса «вычислительных методов». Вот я и спрашиваю: разве условия детерминированности и условия конечности не являются искусственными?

Ну и что (я не знаю какая там вероятность для 1000 лет)?

ненулевая.

O(n) с большим коэффициентом тоже может быть хуже чем O(n^2) с хорошим на всех практически нужных аргументах. Это не отменяет асимптотики, как и того что та вероятностная сортировка с проверкой это алгоритм в строгом смысле.

не отменяет. Вот только вы неправильно считаете, потому-что всё упрощаете. На самом деле, если вы внимательно посмотрите на туже qsort, то вы заметите, что её асимптота совсем НЕ O(log(N)*N), а является таковой только в сферическом вакуумном случае. Если начальные данные можно считать случайными, то реальная асимптота лежит в промежутке от O(N^2) до O(N*log(N)), и занимает случайное значение. Проще говоря, если размер массива в 1000 раз больше, то время его сортировки больше от 10 000 до 1 000 000 раз. (да, распределение неравномерное, IRL в большинстве случаев мы выходим на 20 000..200 000 раз, в зависимости от деталей алгоритма). Заметь, я тут только про асимптоту говорю, точнее про её реальное поведение при большом N. Факт того, что асимптота не учитывает константу пропорциональности оставь самым маленьким, я в курсе.

Как по мне, твои отсылки к «IRL» не менее теоретизированы, точнее не к месту. Есть фундаментальная разница между математической функцией вообще и разрешимым алгоритмом, просто потому что классы сложности отличаются.

ага. Как небо и земля. Если рассматривать sort() как математическую функцию, то единственное, что можно про неё сказать, так это то, что оно сортирует. И ВСЁ. Может это определение и устраивает математиков, но для меня оно бесполезно, чуть более, чем полностью.

Приравнять их - это случится такой «маленький» математический апокалипсис (начать хотя бы с теорем Гёделя).

теорема Гёделя - сама по себе апокалипсис для математики.

Молодой человек, уверяю вас, если бы каждый препод падал с инфарктом от первого попавшегося Митрофанушки - в мире бы не осталось бы ВУЗов. ;) По остальным вопросам вас вроде бы уже просветили коллеги (не могу сказать, что успешно - впрочем, все равно спасибо им за сей, увы, неблагодарный труд).

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

разве условия детерминированности и условия конечности не являются искусственными?

Они не искусственные - есть иерархия классов сложности (хотя и не построенная ещё полностью, P ? NP, например), это просто данность. А какое значение мы примем для слова «алгоритм» это уже _конвенция_ (ещё раз) - от замены значений слов смысл не изменится, лишь бы разные понятия оставались обозначены разными словами. Если, вдруг, понятие «алгоритм» станет эквивалентно понятию «функция», то это будет либо негодное (лишнее) понятие, либо неправильное, то есть оно явно должно чем-то отличаться от понятия функции. Я вот привык к тому, что алгоритм это где-то в районе decidable.

Вот только вы неправильно считаете

Я тут не про сортировку говорю, O(n) и O(n^2) это просто пример - и асимптотика и класс сложности это такие качественные оценки, даже если у алгоритма с «хорошей» асимптотикой ужасный коэффициент, тогда как у алгоритма с «плохой» сложностью он хороший, так же - алгоритм может быть «завершим», но работать over9000 лет, а другое вычисление будет «незавершимо» для задачи достижения точных ответов, но приближенные значение будет получать за вполне разумное время.

Если рассматривать sort() как математическую функцию, то единственное, что можно про неё сказать

«Если рассматривать группу как множество, то единственное, что можно про неё сказать...». А теперь рассмотрим множество неразрешимую проблему останова и её разрешимые приближения - вполне себе задача для статического анализа ЯП.

теорема Гёделя - сама по себе апокалипсис для математики.

Почему? Они вполне «фатально неизбежны», то есть «иначе и быть не может». Мое предложение «[не] написать универсальный termination checker для сишки [на сишке]», например, это разновидность предложения «доказать [первую] теорему о неполноте», только в других терминах.

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

Внезапно :)

Они не искусственные - есть иерархия классов сложности (хотя и не построенная ещё полностью, P ? NP, например), это просто данность. А какое значение мы примем для слова «алгоритм» это уже _конвенция_ (ещё раз) - от замены значений слов смысл не изменится, лишь бы разные понятия оставались обозначены разными словами. Если, вдруг, понятие «алгоритм» станет эквивалентно понятию «функция», то это будет либо негодное (лишнее) понятие, либо неправильное, то есть оно явно должно чем-то отличаться от понятия функции. Я вот привык к тому, что алгоритм это где-то в районе decidable.

Во первых, под эквивалентностью «алгоритм===функция», я понимал естественно совсем НЕ саму функцию, но _определение_ функции. Крутани тред до этого сообщения: За что не любят Common Lisp? (комментарий) В нём речь шла вовсе не о функции «факториал», а об _определении_ функции, или как выразился мой оппонент «о способе записи». Вот этот «способ записи» и является «алгоритмом». И именно между ними и был поставлен знак равенства. В треде имеется также и картинка: http://upload.wikimedia.org/math/f/6/a/f6ab785bcc8d659ec5713c11d84781a4.png на которой мы видим _алгоритм_ вычисления факториала, а совсем не сам факториал. Причём он вполне себе decidable. А «бредом» он станет только если его выдрать из контекста, что и было сделано одним из здешних троллей, которого я и отправил подучить матчасть.

Я тут не про сортировку говорю, O(n) и O(n^2) это просто пример - и асимптотика и класс сложности это такие качественные оценки, даже если у алгоритма с «хорошей» асимптотикой ужасный коэффициент, тогда как у алгоритма с «плохой» сложностью он хороший, так же - алгоритм может быть «завершим», но работать over9000 лет, а другое вычисление будет «незавершимо» для задачи достижения точных ответов, но приближенные значение будет получать за вполне разумное время.

дык я с этим-то и не спорил вовсе. Я говорил о том, что даже невычислимый в принципе «алгоритм» вполне может являться годным на практике алгоритмом. Для приведённого мной алгоритма О-большое равно бесконечности, но на самом деле, на практике, он часто даёт результат за конечное время. Причём, его можно изменить так, что-бы он давал результат чаще другого алгоритма с определённым O-большое. Если понимать «получить результат» как «получить результат за вполне определённое время». Т.е., с т.з. пользователя, _случайный_ алгоритм с бесконечным О-большое моет быть _лучше_ детерминированного.

А теперь рассмотрим неразрешимую проблему останова и её разрешимые приближения - вполне себе задача для статического анализа ЯП.

давайте рассмотрим... Я не против. Я правда не вполне понимаю, как можно узнать завис, или не завис недетерминированный алгоритм? Over9000 лет для него - вполне штатное явление(хоть и маловероятное). Но что самое печальное, Over9000 секунд для юзера тоже «зависло», но для всем известной qsort это _тоже_ _штатное_ поведение. Как быть с такими алгоритмами? Это я к тому, что вычисляемость и детерминированность вам в принципе не поможет, ибо вполне себе распространённый алгоритм может вполне себе штатно зависнуть, на вполне себе рабочем оборудовании. И я не понимаю, какой вообще смысл в этой вашей задаче?

Почему?

потому-что поясняет ущербность логики математики, которая не в состоянии непротиворечиво доказать даже саму себя. Толку-то с неё после этого? ВНЕЗАПНО становится ясно, что никакой доказательной базы и нету, а есть только «вычислительные методы», которые принимаются на веру, прямо как Священное Писание.

Мое предложение «[не] написать универсальный termination checker для сишки [на сишке]», например, это разновидность предложения «доказать [первую] теорему о неполноте», только в других терминах.

лично я в этом вашем чекере вижу не больше смысла, чем в делении на ноль. Т.е. возможно какие-то приближения к чекеру и будут полезны на практике (как частные бесконечно малых разных порядков), но сам по себе такой чекер - это ненужная НЁХ. Он бессмысленный по самому своему определению. Или вы этого не понимаете?

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

Внезапно :)

внезапно _определяете_ функцию вы(математики) всегда с помощью НЁХ, которую я называю «алгоритм». Например факториал вы определяете алгоритмом n!=n*(n-1)! (правда вы почему-то не соглашаетесь назвать определение алгоритмом, хотя на мой взгляд, оно вполне годно быть алгоритмом. В данном случае даже конечно и вычислимо).

я понимал естественно совсем НЕ саму функцию, но _определение_ функции

То есть

• У алгоритмически вычислимой функции может быть определение в виде алгоритма.

Только ещё есть варианты:

• У алгоритмически вычислимой функции может не быть (быть неизвестно) определение в виде алгоритма.
• Функция может быть невычислима. Каким определением-алгоритмом она задаётся?
• Функция может быть вычислимой или нет, но задаваться косвенно (ДУ, например). И график функции (который строит алгоритм) может быть не интересен, могут быть нужны только свойства функции (которые не получаются прямым алгоритмическим перебором).

Я правда не вполне понимаю, как можно узнать завис, или не завис недетерминированный алгоритм?

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

И я не понимаю, какой вообще смысл в этой вашей задаче?

Отлавливать опечатки и логические ошибки приводящие к зависаниям в циклах и stack overflow в рекурсии (в том числе между разными функциями) во время набора кода.

потому-что поясняет ущербность логики математики, которая не в состоянии непротиворечиво доказать даже саму себя.

Никакой «логики математики» и «самой себя» нету. Математика вообще это одно, а теоремы Гёделя (_теоремы_, что характерно) утверждают определённые свойства формальных систем. Именно, если язык теории не достаточно богат, то в такой теории (возможно) всякая правда будет настоящей правдой (sound => consistent), а всякая настоящая правда найдёт своё (доказуемое) отражение в такой теории (complete). Примеры таких теорий - аксиоматика Тарского для Евклидовой геометрии и арифметика Пресбургера (которая слабее PA). Такие теории не попадают под действие (первой) теоремы о неполноте.

Теоремы о неполноте отвечают на вопрос о том что будет когда аксиоматическая система станет достаточно богатой, так что в ней станет возможна рефлексия - она тут же станет универсальной системой годной для того чтобы служить основанием для самой себя и для всей математики вообще, или так и останется просто одной из формальных дедуктивных систем? В такой богатой системе будет возможно построить высказывания вроде «это утверждение недоказуемо» и «данная система непротиворечива». Такая богатая теория не сможет быть одновременно complete & (sound | consistent) (для простоты - достаточно рассмотреть «парадокс лжеца»). Если теория полагает что она непротиворечива - она противоречива. Теория может считать, что она противоречива и при этом быть непротиворечивой (outside). Что обычно нужно это непротиворечивость (outside, но не допущение таковой inside) и, как следствие, неполная теория которая не может рассуждать о самой себе, но при этом вполне справляется с доказательством всех остальных теорем для формализации которых эта теория и создавалась. То есть вот есть теория, она используется по назначению, но рассуждать о свойствах этой теории нужно не в самой теории, а во внешнем «фреймворке для выявления общезначимости», то есть в метатеории (например, рассуждать о PA можно в видоизменённой PA или в ZFC).

[...] it's a simple matter, this theorem. It says that Parliament cannot grant itself an amnesty by the vote of one of its sub-committees, nor by itself: it must at least bring in some members from the outside. Isn't that just common sense? Or, alternatively, that you can't fix your glasses while keeping them on your nose.

(c) J.Y.Girard.

Правда, чтобы рассуждать о «фреймворке» нужен «фреймворк для фреймворка» и далее turtles all the way down (PA -> PA' + transfinite induction -> ZFC -> ZFC + Grothendieck Universe -> ?).

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

Что будет если вычислитель станет Тьюринг-полным? Будет существовать программа способная решить завершается ли любая данная программа или нет?

У алгоритмически вычислимой функции может не быть (быть неизвестно) определение в виде алгоритма.

да. Это не важно. У многих теорем математики тоже нет доказательств. Вот например тривиально простая (по определению) великая теорема Ферма (её вроде как доказали, но её доказательство совершенно непонятно даже большинству самих математиков).

Функция может быть невычислима. Каким определением-алгоритмом она задаётся?

очевидно, она задаётся _алгоритмом_, просто доказано, что машины Тьюринга для вычисления функции _недостаточно_. Учитывая дубовость и примитивность машины Тьюринга, это вполне объяснимо.

Функция может быть вычислимой или нет, но задаваться косвенно (ДУ, например). И график функции (который строит алгоритм) может быть не интересен, могут быть нужны только свойства функции (которые не получаются прямым алгоритмическим перебором).

во первых, я разве где-то писал про графики? С чего вы вообще взяли, что алгоритм на входе принимает число, на выходе выдаёт результат вычисления функции? Уже 50+ лет полно алгоритмов, которые работают не с числами. Вот в SICP есть алгоритм дифференцирования многочленов, который выдаёт на выходе многочлен. И это - достаточно тривиальный пример, известный с 50х годов прошлого века. Или это тоже «не алгоритм»?

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

не всё так просто - алгоритм может быть вполне разрешим в математическом смысле, и при этом неразрешим в численном виде. Как пример - факторизация сравнительно небольших чисел (~2^256 например), которая на сегодня невозможна просто из-за слабости вычислителя. Она по твоему будет вполне себе вычислима. Как и qsort (которая на самом деле иногда зависает, а иногда и навечно).

Отлавливать опечатки и логические ошибки приводящие к зависаниям в циклах и stack overflow в рекурсии (в том числе между разными функциями) во время набора кода.

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

Будет существовать программа способная решить завершается ли любая данная программа или нет?

в принципе ИМХО такая программа для машины Тьюринга (и эквивалентных ей) _может_ быть написана. Но:

• время вычислений будет слишком высоко, т.е. ОЧЕНЬ БОЛЬШОЕ. факторизация чисел ~2^256 покажется детской игрой.
• для многих алгоритмов ответом будет «нет». Несмотря на их практическое использование.

очевидно, она задаётся _алгоритмом_, просто доказано, что машины Тьюринга для вычисления функции _недостаточно_

Она не задаётся алгоритмом. Это называется _определима_. Формально - в языке существует класс эквивалентности формул с определёнными свойствами. Очевидно, что язык счётный, поэтому количество определимых вещей счётно, тогда как с точки зрения языка (internal) существуют несчётные вещи, то есть существует несчётное количество неопределимых вещей (опять же, internal). При этом счётное множество определимых вещей само неопределимо, и даже рассуждения (сравнения, например) о вычислимых определимых функциях могут быть алгоритмически неразрешимы.

Конечно, всё это относится только к математическим функциям, компьютерно у нас нет действительных чисел и всё вычислимо и алгоритмизируемо.

Учитывая дубовость и примитивность машины Тьюринга

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

во первых, я разве где-то писал про графики?

man график функции? Грубо говоря, это таблица аргументы * результат.

Алгоритмическое

Foo fn(Bar bar, Baz baz) ...

как раз занимается её построением. Тогда как математически функция fn : Bar * Baz -> Foo может быть определена просто логической формулой безотносительно графика.

не всё так просто

В разных академических языках termination checkеры уже давно реализованы.

Тут речь про то, чтобы поставить, например, аннотацию @halt для функции или модуля, так что любые подозрения на зависающие функции были озвучены. То есть не про какие-то абстрактные разрешимые и нет функции, а про обычные тупые логические ошибки, типа «перепутав i и j одного типа получим зависающий навечно цикл зависание которого выявится только когда control flow придёт сюда в рантайме».

Она не задаётся алгоритмом. Это называется _определима_. Формально - в языке существует класс эквивалентности формул с определёнными свойствами. Очевидно, что язык счётный, поэтому количество определимых вещей счётно, тогда как с точки зрения языка (internal) существуют несчётные вещи, то есть существует несчётное количество неопределимых вещей (опять же, internal). При этом счётное множество определимых вещей само неопределимо, и даже рассуждения (сравнения, например) о вычислимых определимых функциях могут быть алгоритмически неразрешимы. Конечно, всё это относится только к математическим функциям, компьютерно у нас нет действительных чисел и всё вычислимо и алгоритмизируемо.

ИМХО ты совершаешь ошибку, считая всё _вычисляемо_ (в компьютере). Та же сортировка оперирует перестановками, а совсем не вычислениями. В действительности, в наших компьютерах нет не только действительных чисел, но даже натуральных - множество натуральных чисел счётно и бесконечно, и IRL такого нет. Что совсем не мешает нам при анализе использовать машину, с бесконечным числом памяти (как машину Тьюринга), или машину, способную вычислить бесконечное число операций (при вычислении О-большого). По каким таким причинам нельзя ввести множество алеф1 или даже алеф2 - мне непонятно. Насколько я понимаю, множество всех алгоритмов возможных на машине Тьюринга с бесконечным счётным множеством ячеек, как раз и составляет алеф2(т.е. мощнее множества всех вещественных чисел, но равное множеству всех функций). Впрочем - в теории множеств я как свинья в апельсинах...

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

а я в курсе этого печального факта. И более того - у нас ещё и недоделанная машина Тьюринга - бесконечных лент не бывает.

man график функции? Грубо говоря, это таблица аргументы * результат.

построй мне график сортировки. Там тоже есть входная перестановка, и есть выходная. Вот только перестановки не обладают свойством A>=B>=C (упорядоченность), потому как ты их будешь «откладывать на абсциссе/ординате - мне непонятно.

Алгоритмическое Foo fn(Bar bar, Baz baz) ... как раз занимается её построением.

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

Тут речь про то, чтобы поставить, например, аннотацию @halt для функции или модуля, так что любые подозрения на зависающие функции были озвучены. То есть не про какие-то абстрактные разрешимые и нет функции, а про обычные тупые логические ошибки, типа „перепутав i и j одного типа получим зависающий навечно цикл зависание которого выявится только когда control flow придёт сюда в рантайме“.

ИМХО практически любой алгоритм потенциально подозрителен. Потом смысл от этого чекера отсутствует. Разве что он будет ловить только самые примитивные вещи, как это уже сделано в gcc (ну типа „переменная j никогда не используется“ если я её с i перепутал).

построй мне график сортировки

class Enumerable t where
  enumerate :: [t]

instance Enumerable t => Enumerable [t] where
  enumerate = do { re <- [] : enumerate; su <- enumerate; return (su : re) }

graph :: Enumerable a => (a -> b) -> [(a, b)]
graph f = map (id &&& f) enumerate

data BoundedEnumerable t = BE t deriving ( Show, Eq, Ord, Enum, Bounded )

instance (Enum t, Bounded t) => Enumerable (BoundedEnumerable t) where
  enumerate = map BE [minBound .. maxBound]

data ABC = A | B | C deriving ( Show, Eq, Ord, Enum, Bounded )

test = graph (sort :: [BoundedEnumerable ABC] -> [BoundedEnumerable ABC])

для любых функций от любых счётных типов для которых имеет смысл операция «следующий терм» (для списков «A>=B>=C (упорядоченность)» это лексикографический порядок, если что).

Для конечных типов можно ещё построить конечное функциональное пространство:

__ :: t
__ = error "using type-level value at runtime"

class Sized t where
  size  :: t -> Int
  index :: t -> Int
  value :: Int -> t

fs :: (Sized a, Sized b) => a -> b -> [a -> b] -- B ^ A
fs a b = fss (size a) [] where
  fss 0 ix = [value . (ix !!) . index]
  fss n ix = foldr ((++) . fss (n - 1) . (: ix)) [] [0 .. size b - 1]

table :: (Sized a) => a -> [a -> b] -> [[(a, b)]]
table a fs = [[(value x, f $ value x) | x <- [0 .. size a - 1]] | f <- fs]

instance (Enum t, Bounded t) => Sized t where
  size _ = fromEnum (maxBound :: t) - fromEnum (minBound :: t) + 1
  index  = fromEnum
  value  = toEnum

test2 = table (__ :: Bool) $ fs (__ :: Bool) (__ :: Bool)

(для счётных оно уже, теоретически, несчётно).

Потом смысл от этого чекера отсутствует.

Такой же смысл как и у любой другой статической проверки.

для любых функций от любых счётных типов для которых имеет смысл операция «следующий терм» (для списков «A>=B>=C (упорядоченность)» это лексикографический порядок, если что).

путь от 213 и от 132 до 123 одинаковый. Почему первая перестановка «больше» второй? По твоему, 213>132>123, но для сортировки нет разницы между двумя этими перестановками. Мало того, путь от 213 никак НЕ лежит через 132. Потому перестановки _нельзя_ сопоставить числам. Три любых неравных числа образуют _однозначную_ тройку A>B>C, но три разных перестановки такой тройки не образуют.

http://en.wikipedia.org/wiki/Lexicographical_order

> take 40 $ enumerate :: [[ABC]]
[[A],[B],[C],[A,A],[B,A],[C,A],[A,B],[B,B],[C,B],[A,C],[B,C],[C,C],[A,A,A],[B,A,A],[C,A,A],[A,B,A],[B,B,A],[C,B,A],[A,C,A],[B,C,A],[C,C,A],[A,A,B],[B,A,B],[C,A,B],[A,B,B],[B,B,B],[C,B,B],[A,C,B],[B,C,B],[C,C,B],[A,A,C],[B,A,C],[C,A,C],[A,B,C],[B,B,C],[C,B,C],[A,C,C],[B,C,C],[C,C,C],[A,A,A,A]]

> take 40 $ graph (sort :: [ABC] -> [ABC])
[([A],[A]),([B],[B]),([C],[C]),([A,A],[A,A]),([B,A],[A,B]),([C,A],[A,C]),([A,B],[A,B]),([B,B],[B,B]),([C,B],[B,C]),([A,C],[A,C]),([B,C],[B,C]),([C,C],[C,C]),([A,A,A],[A,A,A]),([B,A,A],[A,A,B]),([C,A,A],[A,A,C]),([A,B,A],[A,A,B]),([B,B,A],[A,B,B]),([C,B,A],[A,B,C]),([A,C,A],[A,A,C]),([B,C,A],[A,B,C]),([C,C,A],[A,C,C]),([A,A,B],[A,A,B]),([B,A,B],[A,B,B]),([C,A,B],[A,B,C]),([A,B,B],[A,B,B]),([B,B,B],[B,B,B]),([C,B,B],[B,B,C]),([A,C,B],[A,B,C]),([B,C,B],[B,B,C]),([C,C,B],[B,C,C]),([A,A,C],[A,A,C]),([B,A,C],[A,B,C]),([C,A,C],[A,C,C]),([A,B,C],[A,B,C]),([B,B,C],[B,B,C]),([C,B,C],[B,C,C]),([A,C,C],[A,C,C]),([B,C,C],[B,C,C]),([C,C,C],[C,C,C]),([A,A,A,A],[A,A,A,A])]

мне больше нравится этот генератор

for((j=0; j<10; j++)) do echo -e "a\nb\nc" | shuf | sed -n 'H;${g;s/\n//gp}'; done

чем он хуже?

Он вообще никакой :) То есть ни порядка, ни покрытия всех элементов. Нужно перечислить все финитные строки над финитным или (бесконечно) счётным алфавитом в строгом порядке - получится финитное или счётное множество всех списков конечной длины, счётное, то есть каждому списку будет однозначно соответствовать целое число, а всякому целому числу - список, после можно построить множество пар из всех этих списков и применений сортировки к ним, получив тем самым подмножество декартового произведения списки * списки с выполнением условия сортировки, то есть, по определению графика, график сортировки.

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

Он вообще никакой :) То есть ни порядка, ни покрытия всех элементов. Нужно перечислить все финитные строки над финитным или (бесконечно) счётным алфавитом в строгом порядке

дык и у тебя никакой. Повторяюсь - алфавитный порядок тут искусственен. А покрытие у меня есть. Можешь сделать его бесконечно хорошим за бесконечное время.

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

точнее, ты перечислил в _произвольном_ порядке перестановки, и получил _единственный_ результат (ибо сортировка даёт один и тот же результат, без учёта устойчивости). «График» моего генератора будет эквивалентен «графику» твоего, ибо любая перестановка преобразуется в «abc», неважно - какая. Потому мой генератор ничем не хуже твоего (для сортировки).

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

программа компилятора/интерпретатора тоже строит график? ладно, пусть это сложно. Вот простая функция(есть в php) которая вычисляет расстояние между двумя словами. От «кошка» до «кашка» единица, а до «кот» - 3. А вот до «ложка» 2, хотя «ложка» от «кошка» в словаре намного дальше «кот». (гуглить «метрика Левенштейна»).

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

алгоритм определяется алгоритмами на каком-то ЯП. Который работает в какой-то вычислительной машине(не обязательно реальной. CL например работает в виртуальной). Машина(как и алгоритм) не обязана быть конечной, и/или детерминированной. Также она не обязана строить графики. (и вообще что-то вычислять. Вот sed например, ничего не вычисляет)

дык и у тебя никакой

У меня нормальный.

Повторяюсь - алфавитный порядок тут искусственен.

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

Это не важно. Для построения всего графика как таблицы нужен любой однозначный порядок. Я взял лексикографический - он вполне однозначный и этого достаточно. Любое счётное количество термов (считай, почти любой тип) можно однозначно упорядочить (чисто по определению счётности). Чисто формально так. Практически - да, это не всегда нужно и имеет смысл.

А покрытие у меня есть.

Нету. У тебя вообще shuf - всякий раз будет разный порядок и никакого покрытия.

Можешь сделать его бесконечно хорошим за бесконечное время.

Вероятность того что твой алгоритм сделает то что нужно = 0.0%? Но зачем? Делаем сразу вменяемый алгоритм без всяких shuf и всё.

и получил _единственный_ результат (ибо сортировка даёт один и тот же результат, без учёта устойчивости)

? Я перечислил _все_ списки и для _каждого_ списка x получил отсортированный результат sort(x). Итого - получился график любой алгоритмически строгой функции сортировки в виде таблицы.

«График» моего генератора будет ...

Пока что ты только взял «abc» и построил десять случайных перестановок. То есть всех списков не перечислил в однозначном порядке и графика (применением любой алгоритмически строгой функции sort к каждому списку) не получил.

программа компилятора/интерпретатора тоже строит график?

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

Вот простая функция(есть в php) которая вычисляет расстояние между двумя словами.

И что?

алгоритм определяется алгоритмами на каком-то ЯП

Отлично. А «математические функции вообще определяются формулами соответствующего математического языка». Например, в теории множеств действительные числа определяются формулами f : Set -> Prop в языке первого порядка (из ZFC, например), так что f(r) уникально истино для определяемого числа r. При этом существуют определимые, но невычислимые действительные числа.

Который работает в какой-то вычислительной машине(не обязательно реальной. CL например работает в виртуальной). Машина(как и алгоритм) не обязана быть конечной, и/или детерминированной. Также она не обязана строить графики. (и вообще что-то вычислять. Вот sed например, ничего не вычисляет)

Сортировки, перестановки, функции, графики, алгоритмы, бесконечные машины, CL, sed - всё смешалось. Ну тут два варианта - можно говорить просто о насущных вещах, например, в контексте языка си «функция» это понятно что, тогда принципиально разные вещи не будут смешиваться. А если уж рассуждать о «математических определениях факториала», «алгоритмах вообще» и т.п., то нужно как-то стараться использовать общепринятую терминологию и не делать безумных логических кульбитов. Таково моё ИМХО :)

У меня нормальный.

у меня тоже нормальный. Метод Монте-Карло вот отлично работает на случайных данных.

Это не важно. Для построения всего графика как таблицы нужен любой однозначный порядок. Я взял лексикографический - он вполне однозначный и этого достаточно. Любое счётное количество термов (считай, почти любой тип) можно однозначно упорядочить (чисто по определению счётности). Чисто формально так. Практически - да, это не всегда нужно и имеет смысл.

в том-то и дело, что с т.з. сортировки на месте, твой порядок НЕ является однозначным. Это искусственная однозначность, которую ты ввёл просто для своего удобства. Конечно, она подойдёт для таблицы, которой всё равно, в каком порядке строчки, но согласись, графиком с перепутанной абсциссой можно доказать(показать) любую наперёд заданную закономерность. Потому такой _график_ не имеет смысла. Единственное, что можно извлечь из такого графика: максимум/минимум/среднее/разброс значений. Вопрос КАК меняется цена сортировки остаётся открытым. И это вполне объяснимо, ибо множество перестановок невозможно однозначно пронумеровать (даже конечное).

Нету. У тебя вообще shuf - всякий раз будет разный порядок и никакого покрытия.

у меня бесконечно-хорошее покрытие за бесконечное время. А по твоему, порядок не имеет значения.

Вероятность того что твой алгоритм сделает то что нужно = 0.0%? Но зачем? Делаем сразу вменяемый алгоритм без всяких shuf и всё.

вероятность у меня близка к 99% за некое время T1. В твоём случае, за время T2 у тебя будет 100% гарантированно. А вот теперь докажи хотя-бы сравнимость величин T2 и T1. Возможно, моё T1 это 5 минут, а твоё T2 это миллион лет? Лучше иметь 99% за 5 минут, чем 100% за 1000000 лет (особенно в нашем случае, где можно быстро проверить правильность сортировки). «всякая shuf», между прочем, куда как быстрее, чем твоя лексиграфическая сортировка.

Пока что ты только взял «abc» и построил десять случайных перестановок. То есть всех списков не перечислил в однозначном порядке и графика (применением любой алгоритмически строгой функции sort к каждому списку) не получил.

я получил все 6 перестановок: abc, acb, bac, bca, cab, cba. Этого достаточно. Причём тут ещё списки типа (a) - мне непонятно. Я говорил о сортировке ТРЁХ элементов.

Который работает в какой-то вычислительной машине(не обязательно реальной. CL например работает в виртуальной). Машина(как и алгоритм) не обязана быть конечной, и/или детерминированной. Также она не обязана строить графики. (и вообще что-то вычислять. Вот sed например, ничего не вычисляет)

Сортировки, перестановки, функции, графики, алгоритмы, бесконечные машины, CL, sed - всё смешалось. Ну тут два варианта - можно говорить просто о насущных вещах, например, в контексте языка си «функция» это понятно что, тогда принципиально разные вещи не будут смешиваться. А если уж рассуждать о «математических определениях факториала», «алгоритмах вообще» и т.п., то нужно как-то стараться использовать общепринятую терминологию и не делать безумных логических кульбитов. Таково моё ИМХО :)

К сожалению, общепринятой терминологии не существует. Например ты постоянно мешаешь в одну кучу таблицу и график. А вот для меня это разные вещи: в таблице строчки не обязаны быть упорядоченными, в отличие от графика, в котором ось абсцисс и ось ординат _всегда_ упорядоченна, и мы всегда можем сказать, что A<B<C, для любых трёх различных точек. При этом на графике абсциссы A, B и C будут лежать именно в таком порядке, и их невозможно будет никак поменять (кроме случая, если их ординаты равны). Ну а ты строишь «график» перестановок, использующий искусственный «факт» алфавитного порядка. Если взять не перестановки, а алгоритмы (в бинарном коде), то твой «график» будет зависеть от того, каким байтом ты обозначаешь конкретную команду. Но т.к. сама команда одна и та же, то и график измениться не должен. Но у тебя почему-то изменится.