I/D machine

The I/D machine is a Turing-complete 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.
== Data storage ==
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:
=== Two-command view ===
The two-command view of the language, unsurprisingly, has two commands:
* I: Increments the cell the data pointer points to (i.e. ++*p).
* D: Dereferences the data pointer, and assigns the resulting value back to the data pointer (i.e. p=*p).
That's it. Any commands other than I and 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.
The two-command view of the I/D machine can be seen as a brainfuck derivative. I is the traditional + command, and D is a command that doesn't look strange in one. In fact, Symbolic Brainfuck has both commands, named + and ⌂ (actually represented as the byte \x7F in code).
=== One-command view ===
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 D and 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.
== Computational class ==
The I/D machine is Turing-complete, as cyclic tag can be compiled into it. See I/D machine Turing-completeness proof for more information.
== Implementations ==
=== Perl ===
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):
 $p=$a[$p]+=$_ for@F;redo
=== RAM0 ===
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:
* I becomes AS (i.e. increment z and store the result in *n)
* D becomes 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 ASNL commands.
=== Zig ===
A Zig implementation made by DivergentClouds.
===Scratch===
Interpreter in Scratch made by User:ChuckEsoteric08 with limited storage
=== Python ===
an two-command view interpreter written in Python 3 with only one big expression
(
 __builtins__.__setattr__('DP',0),addrs:={},
 get:=lambda:addrs.get(DP,0),
 do:=lambda i:{'I':lambda:addrs.__setitem__(DP,get()+1),
 'D':lambda:__builtins__.__setattr__('DP',get())}[i](),
 program:=list(filter(lambda x:x in'ID',r'''
 IIID
 )),
 [
 [
 (do(i),print(addrs,DP),__import__('time').sleep(0.5))
 for i in program]
 for _ in iter(lambda:1,0)]
)
== See also ==
* Iota
* Three Star Programmer
Category:LanguagesCategory:Computational modelsCategory:2018Category:Cell-basedCategory:Turing tarpitsCategory:No IOCategory:ImplementedCategory:Low-levelCategory:OISC