Өгөгдлийн шахалтын асуудал нь хамгийн энгийн хэлбэрээр тоонууд болон тэдгээрийн тэмдэглэгээтэй холбоотой байж болно. Тоонуудыг тоогоор тэмдэглэж болно ("арван нэгэн" 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 (болон түүний функциональ аналогууд) - мөн асуудал ийм програмыг туршихаас цааш явахгүй!
Бэрригийн парадоксоос ялгаатай нь тэмдэглэгээний албан бус байдал дээр баригдсан бол хоёр дахь тохиолдолд бид сайн далдлагдсан өөрчлөлттэй байна. . Хөтөлбөрийн үр дүнг хязгаарлагдмал хугацаанд тодорхойлох боломжгүй юм. Ялангуяа Колмогоровын нарийн төвөгтэй байдал : өгөгдсөн тооны хувьд энэ тоог хэвлэдэг хамгийн богино програмын уртыг олох алгоритм байхгүй; Энэ нь Берригийн асуудлыг шийдэх ямар ч шийдэл байхгүй гэсэн үг - өгөгдсөн тооны хамгийн богино аман тэмдэглэгээний уртыг олох.
Эх сурвалж: www.habr.com