3 ms·
Another interesting question: If you could design your own instruction set, what is the smallest you could make a complete chess program? Is there an ultimate
by sillysaurus3 12y ago
Another interesting question: If you could design your own instruction set, what is the smallest you could make a complete chess program? Is there an ultimate limit, information-theory style?
- mikeash 12y agoI propose an instruction set which consists of a single instruction. I'll give it the mnemonic CHS, and when executed, it causes the CPU to play a game of chess with the user. (That's a long way to say that the question is somewhat under-constrained.)
- jdmichal 12y agoI propose yet another instruction set in which the CPU, unless interrupted, plays a game of chess with the user. 0-byte program achieved.
- joshu 12y agoThat's wordplay masquerading as understanding. Instead consider a CPU architecture and accompanying notation designed especially for playing chess. The other idea is not very interesting. Assuming some arbitrary architecture plus the necessary code to emulate it on a normal architecture (including your stupid CHS example) would normalize the "size" of the program, anyway -- unless there are hardware structures that are especially good for chess. Which was the essence of the question.
- rwmj 12y agohttps://en.wikipedia.org/wiki/Kolmogorov_complexity https://en.wikipedia.org/wiki/Kolmogorov_complexity