From: Jacko on
On 11 Aug, 15:48, Shubee <e.shu...(a)gmail.com> wrote:
> On Aug 10, 11:55 pm, Tim Little <t...(a)little-possums.net> wrote:
>
> > On 2010-08-11, Shubee <e.shu...(a)gmail.com> wrote:
>
> > > What's so impossible about defining "definable" numbers?
>
> > Nothing, but you just have to be quite precise about what counts as a
> > definition.  For example, does "the least natural number not having a
> > three word definition" count as a definition?
>
> That's a good one Tim. Thank you. Isn't the creation of a precise
> mathematical language for new axiom sets a standard occurrence in
> mathematical logic? Are you saying that this can't be done for the
> concept that I'm trying to justify? I realize that something has to
> break down somewhere. I simply have no idea where that would be.

No. This creation of language process you speak of, does this happen
before or after the insight? Does it occur before and inconsistancy
eliminates unuseful definitions of axioms, or does it occur after the
resonace of a system triggers a right brain experience to get the left
brain to combinate words to make a sequencial communicative system?

Can't be done requires a sound logical proof of such. Not a half proof
by negation with no proof of the assumption space being a modulo 2
group along each axis of assumption.
From: Ludovicus on
On Aug 8, 12:10 pm, Shubee <e.shu...(a)gmail.com> wrote:
> I'm interested in the mathematical consequences of randomness if
> randomness is defined as follows. Let's represent an infinite sequence
> of numbers by the function f on the natural numbers N to the set
> {0,1,2,3,4,5,6,7,8,9}.
>
> Suppose we say that the infinite sequence f is random if no algorithm
> exists that generates the sequence f(n).

This definition of randomness presents a serious problem.
If the sequence is infinite the adequacy of any algorithm is
undecidable.
If the sequence is finite it is ease to find an algorithm that
reproduces
the sequence. The algorithm of pi can reproduce any finite sequence
from
some position on.
Ludovicus
From: Tim Little on
On 2010-08-11, Shubee <e.shubee(a)gmail.com> wrote:
> That's a good one Tim. Thank you. Isn't the creation of a precise
> mathematical language for new axiom sets a standard occurrence in
> mathematical logic?

Yes, it is. You could for example re-use some language like ZFC,
which is capable of expressing rather a lot about real numbers.
However, there is no prior reason to suppose that the concept "is
definable in ZFC" is expressible in the language of ZFC. That makes
it hard to define the list of such numbers in ZFC.


> Are you saying that this can't be done for the concept that I'm
> trying to justify? I realize that something has to break down
> somewhere. I simply have no idea where that would be.

It fails when you try to include all definitions in any conceivable
system that could possibly ever be invented. As soon as you pin down
some consistent system X for defining numbers, you find that "can be
defined in X" is not a property that can be expressed in X. There are
always stronger systems that express more.


- Tim
From: Chip Eastham on
On Aug 11, 5:45 pm, Ludovicus <luir...(a)yahoo.com> wrote:
> On Aug 8, 12:10 pm, Shubee <e.shu...(a)gmail.com> wrote:
>
> > I'm interested in the mathematical consequences of randomness if
> > randomness is defined as follows. Let's represent an infinite sequence
> > of numbers by the function f on the natural numbers N to the set
> > {0,1,2,3,4,5,6,7,8,9}.
>
> > Suppose we say that the infinite sequence f is random if no algorithm
> > exists that generates the sequence f(n).
>
> This definition of randomness presents a serious problem.

I'm all ears.

> If the sequence is infinite the adequacy of any algorithm is
> undecidable.

Perhaps you mean that if an infinite sequence is random
as the OP has defined it above, then the adequacy of any
algorithm is undecidable. (Obviously there are infinite
sequences such as a constant sequence for which the
"adequacy" of an algorithm is decidable.) But consider
the string of digits 0 and 1 according to whether for an
enumeration of Turing machines, the Nth machine halts or
not. It is decidable that no algorithm can compute this
infinite sequence of digits, at least assuming that the
computations of algorithms and of Turing machines are
equivalent.

> If the sequence is finite it is ease to find an algorithm that
> reproduces the sequence.

Okay, but this isn't a "problem", is it? The OP specifically
refers to whether an infinite sequence is "random" according
to a criterion of algorithmic/effective computability.

> The algorithm of pi can reproduce any finite sequence
> from some position on.

Perhaps, though I'm doubtful anyone has proved this.
In any case even if it were true, how does it present
"a serious problem" with the OP's definition of
randomness?

I'd grant that the OP's definition has more to do
with the "indescribable" in his(?) subject line and
not so much with what one considers random number
generators.

> Ludovicus
From: Aatu Koskensilta on
Chip Eastham <hardmath(a)gmail.com> writes:

> Perhaps you mean that if an infinite sequence is random as the OP has
> defined it above, then the adequacy of any algorithm is undecidable.

This doesn't really make any sense. If no algorithm produces a sequence
a0, a1, ... then clearly the problem "Is algorithm A adequate?" is
decidable -- just answer "No" for any A. The problem

Does algorithm A produce the sequence a0, a1, a2, ...

(for a fixed sequence a0, a1, a2, ...) is undecidable just in case the
sequence a0, a1, a2, ... is computable, that is, for any infinite
sequence s the set

Ps = { A | A is an algorithm that produces the sequence s}

is undecidable just in case s is computable. Just recall that
extensional equivalence of algorithms is undecidable.

> (Obviously there are infinite sequences such as a constant sequence
> for which the "adequacy" of an algorithm is decidable.)

Determining whether an algorithm produces a constant sequence is
undecidable.

> But consider the string of digits 0 and 1 according to whether for an
> enumeration of Turing machines, the Nth machine halts or not. It is
> decidable that no algorithm can compute this infinite sequence of
> digits, at least assuming that the computations of algorithms and of
> Turing machines are equivalent.

Here you're using a different notion of decidability, decidability in a
formal theory. "The sequence a0, a1, a2, ... can't be produced by an
algorithm" is expressible in the usual theories only for countably many
sequences, so in general it makes no sense to say it's decidable or
undecidable in T that a sequence can or can't be produced by an
algorithm. There is also no absolute mathematically defined notion of
decidability that applies to mathematical statements.

> Perhaps, though I'm doubtful anyone has proved this.

The decimal expansion of pi hasn't been proved to be disjunctive
sequence.

--
Aatu Koskensilta (aatu.koskensilta(a)uta.fi)

"Wovon man nicht sprechen kann, dar�ber muss man schweigen"
- Ludwig Wittgenstein, Tractatus Logico-Philosophicus