Как вычислить логарифм от алгоритма?

[bin]

При обсуждении одной рукописи выявилась забавная опечатка: вместо

Цитата:

алгоритм логарифма

Имелся ввиду алгоритм вычисления логарифма, написано:

Цитата:

логарифм алгорифма

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

[AlexDem]

Более естественно взять гёделевскую нумерацию. Только это не смешно и смысла никакого

[Sicker]

Надо сначала определить сложение и умножение алгоритмов, а потом представить логарифм рядом

[warlock66613]

AlexDem в сообщении #1003023 писал(а):

смысла никакого

А вот интересно, как можно формализовать это утверждение (об отсутствии всякого смысла в логарифмах гёделевских номеров алгоритмов)? Ведь это утверждение явно содержательно, а значит (?) формализуемо.

[AlexDem]

warlock66613, ой, а у нас с Вами количество сообщений совпадает - $2929$, вот, казалось бы, какой в этом смысл?

(Оффтоп)

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

[bot]

AlexDem в сообщении #1004317 писал(а):

А отсутствие смысла, видимо, означает противоречивость теории

Без определения смысла, проблема его существования (или отсутствия) лишена смысла.

[AlexDem]

-- В чём смысл жизни?
-- 42.

(В своём изречении я нагрузил понятие смысла чуть меньшим смыслом - как наличие в высказывании кроме синтаксиса ещё и семантики, что увязал с наличием модели, относительно которой данное высказывание справедливо)

[warlock66613]

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

[AlexDem]

Ну это должна быть функция $f(x) = g \circ \ln(x)$, такая что если $n$ - гёделевский номер, то $f(n)$ - тоже гёделевский номер, причём существует такое $n$, что последовательная суперпозиция $f \circ \ldots \circ f \circ f(n)$ порождает все гёделевские номера. Можно поинтересоваться вычислимостью функции $f(n)$ (тут, похоже, ответ положительный, хотя боюсь провраться, ориентируюсь на такую цитату: "Оказывается, функцию, осуществляющую гёделеву нумерацию формул элементарной арифметики, можно сделать даже примитивно-рекурсивной." - ну а наша $f(x)$ не далеко ушла).