[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

What's this? A discussion about angels dancing on a the head of a pin? Great, I'm in. On 13/02/2014 14:00, Marko Rauhamaa wrote: > Oscar Benjamin <oscar.j.benjamin at gmail.com>: > >> This isn't even a question of resource constraints: a digital computer >> with infinite memory and computing power would still be limited to >> working with countable sets, and the real numbers are just not >> countable. The fundamentally discrete nature of digital computers >> prevents them from being able to truly handle real numbers and real >> computation. > > Well, if your idealized, infinite, digital computer had ?? bytes of RAM > and ran at ?? hertz and Python supported transfinite iteration, you > could easily do reals: > > def real_sqrt(y): > for x in continuum(0, max(1, y)): > # Note: x is not traversed in the < order but some other > # well-ordering, which has been proved to exist. > if x * x == y: > return x > assert False > > The function could well return in finite time with a precise result for > any given nonnegative real argument. Minor point: ?? does not mean the cardinality c of the continuum, it means the smallest cardinal larger than ??. It has been proved that the question of whether ?? == c is independent of ZFC, so it is in a sense unanswerable. More importantly, though, such a computer could not complete the above iteration in finite time unless time itself is not real-valued. That's because if k is an uncountable ordinal then there is no strictly order-preserving function from k to the unit interval [0, 1]. For suppose otherwise, and let f be such a function. Let S denote the set of successor ordinals in k, and let L denote the set of limit ordinals in k. Then lambda x: x + 1 is an injective function from L (or L with a single point removed if k is the successor of a limit ordinal) to S, so that S is at least as large as L and since k == S | L it follows that S is uncountable. For each x + 1 in S, let g(x + 1) = f(x + 1) - f(x) > 0. Let F be any finite subset of S and let y = max(F). It is clear that f(y) >= sum(g(x) for x in F). Since also f(y) <= 1, we have sum(g(x) for x in F) if <= 1 for all finite F. In particular, for any integer n > 0, the set S_n = {x for x in S if g(x) > 1/n} has len(S_n) < n. But then S is the union of the countable collection {S_n for n in N} of finite sets, so is countable; a contradiction. On 13/02/2014 19:47, Marko Rauhamaa wrote: > My assumption was you could execute ?? statements per second. That > doesn't guarantee a finite finish time but would make it possible. That > is because > > ?? * ?? = ?? = ?? * 1 I don't think that's enough - assuming the operations of your processor during a second can be indexed by some ordinal k with len(k) == c, if each of the c operations per iteration must be complete before the next step of the for loop is complete then you need an injective function from c * c to k that preserves the lexicographic ordering. I don't know whether such a function exists for arbitrary such k, but k can be chosen in advance so that it does.

- Prev by Date:
**singleton ... again** - Next by Date:
**A curious bit of code...** - Previous by thread:
**Working with the set of real numbers** - Next by thread:
**Working with the set of real numbers** - Index(es):