изчислима функция

Изчислимо функции - е набор от функции на формата, е. N → N., които могат да бъдат приложени на машина Тюринг. Задачата на изчисляване на функцията F се нарича алгоритъм алгоритъм разтворим или неразтворим. в зависимост от това, дали да се напише алгоритъм е възможно. изчислява тази функция.

Както множеството N обикновено се разглежда набор B *> - множество от думи в двоична азбука B = <0. 1>>. при условие, че резултатът от изчислението, може да не е само една дума, но също така и специална стойност на "несигурност", което съответства на случая, когато алгоритъмът "увисва". По този начин, може да се дефинира като N:

където В = <0. 1>>. и и п г д е - специален елемент, което показва несигурност.

Ролята на множеството N може да играе набор от естествени числа, към който се добавя елемент ф п г д е. и след това изчислимите функции - това е подмножество от функциите на естествен аргумент naturalnoznachnyh. Той е удобен да се предположи, че както N може да служи на различни изброимо множество - множеството на естествените числа, множеството от рационални числа, множеството от думи във всеки краен азбука и т.н. Важно е да има някакъв формален език в краен азбука описване на елементите на N и на проблема с признаването. правилното описание е изчислима. Например, за да се опише естествени числа е удобно да се използва двоична бройна система - описание езика на естествените числа в азбука Б.

В това определение, вместо художник Тюринг машини могат да вземат един от Тюринг-пълни изпълнители. Грубо казано, на "референтен изпълнител" може да бъде абстрактна компютър, подобни на тези, използвани персонални компютри, но с потенциално безкрайна архитектура на паметта и характеристики, което позволява използването на тази безкрайна памет.

Важно е да се отбележи, че най-различни програми за този изпълнител (например, много от Тюринг машини с фиксирана азбука на входни и изходни данни) е броим. Следователно, множеството от изчислимите функции е най-много бройна, докато различни функции на форма F. N → N. несметен, бройна ако Н. Така че не е изчислима функция, със силата на своите задава повече от кардиналността на снимачната площадка на изчислимите функции. Пример за не-изчислимите функции (алгоритъм неразрешими проблеми) може да бъде функция на определяне на спирка - функция, която взима като вход описание на машина Тюринг и вход към него, и се връща 0 или 1, в зависимост от това, дали това ще спре машината за даден вход или не. Друг пример е не-изчислимите функции Колмогоров сложност.

Разбирането, че някои от функциите на формуляр Е. B * → B * \ до B ^> е изчислима, а някои не се появи преди появата на първите компютри. Изчислимост теория произлиза от Тюринг дисертация (1936), в която той въвежда понятието за абстрактна компютър и функции изчислимите върху него. С развитието на изчислителна теория, са формулирани няколко определения, които, както се оказа, се определят със същия набор от функции - на снимачната площадка на изчислимите функции: