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

1-мисол. натурал сонлар квадратлари тўплами эффектив саналувчи тўплам бўладими ёки йўқми?
Ечим. тўплам эффектив саналувчи тўплам бўлади, чунки унинг элементларини ҳосил этиш учун кетма-кет натурал сонларни олиб, уларни квадратга кўтариш керак. Бу тўплам ҳам ечилувчи бўлади. Ҳақиқатан ҳам, бирорта натурал соннинг тўпламга кириш ёки кирмаслигини аниқлаш учун уни туб кўпайтувчиларга ажратиш керак. Бу усул унинг натурал соннинг квадратими ёки йўқми деган муаммони ҳал қилиб беради.
2-мисол. Тартибланган натурал сонлар жуфтлик-ларидан иборат тўплам эффектив саналувчи экан-лигини исботланг.
Ечим. Тартибланган натурал сонлар жуфтлик-ларидан иборат тўпламнинг эффектив саналувчи эканлигини исботлаш учун диагонал методи деб айтиладиган методдан фойдаланамиз.
Бунинг учун ҳамма тартибланган натурал сонлар жуфтликларини қуйидаги кўринишда ёзамиз:


(0,0), (0,1), (0,2), (0,3), (0,4), ....

(1,0), (1,1), (1,2), (1,3), (1,4), ....

(2,0), (2,1), (2,2), (2,3), (2,4), ....

(3,0), (3,1), (3,2), (3,3), (3,4), ....

........................................................................
Юқори чап бурчакдан бошлаб кетма-кет диагоналлар бўйича ўтиб тўплам элементларини санаб чиқамиз. Бу жуфтликларнинг рўйхати қуйидагича бўлади:
(0,0), (1,0), (0,1), (2,0), (1,1), (0,2), (3,0), (2,1),
(1,2), (0,3), (4,0), (3,1), (2,2), (1,3), (0,4), ...... 3-теорема. Ечилувчи бўлмаган эффектив саналувчи натурал сонлар тўплами мавжуд.
Исбот. Эффектив саналувчи ихтиёрий натурал сонлар тўплами берилган бўлсин. тўпламнинг ечилувчи эмаслигини исботлаш учун, Пост теоремасига (2-теорема) кўра, унинг тўлдирувчиси эффектив саналувчи эмаслигини исботлаш етарли.
- ҳамма саналувчи натурал сонлар тўпламларидаги эффектив санаб чиқилган тўпламлар бўлсин.
Демак, ҳар қандай учун тўпламни тиклаш мумкин.
Энди тўпламнинг ҳамма элементларини санаб чиқадиган алгоритмни киритайлик. Бу алгоритм рақамли қадамда ни ҳисоблаб чиқади. Агар бу сон сони билан устма-уст тушса, бу ҳолда алгоритм уни тўпламига киритади, яъни .
Бундан кўриниб турибдики, ҳар қандай саналувчи тўпламдан тўплам ҳеч бўлмаганда битта элемент билан фарқ қилади, чунки шундай элементлардан иборатки, . Шунинг учун ҳам саналувчи тўплам эмас. Демак, Пост теоремасига асосан ечилувчи тўплам бўлмайди.
Изоҳ. Исбот этилган теорема аслида Гёделнинг формал арифметиканинг тўлиқсизлиги ҳақидаги теоремасини ошкормас (ошкора эмас) равишда қамраб олган.