1. Алгоритм тушунчаси ва унинг характерли хусусиятлари. Ечилувчи ва саналувчи тўпламлар

3. Алгоритм тушунчасига аниқлик киритиш

Математика тарихида бир хил турдаги саволлар тўпламига «ҳа» ёки «йўқ» ёки бир хил турдаги функциялар синфи «ҳисобланувчи» ёки «ҳисобланувчи эмас» деган жавоблар бериши мумкин бўлган алгоритмларни излаш узоқ давом этди. Айрим вақтларда бу изланишлар натижасиз тугади.

Бу ҳолларда, табиийки, алгоритмнинг мавжудлигига шубҳа билан қаралади.
1-мисол. Мисол сифатида Ферманинг «буюк теорема»сининг ечиш муаммосини кўрсатиш мумкин. 1637 йиллар атрофида Ферма қуйидаги теореманинг исботи менда бор деб эълон қилди: « тенглама бўлганда мусбат бутун сон қийматли ечимга эга эмас». Ҳозирги кунгача бу тасдиқ на исбот қилинган ва на рад этилган.
2-мисол. 1900 йилда Парижда ўтказилган иккинчи халқаро математиклар конгрессида немис математиги Давид Гильберт ечилиши муҳим бўлган 23 математик муаммолар рўйхатини ўқиб берди. Шулар орасида қуйидаги 10-чи Гильберт муаммоси бор эди: «Ҳар қандай коэффициентлари бутун сонлардан иборат бўлган алгебраик тенгламанинг бутун сонли ечими мавжудми?», яъни ҳар қандай бутун сонли коэффициентлардан иборат бўлган алгебраик тенглама бутун сонли ечимга эгами деган муаммони ечадиган (ҳал қиладиган) алгоритм яратиш кераклигини Д.Гильберт кўрсатди.
Математикада бутун сонли коэффициентларга эга бўлган алгебраик тенгламага диофант тенгламаси деб айтилади.
Масалан,
,

кўринишдаги тенгламалар диофант тенгламалари бўлади, улардан биринчиси уч ўзгарувчили ва иккинчиси бир ўзгарувчили тенгламадир. Умумий ҳолда тенглама исталган сондаги ўзгарувчиларга боғлиқ бўлиши мумкин. Бундай тенгламалар бутун сонли ечимларга эга бўлиши ҳам, эга бўлмаслиги ҳам мумкин. Масалан, чексиз кўп бутун сонли ечимларга эга ва тенглама бутун сонли ечимга эга эмас.
Бир ўзгарувчили диофант тенгламасининг ҳамма бутун сонли ечимларини топиш алгоритми анчадан бери мавжуд. Аниқланганки, агар

бутун сонли коэффициентлардан иборат тенгламанинг бутун илдизи бўлса, у ҳолда у коэффициентнинг бўлувчиси бўлади.
Келтирилган тасдиққа асосланиб, қуйидаги алгоритмни тавсия этиш мумкин:
1) соннинг ҳамма бўлувчиларини топиш: .
2) соннинг ҳар бир бўлувчиси учун нинг қий-матини аниқлаш: .
3) Агар ларнинг бирорта учун бўлса, у ҳолда тенгламанинг ечими бўлади. Агар ларнинг ҳаммасида бўлса, у ҳолда тенглама бутун сонли ечимга эга эмас.
Гильбертнинг 10-муаммоси билан дунёнинг кўп математиклари деярли 70 йил шуғулландилар. Фақатгина 1968 йилда Санкт-Петербурглик ёш математик Ю.В.Матиясевич ва сал кейинроқ рус математиги Г.В.Чудновский бу муаммони ҳал қилдилар: қўйилган масаланинг ечимини бера оладиган алгоритм мавжуд эмас.
Алгоритмнинг интуитив таърифи қатъий эмаслигига қарамасдан, у муайан масаланинг ечимини топадиган алгоритмнинг тўғрилигига шубҳа уйғотмайди.
Математикада шундай ечими топилмаган алгоритмик муаммолар мавжудки, улар ечимга эгами ёки эга эмасми эканлигини аниқлаш муаммоси пайдо бўлади. Бу муаммони ечишда алгоритмнинг интуитив таърифи ёрдам бера олмайди. Бу ҳолларда ёки алгоритмнинг мавжудлигини, ёки унинг мавжуд эмаслигини исботлаш керак бўлади.
Биринчи ҳолда масалани ечадиган жараённи тасвирлаш кифоя. Бу жараённинг ҳақиқатан ҳам алгоритм эканлигига ишонч ҳосил қилиш учун алгоритмнинг интуитив тушунчаси етарли бўлади.
Иккинчи ҳолда алгоритмнинг мавжуд эмаслигини исботлаш керак. Бунинг учун алгоритмнинг нима эканлигини аниқ билиш талаб қилинади. ХХ асрнинг 30-йилларигача алгоритмнинг аниқ таърифи мавжуд эмасди. Шунинг учун ҳам алгоритм тушунчасига аниқ таъриф бериш кейинги давр математикасининг асосий масаласи бўлиб қолди. Бу таърифни ишлаб чиқиш кўп қийинчиликларга дуч келди.