Divmeq
Divmeq (derived from 'DIVide and branch, if Modulo EQuals 0') is a one-instruction Turing-complete esoteric programming language created by User:TheCanon2.
Divmeq was designed with the goal of being the simplest Turing-complete language. Divmeq's unusual properties help accomplish this.
- One instruction, with only two operands
- A single accumulator
- No self-modifying code
- No output
Thus, Divmeq should be able to be easily implemented in any reasonable language.
Commands
Divmeq has a single unbounded accumulator, x
. The Divmeq command accepts two operands, A
and B
.
If x is divisible by A, divide x by A and jump to line B. Else, move 1 line forward.
Line numbers start at 0 and increment by 1 for each line in the program. The program halts if the line number is greater than the length of the program.
Divmeq accepts a numeric input at the beginning of a program, which is written to the accumulator. The accumulator is set to 1 if no input is given.
Examples
Hello, World!
0: 1/72 1 1: 72/101 2 2: 101/108 3 3: 1 4 4: 108/111 5 5: 111/44 6 6: 1.375 7 7: 32/87 8 8: 29/37 9 9: 37/38 10 10: 19/18 11 11: 1.08 12 12: 100/33 13
The ASCII values in 'Hello, World!' are in the pseudo-output.
Truth machine
0: 2 2 1: 1 1
This halts if the input is 0 and never halts if the input is 1.
XKCD Random Number
0: 0.25 1
Sets the accumulator to 4.
A+B problem
0: 1 2 1: 0.5 2 2: 3 1
When given input , returns . Prime factorisation is essential for storing more than one value in Divmeq's accumulator.
This program can be shortened to:
0: 1.5 0
A-B problem
0: 1 2 1: 2 2 2: 3 1
When given input , returns .
This program can be shortened to:
0: 6 0
A*B problem
0: 3 2 1: 1 7 2: 7 2 3: 2/77 3 4: 11/2 4 5: 7/5 5 6: 1 0 7: 2 7 8: 5/2 8
When given input , returns . Does not work for larger values of due to errors caused by floating point precision.
Squaring
0: 2/15 0 1: 5/2 1 2: 3 4 3: 1 9 4: 7 4 5: 2/77 5 6: 11/2 6 7: 7/5 7 8: 1 2 9: 2 9 10: 5/2 10
When given input , returns . Does not work for larger values of due to errors caused by floating point precision.
Computational class
Divmeq is Turing-complete for it can simulate any section 14.2 single-register Minsky machine.
0: 1/n 1
Multiply r by n
0: n A
Check if r is divisible by n, and if so, divide by n and jump to A
However, the nature of quines in Divmeq is uncertain, thus the Turing-completeness of Divmeq may be disproven.
Implementations
The following Python script is an interpreter.
prgm = [[]] prgm.pop(0) while True: line = input('%s: ' % len(prgm)) # Displays line numbers automatically if line != "eof": line = list(line.split(" ")) prgm.append([eval(line[0]), int(line[1])]) else: break init = input('>i ') # Grabs user input if init == "": x = 1 else: x = float(init) # Executes the program def divmeq(A, B): global x global inst if x % A < 1e-16 or x % A > (A - 1e-16): # 1e-16 may need to be adjusted x /= A x = round(x, 0) # Fixes errors caused by float division inst = B else: inst += 1 inst = 0 while inst < len(prgm): divmeq(prgm[inst][0], prgm[inst][1]) print(x, end=" ")
This interpreter uses the symbol eof
to mark the end of a program.
Any subsequent parameters after A and B are ignored, allowing for comments. This interpreter also prints the value of the accumulator after every instruction for ease of programming.