АлгориФм vs АлгориТм

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

В ожеговском "Толковом словаре русского языка" ни "алгориФм", ни, тем более, "алгориТм", не значатся. А вот если заглянуть на страницу 786 "Математического энциклопедического словаря" (М., "Советская энциклопедия", 1988), то там можно прочитать, что в 1861 году Буняковский писал статью под названием "АлгориФм", а отнюдь не "АлгориТм". Кроме того, я лично видел статью про "алгориФм" в одном дореволюционном словаре, где это слово было написано через фиту, как и слова "арифметика" и "логарифм". Специально для Sonte поясняю: слово "математика" там писалось через "т" :(

Впрочем, может, это все дела давно минувших дней? Что ж, пойдем в направлении современности.

Н.Н.Лузин, почитаемый многими за бога от математики, об алгориТмах не имел никакого понятия. Чтобы в этом убедиться, достаточно заглянуть на стр.53 брошюры "Современное состояние теории функций действительного переменного" (М.-Л., ГТТИ, 1933).

Однако уже в томе 2 второго издания БСЭ (1950 год) гордо торчит статья об алгориТме. Ура! Значит, к этому моменту алгориФмы кончились! Но... ура ли? Автором статьи является Колмогоров, который слова "алгориФм" на дух не выносил, и, разумеется, перенес свои личные пристрастия в редактируемое им издание. И тот факт, что в статье про "алгориТм" А.Н. оказался вынужден (наверняка "скрипя сердцем" ;) ) пояснить, что под "алгориТмом" он понимает все же "алгориФм", о чем-то да говорит...

Действительно, если взять вышедшую в том же 1950 году (причем даже позже тома БСЭ с колмогоровской агиткой против правил русской грамматики!) первую книгу "Энциклопедии элементарной математики", то там можно обнаружить (хотя бы в оглавлении и предметном указателе, если лень лазить по тексту) и "алгориФм Евклида", и "алгориФмические числа", и много чего другого алгориФмического при полном отсутствии чего бы то ни было алгориТмического. Впрочем, может, и 1950 год - это седая древность? Тогда можно обратиться, например, к году 1968-му, когда Канторович, хамски плюя на колмогоровские седины, обозвал вычислительный процесс алгориФмом (на стр.7 брошюры "Математическое оптимальное программирование в экономике" ).

Число этих примеров может быть умножено и доведено до современности (я брал только ту литературу, которая у меня находится "под руками", старательно исключая при этом работы школы А.А.Маркова-младшего). Поэтому крайне интересно, имеются ли у сторонников "алгориТма" какие-то реальные аргументы в защиту их позиции, не сводящиеся к неопровержимому magister dixit ("а нас так научили" )?

С уважением,
Гастрит

P.S.: Некоторые грамотеи считают, что слово "поликлиника" должно писаться через "у": "полУклиника", так как означает де это слово "половина клиники". Не имеем ли мы в случае с "алгориТмом" другой пример такого же рода грамотности? :)

Цитата

egor писал(а) :
А также использование буквы "е" и внимательное отношение к "тся" и "ться". Речь идет о вкусах и обычаях.

Мне это, кстати, тоже нравится :) Но это не вопрос вкусов и обычаев - коль скоро буква "е" есть в языке, то поставь ее на ее место! Орфографические правила про "тся" и "ться" тоже, кажись, никто не отменял.

Цитата

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

Вопрос не в желании/нежелании. Вопрос в том, какое написание и произношение является правильным с точки зрения русской грамматики? Подчеркиваю: не английской, не немецкой, а именно русской.

Цитата

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

Видимо, да. Однако так, вроде, никто и не пишет. А вот "алгоритмы" достали, честное слово :(

С уважением,
Гастрит

Цитата

Игорь Абрамов писал(а) :
Не очень понятна Ваша аргументация, Гастрит.
Да, и впрямь, раньше писали алгориФм, а сейчас
принято алгориТм. Почему одно более правильно,
чем другое?

Если верить Колмогорову (чье свидетельство тем более ценно, что сам он писал "алгориТм" ), слово "алгорифм" произошло в результате смешения имени Аль Хорезми с греческим словом "число", от которого происходит также и термин "арифметика", который через "т" никто пока писать не предлагает.

Цитата

По крайней мере, Ф в слове алгориФм не родная, а приобретенная
впоследствии. Оригинально там ни ф и т не было.

В русском языке родная - фита. О чем я уже упоминал.

Цитата

Я не вижу никаких серьезных оснований в пользу написания
алгориФм. Скорее уж T, так же как и в приведенном Вами
слове маТематика. (Я что-то не могу сходу сообразить в каких словах
у нас -th- заимствуется как -Ф-, но допускаю, что такое наблюдается.
арифметика и кафедра тут не подходят, так как заимствованы
напрямую из греческого. И еще заметьте, Фома но Томас).

Именно потому, что Фома не Томас, а арифметика не аритметика - и алгорифм не алгоритм. Все они в дореформенном русском языке писались через фиту, которая теперь "ф" (не верите - перечитайте лесковского "Очарованного странника" ;) ), причем "арифметика" и "алгорифм" - даже однокоренные.

Цитата

Аргумент "сначала писали алгорифм" не очень сильный.
Раньше писали "шкап", а теперь "шкаф". Притом сейчас нормой является
не слишком правльное и благозвучное "бесконечность", а не
"безконечность".

"Безконечность" превратилась в "бесконечность" в результате реформы орфографии. Где и когда было законодательно решено превратить "алгорифм" в "алгоритм"?

С уважением,
Гастрит

Цитата

egor писал(а) :
Это не по теме, но по адресу (Гастриту и другим знатокам).

1. Насколько я понял, нет алгорифма, который по заданной монотонной ограниченной последовательности рациональных чисел x(n)строит "конструктивную оценку ее сходимости в себе" (кажется, это называют регуляризатором сходимости), т. е. для любого натурального E>0 строит такой номер N(E), что при n,m>N(eps) выполняется |x(n)-x(m)|<1/E.
Эквивалентная формулировка: нет алгорифма, который выделяет из ограниченной монотонной последовательности "регулярно сходящуюся" подпоследовательность
(например, такую, что |x(n(k))-x(n(k+1))|<2^{-k}).
Первый вопрос: действительно ли доказано, что такого алгорифма нет?

Гораздо хуже: в 1947 году указан (Шпекером) конкретный пример последовательности, для которой такой алгорифм невозможен.

Цитата

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

Можно вполне формально ее опровергнуть - правда, в предположении, что "группе хороших математиков" не удастся изыскать контрпример к тезису Черча.

Итак, вот конкретная задача.
Шаг 1: Занумеруем все нормальные алгорифмы в четырехбуквенном алфавите abcd. Аналогично, рассмотрим канторовскую нумерацию пар натуральных чисел n_1(k) и n_2(k).
Шаг 2: Рассмотрим ряд \sum_{k=1}^{\infty} C(k), где C(k) есть 2^{-n_1(k)}, если алгорифм с номером n_1(k) при применении его к своей записи в алфавите ab останавливается ровно на n_2(k)-ом шаге, и C(k)=0 в противном случае. Ясно, что частичные суммы ряда ограничены единицей. Однако наличие у этого ряда регулятора сходимости позволяло бы алгорифмически решать проблему применимости нормального алгорифма к своей записи, какова проблема доказуемо алгорифмически неразрешима :(

С уважением,
Гастрит

Цитата

egor писал(а) :
Спасибо за объяснение.

Цитата

Гастрит писал:
Итак, вот конкретная задача.
Шаг 1: Занумеруем все нормальные алгорифмы в четырехбуквенном алфавите abcd. Аналогично, рассмотрим канторовскую нумерацию пар натуральных чисел n_1(k) и n_2(k).
Шаг 2: Рассмотрим ряд \sum_{k=1}^{\infty} C(k), где C(k) есть 2^{-n_1(k)}, если алгорифм с номером n_1(k) при применении его к своей записи в алфавите ab останавливается ровно на n_2(k)-ом шаге, и C(k)=0 в противном случае. Ясно, что частичные суммы ряда ограничены единицей. Однако наличие у этого ряда регулятора сходимости позволяло бы алгорифмически решать проблему применимости нормального алгорифма к своей записи, какова проблема доказуемо алгорифмически неразрешима :(

Видимо, это и есть суть статьи Шпекера? Если нет, то хотелось бы ссылку :)

Примерно. Статья, правда, была (судя по названию - честно говоря, статьи как таковой я не читал) написана в терминах рекурсивных функций. То, что написал я, примерно соответствует изложению вопроса в "Теории алгорифмов" Маркова и Нагорного (глава "Алгорифмы и математический анализ" ). Там же есть и все ссылки на первоисточники :)

С уважением,
Гастрит

Только что прочитал:

Цитата

А. А. Марков "О конструктивных функциях", введение, п. 5
"Имеются системы ПРФ, осуществляющие взаимно однозначное отображение совокупности натуральных чисел на совокупность троек натуральных чисел и обратное отображение."

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

Цитата

Alopex писал(а) :
Дорогой Гастрит, в продолжение сообщения Игоря хочу Вам сказать, что, строго говоря, как это ни странно, следует говорить и писать именно "маФематика"* ( ставя на место "ф", разумеется, староорфографную фиту, а не "эф" ). И причина здесь в том, что в греческом языке есть две хитрые буквы, произношение которых временами сходно, и которое я попытаюсь сейчас изложить.

Знаю, уважаемый Alopex, знаю. На этом Sonte уже пытался меня ловить. Однако написание и произношение "математика" является каноническим уже на протяжении не одного столетия. Так что это слово следует отнести к исключениям.

В случае же с "алгоритмом" дело хитрее: параллельный вариант "алгорифм" продолжает жить, при этом на букву "ф" в однокоренном (!) слове "арифметика" (как и в "логарифм"'е) вообще никто не замахивается.

Цитата

Что же касается "алгорифма", то тут, как мне кажется, мы имеем дело с курьезом: уж очень это слово смахивает на греческое, да и, возможно, в том языке, из которого оно взято, произносилось или писалось именно со звуком "th", а потому "на автомате" для него была избрана русская фита, а не, быть может, более верное "т".

Известно, что надо делать, когда кажется :) Слову "алгорифм" не пятьдесят лет, как думают студенты, начинающие изучать программирование, а в десятки раз больше. И русским языком оно заимствовано явно не из английского ;)

И вообще - "т" в данном случае самая неверная из всех мыслимых букв. Если исходить из того, что термин происходит от имени Аль Хорезми, то надо ставить "з": "алгоризм". Если же учитывать последующее смешение термина с греческим "арифмос" (через 8-ую букву алфавита ;)), то в русском неэразмовском языке должна употребляться "ф", как и у других слов, связанных с этим корнем. У "математики" корень все же другой.

С уважением,
Гастрит

Цитата

Игорь Абрамов писал(а) :
Дело то в том, что в греческом языке слова алгори[тф]м не было.
И заимствовано оно, похоже, из немецкого (может из
французского, у меня нет данных было ли похожее слово
во французском в 18-19 веках.
В немецком (и впоследствии английском) оно писались через -th-,
что обычно в русском переходит в -т-. А стилизация под
греческий тут уже вторична, так как важен не только оригинал
написания/звучания, но и путь заимствования.

Вы знаете этот путь? Я, честно говоря, не вполне :(

Но сразу вопросы: почему именно из немецкого, и почему в 18-19 веках, а не в 15, например? В латинском языке соответствующий термин (пусть и писавшийся через "s" ) существовал аж в 11 столетии - вспомним разборки абацистов с алгорифмиками, в которых принимал участие еще папа Сильвестр II.

Цитата

У меня, кстати стало появляться подозрение,
нет ли неких тонких отличий в том, что понимается под алгоритмом,
от того, что понимается под алгорифмом.

Мне почему-то вспомнился анекдот про Ландау, который на вопрос "Чем отличается позиция Паули от позиции его оппонента X (не помню, о ком шла речь)" ответил "Тем, что Паули понимает, о чем говорит, а X - нет" :)

С уважением,
Гастрит

Цитата

egor писал(а) :
Неужели нельзя формализовать на конструктивных позициях конечные множества? Да, есть статья Маркова, в которой показано, что понятие "конечного множества" не монолитно. Но трудно поверить, что конечные множества, у которых все элементы могут быть записаны конечными словами (или натуральными числами), противоречат конструктивному подходу. При этом сам способ сведения к словам (или натуральным числам) часто не очень важен.
Ведь так приятно говорить на языке множеств и отображений в теории конечных групп, комбинаторике и т. п.

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

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

Главная задача состоит в том, чтобы не смешивать разные явления. Приятно говорить на языке множеств и отображений? Ради бога - но только не забывайте, что множества и отображения бывают разные. Одни "множества" дискретны и задаются, по существу, непосредственной нумерацией элементов. Другие же "множества" непрерывны, и задаются аппроксимативно: "интересующее нас местоположение с такой-то точностью задается узлом сетки номер такой-то". То же самое про отображения. Одни представляют собой алгорифмы. Другие представляют собой отношения ("множества пар", если угодно), для которых опровергнуто предположение о существовании такого X, что при любом Y пара {X,Y} не принадлежит нашему "множеству" - однако при этом алгорифма, переводящего X в Y, быть не может. Третьи отображения также задаются аппроксимативно, и т.д. В теоретико-множественной математике все эти градации затерты.

С уважением,
Гастрит

Цитата

Sonte писал(а):
Но меня больше всего занимает еще один вопрос [...] Когда слово 'алгоритм' (либо 'алгорифм') стало использоваться в современном значении? Когда и в каком языке это значение возникло? Когда появилось в русском языке? [...]

Поэтому просьба к Гастриту и всем желающим: посмотреть в доступных источниках, как употребляется и употребляется ли это слово? В частности, в каком контексте его упоминает Лузин? Что писал Буняковский? Когда и как это слово появилось в работах Маркова (знаю только статью 1947 года)? И так далее.

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

Цитата

Sonte писал(а) :
Продолжили любимое присловье Маркова "если алгоритм, то и аритметика" пародийным "...и наоборот, если алгорифм, то мафематика" задолго до меня, еще при жизни Андрея Андреевича.

Похоже, продолжатели знали русский (да и греческий) языки гораздо хуже Андрея Андреевича :( Слова "алгорифм" и "арифметика" - однокоренные; "алгорифм" и "математика" - не однокоренные.

Кстати: известно ли Вам, что Колмогоров, всю свою жизнь писавший "алгориТм", под конец жизни раскаялся и осознал всю неправильность такого написания? ;) Не верите - загляните в учебник Колмогорова и Драгалина :) :) :)

С уважением,
Гастрит