Skip to content

Instantly share code, notes, and snippets.

@aaronryank
Last active October 4, 2017 04:09
Show Gist options
  • Save aaronryank/5eff98fe13c4d05c091982daa56d0c23 to your computer and use it in GitHub Desktop.
Save aaronryank/5eff98fe13c4d05c091982daa56d0c23 to your computer and use it in GitHub Desktop.
A draft for a pop-con on PPCG SE

Design a One Instruction Set Computer

Yes, it's a [tag:popularity-contest]. Please read the entire question before downvoting or close-voting. The three headers make up the spec, and the bullet points below them make up the rules.

Your challenge is to design a one instruction set computer (OISC):

An [OISC] is an abstract machine that uses only one instruction – obviating the need for a machine language opcode. With a judicious choice for the single instruction and given infinite resources, an OISC is capable of being a universal computer in the same manner as traditional computers that have multiple instructions.

For the purposes of this challenge, an OISC is a Turing-complete programming language with a single command that takes at least one argument. It must take at least one argument to prevent it from being a ZISC or a Lenguage-equivalent.. You may take as many arguments as you want, as long as rule #1 is followed.

Here are some examples of single commands that make a Turing-complete OISC:

As [tag:popularity-contest]s are usually closed, here are three rules in an attempt to make this challenge objective:

You must create a real OISC

No matter what arguments are passed to the instruction, the same behavior will happen. So a "OISC" language with commands that have integer names is invalid. To elaborate, this is an invalid submission:

  • When the first argument to foobar is 1, it will output the memory position specified by second argument if the position of the third is truthy.
  • When the first argument to foobar is 2, it will read a character into the position of the second argument and store the result in the position of the third.
  • When the first argument to foobar is 3, it will theoretically calculate Graham's number into the second argument position and store the number of seconds it ran before running out of memory in the third.

That qualifies as creating builtins to solve the challenge and is a standard loophole. However, this is a valid submission:

foobar is equivalent to this code:

mem[b] = mem[b] - mem[a];
if (mem[b] < 0) goto c;
  • The 0th memory position is an output buffer. Whenever this is nonzero, the value stored in it is outputted as an ASCII character and immediately set to zero.
  • The 1st memory position is an input buffer. Whenever it is accessed, an ASCII character is read from standard input and stored in the buffer.

You must provide an interpretation or proof thereof

You must provide an interpreter for your language. This interpreter should only be restricted by memory/time (e.g. must have no user-imposed restrictions). If you do not provide an interpreter for your language (for whatever reason other than laziness) you must prove that it is possible for one to be written. An interpreter must be possible.

You must prove its Turing-completeness

You must prove (usually by demonstration) that your language can interpret or have the same behavior as another Turing-complete language. A simple test would be Brainf**k. If you do not provide an interpreter for another Turing-complete language, you must demonstrate equivalence to another Turing-complete language. For example, a (non-OISC) language that has all the same commands as Brainf**k (and the same lack of user-imposed memory restrictions) is Turing-complete because anything that can be done in Brainf**k can be done in the language.

Here is a list of very simple-to-implement Turing-complete languages.

Additional OISC requirements:

  • You must create your own OISC and not simply implement a pre-existing one.
  • This OISC should only have one instruction - it cannot have multiple instructions with one of them making it Turing-complete.
  • Your OISC may have any syntax you like, except the name of the command should not need to be present in the source code at any time.
    So while a line in your source code may look like 1,2,3 or 1 2 3 or 1, 2, 3; etc, it may not look like CMD 1,2,3 or CMD 1 2 3 or CMD 1 2 3; etc.

As with [tag:popularity-contest], the answer with the most votes wins. This challenge will officially end with a winner chosen in two weeks of posting, but it will always be open to further submissions.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment