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: s 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