Paradoxes ກ່ຽວກັບການບີບອັດຂໍ້ມູນ

ບັນຫາຂອງການບີບອັດຂໍ້ມູນ, ໃນຮູບແບບທີ່ງ່າຍດາຍທີ່ສຸດ, ສາມາດພົວພັນກັບຕົວເລກແລະຫມາຍເຫດຂອງມັນ. ຕົວເລກສາມາດສະແດງໂດຍຕົວເລກ ("ສິບເອັດ" ສໍາ​ລັບ​ຈໍາ​ນວນ 11​)​, ສໍາ​ນວນ​ທາງ​ຄະ​ນິດ​ສາດ ("ສອງໃນສິບສອງ" ສໍາລັບ 1048576), ການສະແດງສະຕິງ ("ຫ້າເກົ້າ" ສໍາລັບ 99999), ຊື່ທີ່ເຫມາະສົມ ("ຈໍານວນຂອງສັດເດຍລະສານ" ສໍາລັບ 666, "ປີຂອງການເສຍຊີວິດຂອງ Turing" ສໍາ​ລັບ​ປີ 1954​)​, ຫຼື​ການ​ປະ​ສົມ​ໂດຍ​ຕົນ​ເອງ​. ການອອກແບບໃດກໍ່ຕາມແມ່ນເຫມາະສົມທີ່ interlocutor ສາມາດກໍານົດຢ່າງຊັດເຈນວ່າຈໍານວນທີ່ພວກເຮົາເວົ້າກ່ຽວກັບ. ແນ່ນອນ, ບອກ interlocutor ຂອງທ່ານ "ໂຮງງານຂອງແປດ" ປະສິດທິພາບຫຼາຍກ່ວາ notation ທຽບເທົ່າ "ສີ່ສິບພັນສາມຮ້ອຍຊາວ". ຄຳຖາມທີ່ມີເຫດຜົນເກີດຂຶ້ນຢູ່ບ່ອນນີ້: ໝາຍເຫດສັ້ນທີ່ສຸດສຳລັບຕົວເລກໃດ?

ນັກປັດຊະຍາ Bertrand Russell ຈັດພີມມາໃນປີ 1908 "ຄວາມຂັດແຍ້ງຂອງເບີຣີ", ເຊິ່ງສໍາຜັດກັບບັນຫາຂອງຫມາຍເລກຈາກຂ້າງກົງກັນຂ້າມ: ຕົວເລກນ້ອຍທີ່ສຸດທີ່ບໍ່ຕ້ອງການແປດສິບຕົວອັກສອນແມ່ນຫຍັງ?
ຕົວເລກດັ່ງກ່າວຕ້ອງມີ: ຈາກແປດສິບຕົວອັກສອນພາສາລັດເຊຍແລະຊ່ອງຫວ່າງທີ່ທ່ານສາມາດສ້າງໄດ້ພຽງແຕ່ 3480 ການອອກແບບ, ຊຶ່ງຫມາຍຄວາມວ່າການໃຊ້ແປດສິບຕົວອັກສອນທ່ານສາມາດກໍານົດໄດ້ບໍ່ເກີນ 3480 ຕົວເລກ. ນີ້ຫມາຍຄວາມວ່າມັນເປັນໄປບໍ່ໄດ້ທີ່ຈະກໍານົດຈໍານວນທີ່ແນ່ນອນບໍ່ເກີນ 3480 ໃນທາງນີ້.

ນີ້ຫມາຍຄວາມວ່າຕົວເລກນີ້ຈະກົງກັນກັບການກໍານົດ "ຕົວເລກນ້ອຍທີ່ສຸດທີ່ແປດສິບຕົວອັກສອນບໍ່ພຽງພໍ", ເຊິ່ງມີພຽງແຕ່ 78 ຕົວອັກສອນ! ໃນອີກດ້ານຫນຶ່ງ, ຈໍານວນນີ້ຕ້ອງມີ; ໃນທາງກົງກັນຂ້າມ, ຖ້າຕົວເລກນີ້ມີຢູ່, ການກໍານົດຂອງມັນບໍ່ກົງກັນກັບມັນ. Paradox!

ວິທີທີ່ງ່າຍທີ່ສຸດທີ່ຈະປະຖິ້ມຄວາມຜິດຖຽງກັນນີ້ແມ່ນການອ້າງອີງເຖິງຄວາມບໍ່ເປັນທາງການຂອງຄໍາເວົ້າ. ເຊັ່ນດຽວກັນກັບ, ຖ້າຫາກວ່າພຽງແຕ່ຊຸດການສະແດງອອກສະເພາະໄດ້ຖືກອະນຸຍາດໃຫ້ຢູ່ໃນ notation, ຫຼັງຈາກນັ້ນ "ຕົວເລກນ້ອຍທີ່ສຸດທີ່ແປດສິບຕົວອັກສອນບໍ່ພຽງພໍ" ຈະບໍ່ເປັນ notation ທີ່ຖືກຕ້ອງ, ໃນຂະນະທີ່ notations ທີ່ເປັນປະໂຫຍດການປະຕິບັດເຊັ່ນ: "ໂຮງງານຂອງແປດ" ຈະຍັງຄົງເປັນທີ່ຍອມຮັບ.

ມີວິທີການທີ່ເປັນທາງການເພື່ອອະທິບາຍລໍາດັບ (ສູດການຄິດໄລ່) ຂອງການປະຕິບັດຕົວເລກ? ມີ, ແລະອຸດົມສົມບູນ - ເຂົາເຈົ້າເອີ້ນວ່າພາສາການຂຽນໂປລແກລມ. ແທນທີ່ຈະເປັນນາມສະກຸນ, ພວກເຮົາຈະໃຊ້ໂປຣແກຣມ (ຕົວຢ່າງ, ໃນ Python) ທີ່ສະແດງຕົວເລກທີ່ຕ້ອງການ. ຕົວຢ່າງ, ສໍາລັບຫ້າເກົ້າໂຄງການແມ່ນເຫມາະສົມ print("9"*5). ພວກເຮົາຈະສືບຕໍ່ມີຄວາມສົນໃຈໃນໂຄງການທີ່ສັ້ນທີ່ສຸດສໍາລັບຕົວເລກທີ່ກໍານົດ. ຄວາມຍາວຂອງໂຄງການດັ່ງກ່າວເອີ້ນວ່າ ຄວາມສັບສົນຂອງ Kolmogorov ຕົວເລກ; ມັນແມ່ນຂອບເຂດຈໍາກັດທາງທິດສະດີທີ່ຕົວເລກທີ່ກໍານົດສາມາດຖືກບີບອັດ.

ແທນ​ທີ່​ຈະ​ເປັນ paradox ຂອງ Berry​, ໃນ​ປັດ​ຈຸ​ບັນ​ພວກ​ເຮົາ​ສາ​ມາດ​ພິ​ຈາ​ລະ​ນາ​ທີ່​ຄ້າຍ​ຄື​ກັນ​: ຕົວເລກທີ່ນ້ອຍທີ່ສຸດທີ່ໂຄງການກິໂລໄບບໍ່ພຽງພໍກັບຜົນຜະລິດແມ່ນຫຍັງ?

ພວກເຮົາຈະໃຫ້ເຫດຜົນໃນລັກສະນະດຽວກັນກັບແຕ່ກ່ອນ: ມີບົດເລື່ອງ 2561024 ກິໂລໄບ, ຊຶ່ງຫມາຍຄວາມວ່າບໍ່ເກີນ 2561024 ຕົວເລກສາມາດອອກໄດ້ໂດຍໂຄງການກິໂລໄບ. ນີ້ຫມາຍຄວາມວ່າຕົວເລກທີ່ແນ່ນອນບໍ່ເກີນ 2561024 ບໍ່ສາມາດມາຈາກວິທີນີ້.

ແຕ່ໃຫ້ພວກເຮົາຂຽນໂປຼແກຼມໃນ Python ທີ່ສ້າງຂໍ້ຄວາມກິໂລໄບທີ່ເປັນໄປໄດ້ທັງຫມົດ, ດໍາເນີນການໃຫ້ພວກເຂົາສໍາລັບການປະຕິບັດ, ແລະຖ້າພວກເຂົາອອກຕົວເລກ, ຫຼັງຈາກນັ້ນເພີ່ມຕົວເລກນີ້ໃສ່ວັດຈະນານຸກົມຂອງຜູ້ທີ່ສາມາດບັນລຸໄດ້. ຫຼັງຈາກກວດເບິ່ງຄວາມເປັນໄປໄດ້ທັງຫມົດ 2561024, ບໍ່ວ່າມັນຈະໃຊ້ເວລາດົນນານ, ໂປລແກລມຊອກຫາຕົວເລກທີ່ນ້ອຍທີ່ສຸດທີ່ຫາຍໄປຈາກວັດຈະນານຸກົມແລະພິມຕົວເລກນັ້ນ. ມັນເບິ່ງຄືວ່າຈະແຈ້ງວ່າໂຄງການດັ່ງກ່າວຈະເຫມາະກັບກິໂລໄບຂອງລະຫັດ - ແລະຈະອອກຕົວເລກທີ່ບໍ່ສາມາດອອກໄດ້ໂດຍໂຄງການກິໂລໄບ!

ຕອນນີ້ຈັບໄດ້ຫຍັງ? ມັນ​ບໍ່​ສາ​ມາດ​ໄດ້​ຮັບ​ການ​ສະ​ຖານ​ທີ່​ບໍ່​ເປັນ​ທາງ​ການ​ຂອງ notation ໄດ້​!

ຖ້າທ່ານສັບສົນກັບຄວາມຈິງທີ່ວ່າໂຄງການຂອງພວກເຮົາຈະຕ້ອງການຄວາມຊົງຈໍາທາງດາລາສາດເພື່ອເຮັດວຽກ - ວັດຈະນານຸກົມ (ຫຼືອາເລບິດ) ຂອງ 2561024 ອົງປະກອບ - ຫຼັງຈາກນັ້ນທ່ານສາມາດເຮັດສິ່ງດຽວກັນໂດຍບໍ່ມີມັນ: ສໍາລັບແຕ່ລະຕົວເລກ 2561024, ໃນທາງກັບກັນ. , ໄປໂດຍຜ່ານທັງຫມົດ 2561024 ໂຄງການທີ່ເປັນໄປໄດ້, ຈົນກ່ວາບໍ່ມີຫນຶ່ງທີ່ເຫມາະສົມ. ມັນບໍ່ສໍາຄັນວ່າການຄົ້ນຫາດັ່ງກ່າວຈະມີເວລາດົນຫຼາຍ: ຫຼັງຈາກການກວດສອບຫນ້ອຍກວ່າ (2561024) 2 ຄູ່ຈາກຈໍານວນແລະໂຄງການ, ມັນຈະສິ້ນສຸດແລະຊອກຫາຕົວເລກທີ່ຫນ້າຮັກຫຼາຍນັ້ນ.

ຫຼືມັນຈະບໍ່ສໍາເລັດ? ແທ້ຈິງແລ້ວ, ໃນບັນດາໂຄງການທັງຫມົດທີ່ຈະພະຍາຍາມ, ຈະມີ while True: pass (ແລະ analogues ທີ່ເປັນປະໂຫຍດຂອງມັນ) - ແລະບັນຫາຈະບໍ່ໄປຫຼາຍກວ່າການທົດສອບໂຄງການດັ່ງກ່າວ!

ບໍ່ເຫມືອນກັບຄໍາອຸປະຖໍາຂອງ Berry, ບ່ອນທີ່ການຈັບໄດ້ຢູ່ໃນຄວາມບໍ່ເປັນທາງການຂອງ notation, ໃນກໍລະນີທີສອງ, ພວກເຮົາມີການປະຕິຮູບການປອມແປງທີ່ດີ. "ບັນຫາການຢຸດເຊົາ". ຄວາມຈິງແລ້ວແມ່ນວ່າມັນເປັນໄປບໍ່ໄດ້ທີ່ຈະກໍານົດຜົນຜະລິດຂອງມັນຈາກໂຄງການໃນເວລາກໍານົດ. ໂດຍສະເພາະ, ຄວາມສັບສົນ Kolmogorov incomputable: ບໍ່ມີ algorithm ທີ່ຈະອະນຸຍາດໃຫ້, ສໍາລັບຈໍານວນໃດຫນຶ່ງ, ເພື່ອຊອກຫາຄວາມຍາວຂອງໂປລແກລມສັ້ນທີ່ສຸດທີ່ຈະພິມຕົວເລກນີ້; ຊຶ່ງຫມາຍຄວາມວ່າບໍ່ມີການແກ້ໄຂບັນຫາຂອງ Berry - ເພື່ອຊອກຫາຄວາມຍາວຂອງຄໍາທີ່ສັ້ນທີ່ສຸດສໍາລັບຕົວເລກທີ່ກໍານົດ.

ແຫຼ່ງຂໍ້ມູນ: www.habr.com