X-Message-Number: 8625
Date: Thu, 25 Sep 1997 19:27:33 -0400
From: "John P. Pietrzak" <>
Subject: Re: Digital Shakespeare
References: <>

Hi, I'm back. :)  I've found 200+ messages in my mailbox after leaving
it alone for a bit over a week, so it'll be a while before I clear it
all out (and unsubscribe from some mailing lists...); so, I'll be making
a few archaic replies over the next few days.

[On the AIC as a definition of complexity]
> On Tue, 16 Sep 1997 "John P. Pietrzak" Wrote:
> 
>         >Now, may I ask, what does string compressability have to do
>         >with algorithm complexity?
> 
> I don't know and never said I did, I was talking about a possible
> definition so naturally I can't use the word "complexity" in a
> definition of complexity and I did not.

Wow.  Having a bit of trouble parsing this sentence (maybe I'm just
too tired right now).  (a) You give AIC as possible definiton of
complexity.  (b) I refute claim, asking for more detail (particularly
involving string compressibility).  (c) You state that string
compressability is not involved (in AIC?) and that the term
complexity is out of bounds when describing the definition of the
term complexity.  I'm sorry if it sounded that way, I must have
written it incorrectly.  I just don't see compressibility as equivalent
to complexity, and wanted more detail.  Perhaps the following material
will help me out.

> I said that if complexity is nothing but AIC (and I don't think it is)
> then complexity is  "the smallest computer program that can produce
> the string". "Smallest" is an objective and universal measure, easy to
> understand, if there is an objective and universal measure of
> "algorithm complexity" nobody has found it yet and it sure isn't easy
> to understand.

Good.  Then you agree with me, the AIC is NOT a measure of algorithmic
complexity.

>         >Suppose I take two strings of the same length, one of which
>         >is very uncompressible, the other being very compressible, if
>         >the algorithm to print out the uncompressible string consists
>         >of a single (gigantic) printf() statement, does that mean
>         >that _algorithm_ is more complex than the compression
>         >algorithm for the second string, which is smaller but
>         >contains more statements?
> 
> 
> I don't know  what you mean by "smaller but contains more statements"

Simple.  For me, the algorithm with the smallest number of statements
is the smallest algorithm.  If this was also the measure of size that
the AIC used, then the trivial way to create the smallest algorithm
for any given string would be to write a program consisting of a single
statement which returned that string.  However, the AIC doesn't find
that as a solution, and therefore must be using a different measure of
algorithmic size.

> [...] a Turing machine makes no distinction between data and
> instructions, it's all just marks on a tape. If the string is random
> then the length of the smallest computer program that can produce the
> string is the string itself. If the string is not random, even if it's
> infinitely long like PI, then length of the smallest computer program
> that can produce the string is not only finite it's downright small.

Ah.  Unfortunately, grasshopper, you have underestimated the power of
the "mark".  What is a mark?  Anything you want it to be.  I am
certainly allowed to use a language containing two particular marks,
those being "printf" and the string I want to print.  I then place
those two marks on the tape, and have a truly trivial algorithm for the
TM to execute.  (Of course, you can simplify this to have a single mark
containing "printf(string)", or even gimmick the TM itself so that
no matter what the input (even if empty), it always prints out the
desired string.)

One must be careful when one toys with the TM.  It is a mental tool,
and works by convention; thus, there are certain assumptions you must
recognize and understand before you can successfully create one.
First, remember that the TM language (constituting the marks) is
completely arbitrary, and is therefore not necessarily binary.  Because
of this, one can choose a language particularly suited to solving a
given problem.  Second, remember that there is NO agreed-upon convention
as to what constitutes an "instruction" in any given TM (even a
universal TM).  Therefore, one can choose instructions which are
particularly suited towards solving a given problem.

Ok.  Now, let me assume that you were talking about a TM using a binary
language, and further assume that this TM was built with instructions
simulating those of a standard microprocessor (addition, subtration,
load, store, etc.), with tokens representing those commands using an
optimally small number of bits.  In this case, if you are talking about
the size of the algorithm as being the total number of bits used
to represent the algorithm on the tape, you are indeed correct, there
are algorithms to print certain strings which are smaller than an
algorithm containing the verbatim string itself.

However, I must say that after all these assumptions placed upon an
algorithm working in an imaginary machine, I find this measure of
size rather hard to swallow as a measure of complexity.

> Does this mean that random gibberish is more complex than PI?  Yes is
> you believe that complexity is just AIC. I don't.

But, why would anyone?  Given what I've stated above, I can only
imagine that you're bringing up the AIC as a straw man set up for you
to tear down.

[Back on to the definition of intelligence]
>         >>>In fact, _you_ don't know why you chose them; if you did,
>         >>>you'd have some sort of definition of intelligence.
>         >>Utter and complete nonsense.
>         >Nonsense in that you _do_ know why you chose them?
> 
> No. I chose them, I think, because they seems to work pretty well
> together most of the time, but feel free to disagree because it has
> nothing to do with my comment. What is utter and complete nonsense is
> the idea that if I did know why I picked them then there must be a
> definition of intelligence. I think it very likely that we don't know
> of such a definition because one does not exist or at least can not
> be written down on a paper smaller than the galaxy.

Ok, follow my (admittedly rough) logic here:

axiom	1) You chose several examples of intelligence.
axiom	2) You did _not_ choose them randomly.
thm	3) (from 1 & 2) You must have used something other than random
	choice.
axiom	4) In my world, "not random" == "follows rules" == "has
	definition".
thm	5) (from 3 & 4) You used a definition of intelligence.
axiom	6) You did not use a definition of intelligence.

Considering 5 and 6 here, you can understand my confusion.  One of
the axioms must be incorrect: Either you _didn't_ choose examples of
intelligence, you _did_ choose randomly, things can be "not random"
and yet not follow rules, or you actually do have a definition of
intelligence.  Or I've got something really screwed up.

> Yes there are reasons for most of what we do, but this is not
> geometry, there are no axioms and it's certainly not based on
> definitions, they're stochastic rules of thumb.

(John develops nasty grin on face) Ok, guy, tell me, what is a
stochastic rule of thumb?  How do you know when you are properly
following a rule stochastically and when you aren't?  If you can't
tell, don't tell me that you in fact _are_ following a rule
stochastically!  (In other words, I want your (rigorous!) definition
here. ;) )

>         >Give me knowledge without definitions.
> 
> Most people like most things that are beautiful.
> Most people like some things that are not beautiful.
> A similar problem may have a similar solution
> Intelligent people usually solve problems better that stupid people.
> It's often unwise to judge the value of something by its size.
> Insulting a person usually makes him dislike you.
> If you want to make a lot of money it's often helpful if your
> employees remain conscious when on the job.
> If you travel to Sweden the first person you see when you get off
> the airplane is unlikely to be an albino sumo wrestler playing the
> bagpipes.

What gibberish.  What are people?  What is beautiful?  etc., etc.
You write this material with the underlying assumtion that such
things as people, beauty, and bagpipes are already understood by me.
But I've already claimed that you and I have definitions of, for
example, bagpipes; your use of those words gives me nothing to work with
in understanding your side of the argument.  What if I didn't know
what Sweden was?  How would you explain it to me?  I think it's rather
unlikely that you would be able to trot out a series of examples of the
land mass for me to learn (particularly if life-size); you would rather
have to build up the concept of Sweden for me via referents to other
mutually understood concepts between us.  In other words, you would have
to provide me with a definition of Sweden (in terms of other understood
concepts).


John

Rate This Message: http://www.cryonet.org/cgi-bin/rate.cgi?msg=8625