Re: Infinite Binary Strings: A Question

On Sat, 20 Sep 2008 17:27:20 -0600, Virgil <Virgil@xxxxxxxxx> wrote:

In article <ujpad49brd4f12gc22egojrrog2p6i4ih7@xxxxxxx>, leon street
wrote:

On Wed, 17 Sep 2008 12:58:58 -0700, fishfry
<BLOCKSPAMfishfry@xxxxxxxxxxxxxxxx> wrote:

In article <ue02d491ftp76d233h1it2eqbjp049gpp0@xxxxxxx>, leon street
wrote:


<snip>


My notion of strings being produceable has not really anything
directly to do wtih the usual notions of construction or computation. It's
merely the positive spin of an essentially negative point, namely that
there is no such thing as an arbitrary infinite string in a purely
combinatorial sense. For example, if there are an uncountable infinity of
points in a line segment, then there are also an uncountable infinity of
binary strings, since any point produces a distinct string (sometimes there
will be two strings per point, but this doesn't matter).


<snip>

Leon -- would the following model help? You have a countable set of fair
coins, numbered 1, 2, 3, ...

You flip all the coins simultaneously. That defines an infinite binary
string -- heads for one, tails for zero, say.

What exactly are you saying, now? That the only strings that could
possibly result are the ones that can be described by algorithms or
short text descriptions? Are you denying the existence of coin tosses
that result in random strings?

I do not see whatever consequences there are for random events
giving pause to the assertion that it is impossible to exemplify an
arbitrary infinite string. It's not clear that an infinite collection of
random events is itself a random outcome. For example, an infinite number
of coin tosses has the peculiar property that there will be exactly 50%
Heads and 50% Tails. Why not 60% Heads and 40% Tails? This is quite unlike
a finite number of coin tosses.

A string is random if there is no shorter description of the string than
the string itself. In other words we can't describe it as, "alternate 1
and 0," or "pi in base 2" or anything like that. To describe the string
we have to write out the entire string. That's what randomness means.
You seem to be denying the existence of randomness.

I assume you understand that there are only countably many finite-length
algorithms or descriptions (the strings written in some countable
alphabet); but that there are uncountably many infinite binary strings.
So you seem to be denying the existence of randomness.

Is that what you're getting at?

I believe that aperiodic strings are asystematic, they have
unlistability built in.

Infinitely many aperiodic strings have computability built into them.
Which means that they can be put into lists of such strings by listing
the TMs by which they are computable.

This pertains to any two aperiodic strings which
are quite different, or of independent source. If because of this one
wishes to describe aperiodic strings as uncountable, this may be
misleading. It's a property which applies to the strings, and not the
collection of the strings.

Wrong! No individual string is uncountable but suitable sets of them are
uncountable. So that property applies only to some sets of them.

And it's my opinion that to say there are uncountably many aperiodic
strings is just plain wrong.

It appears that your notion of what that means differs from ours.


Some of my reasons
for the last statement lie outside what has been discussed in this thread,
but briefly, I would say not only that counting does not apply to aperiodic
strings, but further that counting is the only handle we have on how many
of a type of thing there are.

I agree that counting is a handle on questions of "how many", but
counting can be reduced to questions of injection/surjection/bijection
even for finite sets, so what is your objection to
injection/surjection/bijection?

For the substance of my reply to this, may I refer you to my
response to fishfry? It was a toss up (fair coin!) whether I put it there
or here, but it's gone there. I will comment here on this last bit, but I
would suggest, if you wouldn't mind, consulting that response first.

I'm not sure how far I want to go with this without going
off-topic, but I think what I have to say about uncountability provides a
starting point for assessing the use of bijection. I think the
understanding of uncountability that I am suggesting has the implication
that (infinite) sets between which there is no bijection should not be
understood as differing in size or cardinality. It's really about the
inability to systematically render asystematic elements. But this also
invites a re-evaluation of what it is for two sets to be in a relation of
bijection. Just on the face of it, the fact that there is a relation
between two sets has an ambiguous significance. It may imply some deep
similarity between the two sets, or it may be that the particular relation
is a very loose, inclusive sort of relation by which virtue of which it
obtains between almost any two sets you care to take. It may tell you more
about the relation than the sets related by it, so to speak. In this light,
the fact that it is sometimes surprising that certain bijections obtain,
such as that between Q and N, can be seen merely to highlight what an
extraordinary versatile instrument this bijection is, and not to diminish
the disparateness of the two sets between which it obtains. I'm sure you
can think of analogies for this better than I can. Bijection is perhaps not
an arbiter of size, nor of any concept remotely like size.

If Venkat happens to be reading this, I wonder if this captures
something of his objections in that thread about comparing infinite sets.
When one objects to comparisons of size, and then is told that size in this
context means what we want it to mean, it must seem as if what one wants to
get hold of disappears like the Cheshire cat, leaving only the grin behind
to mock.

Anyway, Virgil, many thanks for your comments.

leon
.

Quantcast