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.benja...@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.
--
https://mail.python.org/mailman/listinfo/python-list
