Slashdot Mirror

The "images" were created using the BESM-4 computer. The much more widely used BESM-6 used 48 bit words and you can see its character encoding table here:

http://www.mailcom.com/besm6/encoding_ru.html

The BESM-4 had 45-bit words and I'm not sure what encoding it used, but it's likely to be the same or similar to the above. Note how that character table has math operators like logical conjucntion/disjunction even but lacks an exclamation mark and even two letters of the Russian alphabet. Wasn't exactly meant for word processing ;)

You can start by googling Elbrus or BESM and see that russians had real shitty hw but the knowhow was there http://mailcom.com/besm6/index_ru.shtml http://en.wikipedia.org/wiki/Elbrus_(computer)

They could fund a prize competition such as the following:

Let anyone submit an open source program that produces, with no inputs, one of the major natural language corpora as output.

S = size of uncompressed corpus
P = size of program outputting the uncompressed corpus
R = S/P (the compression ratio).

Award monies in a manner similar to the M-Prize:

Previous record ratio: R0
New record ratio: R1=R0+X
Fund contains: $Z at noon GMT on day of new record
Winner receives: $Z * (X/(R0+X))

Compression program and decompression program are made open source.

Explanation For an idea of why the C-Prize can solve the AI problem, if it is solvable, see Matthew Mahoney's comment on it:

Matt Mahoney
Jun 17, 7:18 pm show options
Newsgroups: comp.compression
From: "Matt Mahoney"
Date: 17 Jun 2005 20:18:59 -0700
Local: Fri, Jun 17 2005 7:18 pm
Subject: Re: The C-Prize

Hutter's AIXI, http://www.idsia.ch/~marcus/ai/paixi.htm makes another argument for the connection between compression and AI that is more general than the Turing test. He proves that the optimal behavior of an agent (an interactive system that receives a reward signal from an unknown environment) is to guess that the environement is most likely computed by the shortest possible program that is consistent with the behavior observed so far. In other words, the most likely outcome for any experiment is the one with the simplest explanation, where "simplest" means the smallest program that could model what you currently know about the universe.

He gives a formal proof, but it basically says that the only possible distribution of the infinite set of programs (or strings) with nonzero probability is one which favors shorter programs over longer ones. Given any string of length n with probability p > 0, there are an infinite set of strings longer than n, but only a finite number of these can have probability higher than p.

-- Matt Mahoney

It is shown that optimal text compression is a harder problem thanartificial intelligence as defined by Turing's (1950) imitation game; thus compression ratio on a standard benchmark corpuscould be used as an objective and quantitative alternative test for AI (Mahoney, 1999).

Let anyone submit an open source program that produces, with no inputs, one of the major natural language corpora as output.

S = size of uncompressed corpus
P = size of program outputting the uncompressed corpus
R = S/P (the compression ratio).

Award monies in a manner similar to the M-Prize:

Previous record ratio: R0
New record ratio: R1=R0+X
Fund contains: $Z at noon GMT on day of new record
Winner receives: $Z * (X/(R0+X))

Compression program and decompression program are made open source.

Explanation For an idea of why the C-Prize can solve the AI problem, if it is solvable, see Matthew Mahoney's comment [tinyurl.com] on it:

Matt Mahoney
Jun 17, 7:18 pm show options
Newsgroups: comp.compression
From: "Matt Mahoney"
Date: 17 Jun 2005 20:18:59 -0700
Local: Fri, Jun 17 2005 7:18 pm
Subject: Re: The C-Prize

Hutter's AIXI, http://www.idsia.ch/~marcus/ai/paixi.htm makes another argument for the connection between compression and AI that is more general than the Turing test. He proves that the optimal behavior of an agent (an interactive system that receives a reward signal from an unknown environment) is to guess that the environement is most likely computed by the shortest possible program that is consistent with the behavior observed so far. In other words, the most likely outcome for any experiment is the one with the simplest explanation, where "simplest" means the smallest program that could model what you currently know about the universe.

He gives a formal proof, but it basically says that the only possible distribution of the infinite set of programs (or strings) with nonzero probability is one which favors shorter programs over longer ones. Given any string of length n with probability p > 0, there are an infinite set of strings longer than n, but only a finite number of these can have probability higher than p.

-- Matt Mahoney

It is shown that optimal text compression is a harder problem thanartificial intelligence as defined by Turing's (1950) imitation game; thus compression ratio on a standard benchmark corpuscould be used as an objective and quantitative alternative test for AI (Mahoney, 1999).

Now, who might fund something like the C-Prize?

Shto?!! That is filthy, American lie! Stock exchange runs on top quality Bol'shaya Ehlektronno-Schetnaya Mashina! Look at picture!

Is massive mainframe system! With boshoya power! As much as, er, four 286s and an Apple IIe ...

The profound danger of a biased AI here is quite avoidable. The theoretic problem of unbiased AI has been formally solved by Marcus Hutter with AIXI:

Computational AI. There are strong arguments that AIXI is the most intelligent unbiased agent possible in the sense that AIXI behaves optimally in any computable environment.

This is the reason I set up the following definition of the C-Prize:

Let anyone submit a program that produces, with no inputs, one of the major natural language corpora as output.

S = size of uncompressed corpus
P = size of program outputting the uncompressed corpus
R = S/P (the compression ratio).

Award monies in a manner similar to the M-Prize:

Previous record ratio: R0
New record ratio: R1=R0+X
Fund contains: $Z at noon GMT on day of new record
Winner receives: $Z * (X/(R0+X))

Compression program and decompression program are made open source.

Explanation For an idea of why the C-Prize can solve the AI problem, if it is solvable, see Matthew Mahoney's comment on it:

Matt Mahoney
Jun 17, 7:18 pm show options
Newsgroups: comp.compression
From: "Matt Mahoney"
Date: 17 Jun 2005 20:18:59 -0700
Local: Fri, Jun 17 2005 7:18 pm
Subject: Re: The C-Prize

Hutter's AIXI, http://www.idsia.ch/~marcus/ai/paixi.htm makes another argument for the connection between compression and AI that is more general than the Turing test. He proves that the optimal behavior of an agent (an interactive system that receives a reward signal from an unknown environment) is to guess that the environement is most likely computed by the shortest possible program that is consistent with the behavior observed so far. In other words, the most likely outcome for any experiment is the one with the simplest explanation, where "simplest" means the smallest program that could model what you currently know about the universe.

He gives a formal proof, but it basically says that the only possible distribution of the infinite set of programs (or strings) with nonzero probability is one which favors shorter programs over longer ones. Given any string of length n with probability p > 0, there are an infinite set of strings longer than n, but only a finite number of these can have probability higher than p.

-- Matt Mahoney

Matt Mahoney is the author of Text Compression as a Test for Artificial Intelligence which states:

It is shown that optimal text compression is a harder problem thanartificial intelligence as defined by Turing's (1950) imitation game; thus compression ratio on a standard benchmark corpuscould be used as an objective and quantitative alternative test for AI (Mahoney, 1999).

(Mahoney is also a competitor who has some winnings from The Calgary Corpus Compression Challenge.)

Now a big question here is whether it might be possible to create a verifiably unbiased AI without making the compression program open source. In any case I don't think it is wise to trust any AI that hasn't at least gone through a compression competition with other purportedly unbiased AI's compressing an open source corpus.

Now, who might fund something like the C-Prize?

Well, here's a suggestion:

Since:

1. Larry Page is on the board of directors of the X-Prize Foundation.
2. The mission of the X-Prize Foundation:

Think about it more like compressing the entire content of the Library of Congress.

What's that, 10 terabytes? The overhead for the program itself would be insignificant, so we're probably arguing over nothing anyway.

Getting back to my point, we're already pretty close to the 1.3 bpc figure, and I think it would be rather trivial to reach that figure in compressing the LoC, if that were your only goal (of course, Shannon's figure was using only 27 characters, 26 letters and a space, so you'd have to force the LoC content into that form first, there'd also be the problem that the LoC contains more than just english text).

The calgary corpus was compressed down to 1.54 bits per character. Now, this figure doesn't include the size of ha, or rar, or the linux distro, but with proper motivation this could be compressed to a size which would be negligible compared to the LoC, though you'd probably have to ditch the Linux distro and just write a bootloader which runs your compressor directly. However, I think this points out how arbitrary it is to count the exectable itself - this means you're factoring in all the specifics of the intel processor, both positive and negative (mostly negative on intel, since you've got all the overhead for input, output, memory allocation, etc, but in theory the processor/bios could be utilized in some way, especially if you don't restrict yourself to intel architecture).

Anyway, I think the 1.3 bits per character mark would be reached in a matter of weeks, given an input as large as the Library of Congress, stripped down to 27 characters, and assuming the payout was at least a few thousand dollars.

Maybe I'm way off, but I hope someone takes your suggestion, because I'd love to give it a try. I'd almost be willing to do it just to prove you wrong, but it'd take a lot more than a few weeks without any monetary incentive.

Most information theorists these days recognize that algorithmic complexity using Kolmogorov complexity is the ideal way to define information content.

Well, we're not talking about information content, we're talking about artificial intelligence.

was build 1936 in Germany (Zuse Z1) and not 1951 in Ukraine as BusinessWeek claimed.

Business Week should have said "stored program computer", or "Von Neumann computer", as per the timeline on this page. (Emphasis on "continental Europe"; the first Von Neumann machine ever, as far as I know, was built at the University of Manchester.)

Sergey Alekseyevich Lebedev, the head of the group that developed that machine (MESM), was born in Russia; that group also created the Big-Ass Computer series (OK, that's not an exact translation of "Bolshaja Elektronno-Schetnaja Mashina" :-)). There's a BESM-6 Nostalgia page about the sixth series of BESM machines. (It's a bit tricky to do the usual sort of buffer overflow tricks on those machines:

Each memory word had two parity bits - one for each half, the combined parity for the whole word must have been odd. Thus, the distinction between code and data was achieved: one had the halfword parities even-odd, the other - odd-even, so code overwriting or branches to data got caught as soon as an offending instruction was executed. (The program had to ask the kernel to switch the mode of the store instruction to "code" before generating executable code, or to use a special system call, so using self-modifying code was discouraged.);

Is at BESM-6 Nostalgia page.

Unless and until they show a self-contained archive of a small size that can be brought to a standalone computer and expanded into a standardized benchmark data compression corpus, they can be ignored.

I pity the poor VPs who gave them money.

...namely, for my BESM-6 museum? Well, it's more of a nostalgia page, but anyway.

BESM6: 60's era monsters, built with transistors(!), real core memory and magnetic drums.

For more information, see the BESM-6 Nostalgia Page.

I was unaware of any computer hardware coming from Russia.

See this page on the BESM-6 computer.