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

2. Ечилувчи ва саналувчи тўпламлар

Қандайдир алфавит берилган бўлсин. Бу алфавитдаги ҳамма сўзлар тўпламини билан ва тўпламнинг қисм тўпламини билан белгилаймиз.

1-таъриф. Агар сўзнинг тўпламга қарашлилик муаммосини ҳал қила оладиган алгоритм мавжуд бўлса, у ҳолда га ечилувчи тўплам деб айтилади.
2-таъриф. Агар тўпламнинг ҳамма элементларини санаб чиқа оладиган алгоритм мавжуд бўлса, у ҳолда га эффектив саналувчи тўплам деб айтилади.
1-теорема. Агар ва лар эффектив саналувчи тўпламлар бўлса, у ҳолда ва лар ҳам эффектив саналувчи тўпламлардир.
Исбот. ва лар эффектив саналувчи тўпламлар бўлсин. У вақтда, 2-таърифга асосан, уларнинг ҳар бири учун алоҳида алгоритм мавжудки, улар орқали мос равишда ва даги ҳамма элементларни санаб чиқиш мумкин. ва тўпламларнинг эффектив ҳисобловчи алгоритми ва тўпламларнинг эффектив ҳисобловчи алгоритм-ларини бир вақтда қўллаш натижасида ҳосил қилинади.
2-теорема (Пост теоремаси). тўпламнинг ўзи ва тўлдирувчиси эффектив саналувчи бўлсганда, шунда ва фақат шундагина тўплам ечилувчидир.
Исбот. а) тўплам ва унинг тўлдирувчиси эффектив саналувчи бўлсин. У вақтда, 2-таърифга асосан, бу тўпламларнинг элементларини санаб чиқа оладиган ва алгоритмлар мавжуд бўлади. У ҳолда ва тўпламларнинг элементларини санаб чиқиш пайтида уларнинг рўйхатида элемент учрайди. Демак, шундай алгоритм юзага келадики, у орқали тўпламга қарашлими ёки қарашли эмасми деган муаммони ҳал қилиш мумкин. Шундай қилиб, ечилувчи тўплам бўлади.
б) ечилувчи тўплам бўлсин. У ҳолда, 1-таърифга асосан, бу тўпламнинг элементими ёки элементи эмасми деган муаммони ҳал қилувчи алгоритм мавжуд бўлади. Бу алгоритмдан фойдаланиб, ва тўпламларга кирувчи элементларнинг рўйхатини тузамиз. Шундай қилиб, ва тўпламлар элементларини санаб чиқувчи иккита ва алгоритмларни ҳосил қиламиз.
Демак, ва тўпламлар эффектив саналувчи тўпламлар бўлади.