The Indescribable Random Numbers
in [Math]
|
Prev: Meaning, Presuppositions, Truth-relevance, Gödel's Theorem and the Liar Paradox
Next: Original Result Tunze.
From: Jacko on 12 Aug 2010 10:36 On 12 Aug, 14:32, Chip Eastham <hardm...(a)gmail.com> wrote: > 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. No, it is almost certain that the sequence could not be computed using a turing halting detection algorithm, but the sequence could also be isomorphic to some other algorithmic cri'tear'ion. Do you compute all your bit sequences using halt testing so as not to be able to compute them? This in no way implies that the isomorphsm process would be useful for solving turing halting, as the program to halt translation function may be replaced by a x -> bitout function in the isomorphism an so x does not have to equal a program index with enough order to decide halting. > > 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? There has been a proof IIRC that pi contains any integer as a set of sequential digits if one goes far enough into the sequence. > 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. Cheers Jacko
From: Ludovicus on 12 Aug 2010 11:35 On 8 ago, 12:10, Shubee <e.shu...(a)gmail.com> wrote: > Suppose we say that the infinite sequence f is random if no algorithm > exists that generates the sequence f(n). How can you examine an infinite sequence without knowing all its characteristics? If they are given then you can build the algorithm. How can you test an algorithm offered as a solution? And if it is finite, it is embedded in the development of any irrational and for that the algorithm exists. Ludovicus
From: Chip Eastham on 12 Aug 2010 11:36 On Aug 12, 10:29 am, Aatu Koskensilta <aatu.koskensi...(a)uta.fi> wrote: > Chip Eastham <hardm...(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. You trimmed off my context, which was trying to make sense of something Ludovicus wrote. There are known computable sequences (and algorithms that can be proven to produce those particular (infinite) sequences, and sequences known to be uncomputable. I'm not sure what Ludovicus meant by "adequacy". I jumped to the guess he simply meant correct (for all digits of a sequence). Shubee's definition doesn't use that word: : Suppose we say that the infinite sequence f is : random if no algorithm exists that generates the : sequence f(n). > > (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. Yes, but not my point. If you recall the context, we need not answer whether each and every algorithm does or does not produce a constant sequence, only whether one exists that does the job. > > 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. You are right that I'm referring to the notion of decidable based on (commonly accepted) formal theories of mathematics, but I think I was consistent in using the term in that sense. Ludovicus said the OP's definition "presents a serious problem" and then goes on the three statements, none of which clearly outlined a problem with the definition. Indeed two are plainly irrelevant in that the OP's definition speaks of infinite sequences and Ludovicus comments(?) about finite sequences. Charitably that leaves his first remark as some terse indication of what the "serious problem" is. For convenience I quote it here: : If the sequence is infinite the adequacy of any : algorithm is undecidable. So I was giving a couple of instances where the OP's definition could be applied decisively. I understand the order of quantification (respecting the OP's definition) to be such that one example of an algorithm that gives a particular infinite sequence proves the definition that this sequence is not random, e.g. a constant sequence. On the other hand there are also sequences that are defined but which can be proved to be uncomputable, e.g. the halting-machine bits. [snipped reference by Ludovicus to pi containing any finite sequence of digits] > > Perhaps, though I'm doubtful anyone has proved this. > > The decimal expansion of pi hasn't been proved to be > disjunctive sequence. regards, chip
From: Ludovicus on 13 Aug 2010 10:31
On Aug 8, 12:10 pm, Shubee <e.shu...(a)gmail.com> wrote: > Suppose we say that the infinite sequence f is random if no algorithm > exists that generates the sequence f(n). > Question: Can it be proven that mathematically random sequences exist > with this definition? How can we test a proposed algorithm as solution if the sequence is unknown? Clearly, if the sequence is infinite and random,"per force" the sequence must be unknown. If the sequence is finite there is not problem, because any sequence of digits is contained in the decimal development an irrational. Ludovicus |