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

[nepejvoda_n_n]

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

Comments

[mishafurman]

Здравствуй, Коля

[nepejvoda_n_n]

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

[mishafurman]

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

[nepejvoda_n_n]

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

[mishafurman]

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

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

[mishafurman]

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