Еще раз о пределе Чейтина

[nepejvoda_n_n]

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

Comments

[mishafurman]

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

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

[nepejvoda_n_n]

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

[mishafurman]

Все определяется сравнением, хотя слово тривиально может несколько сильно звучит. И зависит от времени.
В 50-60 это было нетривиально.
Сейчас этому тренируют в институтух. Именно тренируют - в своем бОльшинстве это стало техникой...
Причем под "этим" я имею в виду практические трансляторы/компилеры.интерпретаторы, от которых требуется производительность - что несколько сложнее...

[nepejvoda_n_n]

Беда в том, что в силу того же предела Чейтина натрен(дресс)ированный в одном, слишком часто становится полным тупицей во многом другом. ПОнимание программы на уровне формального описания семантики зачастую противоположно пониманию ее смысла.

[mishafurman]

Ну - во многом соглашусь. Но мой аргумент-то был был озвучен в совсем другом контексте.

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

[mishafurman]

Кстати, по поводу слохности: во времена моего учения (самый конец 60-х) интерпретатор машинного кода раальной машины (М20/БЭСМ4) - вещь сравнимая - был, хотя и очень хорошей, но курсовой/дипломной работой. Правда, в месте где в то время учили программированию хорошо.