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 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 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...
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
