The I/D machine is an esoteric programming language and computational model created by User:ais523 in 2018, inspired by RAM0 and Three Star Programmer. It can be viewed as either a Turing tarpit with just two commands (neither of which takes arguments), thus being simpler than all known BF instruction minimalizations (although it does not support I/O); or as a particular OISC, with one command that takes an argument.
The I/D machine consists of an unbounded random-access memory; both addresses, and cell values, are unbounded nonnegative integers. Initially, these are all zero. Additionally, the machine has a single register, the "data pointer"; this initially has value 0 (i.e. it's a pointer to the first element of the RAM).
Syntax and semantics
The language can be interpreted in two different, equivalent, ways, which each have their own syntax:
The two-command view of the language, unsurprisingly, has two commands:
I: Increments the cell the data points to (i.e.
D: Dereferences the data pointer, and assigns the resulting value back to the data pointer (i.e.
That's it. Any commands other than
D (and numbers, if the implementation also supports the one-command view) are ignored. In order to do control flow, the program is run forever in an implicit loop.
In the one-command view, the language has only one command, which takes a nonnegative integer n as argument. Syntactically, this is just done by writing the integers in the normal decimal notation in question; any number but
0 must be separated from the subsequent number via a non-digit character (such as whitespace). (0 may be separated from the subsequent number via filler characters, but need not be; due to this rule, numbers may not be given with leading zeros.) Anything but integers is ignored (other than
I if the implementation also supports the two-command view).
The command itself is a run-length-encoded version of the two-command view; it runs
I n times, followed by running
D once. This can either be implemented via expanding the run-length encoding, or more efficiently via combining the effects of the commands:
*p += n; p = *p; (which can be further abbreviated to
p=*p+=n; if you like obfuscated code). Just as with the two-command view, the program runs forever in an implicit loop.
Here's a golfed implementation of the OISC variant in Perl (requires the
-a command line option, and you may want to consider
-Mbigint even though numbers that won't fit in a Perl integer will point to cells that won't fit in your address space anyway):
It's possible to compile the I/D machine to RAM0 via setting up the RAM0 registers so that n always contains the address that the pointer is pointing to, and z always contains the value stored in that address (i.e. the value that is read via dereferencing the pointer); the RAM0 and I/D memory spaces are identical. This invariant is trivially true at the start of the program (with everything being zeros). Here are implementations of the I/D commands in RAM0 that maintain the invariants:
AS(i.e. increment z and store the result in *n)
NL(i.e. set n to z and z to *z)
This therefore gives an alternative proof that RAM0 is Turing-complete using only the