On Thu, Oct 11, 2018 at 9:35 PM Jim Bromer via AGI <[email protected]> wrote:
>
> Matt said, "A string is random if there is no shorter description of
> the string."
>
> That is a conjecture, or a hypothesis.
No, that is a definition. If you think some other definition is more
appropriate, then that's philosophy.
> if there is no general algorithm to distinguish or detect them then
> the hypothesis cannot be validated. While you might present a string
> and declare it to be "random" the fact that you cannot prove that it
> is the shortest description of the string and therefore purely random,
> or random, then the conjecture cannot be sustained.
Sometimes you can prove that a string is not random by compressing it
in your chosen language. Sometimes you can prove that a string is
random by exhaustively searching for shorter descriptions and hoping
that all of them either halt or can be proven to run forever.
Sometimes that is easy. For example, in C, all strings up to 8 bytes
are random because the shortest possible program in C is 8 bytes:
main(){}
What you can't do is find a general algorithm that inputs a string and
tells you if it is random. I already gave you Kolmogorov's simple
proof of this.
--
-- Matt Mahoney, [email protected]
------------------------------------------
Artificial General Intelligence List: AGI
Permalink:
https://agi.topicbox.com/groups/agi/T55454c75265cabe2-Mb28d11dcce94257fa234a24e
Delivery options: https://agi.topicbox.com/groups/agi/subscription
