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

Биринчидан, бундай таъриф алгоритм интуитив таърифининг моҳиятини акс эттириши,
иккинчидан эса, бундай таъриф формал аниқлик нуқтаи назаридан мукаммал бўлиши керак эди.
Бу муаммонинг тадқиқотчилари томонидан алгоритмнинг бир нечта таърифи ишлаб чиқилди. Аммо вақт ўтиши билан бу таърифларнинг ўзаро тенгкучлилиги аниқланди. Ана шу таъриф ҳозирги замон алгоритм тушунчасидир.
Алгоритм тушунчасини аниқлаш бўйича ёндашувларни уч асосий йўналишга бўлиш мумкин.
Биринчи йўналиш – эффектив ҳисобланувчи функция тушунчасини аниқлаш билан боғлиқ. Бу йўналиш бўйича А.Чёрч, К.Гёдел, С.Клинилар тадқиқот ишларини олиб бордилар.
1935 йилда, 1932-1935 йиллар давомида А.Чёрч ва С.Клини томонидан ўрганилган ва « - аниқланувчи функциялар» деб аталган, тўғри аниқланган ҳисобланувчи назарий-сонли функциялар синфининг хоссалари: « - аниқланувчи функциялар» синфи бизнинг интуитив тасаввуримиз бўйича ҳисобланувчи деб қараладиган ҳамма функцияларни қамраб олиши мумкин деган фикр туғдиради. Бу кутилмаган натижа эди.
Ж. Эрбраннинг битта ғояси асосида 1934 йилда К.Гёдел томонидан аниқланган ва «умумрекурсив функциялар» деб аталган бошқа ҳисобланувчи функциялар синфи ҳам « - аниқланувчи функциялар» хоссаларига ўхшаш хоссаларга эга эди.
1936 йилда А.Чёрч ва С.Клини томонларидан бу иккита синф бир хил синф эканлиги исботланди, яъни ҳар қандай - аниқланувчи функция умумрекурсив функция бўлиши ва ҳар қандай умумрекурсив функция - аниқланувчи функция эканлиги тасдиқланди.
1936 йилда Чёрч қуйидаги тезисни эълон қилди: ҳар қандай интуитив эффектив (самарали) ҳисобланувчи функциялар умумрекурсив функциялар-дир.
Бу теорема эмас, балки тезисдир: тезис таркибида интуитив аниқланган эффектив ҳисобланув-чи функция тушунчаси, аниқ математик терминларда аниқланган умумрекурсив функция тушунчаси билан айнан тенглаштирилган. Шунинг учун ҳам бу тезисни исботлаш мумкин эмас. Аммо Чёрч ва бошқа олимлар томонидан бу тезисни қувватловчи кўп далиллар кўрсатилди.
Иккинчи йўналиш – алгоритм тушунчасини бевосита аниқлаш билан боғлиқ: 1936-1937 йилларда, А.Тьюринг Чёрч ишларидан бехабар ҳолда янги функциялар синфини киритди. Бу функцияларни «Тьюринг бўйича ҳисобланувчи функциялар» деб атадилар. Бу синф ҳам юқорида айтилган хоссаларга эга эди ва буни Тьюринг тезиси деб айтамиз. 1937 йилда А.Тьюринг исботладики, унинг ҳисобланувчи функциялари - аниқланувчи функцияларнинг ўзи ва, демак, умумрекурсив функцияларнинг худди ўзи экан. Шунинг учун ҳам Чёрч билан Тьюринг тезислари эквивалентдир.
1936 йилда (Тьюринг ишларидан бехабар ҳолда) Э.Пост айнан Тьюринг эришган натижаларга мос келадиган натижаларни эълон қилди ва 1943 йилда, 1920-1922 йиллардаги нашр этилмаган ишларига суяниб, тўртинчи эквивалент тезисни нашр этади. Шундай қилиб, алгоритм тушунчасини бевосита аниқлашга ва сўнгра унинг ёрдамида ҳисобланувчи функция тушунчасини аниқлашга биринчи бўлиб бир-биридан бехабар ҳолда Э.Пост ва А.Тьюринг эришдилар.
Пост ва Тьюринг алгоритмик процесслар маълум бир тузилишга эга бўлган «машина» бажарадиган процесслар эканлигини кўрсатдилар. Улар ушбу «машина»лар ёрдамида барча ҳисобланувчи функциялар синфи билан барча қисмий рекурсив функциялар синфи бир хил эканлигини кўрсатдилар ва, демак, Чёрч тезисининг яна битта фундаментал тасдиғи юзага келди.