up vote 0 down vote favorite

For fair comparison of codegolf solutions in languages with different source alphabets, there should be a common unit of information.

Most sizes here are expressed in "characters" or "bytes", but not all characters are created equal. A brainfuck character can only have 8 values.

The standard measure of information in information theory is a bit. A brainfuck character is better counted as 3 bits.

Syntactic constraints may further reduce the entropy of program source.

In brainfuck not all 3^n length n programs are valid, because brackets must balance. A fancier measure of information content per character would be the limit for n->infinity of

log (# valid programs of n charcters) / n

but that is generally hard to compute.

For your favorite language, what is the number of possible values of a character? And what is the best known upper bound on the source entropy?

share
"what is the best known upper bound on the source entropy?" -- There is no upper bound, and the lower bound of 1 bit per symbol is attained in languages such as Jot (which has only the two symbols 0 and 1, every {0,1}-string being a valid program). – r.e.s. Sep 11 '12 at 1:05
1  
This is a slippery slope. After a while, this gets into insane territory like people compressing their programs before counting the size, etc. Just say no. Instead, it's probably better to just go with the flow and accept that some languages are naturally more succinct than others, and that yes, they will have a golfing advantage. – Chris Jester-Young♦ Sep 11 '12 at 12:21
Also, for a real-life example of golfing advantage being used for military advantage, see en.wikipedia.org/wiki/Code_talker. Yes, this stuff matters. :-) – Chris Jester-Young♦ Sep 11 '12 at 12:31

migrated from codegolf.stackexchange.com Sep 10 '12 at 23:23

2 Answers

up vote 1 down vote

For fair comparison of codegolf solutions in languages with different source alphabets, there should be a common unit of information.

Define 'fair'. How do you want to count that in languages allowing the full range of utf-8 for example?

share
up vote 0 down vote

Well, I for one, agree in principle.

I also agree with all the obstacles to accomplishing something like this. "How are you gonna handle ...?" [shrug!]

But everyone says a thing can't be done until someone does it.

share

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged