Теорија израчунљивости (рачунарство)

Теорија израчунљивости, такође се зове и теорија рекурзије, је грана математичке логике, информатике и теорије израчунљивости је настала 1930-их са проучавањем израчунљивих функција и Тјурингових степена.

Основна питања упућена теорији рекурзије су Шта то значи за функцију над природним бројевима да буде израчунљива? и Како неизрачунљиве функције могу бити класификоване у хијерархију базирану на њиховом нивоу неизрачунљивости?. Одговори на ова питања вођена су до богате теорије која се и даље активно истражује. Поље је расло да укључи и проучавање генералисаних израчунљивости и дефинитивности. Изум централно комбинаторног објекта теорије рекурзије, названа Универзална Тјурингова машина, претходи и предодређује изум модерних рачунара. Историјски, проучавања алгоритамских неодлучивих скупова и функција су била мотивисана разним проблемима у математици који су постали неодлучиви; на пример,проблем речи за групе и слично. Постоји неколико примена теорије на осталим гранама математике које се не морају концентрисати на неодлувост. Ране примене укључују прослављену Хигманову теорију уграђивања која омогућава везу између теорије рекурзије и теорије групе, резултати Мајкл О. Рабина и Анатолија Малцева на алгоритамској презентацији алгебре, и решење негативног у Хилбертовом десетом проблему. Скорашње примене укључују алгоритамску случајност, резултат Соара, који је укључио рекурзивну-теоретску методу да би решио проблем у алгебарској геометрији, и недавни рад Сламана на нормалним бројевима који решавају проблем у теорији аналитичких бројева.

Рекурзија теорија поклапа се са теоријом доказа, теоријом ефективно описног сета, теоријом модела и апстрактном алгебром. Вероватно, теорија комплексности је дете теорије рекурзије; обе теорије деле исте техничке алате, то јест Тјурингова машина. Теоретичари рекурзије у математичкој логици често проучавају теорију релативне израчунљивости, смањење појмова и степена структура описаних у овом чланку. Ово је у супротности са теоријом субрекурзивне хијерархије, формалних метода и формалних језика који је уобичајен у истраживању теорије израчунљивости у рачунарству. Постоји знатан степен преклапања у знању и методама између ове две истраживачке заједнице; Међутим, ниједна снажна линија не може се исписати између њих. На пример, параметрисану комплексност изумео је еоретичар комплексности Мајкл Феловс и теоретичар рекурзије Род Дауни.

Израчунљиви и неизрачунљиви скупови

Теорија рекурзије настала је 1930их, са радом Курта Гедела, Алонза Черча, Алана Тјуринга, Стефана Клинеа и Емила Поста.

Добијени основни резултати истраживача утврдили су Тјурингову израчунљивост као тачну формализацију неформалне идеје ефективног рачунања. Ове резултате водили су Стефана Клинеа (1952) да кује два имена „Черчова теза(Клине 1952:300) и „Тјурингова теза(Клине 1952:376). Данас се оне често посматрају као једна хипотеза, Черч-Тјурингова теза, које наводе да је било која функција која је израчунљива помоћу алгоритама је и израчунљива функција. Иако у почетку скептичан, 1946 Гедел тврди у прилог овој тези:

„Тарски је нагласио у својим предавањима (и ја мислим праведно) велики значај концепта опште рекурзивности (или Тјурингове израчунљивости). Чини ми се да је овај значај велики због чињенице да је са овим концептом по први пут добијен успех у давању апсолутне идеје ка интересантној епистомолошкој идеји, то јест, у независности од изабраног формализма.*

Са дефиницијом ефективног рачунања су дошли и први докази да су проблеми у математици који не могу бити ефективно одлучени. Черч (1936а, 1936б) и Тјуринг (1936), инспирисани техникама које је користио Гедел (1931) да докаже своју теореме непотпуности, независно је демонстрирао да Ајншајдунгспроблем није ефективно одлучив. Резултат је показао да тамо нема алгоритамских процедура које могу правилно одлучити да ли су произвољни математички искази истинити или лажни.

Многи проблеми у математици су били показани да буду неодлучиви након што су ови почетни примери били објављени. 1947, Марков и Пост објавили су независно радове показујући да проблем речи у семигрупама не може бити ефективно одлучив. Проширењем овог резултата, Петар Новиков и Вилијам Бун су независно показали 1950их да проблем речи у групама није ефективно решив: нема ефективне процедуре која, дајући реч у коначно представљеној групи, ће одлучити произвољни елемент предстаљен речју је елемент идентитета групе. 1970-е, Јури Матијасевич је доказао (користећи резултате Јулије Робинсон) Матијасевичову теорему, која имплицира да Хилбертов десети проблем  нема ефективно решење; овај проблем пита произвољно да ефективна процедура одлучи произвољно да ли Диофантина једначина преко целих бројева има решење у целим бројевима. Листа неодлучивих проблема даје адекватни пример проблема са неизрачунљивим решењем.

Проучавање која математичка конструкција може бити ефективно изведена је понекад називана рекурзивна математика; Приручник рекурзивне математике (Ершов и др. 1998) покрива многе познате резултате у овој области.

Тјурингова израчунљивост

Главни облик израчунљивости проучаван у теорији рекурзије је представио Тјуринг (1936). За скуп природних бројева је речено да буде израчунљив скуп(такође назван и одлучив, рекурзиван, или Тјуринг израчунљив скуп) ако постоји Тјурингова машина која, с обзиром на дати број н, се зауставља са излазом 1 ако је н у скупу и зауставља се са излазом 0 ако н није у скупу. Функција ф из природних бројева сами себи су рекурзивни или (Тјуринг) израчунљива функција ако постоји Тјурингова машина која, на излазу н, се зауставља и враћа излаз ф(н), Употреба Тјурингових машина овде није обавезна; постоје многи други модели израчунавања који имају исте израчунљиве моћи као Тјурингове машине; на пример μ-рекурзивна функција добијена од примитивне рекурзије и μ оператора.

Терминологија за рекурзивне функције и скупове није комплетно стандардизована. Дефиниција у појмовима μ-рекурзивних функција као и различите дениције рекурзивних функција Гедела вођена до традиционалног назива рекурзиван за скупове и функције израчунљив од стране Тјурингове машине. Реч одлучив потиче од немачке речи Ајншајдунгспроблем који је коришћен у оригиналним радовима Тјуринга и осталих. У савременој употреби, појам „израчунљива функција има различите дефиниције: према Кутланду (1980), је парцијално рекурзивна функција (која може бити недефинисана за неке улазе), док према Соару (1987) је тотално рекурзивна (еквивалентна, опште рекурзивна) функција. Овај чланак прати други од ових конвенција. Соар (1996) даје додатне коментаре о терминологији.

Није сваки скуп природних бројева израчунљив. Халтинг проблем, који је скуп (описа) Тјурингових машина које се заустављају на улазу 0, је и добро познат пример неизрачунљивог скупа. Постојање многих неизрачунљивих скупова произилази из чињенице да постоје само израчунљиво много Тјурингових машина, и на тај начин ових много само израчунљивих скупова, али постоје и неизрачунљиво много скупова природних бројева.

Иако Халтинг проблем није израчунљив, могуће је да симулира извршавање програма и произведе бесконачну листу програма које се заустављају. Тако је Халтинг проблем пример рекурзивно пребројив скуп, скуп који може бити набројив Тјуринговом машином (други услови за рекурзивно набројиве укључује и израчунљиво набројиве и полуодлучиве). Еквивалнтно, скуп је рекурзивно набројив ако и само ако је распон неке израчунљиве функције. Рекурзивно набројиви скупови, иако неодлучиви у општем, су проучавани детаљно у теорији рекурзије.

Области истраживања

Почевши са теоријом рекурзивних скупова и функција описаних горе, област теорије рекурзије је расла да обухвати проучавање многих блиско повезаних тема. Оне нису независне области истраживања: свака од њих црпи идеје и резултате од осталих, и већина теоретичара рекурзије су упозната са већином њих.

Релативна израчунљивост и Тјурингови степени

Теорија рекурзије у математичкој логици је традиционално фокусирана ка релативној израчунљивости, генерализација Тјурингове израчунљивости дефинисана је употребом  Пророчке машине, представљену од стране Тјуринга (1939). Тјурингова пророчка машина је хипотетички уређај који, поред обављања поступака регуларне Тјурингове машине, има могучност да поставља питања о пророку, који је одређен скупом природних бројева. Пророчка машина може само постављати питања облика „Да ли је н у пророчком скупу?. Свако питање ће бити одмах одговорено правилно, чак и ако пророчки скуп није израчунљив. Таква пророчка машина са неизрачунљивим пророком ће бити у стању да израчуна скупове које Тјурингова машина без пророка не може.

Неформално, скуп природних бројева А је Тјуринг смањив скупу Б ако је тамо пророчка машина која тачно говори који бројеви су у А када се покрене са Б као пророчки скуп (у овом случају, скуп А је такође рекао да буде (релативно) израчунљив из Б и рекурзиван у Б). Ако је скуп А Тјуринг смањив скупу Б и Б је Тјуринг смањив скупу А онда је за скупове речено да имају исти Тјурингов степен (такође званих и као степен неразрешивости). Тјурингов степен скупа даје прецизну меру колико је скуп неизрачунљив.

Природни примери скупова који нису израчунљиви, укључујући и много различитих скупова који кодирају варијанте халтинг проблема, имају два својства у заједничком:

1. Они су рекурзивно пребројиви, и
2. Сваки се може превести у другу помоћу много-један смањења. То, с обзиром на дате скупове А и Б, тамо је укупна израчунљива фунскција ф таква да је  A = {x : ф(x) ∈ Б}. За ове скупове се каже да су много-један еквивалентни (или м-еквивалентни).

Много-један смањења су „јача од Тјуринговог смањења: ако је скуп А много-један смањив скупу Б, онда је А Тјуринг смањив Б, али обрнуто се не држи увек. Иако су сви природни примери неизрачунљивих скупова много-један еквивалентни, могуће је конструисати рекурзивно пребројиве скупове А и Б таквих да је А Тјуринг смањив ка Б али није много-један смањив ка Б. Може се показати да је сваки рекурзивно пребројив скуп много-један смањив ка халтинг проблему, и такав халтинг проблем је највише компликовани рекурзивно пребројив скуп с обзиром ка много-један смањењу и Тјуринг смањењу. Пост (1944) је питао да ли је сваки рекурзивно пребројив скуп такође и израчунљив или Тјуринг еквивалентан халтинг проблему, то јест, да ли постоји рекурзивно пребројив скуп са Тјуринговим степеном у средини између њих двоје.

Као средње резултате, Пост дефинише природне типове рекурзивних пребројивих скупова као просте, хиперпросте и хиперхиперпросте. Пост је показао да су ови скупови стриктно између израчунљивих скупова и халтинг проблема с обзиром на много-један смањење. Пост је такође показао да су неки од њих стриктно средњи под другим појмовима смањења јачи него Тјурингово смањење. Али је Пост оставио отвореним главни проблем постојања рекурзивно пребројивих скупова средњег Тјуринговог степена; овај проблем је постао познат као Постов проблем. Након десет година, Клине и Пост су показали 1954.-е да је средњи Тјурингов степен између израчунљивих скупова и халтинг проблема, али нису успели да покажу да било који од ових степена садржи рекурзивно пребројив скуп. Врло брзо након тога, Фридберг и Мучник независно су решили постојање рекурзивно пребројивих скупова средњег степена. Овај револуционарни резултат је отворио широко проучавање Тјуринговог степена рекурзивно пребројивих скупова за које се испоставило да садрже веома компликовану и нетривијалну структуру,

Постоје многи неизрачунљиви скупови који нису рекурзивно пребројиви, и истрага Тјурингових степена свих скупова као централну у теорији рекурзије као истрага рекурзивних пребројивих Тјурингових степена. Многи степени са посебним својствима су конструисани: хиперимуни-слободни степени где свака функција за израчунавање релативна у односу на тај степен је главна од стране (нерелативизирајуће) израчунљиве функције; високи степени релативни онима који могу израчунати функцију ф која доминира сваку израчунљиву функцију г у смислу да постоји константа ц у односу на г такву да је г (х) < ф (х) за све х>ц; случајни степени садже алгоритамски случајне скупове; 1-општи степени 1-општих скупова; и степени испод халтинг проблема лимитираних-рекурзивних скупова.

Проучавање случајних (не нужно рекурзивно пребројивих) Тјурингових степена укључују и проучавање Тјуринговог скока. С обзиром на скуп А, Тјурингов скок скупа А је скуп природних бројева кодирајући решење халтинг проблема за пророчке Тјурингове машине које раде са пророком А. Тјурингов скок било ког скупа је увек на вишем Тјуринговом степену него оригинални скуп, и Фрибургова теорема показује да било који скуп који израчунава халтинг проблем може бити добијен као Тјурингов скок другог скупа. Постова теорема успоставља блиске везе између операције Тјуринговог скока и аритметичке хијерархије, која је класификација одређених подгрупа природних бројева базираних на њиховим дефинисаностима у аритметици.

Најскорије истраживање Тјурингових степена је било фокусирано на структуру скупа Тјурингових степена и скупа Тјурингових степена који садрже рекурзивно пребројиве скупове. Дубока теорема Шореа и Сламана (1999) наводи да функција мапирања степена х на степен његовог Тјуринговог скока је дефинисана у делимичном редоследу Тјурингових степена. Недавно истраживање Амбос Спајса и Фејера (2006) даје преглед овог истраживања и историјски напредак.

Остала смањења

Стална област истраживања теорије рекурзије проучава односе смањења осталих осим Тјуринговог смањења. Пост (1944) је представио неколико јаких смањења, тако названих зато што оне улазе у истиниту-табелу смањења. Тјурингова машина имплементира да ће јака смањења израчунати укупну функцију без обзира са којим је пророком представљена. Слаба смањења су она где се процес смањења можда неће раскинути за све пророке; Тјурингово смањење је један пример.

Јака смањења укључују:

Смањење један-један

А је један-један смањиво (или 1-смањиво) ка Б ако је тамо укупна израчунљива инјективна функција ф таква да је свако н у А ако и само ако је ф (н) у Б.

Смањење много-један

Ово је у суштини један-један смањење без ограничења да ће ф бити инјективно. А је много-један смањиво (или м-смањиво) ка Б ако је тамо укупна израчунљива функција ф таква да је свако н у А ако и само ако је ф (н) у Б.

Смањење истина-табеле

А је истина-табела смањива ка Б ако је А Тјуринг смањива ка Б употребом пророчке Тјурингове машине која израчунава укупну функцију без обзира на пророк који је дат. Због компактности Кантор простора, ово је еквивалентно томе да се каже да смањење представља јединствену листу питања (зависи једино од улаза) ка пророку истовремено, и тада када виде своје одговоре могуће је да произведу излаз без додатних питања без обзира на пророчки одговор почетним улазима. Многе варијанте истина-табеле смањења су такође биле проучаване.

Даља смањења (позитивна, дисјункцивна, конјуктивна, линеарна и њихове слабе и ограђене верзије) се разматрају у чланку Смањење (теорија рекурзије).

Главно истраживање о јаким смањењима је да упореде своје теорије, како за класу свих рекурзивно пребројивих скупова, као и за класу свих подгрупа природних бројева. Осим тога, односи између смањења су били приучавани. На пример, познато је да је сваки Тјурингов степен такође истина-табела степена или је уједињење бесконачно много истина-табела степена.

Смањења слабија него Тјурингово смањење (то је, смањења која подразумевају Тјурингово смањење) су такође проучавана. Најпознатија су аритметичко смањење и хипераритметичко смањење. Ова смањења су уско повезана са дефинисаностима у односу на стандардни модел аритметике.

Рајсова теорема и аритметичка хијерархија

Рајс је показао да за сваку нетривијалну класу Ц (које садрже неке, али не сви поновни скупови) индексни скуп Е = {е: ЕТХ скуп Ве је у Ц} има својство да или халтинг проблем или њен комплемент је много-један смањив на Е, то јест, може да се преслика користећи много-један смањење у Е (види Рајсову теорему за више детаља). Али, многи од ових индексних скупова су још компликованији него халтинг проблем. Ова врста скупова  може бити класификована коришћењем аритметичке хијерархије. На пример, индексни скуп ФИН класе свих коначних скупова је на нивоу Σ2, индексни скуп РЕЦ класе свих рекурзивних скупова је на нивоу Σ3, индексни скуп ЦОФИН свих  скоро коначних скупова је такође на нивоу Σ3 и индексни скуп ЦОМП класе свих Тјуринг потпуних скупова Σ4. Ови хијерархијски нивои су индуктивно дефинисани, Σн+1 садржи само све скупове који су рекурзивно пребројиви у односу на Σн; Σ1 садржи рекурзивно пребројиве скупове. Индексни скупови дати овде су чак и потпуни за своје нивое, то јест, сви скупови у овим нивоима могу бити много-један смањени на датим индексним скуповима.

Обрнута математика

Програм обрнуте математике пита који скуп-постојања аксиома су неопходни да се докажу одређене теореме математике у подсистемима аритметике другог реда. Ово проучавање је иницирао Харвеј Фридман и било је проучавано у детаље од  стране Стефана Симпсона и других; Симпсон (1999) даје детаљну расправу програма. Скуп-постојања аксиома у питању одговарају неформално аксиомима говорећи да је моћан скуп природних бројева затворен под различитим смањењем појмова. Најслабији такав аксиом проучаван у обрнутој математици је рекурзивно разумевање, које наводи да је моћан скуп на природним затворен под Тјуринговим смањењем.

Нумерација

Нумерација је набрајање функција; има два параметра, Е и Х и излазе вредности е-те функције у нумерацији на улазу х. Нумерације могу бити делимично-рекурзивне иако су неки од њених чланова укупно рекурзивне, то јест, израчунљиве функције. Допустљиве нумерације су оне у којима се све друге могу превести. Фридбергова нумерација (названа по свом проналазачу) је један-један нумерација свих парцијалних-рекурзивних функција; неопходно је неприхватљива нумерација Каснија истраживања бавила су се и са нумерацијама друге класе као класе рекурзивно пребројивих скупова. Гончаров је открио на пример класу рекурзивно пребројивих скупова за које нумерације спадају у две класе тачно у вези са рекурзивним изоморфизмима.

Приоритетни метод

За даље објашњење, погледајте одељак Постов проблем и метод приоритета у члану Тјурингов степен.

Постов проблем је решен са методом која се зове метод приоритета; доказ користећи овај метод се зове приоритетна расправа. Ова метода се углавном користи за изградњу рекурзивно пребројивих скупова са одређеним особинама. Да бисте користили овај метод, жељене особине скупа који ће се градити су раскинуте у бескрајном спицку циљева, познатих као захтеви, тако да задовољавају све услове које ће изазвати скуп конструисан тако жељених особина. Сваки захтев је добио природан број који представља приоритет захтева; па 0 је додељен најважнији приоритет, 1 је друга најважнија, и тако даље. Скуп је затим изграђен у фазама, свака фаза покушава да задовољи један од више захтева било додавањем бројева сету или забрани бројева из скупа, тако да ће коначни скуп задовољити захтеве. Може се десити да ће задовољење једног услова изазвати остале да постану незадовољни; приоритет се користи да одлучи шта да раде у таквом догађају.

Приоритетни аргументи су били запослени да реше многе проблеме у теорији рекурзије, и они су класификовани у хијерархији на основу њихове сложености (Соар 1987). Због сложених приоритетних аргумената могу бити техничке и тешке за праћење, то се традиционално сматра пожељним да докаже резултате без приоритетних аргумената, или да видимо да ли резултати доказани приоритетним аргументима могу бити доказани и без њих. На пример, Кумер је објавио рад на доказу за постојање Фридбергове нумерације без методе приоритета.

Решетка рекурзивних сетова набрајања

Када је Пост дефинисао појам једноставног скупа као рекурзивно пребројив скуп са бесконачним додацима који не садржи никакав бескрајно рекурзивно пребројив скуп сет почео је да проучава структуру рекурзивно пребројивих скупова под инклузијом. Ова решетка је постала добро проучена структура. Рекурзивни скупови могу се дефинисати у овој структури основним резултатом да је скуп рекурзиван ако и само ако су скуп и његова допуна рекурзивно пребројиви. Бесконачни рекурзивно пребројиви скупови су увек бескрајне рекурзивне подгрупе; али са друге стране, једноставни скупови постоје, али немају скоро коначан рекурзивни надскуп. Пост (1944) је представио већ хиперпросте и хиперхиперпросте скупове; Касније максимални скупови су изграђени који су поново постављени тако да сваки рекурзивно пребројив надскуп је била коначна варијанта датог максималног скупа или је ко-коначна. Постова оригинална мотивација у проучавању ове решетке је била да се пронађе структурални појам такав да сваки скуп који задовољава овај објекат није ни у Тјуринговом степену рекурзивних скупова ни у Тјуринговом степену халтинг проблема. Пост није нашао такву имовину и решење за његов проблем примењује методе приоритетних уместо тога; Харингтон и Соаре (1991) су нашли на крају такве особине.

Аутоморфзни проблеми

Друго важно питање јесте постојање аутоморфизма у рекурзивно-теоретским конструкцијама. Једна од тих структура је да је један од рекурзивно пребројивих скупова по укључивању модула коначних разлика; у овој структури, А је испод Б ако и само ако је скуп разлика Б - А коначна. Максимални скупови (као што је дефинисано у претходном пасусу) имају особину да не могу бити аутоморфне ка немаксималним скуповима, то јест, ако постоји аутоморфизам рекурзивних пребројивих скупова по структури управо поменути, онда сваки максимални скуп се пресликава на други максимални скуп. Соаре (1974) је показао да се и обрнуто држи, то јест, свака два максимална скупа су аутоморфна. Тако максимални сетови формирају орбиту, то јест, сваки аутоморфизам чува максималност и било која два максимална скупа се трансформишу један у други помоћу неког аутоморфизма. Харингтон је дао још један пример једне аутоморфне имовине: да креативни скупови, скупови који су многи-један еквивалентни халтинг проблему.

Поред решетке рекурзивно пребројивих скупова, аутоморфизми су такође проучавани за структуре Тјурингових степена свих скупова, као и за структуре Тјурингових степена рекурзивно пребројивих скупова. У оба случаја, Купер тврди да су конструисали нетривијалне автоморфизме који мапирају неке степене према другим степенима; ова конструкција, међутим, није била верификована и неке колеге верују да изградња садржи грешке и да је питање да ли постоји нетривијални аутоморфизми Тјурингових степена и даље једно од главних нерешених питања у овој области (Сламан и Вудин 1986, Амбос Спајс и Фејер 2006).

Колмогорова комплексност

Област Колмогорове сложености и алгоритамске случајности је развијена током 1960-их и 1970-их од стране Чаитина, Колмогорова, Левина, Мартин-Лофа и Соломонофа (имена су овде дати по абецедном реду, велики део истраживања је независан, а јединство концепта случајности није тада схваћено). Основна идеја је да се размотри универзална Тјурингова Машина У и за мерење сложености броја (или стринга) х као дужина најкраће улаза п таквог да У(п) излаза х. Овај приступ револуцирао је раније начине да се одреди када је бесконачни низ (еквивалентно, карактеристична функција подскуп природних бројева) случајан или не позивајући се на идеју о случајности коначних објеката. Колмогорова комплексност је постала не само предмет независних проучавања, већ се такође примењује и на друге предмете као средство добијања доказа. Постоји још много отворених проблема у овој области. Из тог разлога, недавно истраживање конференција у овој области одржан је у јануару 2007. године и списак отворених проблема је одржаванод стране Јозефа Милера и Андреа Низа.

Учесталост рачунања

Ова грана теорије рекурзије анализирала је следеће питање: За фиксне м и н са 0 <м <н, за које је функција А могућа за израчунавање за било које другачије н улаза Х1, Х2..., Хн торка од н бројева У1, У2..., Ун тако да бар м једначине А (Хк) = Ук су истините. Такви скупови су познати као (м, н) -рекурзивни скупови. Први велики резултат у овој грани теорије рекурзије је Трактенбротов резултат који каже да је скуп израчунљив ако је (м, н) -рекурзивно за неко м, н са 2м> н. С друге стране, Јокушови семирекурзивни скупови су (који су већ неформално познати пре него што их је Јокуш увео 1968) примери скупа који је (м, н) -рекурзивни ако и само ако је 2м <н + 1. Постоје много неизрачунљиво ових скупова, као и неких рекурзивно пребројивих али неизрачунљивих скупова ове врсте. Касније, Дегтев је успоставио хијерархију рекурзивно пребројивих скупова који су (1, н + 1) -рекурзивни, али не (1, н) -рекурзивни. После дуге фазе истраживања руских научника, ова тема постала поново популаризована на западу од стране Бигелове тезе на ограђене упите, који је повезивао фреквенционално израчунавање до наведених ограничених смањења и других сродних појмова. Један од главних резултата је Кумерова Кардинална теорија којом се наводи да је скуп А израчунљив ако и само ако постоји н, такво да су неки алгоритам пребројава за сваку торку од н различитих бројева до Н много могућих избора кардиналности овог скупа од Н бројева испресецан са А; ови избори морају да садрже праве кардиналности, али изоставе бар једно лажно један.

Индуктивни закључак

Ово је рекурзибно-теоријска грана теорије учења. Он је заснован на Голдовом моделу учења у року од 1967. године и развијала од тада више и више модела учења. Генерални сценарио је следећи: С обзиром на класу С израчунљивих функција, постоји ученик (који је, рекурзивно функционалан) који излази за било који улаз облика (ф (0), ф (1)..., Ф (Н)) хипотеза. Ученик М сазнаје функцију Ф ако су скоро све хипотезе исти индекс Е од Ф у вези са претходно договореном прихватању нумерације свих израчунљивих функција; М сазнаје С ако М сазнаје сваку ф у С. Основни резултати су да су све рекурзивно пребројиве класе функције учљиве док класа РЕЦ свих израчунљивих функција није. Многи сродни модели су сматрали као и такође учење класа рекурзивно пребројивих скупова из позитивних података је тема проучавања Голдовог пионирског рада у 1967. па надаље.

Генерализације Тјурингове израчунљивости

Теорија рекурзије обухвата проучавање уопштених појмова из ове области, као што су аритметичко смањење, хипераритметичко смањење и  α-рекурзивне теорије, као што је описано од стране Сакса (1990). Ови генералисани појмови укључују смањења која се не могу извршавати Тјуринговим машинама, али су ипак природне генерализације о Тјуринговом смањењу. Ове студије обухватају приступе да се испита аналитичка хијерархија која се разликује од аритметичке хијерархије дозвољавајући квантификацију у преко скупова природних бројева у додатку квантификације преко појединих бројева. Ове области су повезане са теоријама добро-поређаних и стабала; На пример скуп свих индекса рекурзивних (небинарних) стабала, без бесконачних грана је комплетан за ниво $\Pi _{1}^{1}$ аналитичке хијерархије. Тјурингово смањење и хипераритметичко смањење су важни у области теорије ефективно описаног скупа. Још више општи појам степена израчунљивости је проучавана у теорији скупова.

Континуирана теорија израчунљивости

Теорија Израчунљивости за дигитално израчунавање је добро развијена. Теорија израчунљивости је мање развијена за аналогно израчунавање које се јавља код аналогних рачунара, обраде аналогног сигнала, аналогне електронике, неуронске мреже и теорије контроле континуираног времена, моделирану од стране диференцијалних једначина и континуираних динамичких система (Орпонен 1997; Мур 1996).

Односи између дефинитности, доказа и израчунљивости

Постоје блиски односи између Тјуринговог степена скупа природних бројева и тешкоћа (у смислу аритметичке хијерархије) дефинисања тог скупа користећи формулу првог реда. Један такав однос је прецизно образложен Постовом теоремом. Слабија веза је показана од стране Курта Гедела у доказима његове теореме потпуности и теореме непотпуности. Геделови докази показују да је скуп логичких последица ефикасне теорије првог реда рекурзивно пребројив скуп, и да, ако је теорија довољно јака овај скуп ће бити неизрачунљив. Слично томе, Тарскијева теорема недефинисаности може се тумачити у смислу дефинисаности и у смислу израчунљивости.

Теорија рекурзије је такође повезана са аритметиком другог реда, формалне теорије природних бројева и скупова природних бројева. Чињеница да су неки скупови израчунљиви или релативно израчунљиви често подразумева да ови скупови могу бити дефинисани у слабим подсистемима другог реда аритметике. Програм обрнуте математике користи ове подсистеме за мерење неизрачунљивости у веома добро познатим математичким теоремама. Симпсон (1999) разматра многе аспекте аритметике другог реда и обрнуте математике.

Област теорије доказивања обухвата проучавање аритметике другог реда и Пеано аритметике, као и формалне теорије природних бројева слабијих од Пеано аритметике. Један начин класификације снаге ових слабих система је карактеризацијом која израчунљива функција система може доказати да је укупна (види Фаиртлог и Вајнер (1998)). На пример, у примитивној рекурзивној аритметици било која израчунљива функција која је доказиво укупна је заправо примитивно рекурзивна, док Пеано аритметика показује да функције као Акерманова функција, које нису примитивно рекурзивне, су укупне. Није свака укупна израчунљива функција и доказиво укупна у Пеано аритметици, међутим; пример такве функције обезбеђује Гудштајнова теорема.

Назив предмета

Област математичке логике која се бави израчунљивошћу и њеним генерализацијама је названа "теорија рекурзије" од својих раних дана. Роберт И. Соаре, истакнути истраживач у области, је предложио (Соаре 1996) да област треба назвати "теорија израчунљивости" уместо. Он тврди да Тјурингова терминологија користи реч "израчунљив" је природније и шире схваћена од терминологије која користи реч "рекурзивна" коју је увео Клине. Многи савремени истраживачи су почели да користе ову алтернативну терминологију. Ови истраживачи такође користе терминологију, као што су делимичне израчунљиве функције и израчунљиви пребројиви (ИП) скупови уместо делимично рекурзивне функције и рекурзивно пребројиви (РП) скупови. Нису сви истраживачи били убеђени, међутим, како је објаснио Фортнов и Симпсон. Неки коментатори тврде да су имена теорија рекурзије и теорија израчунљивости не преносе чињеницу да је већина објеката испитиваних у теорији рекурзије нису израчунљиви.

Роџерс (1967) је предложио да је кључна имовина теорије рекурзије да њени резултати и структуре морају бити инваријантни под израчунљивим бијекцијама на природним бројевима (ова сугестија ослања се на идејама Ерланген програма у геометрији). Идеја је да се за израчунавање бијекције само преименује бројеви у скупу, уместо што указују на било који објекат у скупу, као и што ротација еуклидског авиона не мења геометријски аспект линија нацртаних на њему. Од било која две неконачно израчунљива скупа су везана за израчунавање бијекције, овај предлог идентификује све бескрајне израчунљиве скупове (коначни израчунљиви скупови су сматрале као тривијалне). Према Роџерсу, скупови интереса у теорији рекурзије су неизрачунљиви скупови, подељени у класе еквиваленције за израчунљиве бијекције  природних бројева.

Професионалне организације

Главна професионална организација за теорију рекурзије је Удружење за Симболичку Логику, која има неколико истраживачких конференција сваке године. Интердисциплинарно истраживачко Удружење Израчунљивости у Европи (ЦиЕ) организује низ годишњих конференција.

Види још

• Рекурзија (компјутерске науке)
• Логика израчунљивости
• Трансизрачунљив проблем

Литература

Преддипломски текстови

• S. B. Cooper (2004). Computability Theory. Chapman & Hall/CRC. ISBN 978-1-58488-237-4. 
• N. Cutland (1980). Computability, An introduction to recursive function theory. Cambridge University Press. ISBN 978-0-521-29465-2. 
• Y. Matiyasevich (1993). Hilbert's Tenth Problem. MIT Press. ISBN 978-0-262-13295-4. 

Напредни текстови

• S. Jain, D. Osherson, J. Royer and A. Sharma (1999). Systems that learn, an introduction to learning theory, second edition. Bradford Book. ISBN 978-0-262-10077-9. CS1 одржавање: Вишеструка имена: списак аутора (веза)
• S. Kleene (1952). Introduction to Metamathematics. North-Holland (11th printing; 6th printing added comments). ISBN 978-0-7204-2103-3. 
• M. Lerman (1983). Degrees of unsolvability. Perspectives in Mathematical Logic, Springer-Verlag. ISBN 978-3-540-12155-8. 
• Nies, Andre (2009). Computability and Randomness. Oxford University Press. 447 pages. ISBN 978-0-19-923076-1. .
• P. Odifreddi (1989). Classical Recursion Theory. North-Holland. ISBN 978-0-444-87295-1. 
• P. Odifreddi (1999). Classical Recursion Theory, Volume II. Elsevier. ISBN 978-0-444-50205-6. 
• H. Rogers, Jr. The Theory of Recursive Functions and Effective Computability. second edition 1987, MIT Press. ISBN 978-0-262-68052-3.  (paperback). . 1967. ISBN 978-0-07-053522-0. 
• G Sacks (1990). Higher Recursion Theory. Springer-Verlag. ISBN 978-3-540-19305-0. 
• S. G. Simpson (1999). Subsystems of Second Order Arithmetic. Springer-Verlag. ISBN 978-3-540-64882-6. 
• R. I. Soare (1987). Recursively Enumerable Sets and Degrees. Perspectives in Mathematical Logic, Springer-Verlag. ISBN 978-0-387-15299-8. 

Анкетни радови  и збирке

• K. Ambos-Spies and P. Fejer, 2006. "Degrees of Unsolvability." Unpublished preprint.
• J. Barwise, North-Holland . (1977). H. Enderton, 1977. "Elements of Recursion Theory." Handbook of Mathematical Logic, edited. North-Holland Publishing Company. стр. 527–566. ISBN 978-0-7204-2285-6. 
• Y. L. Ershov; S. S. Goncharov; A. Nerode; J. B. Remmel (1998). Handbook of Recursive Mathematics. North-Holland. ISBN 978-0-7204-2285-6. 
• M. Fairtlough and S. Wainer, 1998. "Hierarchies of Provably Recursive Functions". In Handbook of Proof Theory, edited by S. Buss, Elsevier (1998).
• Soare, Robert I. (1996). „Computability and Recursion”. Bulletin of Symbolic Logic. 2 (3): 284—321. JSTOR 420992. S2CID 5894394. doi:10.2307/420992. 

Истраживачки радови и збирке

• Burgin, Mark; Klinger, Allen (2004). „Experience, generations, and limits in machine learning”. Theoretical Computer Science. 317 (1/3): 71—91. doi:10.1016/j.tcs.2003.12.005. 
• Church, Alonzo (1936). „An Unsolvable Problem of Elementary Number Theory”. American Journal of Mathematics. 58 (2): 345—363. JSTOR 2371045. doi:10.2307/2371045. 
• A. Church, 1936b. "A note on the Entscheidungsproblem." . Journal of Symbolic Logic. 1.  , n. 1, and. . 3.  , n. 3. Reprinted in "The Undecidable", M. Davis ed., 1965.
• M. Davis, ур. (2004) [1965]. The Undecidable—Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions. New York: Raven. Reprint, Dover. ISBN 978-0-486-43228-1. 
• Friedberg, Richard M. (1958). „Three Theorems on Recursive Enumeration. I. Decomposition. II. Maximal Set. III. Enumeration Without Duplication”. The Journal of Symbolic Logic. 23 (3): 309—316. JSTOR 2964290. S2CID 25834814. doi:10.2307/2964290. .
• Gold, E. Mark (1967), Language Identification in the Limit (PDF) Gold, E Mark (1967). „Language identification in the limit”. Information and Control. 10 (5): 447—474. doi:10.1016/S0019-9958(67)91165-5. 
• L. Harrington and R. I. Soare, 1991. "Post's Program and incomplete recursively enumerable sets", Proceedings of the National Academy of Sciences of the USA, volume 88, pages 10242—10246.
• C. Jockusch jr, "Semirecursive sets and positive reducibility", Trans. Amer. Math. Soc. Trans. Amer. Math. Soc. 137: 420—436. 1968. 
• S. C. Kleene and E. L. Post, 1954. "The upper semi-lattice of degrees of recursive unsolvability." . Annals of Mathematics. 2 (59): 379—407. 1954.  .
• Moore, Cristopher (1996). „Recursion theory on the reals and continuous-time computation”. Theoretical Computer Science. 162: 23—44. CiteSeerX 10.1.1.6.5519 . doi:10.1016/0304-3975(95)00248-0. 
• Myhill, John (1956). „Problems in symbolic logic”. The Journal of Symbolic Logic. 21 (2): 215—220. S2CID 123260425. doi:10.1017/S002248120008525X. .
• Orponen, P. (1997). „A Survey of Continuous-Time Computation Theory”. Advances in Algorithms, Languages, and Complexity. стр. 209—224. CiteSeerX 10.1.1.53.1991 . ISBN 978-1-4613-3396-8. doi:10.1007/978-1-4613-3394-4_11. 
• Post, Emil L. (1944). „Recursively enumerable sets of positive integers and their decision problems”. Bulletin of the American Mathematical Society. 50 (5): 284—316. S2CID 2560730. doi:10.1090/S0002-9904-1944-08111-1. 
• Post, Emil L. (1947). „Recursive Unsolvability of a Problem of Thue”. Journal of Symbolic Logic. 12 (1): 1—11. JSTOR 2267170. S2CID 30320278. doi:10.2307/2267170. . Reprinted in "The Undecidable", M. Davis ed., 1965.
• Shore, Richard A.; Slaman, Theodore A. (1999). „Defining the Turing Jump”. Mathematical Research Letters. 6 (6): 711—722. ISSN 1073-2780. doi:10.4310/mrl.1999.v6.n6.a10. 
• T. Slaman and W. H. Woodin, 1986. "Definability in the Turing degrees." Illinois J. Math.. Illinois J. Math. 30 (2): 320—334. 1986. 
• Soare, Robert I. (1974). „Automorphisms of the Lattice of Recursively Enumerable Sets Part I: Maximal Sets”. Annals of Mathematics. 100 (1): 80—120. JSTOR 1970842. doi:10.2307/1970842. .
• A. Turing (1937). „On computable numbers, with an application to the Entscheidungsproblem” (PDF). Proceedings of the London Mathematics Society: 230—265. S2CID 73712. doi:10.1112/plms/s2-42.1.230. . Corrections. . 43: 544—546.  . Reprinted in "The Undecidable", M. Davis ed., 1965. PDF from comlab.ox.ac.uk
• A. Turing, 1939. "Systems of logic based on ordinals." Proceedings of the London Mathematics Society, ser. 2. . 45: 161—228.  . Reprinted in "The Undecidable", M. Davis ed., 1965.

Спољашње везе

• Association for Symbolic Logic homepage
• Computability in Europe homepage Архивирано на сајту Wayback Machine (17. фебруар 2011)
• Webpage on Recursion Theory Course at Graduate Level with approximately 100 pages of lecture notes
• German language lecture notes on inductive inference