Prev: True Random Number Generator
Next: Confused about random strings
From: David Eather on 26 Jan 2010 14:25
Peter Fairbrother wrote:
> Kristian Gj�steen wrote:
>> Simon Johnson <simon.johnson(a)gmail.com> wrote:
>>>> It is "easy" to find. Just run each of the finite number of shorter
>>>> programs and see if it produces the string. While a bit tedious,
>>>> this is
>>>> defines the shortest program.
>>> The point is, such a "stepper" programmer would generate the string
>>> would it not, since it constructs and runs each program in passing?
>>
>> This is not the point.
>>
>> The "obvious" enumeration program that runs every short program isn't
>> an algorithm. It might never terminate.
>>
>
> You could tell it to stop after say 128! (or busy beaver 9) steps, which
> would cover the numbers up to 128! or (BB9).
>
> This can be fixed though, by saying a valid program *only* outputs the
> string in question.
>
> But it doesn't solve the language problem.
>
> -- Peter Fairbrother

If it helps at all the Windoze calculator can calculate factorials up to
and beyond (patience is the key) 2^16! directly
(= 5.1629485230975091650002279432724e+287193)
From: WTShaw on 27 Jan 2010 01:19
On Jan 26, 1:25 pm, David Eather <eat...(a)tpg.com.au> wrote:
> Peter Fairbrother wrote:
> > Kristian Gjøsteen wrote:
> >> Simon Johnson  <simon.john...(a)gmail.com> wrote:
> >>>> It is "easy" to find. Just run each of the finite number of shorter
> >>>> programs and see if it produces the string. While a bit tedious,
> >>>> this is
> >>>> defines the shortest program.
> >>> The point is, such a "stepper" programmer would generate the string
> >>> would it not, since it constructs and runs each program in passing?
>
> >> This is not the point.
>
> >> The "obvious" enumeration program that runs every short program isn't
> >> an algorithm. It might never terminate.
>
> > You could tell it to stop after say 128! (or busy beaver 9) steps, which
> > would cover the numbers up to 128! or (BB9).
>
> > This can be fixed though, by saying a valid program *only* outputs the
> > string in question.
>
> > But it doesn't solve the language problem.
>
> > -- Peter Fairbrother
>
> If it helps at all the Windoze calculator can calculate factorials up to
> and beyond (patience is the key) 2^16! directly
> (= 5.1629485230975091650002279432724e+287193)

Historically, displayed digits are not a guarantee of their accuracy.
Proof of the above might be checked if you had the time as the
programmer might have made a mistake never to be questioned. Low
significance tends to have little response in verification. Round
off and be done with it or get ready for an obscure and likely to be
an unrewarded adventure which contains new errors.
From: WTShaw on 29 Jan 2010 04:35
On Jan 21, 6:28 am, "Joseph Ashwood" <ashw...(a)msn.com> wrote:
> "Peter Fairbrother" <zenadsl6...(a)zen.co.uk> wrote in message
>
> news:4b576ab4$0$2532$da0feed9(a)news.zen.co.uk...
>
> > In general there is the idea that random permutations, or sequences, are
> > not compressible.
>
> Actually permutations are compressible. Labeling each permutation with an
> integer, significantly abbreviated the permutation. As an example take AES,
> the key can be trivially converted to an integer, and serves as such an
> index.

If you index a permutation as an integer in another base, all you have
done is just that and such is useless without a conversion table
assigning values to the elements in the permutation. Consider that
permutations can be floating and reassigned convenient to a specific
algorithm in use and the specific elements in them would have no
ranking or absolute value at all. This fact is most useful when
properly harnessed using nonlinear algorithms.

Permutations need not be simply used as linear strings as they could
be but as endless wheels of N characters. The number of permutations
would be somewhat less since there would be not true ends to each
different string. Again, many permutations can be used in linear
manner or best utilized in other ways. Its easier to implement logical
programmed manipulations that simulate real world models than try to
tackle them as anything line linear functions, which they are not.

Randomness in circular permutations distributed differently in each
wheel and available to encrypt random value added to the system as
might be necessary in encryption and be automatically recovered in
decryption. The problem that the attacker faces should be in never
seeing a linear or comprehensive use all segments of permutation keys.
This does meet Shannon's requirement for relative strength without the
linear pitfalls of the OTP.

Although not truly esoteric,if this process is still a mystery to many
of you, remember it has not been beyond more than several others and
have implemented these ideas with some novel differences.
First  |  Prev  | 
Pages: 1 2 3 4 5 6 7
Prev: True Random Number Generator
Next: Confused about random strings