Изчислими функции

Съдържание

Основни дефиниции[редактиране]

Определение:
Функция [math]f : N \rightarrow N \cup \lbrace \bot \rbrace[/math] еизчислима(на английскиcomputable function), ако има програма, която изчислява функцията [math]f[/math] така че:
  • ако [math]f(n)[/math] е дефинирано за естествено число [math]n[/math] , тогава програмата прекратява при въвеждане на [math]n[/math] и извежда [math]f(n)[/math] ;
  • ако [math]f(n)[/math] не е дефиниран, тогава програмата виси на входа [math]n[/math] .

Определение:
Функция [math]f : N \rightarrow N \cup \lbrace \bot \rbrace[/math] еизчислима, ако нейната графика [math]F = \lbrace \langle x, y\rangle \mid f(x)[/math] е дефинирана и равна на [math]y \rbrace[/math] е изброим набор от двойки естествени числа.

Теорема:

Доказателство:[math]\triangleright[/math]

[math]\Rightarrow [/math] Нека напишем полуразрешителна програма за множеството [math]F[/math] .

Тъй като домейнът на изчислима функция е изброим, е възможно да се обхождат елементите на домейна. Ако алгоритъмът е намерил двойката, от която се нуждаем, връща 1. [math]\Leftarrow[/math] Нека напишем програма, която изчислява функцията [math]f[/math] .

Тъй като [math]F[/math] е изброимо множество, е възможно да се обхождат елементите на това множество.

[math]\triangleleft[/math]

Забележка [редактиране]

Входовете и изходите на програмите могат да бъдат не само естествени числа, но и двоични низове, двойки естествени числа, крайни последователности от думи и много други.друго. Следователно, понятието изчислима функция за изброими множества може да се дефинира по подобен начин.

Примери за изчислими функции[редактиране]

  • Функция, която не е дефинирана никъде, е изчислима.
  • [math]f(x) = x^2[/math] , където [math]x[/math] е рационално число.

Свойства на изчислима функция[редактиране]

За да го докажете, е достатъчно да напишете полуразрешителна програма.

Ако функцията [math]f[/math] е дефинирана на входа [math]x[/math], тогава [math]x \in D(f)[/math] . Тогава е необходимо да се върне 1. В противен случай програмата ще увисне, когато се извика [math]f(x)[/math].

Лема:
[math]f[/math] е изчислима функция, [math]D(f)[/math] е домейнът на функцията [math]f[/math] . Тогава [math]D(f)[/math] е изброимо множество.
Доказателство:
[math]\triangleright[/math]
[math]\triangleleft[/math]

За да го докажете, е достатъчно да напишете полуразрешителна програма.

Тъй като [math]D(f)[/math] може да се изброи, можем да итерираме елементите на това множество. Ако програмата намери дума, тя връща 1.

Лема:
[math]f[/math] е изчислима функция, [math]E(f)[/math] е обхватът на [math]f[/math] . Тогава [math]E(f)[/math] е изброимо множество.
Доказателство:
[math]\triangleright[/math]
[math]\triangleleft[/math]

Задоказателство, достатъчно е да напишете полуразрешителна програма.

Тъй като изброимите езици са затворени при операцията на пресичане, следва, че елементите на множеството [math]X \cap D(f)[/math] могат да бъдат итерирани. Ако програмата намери дума, тя връща 1.

Лема:
[math]f[/math] е изчислима функция, [math]X[/math] е изброимо множество. Тогава [math]f(X)[/math] е изброимо множество.
Доказателство:
[math]\triangleright[/math]
[math]\triangleleft[/math]

За да го докажете, е достатъчно да напишете полуразрешителна програма.

Програмата може да увисне при проверка на условието [math]f(x) \in X[/math], ако [math]f(x)[/math] не е дефинирано или [math]f(x) \notin X[/math] . Ако [math]f(x)[/math] не е дефиниран, тогава [math]x \notin f^(X)[/math] . Условието [math]f(x) \notin X[/math] може да бъде проверено, защото [math]X[/math] е изброимо.

Лема:
[math]f[/math] е изчислима функция, [math]X[/math] е изброимо множество. Тогава [math]f^(X)[/math] е изброимо множество.
Доказателство:
[math]\triangleright[/math]
[math]\triangleleft[/math]

Характеризиране на изброими множества от гледна точка на изчислими функции[редактиране]

Определение:
Множеството [math]X[/math] се нарича изброимо(англ.изчислимо изброимо множество), ако поне едно от следните условия е вярно:
  1. има програма, която изброява всички елементи на [math]X[/math] в произволен ред;
  2. [math]X[/math] е областта на изчислимата функция [math]f[/math] ;
  3. [math]X[/math] е диапазонът на изчислимата функция [math]f[/math] ;
  4. функция [math]f_X(x) = \begin 1, & x \in X \\ \bot, & x \notin X \end[/math] е изчислим.

Теорема:

Доказателство:[math]\triangleright[/math]
  • [math]1 \Rightarrow 4[/math]

Нека [math]p[/math] е програма, която изброява [math]X[/math] .

Ето програмата [math]q[/math] , която изчислява функцията [math]f_X(x)[/math] :

Нека [math]X[/math] е областта на изчислимата функция [math]f[/math], изчислена от програмата [math]p[/math] .

Тогава [math]X[/math] се изброява от програма като тази:

Нека [math]X[/math] е диапазонът на изчислимата функция [math]f[/math], изчислена от програмата [math]p[/math] .

Тогава [math]X[/math] се изброява от програма като тази:

  • [math]4 \Rightarrow 2[/math] , [math]4 \Rightarrow 3[/math]

Нека е дадено [math]f_X(x)[/math].

Нека въведем нова функция [math]g(x) = x[/math] if [math]f_X(x) \neq \bot[/math] .

Очевидно е, че е изчислим и че неговият домейн и диапазон са същите като [math]X[/math] .

[math]\triangleleft[/math]

Теорема за уеднаквяване[редактиране]

Доказателство:[math]\triangleright[/math]

Нека напишем програма, която изчислява функцията [math]f[/math] .

Тъй като множеството [math]F[/math] е изброимо, неговите елементи могат да бъдат итерирани.

[math]\triangleleft[/math]

Теорема за псевдообратната функция[редактиране]

Доказателство:[math]\triangleright[/math]

Нека напишем програма, която изчислява функцията [math]g[/math] .