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

See also

• Iota