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

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

существует. f(x) = x. У вас функция q, которая в алфавите {a} «вычисляет» значение. Тоже очевидно a. Так и функция f(x)=x. Это такое «единичное произведение». Вы их можете добавить сколько угодно (добавив while(1); ) в т.ч. нетривиальных (добавив 1+1), но результат будет одинаковый - такой же, как если-бы вы ничего не делали. Если по вашему «ничего не делай» - это не алгоритм, и f(x)=x это не функция - то вы правы.

Это неверно. Для диофантовых уравнений это будет функция ℤⁿ→ℤ₂, принимающая коэффициенты уравнения и возвращающая 0 или 1 в зависимости от его разрешимости. Определение корректно, однозначность соблюдена. Алгоритмическая неразрешимость доказывается. Увы, на ЛОРе (вроде бы?) нет математической разметки, мог бы привести формальное определение, а городить псевдографикой лень.

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

Неверно. Функция существует и нетривиальна. Вычислимость в определении функции не требуется.

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

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

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

while(1)
    x = foo(x);

Ваш собеседник (даже на ЛОРе) ВНЕЗАПНО может оказаться более старшим и опытным. Так пользуйтесь же этим!

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

Попросил его написать метод, разворачивающий строку

наоборот что-ли?

Выучи наконец хоть что-нибудь из математики. В частности, разницу между «алгоритмом», «функцией» и «алгоритмически вычислимой функцией». И запомни навсегда, что математическая функция ничего не «делает», у неё есть только значения для каждого возможного аргумента.

И запомни навсегда, что математическая функция ничего не «делает», у неё есть только значения для каждого возможного аргумента.

зачем мне быть таким же зубрилой как ты? Мне ЕГЭ сдавать не нужно. А ты - учи, молодец. Как выучишь, займёмся представлением функции как алгоритма. И алгоритма - как функции. А пока тебе это видимо ещё рановато.

зачем мне быть таким же зубрилой как ты?

Чтобы не пороть такую хуй&ю, от которой даже ЛОРу плохеет.

Мне ЕГЭ сдавать не нужно.

Уже в ПТУ? Молодец.

вот и я о том. А с какого перепугу вы решаете, что требуется, > а что не требуется? Вам вычислимость не требуется, а мне - > требуется.

При задании функции не требуется указывать ее вычислимость.

Говоришь о математике - используй привычные всем понятия.

Функция - это задание (однозначной) связи (отображения) между аргументами и результатом.

При задании функции не требуется указывать ее вычислимость.

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

ЗЫЖ довольно странно выглядит задача, которую не нужно решать, а нужность которой определяется исключительно для аргумента в споре о том, что функция != алгоритм.

А что ты сказать-то хотел?

По ссылке всё написано - про вычислимые и невычислимые функции, в том числе.

Например, проблема останова это функция вида Программы -> { Да, Нет }. Если «Программы» это программы любой универсальной машины Тьюринга, то эта функция невычислима, проблема неразрешима. Если ограничить язык «Программ», то она может стать разрешимой и алгоритмически эффективно реализуемой, проблема станет разрешимой, то есть станет возможно отсеивать все зависающие программы ещё до их выполнения, но при этом сам язык «Программ» перестанет быть Тьюринг-полным.

Все прочие неразрешимые проблемы тоже естественным образом представляются функциями, просто «быть функцией» это не значит «всегда можно обсчитать на вычислителе X программой P за конечное время T».

Говоришь о математике - используй привычные всем понятия.

изначально я говорил не о математике, я лишь использовал понятия из математике, применительно к LISP'у. Попрошу заметить, что мы сейчас не на экзамене - был-бы я вашим студентом, профессор, я-бы такого не сказал (дабы предупредить у вас инфаркт миокарда).

Функция - это задание (однозначной) связи (отображения) между аргументами и результатом.

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

По ссылке всё написано - про вычислимые и невычислимые функции, в том числе.

ну я прекрасно знаю, что там написано. Ты-то что сказать хотел? Может мне тебя отослать по этой ссылке: http://www.mobintech.ru/multiplication/ ?

Например, проблема останова это функция вида Программы -> { Да, Нет }. Если «Программы» это программы любой универсальной машины Тьюринга, то эта функция невычислима, проблема неразрешима. Если ограничить язык «Программ», то она может стать разрешимой и алгоритмически эффективно реализуемой, проблема станет разрешимой, то есть станет возможно отсеивать все зависающие программы ещё до их выполнения, но при этом сам язык «Программ» перестанет быть Тьюринг-полным.

да. Доказал. А ещё 6*7=42.

Все прочие неразрешимые проблемы тоже естественным образом представляются функциями, просто «быть функцией» это не значит «всегда можно обсчитать на вычислителе X программой P за конечное время T».

а я разве утверждал, что любой алгоритм можно обсчитать на вычислителе? Да ещё и за конечное время??? Ты меня не с кем не путал? Я лишь утверждал, что «математическая функция» эквивалентна «алгоритму». Но кто тебе сказал, что я уже научился хотя-бы формулировать эти алгоритмы в терминах какого-то ЯП? А уж тем более вычислять, да ещё и за конечное время?!

а я разве утверждал, что любой алгоритм можно обсчитать на вычислителе?

Ты спросил «а где здесь „функция“?» про проблему останова и прочие подобные проблемы, как будто функция это всегда алгоритм. CT тезис утверждает, что функция это алгоритм («an algorithm is an effective method expressed as a finite list[1] of well-defined instructions[2] for calculating a function.[3] Starting from an initial state and initial input (perhaps empty),[4] the instructions describe a computation that, when executed, will proceed through a finite [5] number of well-defined successive states, eventually producing „output“[6] and terminating at a final ending state.», «A procedure which has all the characteristics of an algorithm except that it possibly lacks finiteness may be called a 'computational method' (Knuth 1973:5)») только когда она эффективно вычислима («An effective method for calculating the values of a function is an algorithm; functions with an effective method are sometimes called effectively calculable.»), то есть её «всегда можно обсчитать на [тьюринг-полном] вычислителе X программой P за конечное время T». Обратно, всякий алгоритм это функция.

а я разве утверждал, что любой алгоритм можно обсчитать на вычислителе? Да ещё и за конечное время?

Штоа? Ты не хочешь утверждать, что любой алгоритм работает за конечное время?

«математическая функция» эквивалентна «алгоритму»

Ты хочешь сказать «вычислительному методу»? А то я попрошу тебя написать универсальный termination checker для языка си который статически отловит все зависания и дедлоки, раз уж «математическая функция» эквивалентна «алгоритму».

Обратно, всякий алгоритм это функция.

Э... да, но не в том смысле (алгоритм в смысле «программа для машины Тьюринга» есть последовательность команд, т.е., функция из отрезка [1..n] натурального ряда в множество команд). А так это совсем не функция, а то сортировка одна (забили на стабильность), а квиксорт всё-таки отличается от пузырька.

да, но не в том смысле

Всякая алгоритмически вычислимая функция имеет реализацию в виде своего алгоритма (эффективного метода).

и

Всякий алгоритм реализует (является эффективным методом) некую функцию (квиксорт и пузырёк реализуют функции у которых одинаковы области определения и значений, и одно и то же однозначное соответствие между ними)

Так?

Всякий алгоритм реализует ... некую функцию

Тут либо надо добавить «частичную», либо углубиться в семантику Скотта.

Ты спросил «а где здесь „функция“?» про проблему останова и прочие подобные проблемы, как будто функция это всегда алгоритм. CT тезис утверждает, что функция это алгоритм («an algorithm is an effective method expressed as a finite list[1] of well-defined instructions[2] for calculating a function.[3]

ох... Это не просто „алгоритм“, а вычислимый за ограниченное время на машине Тьюринга алгоритм. Даже тривиальный алгоритм „ничего не делай“ невычисляем на машине Тьюринга (что-то она _сделать_ всё равно должна). Кроме того, на машине Тьюринга невычисляем тривиальный бесконечный цикл сишечки - либо оно стоит, либо прыгает между _двумя_ состояниями. А в сишечке состояние одно. Потому, любой _алгоритм_ в смысле Тьюинга не является алгоритмом в смысле сишечки. Или скажем в смысле ЛИСПа.

Штоа? Ты не хочешь утверждать, что любой алгоритм работает за конечное время?

я что идиот? Или мой комп уже прогоняет бесконечный цикл за 5 секунд?!

Ты хочешь сказать «вычислительному методу»? А то я попрошу тебя написать универсальный termination checker для языка си который статически отловит все зависания и дедлоки, раз уж «математическая функция» эквивалентна «алгоритму».

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

А так это совсем не функция, а то сортировка одна (забили на стабильность), а квиксорт всё-таки отличается от пузырька.

sort это и есть одна функция. Если её в очень узком смысле рассматривать. Если учесть стабильность, время, память, и самое главное - функции, которые используются этой функцией, то всё становится совсем не так просто. Фишка в том, что сортировка - это не тривиальная функция вообще-то, а составная.

надо добавить «частичную»

Если нетерминируемое вычисление не считать за алгоритм, то для тотальности достаточно подбирать всякий раз подходящую область определения, вроде _/_ : ℤ × ℤ \ {0} → ℤ.

либо углубиться в семантику Скотта.

Брать A ∪ {⊥} → B ∪ {⊥} вместо A → B?

Всякая алгоритмически вычислимая функция имеет реализацию в виде своего алгоритма (эффективного метода).

невычислимая тоже может иметь реализацию. А может и не иметь. Вот формула Стирлинга говорят тоже расходящаяся, что не мешает ей пользоваться (интересующиеся см. http://en.wikipedia.org/wiki/Stirling's_approximation ). Математики - они такие... У них только на ЛОРе всё просто, однозначно, и определённо.

Всякий алгоритм реализует (является эффективным методом) некую функцию (квиксорт и пузырёк реализуют функции у которых одинаковы области определения и значений, и одно и то же однозначное соответствие между ними)

вот тебе другой алгоритм:

• возьмём случайное число i
• и ещё одно j
• если если знаки i-j и a-a[j] разные, меняем a<->a[j]
• повторить алгоритм

этот алгоритм сходится, и за конечное число итераций сортирует любой массив со сколько угодно высокой вероятностью успеха. Его можно применить на практике. Но он не является детерминированным, и его нельзя выполнить на классической машине Тьюринга. Это как-то мешает называть данный алгоритм алгоритмом? Если добавить проверку упорядоченности результата, алгоритм будет сходится _всегда_, причём время его работы будет в большинстве случаев _лучше_ чем у пузырькового метода.

«алгоритм»

Перечитай первую часть первой главы первого тома Кнута. Алгоритм обладает свойством выполняться за конечное число шагов. Всё остальное это «вычислительный метод».

алгоритм «ничего не делай»

Там же - должен быть вывод (ввода может не быть).

невычисляем тривиальный бесконечный цикл

;) Так он вообще невычисляем и не является алгоритмом. При этом зависающие программы есть и там и там (нужно говорить «существует нетерминируемая программа», а не «невычисляем», ну и никак не «алгоритм»).

Потому, _алгоритм_ в смысле Тьюинга не является алгоритмом в смысле сишечки

Да ладно Тьюринга, пусть сначала «алгоритм» будет алгоритмом в общепринятом смысле этого слова, пусть даже в денотации сишки или x86.

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

Lang ∈ Set // Множество цепочек над словарём

halt-decision ⊆ Lang × {yes, no}

∀ (prog ∈ Lang)
  ∃ (ans ∈ {yes, no})
    ⟨prog, ans⟩ ∈ halt-decision

∀ (prog ∈ Lang)
  ∀ (ans ∈ {yes, no})
    ∀ (ans′ ∈ {yes, no})
      ⟨prog, ans⟩ ∈ halt-decision
        ∧ ⟨prog, ans′⟩ ∈ halt-decision
      ⇒ ans ≡ ans′

это определённо функция если принять следующие идеализации:

• Недетерминированное IO остаётся за рамками рассмотрения.
• Всякие дикие UB тоже, либо не допускаются вообще (компилятору вполне известно где UB, а где нет, он даже UB определённым образом оптимизировать может).
• Баги компилятора, архитектуры, библиотек и прочие внешние непредвиденные условия тоже остаются за рамками рассмотрения.

Осталось только закодировать это как алгоритм.

Фишка в том, что сортировка - это не тривиальная функция вообще-то, а составная.

Фишка в том, что это функция. Всё. А алгоритмы, её реализующие, бывают разные.

А может и не иметь.

Вот и отлично. halt-decision, например, тоже имеет аппроксимации который находят заведомо завершимые программы, но отбрасывают другие завершимые вместе с зависающими.

вот тебе другой алгоритм

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

Если добавить проверку упорядоченности результата

Тогда это снова алгоритм реализующий всё ту же функцию сортировки, да.

Недетерминированное IO остаётся за рамками рассмотрения

Хотя можно и с ним, если halt-decision это неточная аппроксимация (никогда не назовёт зависающую программой независающей, но не наоборот).

Перечитай первую часть первой главы первого тома Кнута. Алгоритм обладает свойством выполняться за конечное число шагов. Всё остальное это «вычислительный метод».

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

Там же - должен быть вывод (ввода может не быть).

ещё раз - в учебнике арифметики нет корней элементарных уравнений второй степени. Хотя основная теорема алгебры говорит, что их всегда два. Во первых потому, что арифметика не алгебра. Во вторых потому, что сначала проходят уравнения второй степени, а уж потом комплексные числа.

;) Так он вообще невычисляем и не является алгоритмом. При этом зависающие программы есть и там и там (нужно говорить «существует нетерминируемая программа», а не «невычисляем», ну и никак не «алгоритм»).

ок. моё понятие «алгоритм» шире твоего.

Да ладно Тьюринга, пусть сначала «алгоритм» будет алгоритмом в общепринятом смысле этого слова, пусть даже в денотации сишки или x86.

ну пусть будет в какой-то нотации.

Осталось только закодировать это как алгоритм.

ЭТО можно переписать более понятнее? я ничего не понял...

Фишка в том, что это функция. Всё. А алгоритмы, её реализующие, бывают разные.

IRL это не тривиальная функция, а суперпозиция других функций. Вот порядок внутри этой суперпозиции как раз и отличает сортировку пузырьком от qsort. Очевидно, если рассматривать sort как тривиальную, то это действительно «просто функция». Например как qsort из glibc (которая на самом деле не совсем qsort, да и чистая qsort тоже разной бывает, но вне glibc это не имеет значения).

В остальном все прекрасно

Ждем, когда CL поработит всё подряд.

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

ты определись - алгоритм это, или не алгоритм?

или покажи мне место, где я говорил «в строгом смысле»?

Тогда это снова алгоритм реализующий всё ту же функцию сортировки, да.

нет. Если добавить проверку, то время завершения становится неопределённым - может секунда, а может тысяча лет(а может никогда). Потому оно не подходит под твои строгие условия. ИЧСХ, IRL мы юзаем qsort, которая при определённых условиях может работать в миллион раз дольше обычного, что IRL диагностируется как «зависание» (нет такого юзера, который будет ждать миллион сек(>11суток), если в прошлый раз было достаточно одной)

halt-decision - это у него функция, которая по любой программе, на заданном языке, скажет останавливается она (yes) или нет(no). Это второй абзац.

А в третьем абзаце просто условие детерминированности half-decision. Т.е. там написано, что если (prog, ans) и (prog, ans') одновременно принадлежат half-decision множеству, то, следовательно, ans == ans'.

ок. моё понятие «алгоритм» шире твоего.

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

это-то я понял. Но всё равно смысла не распарсил...

IRL это не тривиальная функция

Определение «тривиальной функции» в студию.

а суперпозиция других функций.

То есть, функция.

ты определись - алгоритм это, или не алгоритм?

Ну это же просто конвенция. Если принять все условия отсюда, то нет.

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

One has to distinguish between algorithms that use the random input to reduce the expected running time or memory usage, but always terminate with a correct result in a bounded amount of time, and probabilistic algorithms, which, depending on the random input, have a chance of producing an incorrect result (Monte Carlo algorithms) or fail to produce a result (Las Vegas algorithms) either by signalling a failure or failing to terminate.

In the second case, random performance and random output, the term "algorithm" for a procedure is somewhat questionable. In the case of random output, it is no longer formally effective.[1] However, in some cases, probabilistic algorithms are the only practical means of solving a problem.[2]

нет.

а может никогда

Если я правильно понял - для «никогда» там вероятность исчезающе мала.

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

Открой википедию чтоле. Алгоритм завершается. Тчк.

открыл. прочитал. Стал читать дальше...

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

алгоритм может и никогда не выдать результат

Но если ты хочешь называть алгоритмом любую НЁХ на си или лиспе

кого волнует, чего я хочу? IRL часто задача _быстрее_ решается недетерминированным «алгоритмом», и никого не волнует, что это не алгоритм.

Определение «тривиальной функции» в студию.

для каждой железки набор тривиальных функций свой. Но я не встречал железок, с нативной сортировкой на месте массивов.

а суперпозиция других функций.

То есть, функция.

да. С другой стороны «алгоритм». Например, суперпозиция y=f1(f2(x)) может рассматриваться как алгоритм:

• применяем f2 к аргументу x
• применяем f1 к результату прошлого действия.

для каждой железки набор тривиальных функций свой.

А, то есть, математика тут ни при чём. Ясненько.

Значит, никакого отношения к математическим понятиям «алгоритм» и «функция» эта фигня не имеет.

С другой стороны «алгоритм». Например, суперпозиция y=f1(f2(x)) может рассматриваться как алгоритм:

Особенно, если f1 и f2 невычислимы.

One has to distinguish between algorithms that use the random input to reduce the expected running time or memory usage, but always terminate with a correct result in a bounded amount of time, and probabilistic algorithms, which, depending on the random input, have a chance of producing an incorrect result (Monte Carlo algorithms) or fail to produce a result (Las Vegas algorithms) either by signalling a failure or failing to terminate.

In the second case, random performance and random output, the term «algorithm» for a procedure is somewhat questionable. In the case of random output, it is no longer formally effective.[1] However, in some cases, probabilistic algorithms are the only practical means of solving a problem.[2]

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

Вот пока не придумали, я буду называть «алгоритмы» - «алгоритмами», как это вы сами делаете.

Если я правильно понял - для «никогда» там вероятность исчезающе мала.

да. Вероятность бесконечного большого времени бесконечно малая. Пусть это таких теоретиков как ты греет. Если ты спустишься со своего Олимпа, то ты можешь заметить, что вероятность вычисления за 1000 лет, IRL не так уж и мала. А на практике 1000 лет === бесконечность. Надеюсь с этим ты не станешь спорить (ближайшую тысячу лет хотя-бы).

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

достаточно для чего? Если он меня попросит описать некую функцию, а я скажу: эту функцию надо определить так:

y = ★(x)

А, то есть, математика тут ни при чём. Ясненько.

причём. у математиков тоже есть своя виртуальная машинка:

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

так они определяют тривиальное умножение и тривиальное сложение. Как определяют всё остальное - учат в школе.

С другой стороны «алгоритм». Например, суперпозиция y=f1(f2(x)) может рассматриваться как алгоритм:

Особенно, если f1 и f2 невычислимы.

ты не поверишь, но это не играет никакой роли.

этого будет достаточно для формализации?

Если он понимает, что такое ★, x и () - тогда да, а иначе - нет. Любой формализм нужно строить из уже известных вещей (аксиом\определений\теорем) и используя, скажем, логику или индукцию.

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

А достаточность определения определяется исходя из решаемой задачи естественно.

Кстати, а можно услышать твоё опр. алгоритма (со всеми доп. опр. используемыми в нём)? Интереса радия.

Любой формализм нужно строить из уже известных вещей

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

Стал читать дальше...

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

Формальные свойства алгоритмов

Завершаемость

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

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

у математиков тоже есть своя виртуальная машинка:

И какие же функции в ней «тривиальны»? Как именно отличить их от других?

ты не поверишь, но это не играет никакой роли.

Ты прав, не поверю. Понятие «алгоритм» вполне строгое, как бы ты сейчас ни пытался его размазать.

Кстати, а можно услышать твоё опр. алгоритма (со всеми доп. опр. используемыми в нём)? Интереса радия.

ИМХО это суперпозиция тривиальных функций.

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