Теорија израчунљивости, такође се зове и теорија рекурзије, је грана математичке логике, информатике и теорије израчунљивости је настала 1930-их са проучавањем израчунљивих функција и Тјурингових степена.
Основна питања упућена теорији рекурзије су Шта то значи за функцију над природним бројевима да буде израчунљива? и Како неизрачунљиве функције могу бити класификоване у хијерархију базирану на њиховом нивоу неизрачунљивости?. Одговори на ова питања вођена су до богате теорије која се и даље активно истражује. Поље је расло да укључи и проучавање генералисаних израчунљивости и дефинитивности. Изум централно комбинаторног објекта теорије рекурзије, названа Универзална Тјурингова машина, претходи и предодређује изум модерних рачунара. Историјски, проучавања алгоритамских неодлучивих скупова и функција су била мотивисана разним проблемима у математици који су постали неодлучиви; на пример,проблем речи за групе и слично. Постоји неколико примена теорије на осталим гранама математике које се не морају концентрисати на неодлувост. Ране примене укључују прослављену Хигманову теорију уграђивања која омогућава везу између теорије рекурзије и теорије групе, резултати Мајкл О. Рабина и Анатолија Малцева на алгоритамској презентацији алгебре, и решење негативног у Хилбертовом десетом проблему. Скорашње примене укључују алгоритамску случајност, резултат Соара, који је укључио рекурзивну-теоретску методу да би решио проблем у алгебарској геометрији, и недавни рад Сламана на нормалним бројевима који решавају проблем у теорији аналитичких бројева.
Рекурзија теорија поклапа се са теоријом доказа, теоријом ефективно описног сета, теоријом модела и апстрактном алгебром. Вероватно, теорија комплексности је дете теорије рекурзије; обе теорије деле исте техничке алате, то јест Тјурингова машина. Теоретичари рекурзије у математичкој логици често проучавају теорију релативне израчунљивости, смањење појмова и степена структура описаних у овом чланку. Ово је у супротности са теоријом субрекурзивне хијерархије, формалних метода и формалних језика који је уобичајен у истраживању теорије израчунљивости у рачунарству. Постоји знатан степен преклапања у знању и методама између ове две истраживачке заједнице; Међутим, ниједна снажна линија не може се исписати између њих. На пример, параметрисану комплексност изумео је еоретичар комплексности Мајкл Феловс и теоретичар рекурзије Род Дауни.
Израчунљиви и неизрачунљиви скупови Теорија рекурзије настала је 1930их, са радом Курта Гедела, Алонза Черча, Алана Тјуринга, Стефана Клинеа и Емила Поста.Many of these foundational papers are collected in The Undecidable (1965) edited by Martin Davis.
Добијени основни резултати истраживача утврдили су Тјурингову израчунљивост као тачну формализацију неформалне идеје ефективног рачунања. Ове резултате водили су Стефана Клинеа (1952) да кује два имена „Черчова теза(Клине 1952:300) и „Тјурингова теза(Клине 1952:376). Данас се оне често посматрају као једна хипотеза, Черч-Тјурингова теза, које наводе да је било која функција која је израчунљива помоћу алгоритама је и израчунљива функција. Иако у почетку скептичан, 1946 Гедел тврди у прилог овој тези: „Тарски је нагласио у својим предавањима (и ја мислим праведно) велики значај концепта опште рекурзивности (или Тјурингове израчунљивости). Чини ми се да је овај значај велики због чињенице да је са овим концептом по први пут добијен успех у давању апсолутне идеје ка интересантној епистомолошкој идеји, то јест, у независности од изабраног формализма.*The full paper can also be found at pages 150ff (with commentary by Charles Parsons at 144ff) in Feferman et al. editors 1990 , Oxford University Press, New York,. . (p. 150).
Са дефиницијом ефективног рачунања су дошли и први докази да су проблеми у математици који не могу бити ефективно одлучени. Черч (1936а, 1936б) и Тјуринг (1936), инспирисани техникама које је користио Гедел (1931) да докаже своју теореме непотпуности, независно је демонстрирао да Ајншајдунгспроблем није ефективно одлучив. Резултат је показао да тамо нема алгоритамских процедура које могу правилно одлучити да ли су произвољни математички искази истинити или лажни.
Многи проблеми у математици су били показани да буду неодлучиви након што су ови почетни примери били објављени. 1947, Марков и Пост објавили су независно радове показујући да проблем речи у семигрупама не може бити ефективно одлучив. Проширењем овог резултата, Петар Новиков и Вилијам Бун су независно показали 1950их да проблем речи у групама није ефективно решив: нема ефективне процедуре која, дајући реч у коначно представљеној групи, ће одлучити произвољни елемент предстаљен речју је елемент идентитета групе. 1970-е, Јури Матијасевич је доказао (користећи резултате Јулије Робинсон) Матијасевичову теорему, која имплицира да Хилбертов десети проблем нема ефективно решење; овај проблем пита произвољно да ефективна процедура одлучи произвољно да ли Диофантина једначина преко целих бројева има решење у целим бројевима. Листа неодлучивих проблема даје адекватни пример проблема са неизрачунљивим решењем.
Проучавање која математичка конструкција може бити ефективно изведена је понекад називана рекурзивна математика; Приручник рекурзивне математике (Ершов и др. 1998) покрива многе познате резултате у овој области.
Тјурингова израчунљивост Главни облик израчунљивости проучаван у теорији рекурзије је представио Тјуринг (1936). За скуп природних бројева је речено да буде израчунљив скуп(такође назван и одлучив, рекурзиван, или Тјуринг израчунљив скуп) ако постоји Тјурингова машина која, с обзиром на дати број н, се зауставља са излазом 1 ако је н у скупу и зауставља се са излазом 0 ако н није у скупу. Функција ф из природних бројева сами себи су рекурзивни или (Тјуринг) израчунљива функција ако постоји Тјурингова машина која, на излазу н, се зауставља и враћа излаз ф(н), Употреба Тјурингових машина овде није обавезна; постоје многи други модели израчунавања који имају исте израчунљиве моћи као Тјурингове машине; на пример μ-рекурзивна функција добијена од примитивне рекурзије и μ оператора.
Терминологија за рекурзивне функције и скупове није комплетно стандардизована. Дефиниција у појмовима μ-рекурзивних функција као и различите дениције рекурзивних функција Гедела вођена до традиционалног назива рекурзиван за скупове и функције израчунљив од стране Тјурингове машине. Реч одлучив потиче од немачке речи Ајншајдунгспроблем који је коришћен у оригиналним радовима Тјуринга и осталих. У савременој употреби, појам „израчунљива функција има различите дефиниције: према Кутланду (1980), је парцијално рекурзивна функција (која може бити недефинисана за неке улазе), док према Соару (1987) је тотално рекурзивна (еквивалентна, опште рекурзивна) функција. Овај чланак прати други од ових конвенција. Соар (1996) даје додатне коментаре о терминологији.
Није сваки скуп природних бројева израчунљив. Халтинг проблем, који је скуп (описа) Тјурингових машина које се заустављају на улазу 0, је и добро познат пример неизрачунљивог скупа. Постојање многих неизрачунљивих скупова произилази из чињенице да постоје само израчунљиво много Тјурингових машина, и на тај начин ових много само израчунљивих скупова, али постоје и неизрачунљиво много скупова природних бројева.
Иако Халтинг проблем није израчунљив, могуће је да симулира извршавање програма и произведе бесконачну листу програма које се заустављају. Тако је Халтинг проблем пример рекурзивно пребројив скуп, скуп који може бити набројив Тјуринговом машином (други услови за рекурзивно набројиве укључује и израчунљиво набројиве и полуодлучиве). Еквивалнтно, скуп је рекурзивно набројив ако и само ако је распон неке израчунљиве функције. Рекурзивно набројиви скупови, иако неодлучиви у општем, су проучавани детаљно у теорији рекурзије.
Области истраживања Почевши са теоријом рекурзивних скупова и функција описаних горе, област теорије рекурзије је расла да обухвати проучавање многих блиско повезаних тема. Оне нису независне области истраживања: свака од њих црпи идеје и резултате од осталих, и већина теоретичара рекурзије су упозната са већином њих.
Релативна израчунљивост и Тјурингови степени Теорија рекурзије у математичкој логици је традиционално фокусирана ка релативној израчунљивости, генерализација Тјурингове израчунљивости дефинисана је употребом Пророчке машине, представљену од стране Тјуринга (1939). Тјурингова пророчка машина је хипотетички уређај који, поред обављања поступака регуларне Тјурингове машине, има могучност да поставља питања о пророку, који је одређен скупом природних бројева. Пророчка машина може само постављати питања облика „Да ли је н у пророчком скупу?. Свако питање ће бити одмах одговорено правилно, чак и ако пророчки скуп није израчунљив. Таква пророчка машина са неизрачунљивим пророком ће бити у стању да израчуна скупове које Тјурингова машина без пророка не може.
Неформално, скуп природних бројева А је Тјуринг смањив скупу Б ако је тамо пророчка машина која тачно говори који бројеви су у А када се покрене са Б као пророчки скуп (у овом случају, скуп А је такође рекао да буде (релативно) израчунљив из Б и рекурзиван у Б). Ако је скуп А Тјуринг смањив скупу Б и Б је Тјуринг смањив скупу А онда је за скупове речено да имају исти Тјурингов степен (такође званих и као степен неразрешивости). Тјурингов степен скупа даје прецизну меру колико је скуп неизрачунљив.
Природни примери скупова који нису израчунљиви, укључујући и много различитих скупова који кодирају варијанте халтинг проблема, имају два својства у заједничком: Они су рекурзивно пребројиви, и Сваки се може превести у другу помоћу много-један смањења. То, с обзиром на дате скупове А и Б, тамо је укупна израчунљива фунскција ф таква да је A = {x : ф(x) ∈ Б}. За ове скупове се каже да су много-један еквивалентни (или м-еквивалентни).
Много-један смањења су „јача од Тјуринговог смањења: ако је скуп А много-један смањив скупу Б, онда је А Тјуринг смањив Б, али обрнуто се не држи увек. Иако су сви природни примери неизрачунљивих скупова много-један еквивалентни, могуће је конструисати рекурзивно пребројиве скупове А и Б таквих да је А Тјуринг смањив ка Б али није много-један смањив ка Б. Може се показати да је сваки рекурзивно пребројив скуп много-један смањив ка халтинг проблему, и такав халтинг проблем је највише компликовани рекурзивно пребројив скуп с обзиром ка много-један смањењу и Тјуринг смањењу. Пост (1944) је питао да ли је сваки рекурзивно пребројив скуп такође и израчунљив или Тјуринг еквивалентан халтинг проблему, то јест, да ли постоји рекурзивно пребројив скуп са Тјуринговим степеном у средини између њих двоје.
Као средње резултате, Пост дефинише природне типове рекурзивних пребројивих скупова као просте, хиперпросте и хиперхиперпросте. Пост је показао да су ови скупови стриктно између израчунљивих скупова и халтинг проблема с обзиром на много-један смањење. Пост је такође показао да су неки од њих стриктно средњи под другим појмовима смањења јачи него Тјурингово смањење. Али је Пост оставио отвореним главни проблем постојања рекурзивно пребројивих скупова средњег Тјуринговог степена; овај проблем је постао познат као Постов проблем. Након десет година, Клине и Пост су показали 1954.-е да је средњи Тјурингов степен између израчунљивих скупова и халтинг проблема, али нису успели да покажу да било који од ових степена садржи рекурзивно пребројив скуп. Врло брзо након тога, Фридберг и Мучник независно су решили постојање рекурзивно пребројивих скупова средњег степена. Овај револуционарни резултат је отворио широко проучавање Тјуринговог степена рекурзивно пребројивих скупова за које се испоставило да садрже веома компликовану и нетривијалну структуру,