Пушыстый (_winnie) wrote,
Пушыстый
_winnie

Ягодный парадокс ( Berry Paradox )

"Минимальное1 положительное2 число,3 которое4 невозможно5 описать6 менее,7 чем8 тринадцатью9 словами10 русского11 языка12"

Эта фраза в 12 слов определяет некое число, которое невозможно определить менее чем в 13 слов.
Можно дать похожее описание не обязательно на русском, но и на каком-нибудь языке программирования, или в математической нотации.

Парадокс, однако!

Объяснение.

Функция количества букв, необходимых для записи числа - является невычислимой, так же как программа, определяющая, завершится ли программа (halting problem).
Кстати, если попытаться написать такое определение "в лоб" на каком-нибудь скриптовом языке, перечисляя все строки с программами, то имено в проблему останова она и уткнётся.
Но только там парадокс создают долго и нудно, для доказательства "от обратного", чертя всякие схемки на доске, а тут парадокс возникает прямо сразу.
Subscribe
  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 12 comments