32
9
Notice: I'm willing to give a bounty to any answer that I find interesting.
Your challenge is to design a Turing-complete 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.
Here are some examples of single commands that make a Turing-complete OISC.
Rules:
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 include a formal proof that your language is Turing-complete. A simple way to do this is by proving that it can interpret or have the same behavior as another Turing-complete language. The most basic language to interpret would be Brainf**k.
For example, a normal 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 implemented in Brainf**k can be implemented in the language.
Here is a list of very simple-to-implement Turing-complete languages.
Additional OISC requirements
This OISC should only have one instruction - it cannot have multiple instructions with one of them making it Turing-complete.
Your OISC may use any syntax you like. You should define in your answer what is instruction, what is data, and what is a no-op (e.g. whitespace). Be creative!
Arguments do not just need to be integers. For example, /// is a beautiful example of a Turing-complete OISC.
How and if input and output are taken and given are left up to you. Most OISCs implement I/O via specific memory locations, but there may be other ways to do so, and you are encouraged to find one.
A valid answer must provide some example code in your OISC, either by including it in the post or linking to a simple challenge solved in the language.
Voting
Voters, please remember not to upvote boring submissions. Examples:
- Lenguage-equivalents
- An implementation of an existing OISC (answerers, please create your own!)
- An "OISC" in which the first argument specifies a command to call (example)
However, you should upvote interesting, creative submissions, such as:
- An OISC based off of a mathematical equation
- A Turing-complete ZISC based on a neural network
- An OISC in which output I/O happens in other ways than certain memory locations
Winning
As with popularity-contest, the answer with the most votes wins! Good luck!
Sandboxed post and OISC Wikipedia page. – MD XF – 7 years ago
not sure /// is an oisc still, due to its print instruction. – Destructible Lemon – 7 years ago
@DestructibleLemon It doesn't have a
print
instruction. It only has one instruction, which prints as a side effect. – MD XF – 7 years ago10What is an "instruction"? And how do we count them? – Post Rock Garf Hunter – 7 years ago
I wish I knew enough to do this, it looks fun. – NoOneIsHere – 7 years ago
1@NoOneIsHere i wish i knew enough just to vote xD – Brian H. – 7 years ago
2I downvoted this. I think this is a very interesting idea, but you don't explain exactly what an OISC is and how to confirm something is one. I made BF an OISC, but that is clearly against the spirit of the question, but technically valid. – NoOneIsHere – 7 years ago
1@MDXF i don't think you get ///: it has a substitution command, and it has print commands, which is not just a side effect of the substitution command – Destructible Lemon – 7 years ago
@DestructibleLemon no it doesn't have a print command, it just prints everything left after substitution at the end of the program. – MD XF – 7 years ago
@MDXF http://esolangs.org/wiki////#Description
– Destructible Lemon – 7 years ago1@NoOneIsHere Because [tag:popularity-contest]. Yes, it's valid, but it has poor score (vote tally), so it won't win. – user202729 – 7 years ago
1@user202729 Yeah, but just the fact that it is impossible to make sure a language truly has only 1 instruction makes me feel that the challenge is under-speficied. – NoOneIsHere – 7 years ago
Can one mandate that several specific values, [0, 1, and -1], are stored in memory locations? – user230118 – 7 years ago
@user230118 yes, that's fine. – MD XF – 7 years ago
Since I've voted to close this as unclear, I thought it would be a good idea to make explicit why. As per my previous comment there is no explanation as to how one can count the size of the instruction set. Without this definition I don't know how we can determine if an answer is a valid one. – Post Rock Garf Hunter – 7 years ago
@WheatWizard Can you think of an objective definition then? – MD XF – 7 years ago
@MDXF I don't even really understand what you want out of a definition, mostly because I'm unclear as to what you think is an OISC. If had an idea for a definition I would have already suggested it, but I don't know what qualities you want out of a definition. – Post Rock Garf Hunter – 7 years ago
Is
MOV
-like languages not real OISC? – l4m2 – 7 years ago