Re:Church-Turing Thesis Cannot Possibly Be True [video]
by kps on Friday October 19, 2018 @11:27AM
(#18257364)
√2 is a bad example for this purpose; there are only countably many algebraic numbers.
[ Parent
| on HN ]
Re:Church-Turing Thesis Cannot Possibly Be True [video]
by tathougies on Friday October 19, 2018 @06:34PM
(#18260587)
My representation is countable, but not because of the fact it uses the algebraic term 'r * r' in its definition of sqrt(2).
My representation is based on dedekind cuts, implemented in Haskell, which is based on the lambda calculus. There are countably many lamdda terms. Thus, I can only represent countably many real numbers. My representation can store all the computable numbers, but there are computable numbers that are not algebraic.
For example, e is not algebraic, but it is computable. Here is a representation of e
factorials :: Rational
factorials = 1:zipWith (*) [1..] factorials
eApproxes :: [Rational]
eApproxes = scanl (+) 0 (map recip factorials)
e :: Rational
e = Rational (\r -> any (r <) eApproxes)