Idi na sadržaj

Proračunljiv broj

S Wikipedije, slobodne enciklopedije

U matematici i posebno u teoretskom računarstvu i matematičkoj logici, proračunljivi brojevi, isto poznati kao rekurzivni brojevi[1] 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

[uredi | uredi izvor]

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 [2]

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

[uredi | uredi izvor]

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?

[uredi | uredi izvor]

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

[uredi | uredi izvor]

Reference

[uredi | uredi izvor]
  1. ^ van der Hoeven, Joris (14. 2. 2006). "Computations with effective real numbers". Theoretical Computer Science. Real Numbers and Computers (jezik: engleski). 351 (1): 52–60. doi:10.1016/j.tcs.2005.09.060. ISSN 0304-3975.
  2. ^ Marvin Minsky 1967, Computation: Finite and Infinite Machines, Prentice-Hall, Inc. Englewood Cliffs, NJ. Nema ISBN broj. Library of Congress Card Catalog Broj. 67-12342. Poglavlje §9 "The Computable Real Numbers" nadograđuje na teme ovog članka.