Израчунљива функција

"Све рекурзивне функције" се прослеђују овде. За друге врсте "рекурзивне функције", видети Рекурзивна функција (вишезначна одредница).

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

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

Према Черч-Тјурингова тези, функције за израчунавање су управо функције које се могу израчунати помоћу механичког уређаја за израчунавања којем је дато неограничена количина времена и простора. Еквивалентно, ова теза наводи да свака функција која има алгоритам за израчунљива је и обрнуто. Имајте на уму да се алгоритам у том смислу схвата као редослед корака лица са неограниченим временом и бескрајним снабдевањем папира и оловки.

Блумове аксиоме се могу користити за дефинисање апстрактне теорије комплексности израчунавања на сету функција за израчунавање. У теорији комплексности израчунавања, проблем одређивања сложености функција за израчунавање је познат као проблем функције.

Дефиниција

Усклађеност функције је неформални појам. Један од начина да се опише је да се може рећи да је функција за израчунавање ако се њена вредност може добити ефикасним поступком. Са више строгоће, функција $f:\mathbb {N} ^{k}\rightarrow \mathbb {N}$ је израчунљива ако и само ако постоји ефективан поступак који, ако је дата било каја к-торка $\mathbf {x}$ природних бројева, даје вредност $f(\mathbf {x} )$ .^[1] У договору са овом дефиницијом, остатак овог чланка претпоставља да израчунљиве функције узимају коначно много природних бројева као аргументе и производе вредност која је један природан број.

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

Тјурингова машина
μ-рекурзивне функције
Ламбда рачун
Пост машине (Пост-Тјурингове машине и машине за ознаку).
Машине регистра

Иако ови модели користе различите репрезентације за функције, њихови улази и њихови резултати, преводе постојеће између било која два модела, и тако сваки модел описује у суштини иста класа функција, што доводи до мишљења да је формално израчунавање и природно и не превише уско.^[1]

На пример, могу се формализовати израчунљиве функције као μ-рекурзивне функције, које су делимичне функције које узимају коначне записе природних бројева и враћају један природни број (као горе). Оне су најмања класа парцијалних функција које укључују константну, наследника, и пројекцију функције и затворене су под сложеном функцијом, примитивна рекурзија, и μ оператер .

Еквивалентно, израчунљиве функције могу бити озваничене као функције које могу да се обрачунавају од стране идеализованог рачунарског агента, као што је Тјурингова машина или машина регистра. Формално гледано, делимична функција $f:\mathbb {N} ^{k}\rightarrow \mathbb {N}$ може се израчунати ако и само ако постоји компјутерски програм са следећим карактеристикама:

Ако је $f(\mathbf {x} )$ дефинисано, онда ће програм одрадити унету вредност $\mathbf {x}$ са вредношћу $f(\mathbf {x} )$ смештеној у меморији рачунара.
Ако $f(\mathbf {x} )$ није дефинисано, онда програм никада неће извршити унето $\mathbf {x}$ .

Карактеристике израчунљивих функција

Главни чланак: Алгоритам

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

Ендертон [1977] даје следеће карактеристике поступка за израчунавање израчунљиве функције; сличне карактеризације су дали Тјуринг [1936], Роџерс [1967] и други.

"Мора да постоје тачна упутства (тј. програм), коначне дужине, за поступак."

Тако свака израчунљива функција мора имати ограничен програм који у потпуности описује како функција треба да се израчуна. Могуће је израчунати функцију само пратећи упутства; нема нагађања или је потребан посебан увид.

"Ако је поступку дата к-торка x у домену f, а затим коначни број дискретних корака поступка се мора прекинути и произвести f(x)."

Интуитивно, поступак се наставља корак по корак, са посебним правилом да покрије шта се ради на сваком кораку обрачуна. Једино коначно много корака се може обавити пре вредности враћене функције.

"Ако је поступку дата к-торка x која није у свом домену f, онда поступак може ићи унедоглед, никада да се заустави. Или може да се заглави у неком тренутку (тј, једна од њених инструкција се не може извршити) , али не сме се претварати да произведе вредност за f у x. "

Према томе, ако вредност за није f(x) икада пронађена, то мора бити тачна вредност. Није неопходно за рачунарског агента да разликује тачне резултате од оних погрешних, јер је поступак увиек тачан када се ствара исход.

Ендертон иде на листу неколико објашњења ова 3 захтева поступка за израчунљиву функцију:

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

Иако поступак може користити само коначан износ простора током успешног израчунавања, не постоји везан износ простора који се користи. Претпоставља се да може додатни простор за одлагање дати процедура, кад год поступак тражи то.

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

Област рачунске комплексности проучава функције са прописаним границама на времену и / или простору дозвољеном у успешном израчунавању.

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

Скуп А од природних бројева је израчунљив (синоними: рекурзивни, одлучан) ако постоји израчунљива, укупна функција $f$ таква да за било који природни број $n$ , $f (n) = 1$ ако је $n$ у $A$ и $f (n) = 0$ ако $n$ није у $A$ .

Скуп природних бројева је бројно израчунљив (синоними: рекурзивно бројив, полуодлучан) ако постоји израчунљива функција f таква да за сваки број n, f(n) је дефинисано ако и само ако је n у сету. Тако је сет је бројиво израчунљив ако и само ако је домен неке израчунљиве функције. Реч бројив се користи, јер су ово еквиваленти за непразан подскуп B природних бројева:

B је домен израчунљиве функције.
B је опсег укупно израчунљиве функције. Ако је B бесконачно онда се функција може претпоставити да је инјективна.

Ако је скуп B опсег функција f онда функција може да се посматра као набрајање B, јер ће списак f(0), f(1), ... укључивати сваки елемент B.

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

Формални језици

Главни чланак: Формални језик

У теорији израчунљивости у рачунарству, уобичајено је да се размотре формални језици. Алфабет је произвољан скуп. Реч на писму је коначан низ симбола из алфабета; исти симбол може да се користи више од једног пута. На пример, бинарни низови су управо речи азбуке {0, 1}. Језик је подскуп наплате свих речи на фиксном писмом. На пример, прикупљање свих бинарних низова који садрже тачно 3 јединице је језик преко бинарне абецеде.

Кључно својство формалног језика је ниво тежине који је потребан да одлучи да ли ће дати реч у језику. Неки кодни систем мора бити развијен да омогући израчунљивој функцији да да произвољну реч у језику као улаз; ово се обично сматра рутином. Језик је назван израчунљивим (синоними: рекурзивни, одлучан) ако постоји за израчунавање функција f таква да за сваку реч w писма, f(w) = 1 ако је реч у језику и f(w) = 0 ако реч није у језику. Тако је језик за израчунавање само у случају да постоји процедура која је у стању да правилно каже да ли су произвољне речи у језику.

Језик је бројно израчунљив (синоними: рекурзивно бројив, полуодлучан) ако постоји за израчунавање функција f таква да је f(w) дефинисано ако и само ако је реч w је на језику. Термин бројив има исту етимологију као у бројиво израчунљивим скуповима природних бројева.

Примери

Следеће функције су израчунљиве:

Свака функција са ограниченим доменом; пример, неки коначан низ природних бројева.
Свака константна функција f : N^k → N, f(n₁,...n_k) := n.
Сабирање f : N² → N, f(n₁,n₂) := n₁ + n₂
Функција која даје списак главних фактора броја.
Највећи заједнички делилац два броја је за израчунљива функција.
Безуов став, линеарна једначина Диофантина

Ако су f и g израчунљиви, онда су и: f + g, f * g, $f\circ g$ ако је f унарна операција, max(f,g), min(f,g), arg max{y ≤ f(x)} и много других комбинација.

Следећи примери илуструју како функција може бити израчунљива иако се не зна који је алгоритам израчунава.

Функција f таква да је f(n) = 1 ако постоји низ најмање n узастопних петица у децималном проширењу π, f(n) = 0 у супротном, је израчунљива. (Функција f је или стална 1 функција, што је израчунљиво, иначе постоји k такво да је f(n) = 1 ако је n < k и f(n) = 0 ако је n ≥ k. Свака таква функција је израчунљива. Није познато да ли постоје произвољно дугачке петице у децималном проширењу π, тако да не знамо која од тих функција је f. Ипак, знамо да функција f мора бити израчунљива.)
Сваки коначни сегмент на неизрачунљивом низу природних бројева (као што је Бизи бивер функција Σ) је израчунљив. Нпр, за сваки природан број n, постоји алгоритам који израчунава коначни низ Σ (0), Σ (1), Σ (2), ..., Σ (n) - за разлику од чињенице да не постоји алгоритам који израчунава целу Σ-секвенцу, односно Σ (n) за свако n. Тако "Print 0, 1, 4, 6, 13" је безначајни алгоритам за израчунавање Σ (0), Σ (1), Σ (2), Σ (3), Σ (4); Слично томе, за сваку дату вредност n, такав тривијални алгоритам постоји (иако можда никада неће бити познат или произведен од стране било кога) да се израчуна Σ (0), Σ (1), Σ (2), ..., Σ (n).

Черч–Тјурингова теза

Главни чланак: Черч-Тјурингова теза

Черч–Тјурингова теза наводи да свака функција за израчунавање из процедуре која поседује три својства горе наведена је израчунљива функција. Зато што ове три особине нису формално наведене, Черч–Тјурингова теза се не може доказати. Следеће чињенице се често узимају као доказ за тезу:

Многи еквивалентни модели рачунања су познати, а сви они дају исту дефиницију израчунљиве функције (или слабију верзију, у неким случајевима).
Није предложен снажнији модел рачунања који се генерално сматра ефикасним за израчунавање.

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

Неизрачунљиве функције и нерешиви проблеми

Главни чланак: Листа неодлучних проблема

Свака израчунљива функција има ограничену процедуру која је експлицитна, даје недвосмислене инструкције о томе како да се израчуна. Осим тога, ова процедура мора да се кодира у коначном писму које користи рачунарски модел, тако да су само бројиве многе израчунљиве функције. На пример, функције могу да се кодирају коришћењем низа битова (алфабет $Σ = {0, 1}$ ).

Реални бројеви су небројиви тако да већина реалних бројева није израчунљива. Погледајте израчунљив број. Скуп финираних функција на природне бројеве је небројив тако да већина није израчунљива. Конкретни примери таквих функција су Бизи бивер, Колмогорова комплексност, или било која функција која излази на цифре, а не за израчунавање броја, као што су Чејтинова константа.

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

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

Релативна израчунљивост

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

Теорија више рекурзије

Хипераритметичка теорија проучава оне скупове који могу да се израчунају из израчунљивих редних бројева итерације у Тјуринговом скоку празног скупа. Ово је еквивалентно скуповима дефинисаним као универзалне и егзистенцијалне формуле на језику другог реда аритметике и неким моделима хиперрачунања. Чак и више опште теорије рекурзије су проучавале, као што су теорија Е-рекурзије у којој сваки скуп може да се користи као аргумент на е-рекурзивној функцији.

Хиперрачунање

Иако Черч-Тјурингова теза наводи да израчунљиве функције укључују све функције са алгоритмима, могуће је размотрити шире класе функција које опуштају услове које морају да поседују алгоритми. Област хиперрачунања проучава моделе рачунања који превазилазе нормална Тјурингова рачунања.

Види још

Референце

^ ^а ^б Enderton 2002

Литература

Cutland, Nigel. Computability. Cambridge University Press, 1980.
Enderton, H.B. (1977). „Elements of recursion theory”. Handbook of Mathematical Logic. North-Holland. стр. 527—566.
Rogers, H. Theory of recursive functions and effective computation (McGraw–Hill 1967).
Turing, A. (1936), On Computable Numbers, With an Application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, Series 2, Volume 42 (1936). Reprinted in M. Davis (ed.), The Undecidable, Raven Press, Hewlett, NY, 1965.

[automatski_generisano1-1] а ^б Enderton 2002

[1]