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:

Proračunljiv broj je onaj za kojeg postoji Turingova mašina koja se, sa obzirom na n na početnoj traci, završava sa n-tom cifrom tog broja koji je enkodiran na traci.

– Minsky 1967:159

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 $n\geq 1$, funkcija proizvodi cijeli broj k tako da:

${k-1 \over n}\leq a\leq {k+1 \over n}.$

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