ΠŸΠ°Ρ€Π°Π΄ΠΎΠΊΡΡ‹ ΠΎ сТатии Π΄Π°Π½Π½Ρ‹Ρ…

ΠŸΠ°Ρ€Π°Π΄ΠΎΠΊΡΡ‹ ΠΎ сТатии Π΄Π°Π½Π½Ρ‹Ρ… Π—Π°Π΄Π°Ρ‡Π° сТатия Π΄Π°Π½Π½Ρ‹Ρ… Π² своСй ΠΏΡ€ΠΎΡΡ‚Π΅ΠΉΡˆΠ΅ΠΉ Ρ„ΠΎΡ€ΠΌΠ΅ ΠΌΠΎΠΆΠ΅Ρ‚ ΠΎΡ‚Π½ΠΎΡΠΈΡ‚ΡŒΡΡ ΠΊ числам ΠΈ ΠΈΡ… обозначСниям. Числа ΠΌΠΎΠΆΠ½ΠΎ ΠΎΠ±ΠΎΠ·Π½Π°Ρ‡Π°Ρ‚ΡŒ Ρ‡ΠΈΡΠ»ΠΈΡ‚Π΅Π»ΡŒΠ½Ρ‹ΠΌΠΈ (Β«ΠΎΠ΄ΠΈΠ½Π½Π°Π΄Ρ†Π°Ρ‚ΡŒΒ» для числа 11), матСматичСскими выраТСниями (Β«Π΄Π²Π° Π² Π΄Π²Π°Π΄Ρ†Π°Ρ‚ΠΎΠΉΒ» для 1048576), строковыми выраТСниями (Β«ΠΏΡΡ‚ΡŒ дСвяток» для 99999), ΠΈΠΌΠ΅Π½Π°ΠΌΠΈ собствСнными («число звСря» для 666, Β«Π³ΠΎΠ΄ смСрти Π’ΡŒΡŽΡ€ΠΈΠ½Π³Π°Β» для 1954), ΠΈΠ»ΠΈ ΠΏΡ€ΠΎΠΈΠ·Π²ΠΎΠ»ΡŒΠ½Ρ‹ΠΌΠΈ ΠΈΡ… комбинациями. Годится любоС ΠΎΠ±ΠΎΠ·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅, ΠΏΠΎ ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΌΡƒ собСсСдник смоТСт ΠΎΠ΄Π½ΠΎΠ·Π½Π°Ρ‡Π½ΠΎ ΠΎΠΏΡ€Π΅Π΄Π΅Π»ΠΈΡ‚ΡŒ, ΠΎ ΠΊΠ°ΠΊΠΎΠΌ числС Ρ€Π΅Ρ‡ΡŒ. ΠžΡ‡Π΅Π²ΠΈΠ΄Π½ΠΎ, Ρ‡Ρ‚ΠΎ ΡΠΎΠΎΠ±Ρ‰ΠΈΡ‚ΡŒ собСсСднику Β«Ρ„Π°ΠΊΡ‚ΠΎΡ€ΠΈΠ°Π» восьми» эффСктивнСС, Ρ‡Π΅ΠΌ эквивалСнтноС ΠΎΠ±ΠΎΠ·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ «сорок тысяч триста Π΄Π²Π°Π΄Ρ†Π°Ρ‚ΡŒΒ». Π—Π΄Π΅ΡΡŒ Π²ΠΎΠ·Π½ΠΈΠΊΠ°Π΅Ρ‚ Π»ΠΎΠ³ΠΈΡ‡Π½Ρ‹ΠΉ вопрос: ΠΊΠ°ΠΊΠΎΠ΅ ΠΎΠ±ΠΎΠ·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ для Π·Π°Π΄Π°Π½Π½ΠΎΠ³ΠΎ числа самоС ΠΊΠΎΡ€ΠΎΡ‚ΠΊΠΎΠ΅?

Ѐилософ Π‘Π΅Ρ€Ρ‚Ρ€Π°Π½ РассСл Π² 1908 ΠΎΠΏΡƒΠ±Π»ΠΈΠΊΠΎΠ²Π°Π» «парадокс Π‘Π΅Ρ€Ρ€ΠΈΒ», ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ Π·Π°Ρ‚Ρ€Π°Π³ΠΈΠ²Π°Π΅Ρ‚ вопрос ΠΎΠ±ΠΎΠ·Π½Π°Ρ‡Π΅Π½ΠΈΠΉ чисСл с ΠΏΡ€ΠΎΡ‚ΠΈΠ²ΠΎΠΏΠΎΠ»ΠΎΠΆΠ½ΠΎΠΉ стороны: ΠΊΠ°ΠΊΠΎΠ΅ самоС малСнькоС число, для обозначСния ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠ³ΠΎ нСдостаточно Π²ΠΎΡΡŒΠΌΠΈΠ΄Π΅ΡΡΡ‚ΠΈ Π±ΡƒΠΊΠ²?
Π’Π°ΠΊΠΎΠ΅ число обязано ΡΡƒΡ‰Π΅ΡΡ‚Π²ΠΎΠ²Π°Ρ‚ΡŒ: ΠΈΠ· Π²ΠΎΡΡŒΠΌΠΈΠ΄Π΅ΡΡΡ‚ΠΈ русских Π±ΡƒΠΊΠ² ΠΈ ΠΏΡ€ΠΎΠ±Π΅Π»ΠΎΠ² ΠΌΠΎΠΆΠ½ΠΎ ΡΠΎΡΡ‚Π°Π²ΠΈΡ‚ΡŒ всСго 3480 ΠΎΠ±ΠΎΠ·Π½Π°Ρ‡Π΅Π½ΠΈΠΉ, Π·Π½Π°Ρ‡ΠΈΡ‚, с использованиСм Π²ΠΎΡΡŒΠΌΠΈΠ΄Π΅ΡΡΡ‚ΠΈ Π±ΡƒΠΊΠ² ΠΌΠΎΠΆΠ½ΠΎ ΠΎΠ±ΠΎΠ·Π½Π°Ρ‡ΠΈΡ‚ΡŒ Π½Π΅ Π±ΠΎΠ»Π΅Π΅ 3480 чисСл. Π—Π½Π°Ρ‡ΠΈΡ‚, Π½Π΅ΠΊΠΎΠ΅ число, Π½Π΅ большСС Ρ‡Π΅ΠΌ 3480, ΠΎΠ±ΠΎΠ·Π½Π°Ρ‡ΠΈΡ‚ΡŒ Ρ‚Π°ΠΊΠΈΠΌ ΠΎΠ±Ρ€Π°Π·ΠΎΠΌ Π½Π΅Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎ.

Π—Π½Π°Ρ‡ΠΈΡ‚, этому числу Π±ΡƒΠ΄Π΅Ρ‚ ΡΠΎΠΎΡ‚Π²Π΅Ρ‚ΡΡ‚Π²ΠΎΠ²Π°Ρ‚ΡŒ ΠΎΠ±ΠΎΠ·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ «самоС малСнькоС число, для обозначСния ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠ³ΠΎ нСдостаточно Π²ΠΎΡΡŒΠΌΠΈΠ΄Π΅ΡΡΡ‚ΠΈ Π±ΡƒΠΊΠ²Β», Π² ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΌ всСго 78 Π±ΡƒΠΊΠ²! Π‘ ΠΎΠ΄Π½ΠΎΠΉ стороны, это число обязано ΡΡƒΡ‰Π΅ΡΡ‚Π²ΠΎΠ²Π°Ρ‚ΡŒ; с Π΄Ρ€ΡƒΠ³ΠΎΠΉ, Ссли это число сущСствуСт, Ρ‚ΠΎ Π΅Π³ΠΎ ΠΎΠ±ΠΎΠ·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ Π΅ΠΌΡƒ Π½Π΅ соотвСтствуСт. ΠŸΠ°Ρ€Π°Π΄ΠΎΠΊΡ!

Π‘Π°ΠΌΡ‹ΠΉ простой способ ΠΎΡ‚ΠΌΠ°Ρ…Π½ΡƒΡ‚ΡŒΡΡ ΠΎΡ‚ этого парадокса β€” ΡΠΎΡΠ»Π°Ρ‚ΡŒΡΡ Π½Π° Π½Π΅Ρ„ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½ΠΎΡΡ‚ΡŒ словСсных ΠΎΠ±ΠΎΠ·Π½Π°Ρ‡Π΅Π½ΠΈΠΉ. Мол, Ссли Π±Ρ‹ Π² обозначСниях допускался лишь ΠΊΠΎΠ½ΠΊΡ€Π΅Ρ‚Π½ΠΎ ΠΎΠΏΡ€Π΅Π΄Π΅Π»Ρ‘Π½Π½Ρ‹ΠΉ Π½Π°Π±ΠΎΡ€ Π²Ρ‹Ρ€Π°ΠΆΠ΅Π½ΠΈΠΉ, Ρ‚ΠΎ «самоС малСнькоС число, для обозначСния ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠ³ΠΎ нСдостаточно Π²ΠΎΡΡŒΠΌΠΈΠ΄Π΅ΡΡΡ‚ΠΈ Π±ΡƒΠΊΠ²Β» Π½Π΅ Π±Ρ‹Π»ΠΎ Π±Ρ‹ допустимым ΠΎΠ±ΠΎΠ·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ΠΌ, Ρ‚ΠΎΠ³Π΄Π° ΠΊΠ°ΠΊ практичСски ΠΏΠΎΠ»Π΅Π·Π½Ρ‹Π΅ обозначСния Ρ‚ΠΈΠΏΠ° Β«Ρ„Π°ΠΊΡ‚ΠΎΡ€ΠΈΠ°Π» восьми» ΠΎΡΡ‚Π°Π»ΠΈΡΡŒ Π±Ρ‹ допустимыми.

Π•ΡΡ‚ΡŒ Π»ΠΈ Ρ„ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½Ρ‹Π΅ способы описания ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎΡΡ‚ΠΈ (Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ°) дСйствий Π½Π°Π΄ числами? Π•ΡΡ‚ΡŒ, ΠΈ Π² ΠΈΠ·ΠΎΠ±ΠΈΠ»ΠΈΠΈ β€” ΠΈΡ… Π½Π°Π·Ρ‹Π²Π°ΡŽΡ‚ языками программирования. Π‘ΡƒΠ΄Π΅ΠΌ вмСсто словСсных ΠΎΠ±ΠΎΠ·Π½Π°Ρ‡Π΅Π½ΠΈΠΉ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚ΡŒ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡ‹ (Π½Π°ΠΏΡ€ΠΈΠΌΠ΅Ρ€, Π½Π° Python), выводящиС Π½ΡƒΠΆΠ½Ρ‹Π΅ числа. НапримСр, для пяти дСвяток ΠΏΠΎΠ΄ΠΎΠΉΠ΄Ρ‘Ρ‚ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΠ° print("9"*5). По-ΠΏΡ€Π΅ΠΆΠ½Π΅ΠΌΡƒ Π±ΡƒΠ΄Π΅ΠΌ ΠΈΠ½Ρ‚Π΅Ρ€Π΅ΡΠΎΠ²Π°Ρ‚ΡŒΡΡ самой ΠΊΠΎΡ€ΠΎΡ‚ΠΊΠΎΠΉ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΠΎΠΉ для Π·Π°Π΄Π°Π½Π½ΠΎΠ³ΠΎ числа. Π”Π»ΠΈΠ½Ρƒ Ρ‚Π°ΠΊΠΎΠΉ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡ‹ Π½Π°Π·Ρ‹Π²Π°ΡŽΡ‚ колмогоровской ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒΡŽ числа; это тСорСтичСский ΠΏΡ€Π΅Π΄Π΅Π», Π΄ΠΎ ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠ³ΠΎ Π·Π°Π΄Π°Π½Π½ΠΎΠ΅ число ΠΌΠΎΠΆΠ½ΠΎ ΡΠΆΠ°Ρ‚ΡŒ.

ВмСсто парадокса Π‘Π΅Ρ€Ρ€ΠΈ Ρ‚Π΅ΠΏΠ΅Ρ€ΡŒ ΠΌΠΎΠΆΠ½ΠΎ Ρ€Π°ΡΡΠΌΠΎΡ‚Ρ€Π΅Ρ‚ΡŒ Π°Π½Π°Π»ΠΎΠ³ΠΈΡ‡Π½Ρ‹ΠΉ: ΠΊΠ°ΠΊΠΎΠ΅ самоС малСнькоС число, для Π²Ρ‹Π²ΠΎΠ΄Π° ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠ³ΠΎ нСдостаточно ΠΊΠΈΠ»ΠΎΠ±Π°ΠΉΡ‚Π½ΠΎΠΉ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡ‹?

Π Π°ΡΡΡƒΠΆΠ΄Π°Ρ‚ΡŒ Π±ΡƒΠ΄Π΅ΠΌ Ρ‚Π°ΠΊ ΠΆΠ΅, ΠΊΠ°ΠΊ ΠΈ Ρ€Π°Π½ΡŒΡˆΠ΅: сущСствуСт 2561024 ΠΊΠΈΠ»ΠΎΠ±Π°ΠΉΡ‚Π½Ρ‹Ρ… тСкстов, Π·Π½Π°Ρ‡ΠΈΡ‚, ΠΊΠΈΠ»ΠΎΠ±Π°ΠΉΡ‚Π½Ρ‹ΠΌΠΈ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΠ°ΠΌΠΈ ΠΌΠΎΠΆΠ½ΠΎ вывСсти Π½Π΅ Π±ΠΎΠ»Π΅Π΅ 2561024 чисСл. Π—Π½Π°Ρ‡ΠΈΡ‚, Π½Π΅ΠΊΠΎΠ΅ число, Π½Π΅ большСС Ρ‡Π΅ΠΌ 2561024, вывСсти Ρ‚Π°ΠΊΠΈΠΌ способом Π½Π΅Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎ.

Но напишСм Π½Π° Python ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡƒ, которая Π³Π΅Π½Π΅Ρ€ΠΈΡ€ΡƒΠ΅Ρ‚ всС Π²ΠΎΠ·ΠΌΠΎΠΆΠ½Ρ‹Π΅ ΠΊΠΈΠ»ΠΎΠ±Π°ΠΉΡ‚Π½Ρ‹Π΅ тСксты, запускаСт ΠΈΡ… Π½Π° Π²Ρ‹ΠΏΠΎΠ»Π½Π΅Π½ΠΈΠ΅, ΠΈ Ссли ΠΎΠ½ΠΈ выводят ΠΊΠ°ΠΊΠΎΠ΅-Ρ‚ΠΎ число β€” Ρ‚ΠΎ добавляСт это число Π² ΡΠ»ΠΎΠ²Π°Ρ€ΡŒ достиТимых. ПослС ΠΏΡ€ΠΎΠ²Π΅Ρ€ΠΊΠΈ всСх 2561024 возмоТностСй, сколько Π±Ρ‹ Π²Ρ€Π΅ΠΌΠ΅Π½ΠΈ это Π½ΠΈ заняло β€” ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΠ° ΠΈΡ‰Π΅Ρ‚, ΠΊΠ°ΠΊΠΎΠ΅ самоС малСнькоС число отсутствуСт Π² словарС, ΠΈ Π²Ρ‹Π²ΠΎΠ΄ΠΈΡ‚ это число. ΠšΠ°ΠΆΠ΅Ρ‚ΡΡ ΠΎΡ‡Π΅Π²ΠΈΠ΄Π½Ρ‹ΠΌ, Ρ‡Ρ‚ΠΎ такая ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΠ° улоТится Π² ΠΊΠΈΠ»ΠΎΠ±Π°ΠΉΡ‚ ΠΊΠΎΠ΄Π° β€” ΠΈ Π²Ρ‹Π²Π΅Π΄Π΅Ρ‚ Ρ‚ΠΎ самоС число, ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠ΅ Π½Π΅Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎ вывСсти ΠΊΠΈΠ»ΠΎΠ±Π°ΠΉΡ‚Π½ΠΎΠΉ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΠΎΠΉ!

Π’ Ρ‡Ρ‘ΠΌ ΠΆΠ΅ ΠΏΠΎΠ΄Π²ΠΎΡ… Ρ‚Π΅ΠΏΠ΅Ρ€ΡŒ? На Π½Π΅Ρ„ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½ΠΎΡΡ‚ΡŒ ΠΎΠ±ΠΎΠ·Π½Π°Ρ‡Π΅Π½ΠΈΠΉ Π΅Π³ΠΎ ΡΠΏΠΈΡΠ°Ρ‚ΡŒ ΡƒΠΆΠ΅ нСльзя!

Если вас смущаСт Ρ‚ΠΎ, Ρ‡Ρ‚ΠΎ наша ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΠ° ΠΏΠΎΡ‚Ρ€Π΅Π±ΡƒΠ΅Ρ‚ астрономичСского количСства памяти для Ρ€Π°Π±ΠΎΡ‚Ρ‹ β€” ΡΠ»ΠΎΠ²Π°Ρ€ΡŒ (ΠΈΠ»ΠΈ Π±ΠΈΡ‚ΠΎΠ²Ρ‹ΠΉ массив) ΠΈΠ· 2561024 элСмСнтов β€” Ρ‚ΠΎ ΠΌΠΎΠΆΠ½ΠΎ всё Ρ‚ΠΎ ΠΆΠ΅ самоС ΠΎΡΡƒΡ‰Π΅ΡΡ‚Π²ΠΈΡ‚ΡŒ ΠΈ Π±Π΅Π· Π½Π΅Π³ΠΎ: для ΠΊΠ°ΠΆΠ΄ΠΎΠ³ΠΎ ΠΈΠ· 2561024 чисСл ΠΏΠΎ ΠΎΡ‡Π΅Ρ€Π΅Π΄ΠΈ ΠΏΠ΅Ρ€Π΅Π±ΠΈΡ€Π°Ρ‚ΡŒ всС 2561024 Π²ΠΎΠ·ΠΌΠΎΠΆΠ½Ρ‹Ρ… ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌ, ΠΏΠΎΠΊΠ° Π½Π΅ найдётся подходящая. НС Π²Π°ΠΆΠ½ΠΎ, Ρ‡Ρ‚ΠΎ Ρ‚Π°ΠΊΠΎΠΉ ΠΏΠ΅Ρ€Π΅Π±ΠΎΡ€ продлится ΠΎΡ‡Π΅Π½ΡŒ Π΄ΠΎΠ»Π³ΠΎ: послС ΠΏΡ€ΠΎΠ²Π΅Ρ€ΠΊΠΈ ΠΌΠ΅Π½Π΅Π΅ Ρ‡Π΅ΠΌ (2561024)2 ΠΏΠ°Ρ€ ΠΈΠ· числа ΠΈ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡ‹ ΠΎΠ½ вСдь Π·Π°Π²Π΅Ρ€ΡˆΠΈΡ‚ΡΡ, ΠΈ Π½Π°ΠΉΠ΄Ρ‘Ρ‚ Ρ‚ΠΎ самоС Π·Π°Π²Π΅Ρ‚Π½ΠΎΠ΅ число.

Или Π½Π΅ Π·Π°Π²Π΅Ρ€ΡˆΠΈΡ‚ΡΡ? Π’Π΅Π΄ΡŒ срСди всСх ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌ, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ Π±ΡƒΠ΄ΡƒΡ‚ испробованы, встрСтится while True: pass (ΠΈ Π΅Ρ‘ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠΎΠ½Π°Π»ΡŒΠ½Ρ‹Π΅ Π°Π½Π°Π»ΠΎΠ³ΠΈ) β€” ΠΈ дальшС ΠΏΡ€ΠΎΠ²Π΅Ρ€ΠΊΠΈ Ρ‚Π°ΠΊΠΎΠΉ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡ‹ Π΄Π΅Π»ΠΎ ΡƒΠΆΠ΅ Π½Π΅ ΠΏΠΎΠΉΠ΄Ρ‘Ρ‚!

Π’ ΠΎΡ‚Π»ΠΈΡ‡ΠΈΠ΅ ΠΎΡ‚ парадокса Π‘Π΅Ρ€Ρ€ΠΈ, Π³Π΄Π΅ ΠΏΠΎΠ΄Π²ΠΎΡ… Π±Ρ‹Π» Π² Π½Π΅Ρ„ΠΎΡ€ΠΌΠ°Π»ΡŒΠ½ΠΎΡΡ‚ΠΈ ΠΎΠ±ΠΎΠ·Π½Π°Ρ‡Π΅Π½ΠΈΠΉ, Π²ΠΎ Π²Ρ‚ΠΎΡ€ΠΎΠΌ случаС ΠΌΡ‹ ΠΈΠΌΠ΅Π΅ΠΌ Ρ…ΠΎΡ€ΠΎΡˆΠΎ Π·Π°ΠΌΠ°ΡΠΊΠΈΡ€ΠΎΠ²Π°Π½Π½ΡƒΡŽ ΠΏΠ΅Ρ€Π΅Ρ„ΠΎΡ€ΠΌΡƒΠ»ΠΈΡ€ΠΎΠ²ΠΊΡƒ Β«ΠΏΡ€ΠΎΠ±Π»Π΅ΠΌΡ‹ остановки». Π”Π΅Π»ΠΎ Π² Ρ‚ΠΎΠΌ, Ρ‡Ρ‚ΠΎ ΠΏΠΎ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΠ΅ Π½Π΅Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎ Π·Π° ΠΊΠΎΠ½Π΅Ρ‡Π½ΠΎΠ΅ врСмя ΠΎΠΏΡ€Π΅Π΄Π΅Π»ΠΈΡ‚ΡŒ Π΅Ρ‘ Π²Ρ‹Π²ΠΎΠ΄. Π’ частности, колмогоровская ΡΠ»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ нСвычислима: Π½Π΅Ρ‚ Π½ΠΈΠΊΠ°ΠΊΠΎΠ³ΠΎ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ°, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ Π±Ρ‹ ΠΏΠΎΠ·Π²ΠΎΠ»ΠΈΠ» для Π·Π°Π΄Π°Π½Π½ΠΎΠ³ΠΎ числа Π½Π°ΠΉΡ‚ΠΈ Π΄Π»ΠΈΠ½Ρƒ самой ΠΊΠΎΡ€ΠΎΡ‚ΠΊΠΎΠΉ ΠΏΡ€ΠΎΠ³Ρ€Π°ΠΌΠΌΡ‹, выводящСй это число; Π° Π·Π½Π°Ρ‡ΠΈΡ‚, Π½Π΅Ρ‚ Ρ€Π΅ΡˆΠ΅Π½ΠΈΡ ΠΈ для Π·Π°Π΄Π°Ρ‡ΠΈ Π‘Π΅Ρ€Ρ€ΠΈ β€” Π½Π°ΠΉΡ‚ΠΈ для Π·Π°Π΄Π°Π½Π½ΠΎΠ³ΠΎ числа Π΄Π»ΠΈΠ½Ρƒ самого ΠΊΠΎΡ€ΠΎΡ‚ΠΊΠΎΠ³ΠΎ словСсного обозначСния.

Π˜ΡΡ‚ΠΎΡ‡Π½ΠΈΠΊ: habr.com

Π”ΠΎΠ±Π°Π²ΠΈΡ‚ΡŒ ΠΊΠΎΠΌΠΌΠ΅Π½Ρ‚Π°Ρ€ΠΈΠΉ