3 ms·

> The instruction set must be Turing complete.

by Shoop 12y ago

tbirdz 12y ago
I don't quite see how this requirement changes anything. You could have a full Turing complete instruction set, and still have a CHESS instruction that plays a game of chess with the user. The "Chess program" would still be 1 instruction.
- sillysaurus3 12y ago
  Well, an instruction set is said to be Turing complete if it can be used to simulate any Turing machine. A single instruction can't, so if you design an instruction set to implement Chess and then don't use it, that's not really the point of the question. Any ideas about how to better specify the rules of the competition to exclude degenerate answers like the one you provided? The goal is to answer the interesting question. You'd never find such a high-level instruction in a real instruction set, because it wouldn't be useful except to play Chess. I'd add a rule like "The goal of your instruction set is to be useful while still implementing Chess," but then that would exclude answers which give interesting instruction sets that aren't necessarily useful except in implementing Chess in the fewest possible bytes. Thanks for pointing out the flaws in my ruleset. I've been toying around with creating a blogpost about this, so having a bulletproof ruleset or at least one that isn't so easily sidestepped would be great.
  - dragonwriter 12y ago
    > Well, an instruction set is said to be Turing complete if it can be used to simulate any Turing machine. A single instruction can't Incorrect. A single instruction can be Turing complete. http://en.wikipedia.org/wiki/One_instruction_set_computer http://en.wikipedia.org/wiki/One_instruction_set_computer Though the relevant question is whether universal computation can be built on the back of an instruction which plays chess rather than one of the more typical bases for a OISC.
    - sillysaurus3 12y ago
      This is awesome. Thank you. What are some typical bases for OSIC?
    - taejo 12y ago
      > Though the relevant question is whether universal computation can be built on the back of an instruction which plays chess rather than one of the more typical bases for a OISC. Well you can have two instructions: SUBLEQ and CHESS. Then it's Turing-complete, and there's a one-bit program that plays chess.
  - vegedor 12y ago
    The instruction set has to exclusively contain instructions necessary to achieve the Turing-completeness. That excludes most of x86 etc. etc. Size-coding is all about restrictions. OTOH, if you could find that the CHESS instruction is Turing-complete, that would be a feat.
deleted 12y ago
[deleted]

> The instruction set must be Turing complete.

by Shoop 12y ago

> The instruction set must be Turing complete.

I don't quite see how this requirement changes anything. You could have a full Turing complete instruction set, and still have a CHESS instruction that plays a game of chess with the user. The "Chess program" would still be 1 instruction.

sillysaurus3 12y ago
Well, an instruction set is said to be Turing complete if it can be used to simulate any Turing machine. A single instruction can't, so if you design an instruction set to implement Chess and then don't use it, that's not really the point of the question. Any ideas about how to better specify the rules of the competition to exclude degenerate answers like the one you provided? The goal is to answer the interesting question. You'd never find such a high-level instruction in a real instruction set, because it wouldn't be useful except to play Chess. I'd add a rule like "The goal of your instruction set is to be useful while still implementing Chess," but then that would exclude answers which give interesting instruction sets that aren't necessarily useful except in implementing Chess in the fewest possible bytes. Thanks for pointing out the flaws in my ruleset. I've been toying around with creating a blogpost about this, so having a bulletproof ruleset or at least one that isn't so easily sidestepped would be great.
- dragonwriter 12y ago
  > Well, an instruction set is said to be Turing complete if it can be used to simulate any Turing machine. A single instruction can't Incorrect. A single instruction can be Turing complete. http://en.wikipedia.org/wiki/One_instruction_set_computer http://en.wikipedia.org/wiki/One_instruction_set_computer Though the relevant question is whether universal computation can be built on the back of an instruction which plays chess rather than one of the more typical bases for a OISC.
  - sillysaurus3 12y ago
    This is awesome. Thank you. What are some typical bases for OSIC?
  - taejo 12y ago
    > Though the relevant question is whether universal computation can be built on the back of an instruction which plays chess rather than one of the more typical bases for a OISC. Well you can have two instructions: SUBLEQ and CHESS. Then it's Turing-complete, and there's a one-bit program that plays chess.
- vegedor 12y ago
  The instruction set has to exclusively contain instructions necessary to achieve the Turing-completeness. That excludes most of x86 etc. etc. Size-coding is all about restrictions. OTOH, if you could find that the CHESS instruction is Turing-complete, that would be a feat.

deleted 12y ago

[deleted]