Re: [agi] How can you prove form/behaviour are disordered?
On 6/8/07, Matt Mahoney [EMAIL PROTECTED] wrote: The author has received reliable information, from a Source who wishes to remain anonymous, that the decimal expansion of Omega begins Omega = 0.998020554253273471801908... For which choice of universal Turing machine? It's actually 0.00787499699781238... At least when based on the Turing machine described here: http://www.emis.de/journals/EM/expmath/volumes/11/11.3/Calude361_370.pdf Shane - This list is sponsored by AGIRI: http://www.agiri.org/email To unsubscribe or change your options, please go to: http://v2.listbox.com/member/?member_id=231415user_secret=e9e40a7e
Re: [agi] How can you prove form/behaviour are disordered?
Unfortunately, it wasn't an open Source ... On Thursday 07 June 2007 10:52:03 pm Matt Mahoney wrote: --- J Storrs Hall, PhD [EMAIL PROTECTED] wrote: The author has received reliable information, from a Source who wishes to remain anonymous, that the decimal expansion of Omega begins Omega = 0.998020554253273471801908... For which choice of universal Turing machine? - This list is sponsored by AGIRI: http://www.agiri.org/email To unsubscribe or change your options, please go to: http://v2.listbox.com/member/?member_id=231415user_secret=e9e40a7e
Re: [agi] How can you prove form/behaviour are disordered?
--- Shane Legg [EMAIL PROTECTED] wrote:
On 6/8/07, Matt Mahoney [EMAIL PROTECTED] wrote:
The author has received reliable information, from a Source who wishes to
remain anonymous, that the decimal expansion of Omega begins
Omega = 0.998020554253273471801908...
For which choice of universal Turing machine?
It's actually 0.00787499699781238...
At least when based on the Turing machine described here:
http://www.emis.de/journals/EM/expmath/volumes/11/11.3/Calude361_370.pdf
Shane
It seems you could get fairly accurate approximations of Omega for other
languages like C using this approach. For example, there is (AFAIK) only one
C program of length 64 bits or less that halts:
main(){}
and you could possibly prove upper bounds on longer programs. Here are some
halting programs of length 72 bits:
;main(){}
main(){;}
main(){};
main(){}
main (){}
main( ){}
main() {}
main(){ }
main(){}
and others replacing the space with any of the ASCII codes 9, 10, 11, 12, or
13 (at least for gcc). That is 39 (unless I missed some). I think with some
work you could prove about 66 bits of Omega_C:
.0100
or 20 decimal digits:
.0005
What is the shortest C program that does not halt? Here are some 136 bit
programs:
main(){while(1);}
main(){a:goto a;}
And a 128 bit program:
main(){for(;;);}
The following 120 bit program might run forever in some implementations:
main(){main();}
What is the shortest halting program in Java? I can find 2916 programs of
length 360 bits, but nothing shorter, for example:
class _{public static void main(String[]$){}}
unless you count programs that throw exceptions as legal, in which case you
can have 72 bits:
class x{}
-- Matt Mahoney, [EMAIL PROTECTED]
-
This list is sponsored by AGIRI: http://www.agiri.org/email
To unsubscribe or change your options, please go to:
http://v2.listbox.com/member/?member_id=231415user_secret=e9e40a7e
Re: [agi] How can you prove form/behaviour are disordered?
--- Matt Mahoney [EMAIL PROTECTED] wrote:
It seems you could get fairly accurate approximations of Omega for other
languages like C using this approach. For example, there is (AFAIK) only
one
C program of length 64 bits or less that halts:
main(){}
and you could possibly prove upper bounds on longer programs. Here are some
halting programs of length 72 bits:
;main(){}
main(){;}
main(){};
main(){}
main (){}
main( ){}
main() {}
main(){ }
main(){}
and others replacing the space with any of the ASCII codes 9, 10, 11, 12, or
13 (at least for gcc). That is 39 (unless I missed some).
Here are 53 more:
main(_)(){}
main(a)(){}
main(b)(){}
...
main(Z)(){}
How many halting C programs are there of length 80 bits?
What is the shortest C program that does not halt? Here are some 136 bit
programs:
main(){while(1);}
main(){a:goto a;}
And a 128 bit program:
main(){for(;;);}
The following 120 bit program might run forever in some implementations:
main(){main();}
This halts when compiled with gcc -O (stack overflow but no apparent error)
but not with -O2 or higher. Compiling with -S shows that the tail recursion
is optimized into a loop.
-- Matt Mahoney, [EMAIL PROTECTED]
-
This list is sponsored by AGIRI: http://www.agiri.org/email
To unsubscribe or change your options, please go to:
http://v2.listbox.com/member/?member_id=231415user_secret=e9e40a7e
Re: [agi] How can you prove form/behaviour are disordered?
Hi Matt
Re Halting/non-halting programs:
This try-out works fine for small values of {program length}. For large values
the problem is essentially unsolvable, though I admit that you could get a fair
feeling for the distribution by simulating a large number of randomly generated
programs. The busy beaver sequence is (provably) the fastest growing number
sequence... (I know because I tried looking for that once but the best I could
come up was with what was apparently called the arrow notation.)
Re NL pattern finding:
The problem arises with:
- Apples are (the forbidden :) fruit. My laptop is an apple. Therefore my
laptop is (the forbidden) fruit.
- People have legs. Johnny the cripple is a person (a people?). Therefore...
- Eggs are white (or brown:). Yolk is in the egg. Therefore yolk is white.
Matt Mahoney [EMAIL PROTECTED] 06/08/07 9:24 PM
What is the shortest C program that does not halt? Here are some 136 bit
programs:
What is the shortest halting program in Java? I can find 2916 programs of
length 360 bits, but nothing shorter, for example:
- Frogs are green. Kermit is a frog. Therefore Kermit is green.
- Cities have tall buildings. New York is a city. Therefore New York has
tall buildings.
- Summers are hot. July is in the summer. Therefore July is hot.
-
This list is sponsored by AGIRI: http://www.agiri.org/email
To unsubscribe or change your options, please go to:
http://v2.listbox.com/member/?member_id=231415user_secret=e9e40a7e
[agi] How can you prove form/behaviour are disordered?
Eric B asked me for a test to prove free thinking - I'm getting to it - but I realised it raised a much deeper philosophical presumably mathematical issue which some of you guys, especially the supermathematicians, may have well have given thought to, and I certainly haven't. The issue is this: how can you prove a given form - whether a physical form or form of behaviour - is disordered? How can you prove that it cannot be considered as having been programmed, and there is no underlying formula for it? (And another way of saying disordered is free as in free-form - and NOT free-willed). How can you show that a free verse form really is free and does not conform to some underlying pattern? Or that a Jackson Pollock abstract action painting is not the result of a complex formula or program? Or that a given series of numbers 3..1,017..19.. 4..1,000,039..etc is not produced by any formula? Or that a given stream of association of words (in which some do appear to connect to each other, and others don't) really is disordered? How, to take an application of that, could you show that a schizophrenic's stream of speech really is mentally disordered? Or that a ramshackle dwelling really has been chaotically cobbled together? Will the proponent of order, so to speak, always be able to claim that no matter how disordered a given form may appear, (and no matter how most people may agree that it is disordered), there is always an underlying order waiting to be revealed? P.S. None of this actually relates to answering Eric's request. But I realised it did raise an important issue. - This list is sponsored by AGIRI: http://www.agiri.org/email To unsubscribe or change your options, please go to: http://v2.listbox.com/member/?member_id=231415user_secret=e9e40a7e
Re: [agi] How can you prove form/behaviour are disordered?
1) encode your form in bits -- it doesn't matter what encoding you use. Say the number of bits you need is N. 2) Try all the Turing machines that can be expressed in less than N bits. 3) If one of them produces your sequence, there is a hidden order to it, that can be expressed as that Turing machine. If not, your form is disordered. Josh On Thursday 07 June 2007 01:41:14 pm Mike Tintner wrote: Eric B asked me for a test to prove free thinking - I'm getting to it - but I realised it raised a much deeper philosophical presumably mathematical issue which some of you guys, especially the supermathematicians, may have well have given thought to, and I certainly haven't. The issue is this: how can you prove a given form - whether a physical form or form of behaviour - is disordered? How can you prove that it cannot be considered as having been programmed, and there is no underlying formula for it? (And another way of saying disordered is free as in free-form - and NOT free-willed). How can you show that a free verse form really is free and does not conform to some underlying pattern? Or that a Jackson Pollock abstract action painting is not the result of a complex formula or program? Or that a given series of numbers 3..1,017..19.. 4..1,000,039..etc is not produced by any formula? Or that a given stream of association of words (in which some do appear to connect to each other, and others don't) really is disordered? How, to take an application of that, could you show that a schizophrenic's stream of speech really is mentally disordered? Or that a ramshackle dwelling really has been chaotically cobbled together? Will the proponent of order, so to speak, always be able to claim that no matter how disordered a given form may appear, (and no matter how most people may agree that it is disordered), there is always an underlying order waiting to be revealed? P.S. None of this actually relates to answering Eric's request. But I realised it did raise an important issue. - This list is sponsored by AGIRI: http://www.agiri.org/email To unsubscribe or change your options, please go to: http://v2.listbox.com/member/?; - This list is sponsored by AGIRI: http://www.agiri.org/email To unsubscribe or change your options, please go to: http://v2.listbox.com/member/?member_id=231415user_secret=e9e40a7e
Re: [agi] How can you prove form/behaviour are disordered?
On 6/8/07, Mike Tintner [EMAIL PROTECTED] wrote: The issue is this: how can you prove a given form - whether a physical form or form of behaviour - is disordered? How can you prove that it cannot be considered as having been programmed, and there is no underlying formula for it? (And another way of saying disordered is free as in free-form - and NOT free-willed). Google some stuff on compression and information theory. Compression algorithms try and predict the probability of the next bit/byte/thing being in different states. If all states are equally likely, then entropy is maximal, and it's not possible to compress the observations. Of course, in such a case, the heuristic for estimating probabilities might not be optimal. J - This list is sponsored by AGIRI: http://www.agiri.org/email To unsubscribe or change your options, please go to: http://v2.listbox.com/member/?member_id=231415user_secret=e9e40a7e
Re: [agi] How can you prove form/behaviour are disordered?
--- Joel Pitt [EMAIL PROTECTED] wrote: On 6/8/07, Mike Tintner [EMAIL PROTECTED] wrote: The issue is this: how can you prove a given form - whether a physical form or form of behaviour - is disordered? How can you prove that it cannot be considered as having been programmed, and there is no underlying formula for it? (And another way of saying disordered is free as in free-form - and NOT free-willed). Google some stuff on compression and information theory. Compression algorithms try and predict the probability of the next bit/byte/thing being in different states. If all states are equally likely, then entropy is maximal, and it's not possible to compress the observations. Of course, in such a case, the heuristic for estimating probabilities might not be optimal. Kolmogorov proved that there is no optimal solution. In general there is no algorithm for proving that a sequence is not compressible, or that it cannot be compressed further. http://en.wikipedia.org/wiki/Kolmogorov_complexity The enumeration of Turing machines mentioned earlier would not be a general solution because you don't know which ones will halt. -- Matt Mahoney, [EMAIL PROTECTED] - This list is sponsored by AGIRI: http://www.agiri.org/email To unsubscribe or change your options, please go to: http://v2.listbox.com/member/?member_id=231415user_secret=e9e40a7e
Re: [agi] How can you prove form/behaviour are disordered?
On Thursday 07 June 2007 08:37:51 pm Matt Mahoney wrote: The enumeration of Turing machines mentioned earlier would not be a general solution because you don't know which ones will halt. You may not know, but I have an old mimeographed preprint of a paper On Random and Hard-to-Describe Numbers by Charles Bennett (dated 23 may 1979) that ends with the following paragraph: The author has received reliable information, from a Source who wishes to remain anonymous, that the decimal expansion of Omega begins Omega = 0.998020554253273471801908... Josh - This list is sponsored by AGIRI: http://www.agiri.org/email To unsubscribe or change your options, please go to: http://v2.listbox.com/member/?member_id=231415user_secret=e9e40a7e
Re: [agi] How can you prove form/behaviour are disordered?
On 6/7/07, J Storrs Hall, PhD [EMAIL PROTECTED] wrote: On Thursday 07 June 2007 08:37:51 pm Matt Mahoney wrote: The enumeration of Turing machines mentioned earlier would not be a general solution because you don't know which ones will halt. You may not know, but I have an old mimeographed preprint of a paper On Random and Hard-to-Describe Numbers by Charles Bennett (dated 23 may 1979) that ends with the following paragraph: The author has received reliable information, from a Source who wishes to remain anonymous, that the decimal expansion of Omega begins Omega = 0.998020554253273471801908... Sure, but it's still 1.0, so what good is that? -Jey Kottalam - This list is sponsored by AGIRI: http://www.agiri.org/email To unsubscribe or change your options, please go to: http://v2.listbox.com/member/?member_id=231415user_secret=e9e40a7e
Re: [agi] How can you prove form/behaviour are disordered?
--- J Storrs Hall, PhD [EMAIL PROTECTED] wrote: On Thursday 07 June 2007 08:37:51 pm Matt Mahoney wrote: The enumeration of Turing machines mentioned earlier would not be a general solution because you don't know which ones will halt. You may not know, but I have an old mimeographed preprint of a paper On Random and Hard-to-Describe Numbers by Charles Bennett (dated 23 may 1979) that ends with the following paragraph: The author has received reliable information, from a Source who wishes to remain anonymous, that the decimal expansion of Omega begins Omega = 0.998020554253273471801908... For which choice of universal Turing machine? -- Matt Mahoney, [EMAIL PROTECTED] - This list is sponsored by AGIRI: http://www.agiri.org/email To unsubscribe or change your options, please go to: http://v2.listbox.com/member/?member_id=231415user_secret=e9e40a7e
