The premise of my assertion did not hold; that is, I did not recall very
well. So, I am trying again. The formula for Omega is not right because I
forgot to ponder the probability that a program chosen at random has a
length equal to L, and because halting and executing are not equivalent
(e.g., halting caused by an error still counts). Nevertheless, there seems
to be a connection.
What follows is an attempt to calculate, exactly, the probability that a
random expression of length L would execute. This probability, sounding
like you-know-who, depends on what the meaning of "execute" is. Let us
consider the meaning in the sense of ::, that is, "completes without error."
The probability that an expression, of length L, whose characters and chosen
(uniformly) at random from a character set S is given by the expression 'S
probability L' where the verb 'probability' can be defined as follows:
execute=. (1: @: ".) :: 0:
for=. ("1) (@:(>@:{))
mean=. +/ % #
probability=. ((mean ; mean&x:) @ , @ (execute for) @: (] $ < @[)) f.
probability
((+/ % #) ; (+/ % #)&x:)@,@(1:@:". ::0:"1@:(>@:{))@:(] $ <@[)
(However, notice that
xxx
|value error: xxx
yet
execute'xxx'
1
)
To avoid potential naming issues, as those experimented by Devon, we should
try the fixed definition in a fresh J session. The probabilities (FP and
exact ratio) of random expressions of length 1 and 2 chosen from the
alphabet are,
a.&((+/ (% ; %&x:) #)@,@(1:@:".@:({&a.) ::0:"1@:(>@:{))@:(] $ <@(a. i.
])@[)) 1
+--------+------+
|0.363281|93r256|
+--------+------+
a.&((+/ (% ; %&x:) #)@,@(1:@:".@:({&a.) ::0:"1@:(>@:{))@:(] $ <@(a. i.
])@[)) 2
+--------+----------+
|0.111771|7325r65536|
+--------+----------+
The probabilities of random expressions of length 1 and 2 chosen from
128{.a. are a little more interesting,
(128{.a.)&((+/ (% ; %&x:) #)@,@(1:@:".@:({&a.) ::0:"1@:(>@:{))@:(] $
<@(a. i. ])@[)) 1
+--------+------+
|0.726563|93r128|
+--------+------+
(128{.a.)&((+/ (% ; %&x:) #)@,@(1:@:".@:({&a.) ::0:"1@:(>@:{))@:(] $
<@(a. i. ])@[)) 2
+--------+----------+
|0.447083|7325r16384|
+--------+----------+
We can go even further if we choose from
'
!"#$%&''()*+,./0123456789:;<=>@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklm
nopqrstuvwxyz{|}~'
'
!"#$%&''()*+,-./0123456789:;<=>@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijkl
mnopqrstuvwxyz{|}~'&((+/ (% ; %&x:) #)@,@(1:@:".@:({&a.) ::0:"1@:(>@:{))@:(]
$ <@(a. i. ])@[)) 1
+--------+-----+
|0.968421|92r95|
+--------+-----+
'
!"#$%&''()*+,-./0123456789:;<=>[EMAIL PROTECTED]
lmnopqrstuvwxyz{|}~'&((+/ (% ; %&x:) #)@,@(1:@:".@:({&a.)
::0:"1@:(>@:{))@:(] $ <@(a. i. ])@[)) 2
+--------+---------+
|0.791136|1428r1805|
+--------+---------+
'
!"#$%&''()*+,-./0123456789:;<=>[EMAIL PROTECTED]
lmnopqrstuvwxyz{|}~'&((+/ (% ; %&x:) #)@,@(1:@:".@:({&a.)
::0:"1@:(>@:{))@:(] $ <@(a. i. ])@[)) 3
+--------+-------------+
|0.695165|596017r857375|
+--------+-------------+
At this point the process has encountered an interesting set of characters,
for instance, the expression '$:0' enters an infinite regress, runs out of
resources, and generates an error,
execute'$:0'
0
This is just one (the first?) of many more of this type to come. Actually,
the evaluating expression would have to test itself (ad nauseam) for a
certain L. Which one?
The tricky expression '(-^:_)1' appears for L=7. It does not appear to run
out of resources and it does not complete with an error; it just does not
complete. Does it execute? Either way, we could try to find expressions of
this kind, as Devon suggested, by printing the expressions before trying to
execute them to identify those that seem to hang (and attempt to prove
afterwards that they actually do). Unfortunately, some times, J quits all
together under pressure,
execute'(".@({&a.,":))40 34 46 64 40 123 38 97 46 44 34 58 41 41'
Can you write a program that finds these kind of scary expressions?
The original question seems to be one of those 'simple' questions that...
> -----Original Message-----
> From: [EMAIL PROTECTED] [mailto:general-
> [EMAIL PROTECTED] On Behalf Of Jose Mario Quintana
> Sent: Wednesday, September 26, 2007 10:06 AM
> To: 'General forum'
> Subject: RE: [Jgeneral] :[[(- .]]:!*: +()! *)[(:[ ! )+!*-!
>
>
> If I recall correctly, that generic probability, say P(L) is, in
> principle,
> related to Chaitin's Omega using J as a, Turing complete, programming
> language :
>
> Omega = sum (over L= 0,1,2,...) of P(L)
>
> According to Chaitin, Omega is a well defined real number and it is not
> only
> non-computable but, in some sense, it is the hardest kind of numbers to
> compute. It packs information about the halting problem so efficiently
> that
> is digits very quickly become randomly (uniformly) distributed. Yet,
> it is
> claimed, knowing just few thousands of its digits would resolve many
> current
> outstanding conjectures in number theory (those that can be posed as,
> relatively simple, hating problems).
>
> Chaitin's literature on Algorithmic Information Theory can be found in
> his
> home page:
>
> http://www.cs.auckland.ac.nz/~chaitin/
>
>
>
>
>
> > [EMAIL PROTECTED] On Behalf Of Stuart Baker
> > Sent: Tuesday, September 25, 2007 5:30 AM
> > To: General forum
> > Subject: Re: [Jgeneral] :[[(- .]]:!*: +()! *)[(:[ ! )+!*-!
> >
> > I wonder what is the probability that a randomly selected string of a
> > given length (maybe with an agreed proportion of non-alpha
> characters)
> > is actually executable in J? What kind of probability distribution
> > over increasing string length would you get? Overall it must be a lot
> > higher than with most of the other languages - I have occasionally
> > slumped over the keyboard late at night and accidentally entered
> > gibberish - no Shakespeare yet, but occasionally something happens
> > other than just getting an error...
> >
> > (another Stuart - Baker)
> >
> > On 9/23/07, Stuart Bruff <[EMAIL PROTECTED]> wrote:
> > > Out of curiosity, how many of you would automatically try (as I
> did)
> > to
> > > interpret the following nonsense that appeared as the header from a
> > piece of
> > > spam I received?
> > >
> > > :[[(- .]]:!*: +()! *)[(:[ ! )+!*-!
> > >
> > > I initially thought it was a misplaced J Forum email. I can't
> decide
> > whether
> > > it's sadder that I tried to interpret it, or that it took me about
> 3
> > seconds to
> > > realize it what it actually was :-(
> > >
> > > Stuart
> > > -------------------------------------------------------------------
> --
> > -
> > > For information about J forums see
> > http://www.jsoftware.com/forums.htm
> > >
> > ---------------------------------------------------------------------
> -
> > For information about J forums see
> http://www.jsoftware.com/forums.htm
>
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
