czyli najstarszy sposób określający, co można wyliczyć, a co nie.
podstawowymi przykładami funkcji obliczalnych są:
- funkcja zerowa: f(x) = 0
- funkcja następnika: f(x) = x + 1
- funkcja rzutowania: f(x1, x2, … , xn) = xj
ponadto jeżeli dane funkcje są obliczalne to można obliczyć również ich złożenie.
rekursja
jeżeli:
- funkcja h(x1, x2, … , xn) jest obliczalna
- funkcja g(x1, x2, … , xn) jest obliczalna
- f(x1, x2, … , xn ; 0) = h(x1, x2, … , xn)
- f(x1, x2, … , xn ; k+1) = g(f(x1, x2, … , xn ; k), x1, x2, … , xn; k)
to funkcja f jest obliczalna.
jak widać rekursja może korzystać z argumentów, na których liczona jest wartość.
zbadajmy czy dane funkcje są obliczalne:
- f(x)=2x
funkcję tę można przedstawić jako:
f(0)=2
f(k+1)=f(k)+2
zatem jest ona obliczalna
- dodawanie
p(x,0)=x
p(x,k+1)=p(x,k) + 1
p(x,y) = x+y
wniosek: dodawanie jest funkcją obliczalną
funkcja dająca się w powyższy sposób zbadać jest funkcją pierwotnie rekurencyjną
funkcjami obliczalnymi są również:
- mnożenie
m(x,0)=0
m(x,y+1)=m(x,y)+x
- potęgowanie
p(x,0)=1
p(x,k+1)=p(x,k)*x
- odejmowanie
f(x,0)=x
| f(x, k+1) = | { | f(x,k)-1 dla f(x,k)>0 0 dla f(x,k)=0 |
- obliczanie 2x
f(0)=1
f(x+1)=f(x)*2=f(x)+f(x)
- funkcja
| f(x) = | { | 1 jeśli x != 0 0 jeśli x = 0 |
- funkcja
| f(x) = | { | g(x) dla x != 0 c dla x = 0 |
funkcję tę można przedstawić jako:
f(0)=c
f(x)=g(x)
zatem jest ona obliczalna
kolejnymi funkcjami obliczalnymi, opierającymi się na nieco innym schemacie są:
- pierwiastek z x>=0
takie y>=0, że y*y=x
- logarytm z x
logx = μ * y <= x: 2y > x
czyli najmniejsze takie y, że nie większe od x
co również jest obliczalne
obliczalne są również sumy.
Dwie liczby a i b można zakodować jedną liczbą, w postaci: 2b(2a+1), co jest funkcją obliczalną.
Przykładowo: 24=8*3=23(2*1+1) => b=3, a=1
Wartościami liczb mogą być nie tylko pary liczb, ale i trójki, czwórki, …
WNIOSEK: większość znanych funkcji jest pierwotnie rekurencyjna.
a co jeśli dopuścimy szukanie nieograniczone?
μy : f(y)=0 czyli najmniejsze takie y, że f(y)=0
teoretycznie możemy szukać w nieskończoność, jako że funkcja może nie mieć wartości
a wszystko to prowadzi nas do definicji funkcji rekurencyjnej:
funkcja pierwotnie rekurencyjna + przeszukiwanie = funkcja rekurencyjna
KONKLUZJA:
Jeśli funkcja jest rekurencyjna to istnieje maszyna Turinga, która ją obliczy.
Tym samym – jeśli maszyna Turinga coś liczy to można to obliczyć również funkcją rekurencyjną.
