Proračunljiv broj

Sa Wikipedije, slobodne enciklopedije
Idi na: navigacija, traži

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

Citat „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 [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[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 n \ge 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?[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. ^ 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.