Машина која увек стаје

У теорији израчунљивости, машина која увек стаје или одлучивач^[1] или тотална Тјурингова машина^[2] је Тјурингова машина која стаје за сваки улаз.

Како увек стаје, машина је у стању да одлучи да ли дата ниска припада формалном језику. Класа језика који могу да буду одлучени оваквим машинама тачно одговара скупу рекурзивних језика. Међутим, услед халтинг проблема, одређивање да ли произвољна Тјурингова машина стаје за произвољни улаз је са своје стране неодлучив проблем одлучивања.

Функције израчунљиве тоталним Тјуринговим машинама

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

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

Могуће је чак дефинисати програмски језик који ће осигурати да и софистицираније функције стају. На пример, Акерманова функција, која није примитивно рекурзивна, али је ипак тотално израчунљива функција.

Однос са парцијалним Тјуринговим машинама

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

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

Одговор на оба ова питања је негативан.

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

Теорема. Постоје Тјуринг израчунљиве парцијалне функције које немају проширење до тотално Тјуринг израчунљивих функција. Прецизније, парцијална функција f дефинисана тако да f(n) = m ако и само ако Тјурингова машина са индексом n стаје на улазу 0 са излазом m нема проширење до тотално израчунљиве функције.

Ова теорема се доказује свођењем на контрадикцију. Ако би g била тотално израчунљива функција која проширује f онда би g била израчунљива на некој Тјуринговој машини; нека је e индекс такве машине. Ако би била направљена Тјурингова машина M, коришћењем Клинијеве теореме рекурзије, која за улаз 0 симулира машину са индексом e која ради са индексом n_M за M (стога машина M може да произведе свој индекс; ово је улога теореме рекурзије). По претпоставци, ова симулација би у неком тренутку дала одговор. Ако се дефинише M тако да ако g(n_M) = m онда је повратна вредност машине M једнака m + 1. Стога f(n_M), права повратна вредност машине M за улаз 0, неће бити једнака g(n_M). Ово противречи претпоставци да g проширује f.

Друго питање је у суштини питање да ли постоји други разуман модел израчунавања који израчунава само тоталне функције и израчунава све тотално израчунљиве функције. Неформално, ако би такав модел постојао, сваки од његових рачунара би било могуће симулирати на Тјуринговој машини. Стога ако би се овај нови модел рачунања састојао од низа $M_{1},M_{2},\ldots$ машина, постојало би рекурзивно пребројив низ $T_{1},\ldots T_{2},\ldots$ Тјурингових машина које рачунају тоталне функције тако да је свака тотално израчунљива функција израчунљива једном од машина T_i. Ово је немогуће, јер би машина $T$ могла да буде конструисана тако да за улаз i машина T враћа $T_{i}(i)+1\,$ . Ова машина не може да буде еквивалентна ниједној машини T из листе: Нека је та машина у листи на индексу j. Онда $T_{j}(j)=T_{j}(j)+1\,$ , што не враћа целобројни резултат. Стога не може да буде тотална, али функција по конструкцији мора да буде тотална (ако су тоталне функције рекурзивно пребројиве, онда ова функција може да буде конструисана), и ту се јавља контрадикција. Ово показује да и друго питање има негативан одговор.

Скуп индекаса тоталних Тјурингових машина

Проблем одлучивања да ли ће Тјурингова машина са индексом e стати за сваки улаз није одлучив. Овај проблем је на нивоу $\Pi _{2}^{0}$ аритметичке хијерархије. Стога је овај проблем строго тежи од халтинг проблема, који поставља питање да ли ће машина са индексом e стати за улаз 0. Интуитивно, ова разлика у неизрачунљивости је последица чињенице да свака инстанца проблема тоталне машине представља бесконачно много инстанци халтинг проблема.

Види још

Тотално функционално програмирање

Референце

^ Sipser, M. (1996), Introduction to the Theory of Computation, PWS Publishing Co.
^ Kozen, D.C. (1997), Automata and Computability, Springer.
^ Meyer, A.R., Ritchie, D.M. (1967), The complexity of loop programs, Proc. of the ACM National Meetings, 465.

Литература

Brainerd, W.S., Landweber, L.H. (1974), Theory of Computation, Wiley.
Ohlebusch, E. (2002), Advanced Topics in Term Rewriting, Springer.

[1] Sipser, M. (1996), Introduction to the Theory of Computation, PWS Publishing Co.

[2] Kozen, D.C. (1997), Automata and Computability, Springer.

[3] Meyer, A.R., Ritchie, D.M. (1967), The complexity of loop programs, Proc. of the ACM National Meetings, 465.

[1]

[2]

[3]