Why G. Chaitin mesure of complexity is wrong.
Ludovicus
By Ludovicus 20/10/2009
G. CHAITIN's article: 'Randomness and Mathematical Proof' in
Scientific American (May 1975) asserts that:;
'The complexity of a series of digits is the number of bits that
must be put into a computing machine in order to obtain the
origi-
nal series as output.The complexity is therefore equal to the
size
in bits of the minimal program of the series.'
This definition contradicts the accepted concept of complexity
by example, Herbert Simon': ;
'Given the properties of the parts and the laws of its inter-
actions, it is not a trivial thing to infer the properties or the
behavior of the system.'
This is confirmed by Chaos Theory. It's not the length of an
algorithm that conveys to Chaos (great complexity), but the ini-
tial parameters and the interactions between operations .
'EXAMPLES:
1.- Chaos by iteration of a function.
An illustration of complexity with a very short program is de-
monstrated by the iteration of: Y = kY^2- 1.
( With initial 0 < Y < 1 )."
If 1 < k < 2 ,eventually, the values periodically are repeated
but with k = 2 Chaos is established. If Chaos do not occur it's
because the precision is too low.
2.- Conway's Game of Life.
That Cellular Automata is generated by a minimum program
of N bits plus M bits of data.
Suppose that the data are the coordinates of a figure and
the produced sequence be the number of 'critters' in each
cycle. The following configuration of six coordinates will
produce a sequence whose first eight numbers are:
6,5,8,8,12,12,20,12 and then repeat 12,12,..indefinitely.
(That is: low complexity)
o o
o o
o o
But with the same program and number of coordinates:
o o
o
o o o
We have a sequence of 1108 numbers before it repeats.
And the evidence that the process can be not-linear is
that it could exits synergy between two identical configura-
tions:
o o o
o o o . . . o o
o o
o o
This produces a sequence of 3160 numbers before it repeats.
But the definitive demonstration that a minimum finite pro-
gram can produce infinite complexity is that the simple four
laws of Game of Life can simulate a non periodic sequence.
And behold, it can simulate an Universal Turing Machine!
3.- Ludovicus Curve
In what follows two parametric functions with the sole diff.
of a letter's position, produce very different complexities.
Periodic Curve:
X = T + SIN(5 * Y)
Y = T - COS(2 * X)
"PSEUDO -SINUSOID"
Swap X , Y and you have the chaotic Curve:
X = T + SIN(5 * X)
Y = T - COS(2 * Y)
I call it : "LUDOVICUS' FUNCTION"
In his book “META MATH” Vintage 2006 (Pag. 23) , he says:
“…because in general the best way to specify N via a computer
program is just to give it explicitly as a constant in a
program
With no calculation at all !”
Why? If a given N of 10^9 bits long is extracted from a list
of
digits of pi, or ?7 surely ,it can be reproduced with a program many
times smaller!
Timothy Murphy
> G. CHAITIN's article: 'Randomness and Mathematical Proof' in
> Scientific American (May 1975) asserts that:;
> 'The complexity of a series of digits is the number of bits that
> must be put into a computing machine in order to obtain the
> origi-
> nal series as output.The complexity is therefore equal to the
> size
> in bits of the minimal program of the series.'
>
> This definition contradicts the accepted concept of complexity
> by example, Herbert Simon': ;
> 'Given the properties of the parts and the laws of its inter-
> actions, it is not a trivial thing to infer the properties or the
> behavior of the system.'
There are many different notions of "complexity".
Chaitin's definition makes perfect sense.
If you don't like the term "complexity",
call it algorithmic entropy, or informational content.
--
Timothy Murphy
e-mail: gayleard /at/ eircom.net
tel: +353-86-2336090, +353-1-2842366
s-mail: School of Mathematics, Trinity College, Dublin 2, Ireland
Don Stockbauer
> Ludovicus wrote:
> > G. CHAITIN's article: 'Randomness and Mathematical Proof' in
> > Scientific American (May 1975) asserts that:;
> > 'The complexity of a series of digits is the number of bits that
> > must be put into a computing machine in order to obtain the
> > origi-
> > nal series as output.The complexity is therefore equal to the
> > size
> > in bits of the minimal program of the series.'
>
> > This definition contradicts the accepted concept of complexity
> > by example, Herbert Simon': ;
> > 'Given the properties of the parts and the laws of its inter-
> > actions, it is not a trivial thing to infer the properties or the
> > behavior of the system.'
>
> There are many different notions of "complexity".
> Chaitin's definition makes perfect sense.
> If you don't like the term "complexity",
> call it algorithmic entropy, or informational content.
>
You think you'll ever get a simple definition of complexity?
David C. Ullrich
<lui...@yahoo.com> wrote:
> ON CHAITIN MEASURE OF COMPLEXITY
>
> By Ludovicus 20/10/2009
>
>
> G. CHAITIN's article: 'Randomness and Mathematical Proof' in
> Scientific American (May 1975) asserts that:;
> 'The complexity of a series of digits is the number of bits that
> must be put into a computing machine in order to obtain the
>origi-
> nal series as output.The complexity is therefore equal to the
>size
> in bits of the minimal program of the series.'
>
> This definition contradicts the accepted concept of complexity
> by example, Herbert Simon': ;
> 'Given the properties of the parts and the laws of its inter-
> actions, it is not a trivial thing to infer the properties or the
> behavior of the system.'
Huh? Why in the world do you imagine that these two statements
contradict each other?
> This is confirmed by Chaos Theory. It's not the length of an
> algorithm that conveys to Chaos (great complexity),
And where do you get the impression that "chaos" is the same
as "great complexity"?
David C. Ullrich
"Understanding Godel isn't about following his formal proof.
That would make a mockery of everything Godel was up to."
(John Jones, "My talk about Godel to the post-grads."
in sci.logic.)
master1729
i agree with Ullrich.
and all replies to the OP till now.
Ludovicus is delusional to think that those 2 definitions contradict eachother.
the chaitin measure of complexity is
1) not wrong
2) just a kind of complexity , there are others
3) quite similar to kolmogorov complexity ( some argue its equivalent and chaitin ' had nothing ' but thats another subject and not the objection of the OP )
BUT most importantly : chaitin complexity is defined for a series of digits ; thus a number or a single number sequence.
WHEREAS Herbert Simon defines chaos of functions.
so chaitin talks about the complexity of the digits of a real, and h. simon talks about the chaos of functions.
big difference.
yes , i said i agree with david c ullrich !
but i posted to clarify for ludovicus , a typical ullrich ' huh ?! ' is not always sufficient ...
on the other hand maybe im naive and ludovicus will be stubborn ... and i will regret posting more than ullrich.
time will tell.
btw , kolmogorov complexity is one of the best.
regards
tommy1729
Ludovicus
> On Sun, 29 Nov 2009 04:25:07 -0800 (PST), Ludovicus
> >
> contradict each other?
>
> as "great complexity"?
>
>
>
I did not say that chaos means absolute complexity, but that
the relative complexity of a periodic sequence have different
complexity that a chaotic sequence.
And that the decimal period of a rational have different complexity
that the development of an irrational. Notwithstanding they are
produced by the same program but different data with same quantity of
bits.
The kernel of the problem is that the same program with
new data but with the same number of bits produce
very different sequences. With one data it produces a periodic
sequence, with the other produces an irrational sequence.
If they not have different complexities, what use of Chaitin mesure?
The 1200 paages of Wolfram's book "A New Kind of Science" contradicts
the Chaintin's thesis. In "Meta Math" Chaitin accepts that his concept
of complexity is utterly different of Wolfram's.
Why no one discuss my examples but only my wording?
Refute my examples.
Ludovicus
Timothy Murphy
> The 1200 paages of Wolfram's book "A New Kind of Science" contradicts
> the Chaintin's thesis. In "Meta Math" Chaitin accepts that his concept
> of complexity is utterly different of Wolfram's.
That is perfectly possible, but does not show Chaitin (or Wolfram) is wrong.
If you think the use of the word "complexity" causes confusion,
use a different term like "algorithmic entropy"
(which Chaitin often uses, I think).
master1729
in fact wolfram and chaitin do not contradict , but co-exist.
one can transform wolfram complexity to chaitin complexity and visa versa.
tommy1729
Ludovicus
As Chaitin said in "Meta Math" : What Wolfram consider as maximun
complexity,
for me is minimum complexity. He, as most of us, acknowledges that
randomness
means maximum complexity. Wolfram holds that one of his minimum
programs
produce pseudo-randomness so complex that he utilizes it in
"Matemathica" .
Ludovicus.
Aatu Koskensilta
> G. CHAITIN's article: 'Randomness and Mathematical Proof' in
> Scientific American (May 1975) asserts that:;
> 'The complexity of a series of digits is the number of bits that
> must be put into a computing machine in order to obtain the
> original series as output.The complexity is therefore equal to the
> size in bits of the minimal program of the series.'
>
> This definition contradicts the accepted concept of complexity
> by example, Herbert Simon': ;
> 'Given the properties of the parts and the laws of its inter-
> actions, it is not a trivial thing to infer the properties or the
> behavior of the system.'
It is obscure how this "accepted concept of complexity" applies to a
series of digits. It thus makes no immediate sense to claim Chaitin's
definition, or assertion, contradicts the "accepted concept of
complexity". Whether or not the notion of algorithmic complexity, or
randomness, of a string adequately captures this or that informal notion
of complexity also has no bearing on the purely mathematical side to
algorithmic information theory, where we find many interesting and
useful mathematical theorems, applications, notions. That a chaotic
sequence obtained by iterating some function may well have very low
algorithmic complexity in itself doesn't tell us anything about whether
various conceptions, questions, claims about complexity can be
understood and approached in terms of algorithmic information theory.
> Why? If a given N of 10^9 bits long is extracted from a list
> of digits of pi, or ?7 surely ,it can be reproduced with a program
> many times smaller!
That depends on N.
--
Aatu Koskensilta (aatu.kos...@uta.fi)
"Wovon man nicht sprechan kann, dar�ber muss man schweigen"
- Ludwig Wittgenstein, Tractatus Logico-Philosophicus
Aatu Koskensilta
> 3) quite similar to kolmogorov complexity ( some argue its equivalent
> and chaitin ' had nothing ' but thats another subject and not the
> objection of the OP )
I don't know of anyone who argues Chaitin "had nothing". Chaitin,
Solomonoff and Kolmogorov all independently arrived at essentially the
same notion of complexity. Beyond the basic definition Chaitin's main
contribution to the field are his complexity theoretic incompleteness
theorems.
> btw, kolmogorov complexity is one of the best.
One of the best what?
master1729
Good. they are correct then and understood eachother ( 's work ? ).
that 'one of wolframs minimum programs which produces pseudo-randomness ' must be the rule 30 ( cellular automaton ).
since Luis A Rodriguez quotes the reply by chaitin , it seems he agrees , and then i wonder what he objects to in the OP considering his agreement resp disagreement ...
btw i read the book ' a new kind of science ' by wolfram.
regards
the master
tommy1729
master1729
> master1729 <tomm...@gmail.com> writes:
>
> > 3) quite similar to kolmogorov complexity ( some
> argue its equivalent
> > and chaitin ' had nothing ' but thats another
> subject and not the
> > objection of the OP )
>
> I don't know of anyone who argues Chaitin "had
> nothing". Chaitin,
> Solomonoff and Kolmogorov all independently arrived
> at essentially the
> same notion of complexity. Beyond the basic
> definition Chaitin's main
> contribution to the field are his complexity
> theoretic incompleteness
> theorems.
true.
>
> > btw, kolmogorov complexity is one of the best.
>
> One of the best what?
complexity definitions.
because i find it relates best to randomness.
kolmogorov complexity is important imho for testing randomness of strings.
>
> --
> Aatu Koskensilta (aatu.kos...@uta.fi)
>
> "Wovon man nicht sprechan kann, darüber muss man
> schweigen"
> - Ludwig Wittgenstein, Tractatus
> s Logico-Philosophicus
regards
tommy1729
Ludovicus
> Aatu Koskensilta wrote :
> kolmogorov complexity is important imho for testing randomness of strings.
Most people accepts what Kolmogorov and Chaitin says about randomness:
"A random sequence have maximum complexity."
"The program that codes a random sequence cannot have a length
shorter than the sequence."
But building an incremental mesure of complexity based on length
of minimum programs is easily contradicted with counter-examples.
Suppose someone writes a program for the primes sequence 100 bytes
long.
Suppose A is an arbitrary constant 100 bytes long.
Then the arithmetic progression: A.n + 1 needs a program with a
length:
100 + Code
According to Chaitin this arithmetic progression is more complex than
the sequence of primes!
Ludovicus
Ostap S. B. M. Bender Jr.
Why not? There are plenty of complex definitions of simplicity.
David C. Ullrich
wrote:
>On 2 dic, 13:19, master1729 <tommy1...@gmail.com> wrote:
>> Aatu Koskensilta wrote :
>> kolmogorov complexity is important imho for testing randomness of strings.
>
>
>Most people accepts what Kolmogorov and Chaitin says about randomness:
>"A random sequence have maximum complexity."
>"The program that codes a random sequence cannot have a length
>shorter than the sequence."
>
>But building an incremental mesure of complexity based on length
>of minimum programs is easily contradicted with counter-examples.
Counterexamples to a _definition_? Very curious.
>Suppose someone writes a program for the primes sequence 100 bytes
>long.
>Suppose A is an arbitrary constant 100 bytes long.
>Then the arithmetic progression: A.n + 1 needs a program with a
>length:
>100 + Code
>According to Chaitin this arithmetic progression is more complex than
>the sequence of primes!
You didn't state that very well. But never mind the details - yes,
it's clear that there are arithmetic progressions that have Chaitin
complexity greater than the Chaitin complexity of the sequence
of primes. Now where's the supposed contradiction?
>Ludovicus
Ludovicus
> On Thu, 3 Dec 2009 06:09:45 -0800 (PST), Ludovicus <luir...@yahoo.com>
> You didn't state that very well. But never mind the details - yes,
> it's clear that there are arithmetic progressions that have Chaitin
> complexity greater than the Chaitin complexity of the sequence
> of primes. Now where's the supposed contradiction?
> David C. Ullrich
Then, the Chaitin's mesure of complexity is useless.
Here I present the Ludovicus' mesure of difficulty :
"The mesure of difficulty of a theorem is equal to the
quantity of characters needed for its minimum presentation."
Sirs, its first application is the important result:
"The difficulty of Fermat's theorem is less than the
difficulty of Pitagoras theorem."
Now I am waiting that Universities invite me to impart
conferences on that marvelous finding. And editorials
to print my books in so transcendent discovery.
master1729
wrong.
"A random sequence HAS AND EQUALS maximum complexity. IF AND ONLY IF
"The !! SHORTEST !! program that codes THAT random sequence cannot have a length shorter than the sequence."
is more like it ...
thus when you give multiple algoritms for computing things that is a flawed argument.
hope you finally understand.
regards
tommy1729
Ludovicus
> "A random sequence HAS AND EQUALS maximum complexity. IF AND ONLY IF
> "The !! SHORTEST !! program that codes THAT random sequence cannot have a length shorter than the sequence."
> tommy1729
If that is the definition of a random sequence then it is useless.
Because any irrational number contains all the imaginable sequences.
So a very sort program for producing the infinite digits of a
irrational can code any random sequence.
Chaitin affirms that the time of computation is immaterial. Then a
computer working centuries can find the given sequence.
Ludovicus
zzbu...@netscape.net
But, that's also why the people who understand real computers,
rather tham just arbitary Quantum Mechanics momenta
invented Laser-Guided Phasors, rather than double slit
expermiments.
And invented invented Holograms and Desktop Publishing
rather than Spectrum Analizers.
And invented Flat Screen Software Debuggers, rather than
Hollerith Codes.
And invented Blue Ray rather than Hard Disks.
And invented XML, rather than GE.
And invented Atomic Clock Watches and All-In-One Printers
rather than keyboards.
And invented Home Broadband, rather than Unix.
And invented Holograms. USB, and GPS, rather than IBM.
And invented Self-Assembling Robots, External Mini Computer
Harddisks,
and Rapid Prototyping, rather than Intel.
And Invented Weather Satellites, Data Fusion, UAVs, mp3, mpeg,
and Optical Computers, rather and Honeywell.
Jesse F. Hughes
> If that is the definition of a random sequence then it is useless.
> Because any irrational number contains all the imaginable sequences.
The sentence above is simply false. The number
0.1101001000100001000001...
is irrational but does not contain the subsequence 12345.
> So a very sort program for producing the infinite digits of a
> irrational can code any random sequence.
That does not follow. Suppose that pi contains every finite
sequence. We need not only an algorithm to compute pi, but also which
digit begins the sequence in question. If that digit is large and not
very compressible, then the program that uses the computation of pi to
output our sequence may be longer than the sequence.
--
"I am sure that my writings will survive far longer than Wikipedia,
and that deep into the future, about the only human that people will
want to know alot [sic] about is Archimedes Plutonium. At some point
in the future history of humanity, AP will eclipse even Jesus." -- AP
Ilmari Karonen
> Ludovicus <lui...@yahoo.com> writes:
>
>> So a very sort program for producing the infinite digits of a
>> irrational can code any random sequence.
>
> That does not follow. Suppose that pi contains every finite
> sequence. We need not only an algorithm to compute pi, but also which
> digit begins the sequence in question. If that digit is large and not
> very compressible, then the program that uses the computation of pi to
> output our sequence may be longer than the sequence.
I suspect that what he intends to do is simply to have that short
pi-generating program output the digits of pi sequentially until the
desired finite subsequence just happens to come up.
Of course, the reason that won't really help is that the program must
be able to recognize the desired sequence when it sees it. And for
most sequences, the shortest program to recognize the sequence is of
approximately the same length as the shortest program to generate it.
(Indeed, given a program to generate the digits of a normal number, I
believe it should be easy to show, using exactly the argument above,
that there exists a constant C such that, for all finite sequences S,
|length(Gen(S)) - length(Rec(S))| < C, where Gen(S) and Rec(S) are the
shortest programs to generate and recognize the sequence S.)
--
Ilmari Karonen
To reply by e-mail, please replace ".invalid" with ".net" in address.
zzbu...@netscape.net
wrote:
Or you could even state it as:
"It's not like we can't be bought and sold, we just
cam't be bought and sold by Q-bit imbeciles".
> > times smaller!- Hide quoted text -
>
> - Show quoted text -- Hide quoted text -
>
> - Show quoted text -
master1729
thats plain wrong.
tommy1729