Proračunljiv broj

U matematici i posebno u teoretskom računarstvu i matematičkoj logici, proračunljivi brojevi, isto poznati kao rekurzivni brojevi ili proračunljivi realni brojevi, su realni brojevi koji se mogu izračunati u bilo kojem željenom preciznošću sa konačnim algoritmom. Ekvivalentne defincije se mogu dati uz pomoć μ-rekurzije, Turingove mašine ili λ-računa kao formalna reprezantacija algoritma. Proračunljivi brojevi formiraju realno zatvoreno polje i mogu se koristiti umjesto realnih brojeva za mnoge, ali ne sve, matematičke svrhe.

 Primjer neformalne definicije koristeći Turingovu mašinu 
U slijedećem citatu Marvin Minsky definiše da se brojevi mogu izračunati slično načinu kao što je definisao Alan Turing u 1936-oj, tj. kao "niz cifri interpretirano kao decimalni razlomci" između 0 i 1:

Glavna ideja u ovoj definiciji je (1) da je n određen na početku, (2) da izračunavanje samo zahtjeva konačan broj koraka za bilo koji broj n, nakon čega mašina proizvodi željeni rezultat i završava se.

 Formalna definicija 
U formalnoj definiciji se kaže da je realni broj a izračunljiv ako se može aproksimirati sa nekom izračunljivom funkcijom na slijedeći način: sa bilo kojim cijelim datim brojem , funkcija proizvodi cijeli broj k tako da:

 Da li mogu proračunljivi brojevi da se koriste umjesto realnih brojeva? 
Proračunljivi brojevi obuhvataju mnogo specifičnih realnih brojeva koji se pojavljuju u praksi. Ovo uključuje algebarske brojeve ali isto tako i e, π i mnoge druge transcendentne brojeve. I ako proračunljivi brojevi sadrže ove realne brojeve koje možemo izračunati ili aproksimirati, pretpostavka da su svi realni brojevi proračunljivi dovodi do znatno različitih zaključaka o realnim brojevima. Sasvim prirodno se nameće pitanje da li je moguće rasporediti čitav skup realnih brojeva i koristiti proračunljive projeve za cijelu matematiku. Ova ideja se stvara sa konstruktivističke tačke gledišta i razvijena je u, sa strane Erret Bishopa i Fred Richmana tako zvanoj, Ruskoj školi konstruktivne matematike.

 Također pogledajte 
 Odrediv broj
 Poluizračunljiva funkcija
 Transizračunljiv problem

 Reference 

Kategorija:Brojevi
Kategorija:Teorija računanja
Kategorija:Teorija računjivosti