One instruction set computer
en.wikipedia.org
en.wikipedia.org
I wrote a little OISC virtual machine and assembler a while back. I got as far as adding interrupts to the system for keyboard input and console output before I stopped.
http://simonpstevens.com/projects/oiscvm
Source code is on githib:
Minimal architectures are interesting in their own right even if they don't have an immediate practical application, though I can think of some fields where they may be useful rather than merely a curiosity or a teaching aid.
I'll download your vm code and mess around with it some, thank you very much for posting the links.
http://en.wikipedia.org/wiki/SKI_combinator_calculus
You can define the Y combinator, and therefore recursion quite happily (if not very efficiently) using S and K.
I believe there are also approaches that use as single universal combinator - but I can't find any good references to these - I'd be quite interested to see definitions of S and K in terms of a single universal combinator.
There is also a U combinator referenced on this page:
as U = λ f . f(f) - haven't had time to sit down and actually work it through though.
[Edit: I notice that page says that U enables universal computation, not that it is sufficient.]
They recover the S and K by applying U to itself in interesting ways, but that's like saying 'this tool is so universal, you can use it as a hammer and a chisel by banging one instance of the tool with another tool just like it'.
That's not a very mathematical way of putting it I guess but I believe that is more or less the spirit of it.
A Turing tarpit is a Turing-complete programming language whose number of commands, operators, or equivalent objects is very small. These include brainfuck (8 commands, all with 0 operands), OISC (1 command, 3 operands), and Thue (1 command, 2 operands).
http://en.wikipedia.org/wiki/Esoteric_programming_language#T...
[edit: langton's ant suggests so - http://en.wikipedia.org/wiki/Langtons_ant]
One could argue that one has merely embedded the actual operands into the data fed to Rule 110, and I would then observe that in the context of Turing completeness, there is a fundamental fuzziness between data and code that goes "all the way down". All your no-operands single-instruction can really be is "do it", with "it" specified by the data.
A fascinating thing about computing with rule 110 seems to be that it is inherently parallel, the "instruction" is applied to the entire memory area in lockstep. There is no control flow of any kind. So if you have static data you need to encode it as "idle" instructions.
I/O is an even more interesting problem...