Etre
Jump to navigation
Jump to search
Etre is a Turing tarpit designed by User:Keymaker in 2013.
Description
The language has the instructions '-' and '()'. The parentheses must be matching and can contain any number of '-' or '()' pairs. Other characters in a program are simply ignored. The memory is an array or a string, where values are either 0 or 1, and which initially has the length of 1 and the one value at that point is 0. Memory pointer is initally pointing to this first unit/cell.
- - moves the memory pointer one forward/right. If the pointer moves out of bounds, it is set back to the very first cell, and the memory is extended by one 0-cell.
- () form loops. At first, () flips the current memory cell (0 to 1, 1 to 0). Then the loop is executed as long as the current cell (at the beginning of every loop cycle, as in brainfuck loops) is non-zero. A loop, whenever it is encountered, always alters memory (and does it exactly once, before the code within () is executed), but the actual code inside the () might never be executed if the initial flipping changes the current cell from 1 to 0.
Minsky Machine to Etre
One way to prove that the language is Turing-complete is translating Minsky Machine into it. The work can be done for example with this translator: http://yiap.nfshost.com/esoteric/etre/mmtoetre.py
An example Minsky Machine program that doubles a register (its value initially 1) ten times creates the following Etre program:
-------------------------------------------------------------------------------- -------------------------------------------------------------------------------- -------------------------------------------------------------------------------- -------------------------------------------------------------------------------- -------------------------------------------------------------------------------- -------------------------------------------------------------------------------- -------------------------------------------------------------------------------- -------------------------------------------------------------------------------- -------------------------------------------------------------------------------- -------------------------------------------------------------------------------- -------------------------------------------------------------------------------- -------------------------------------------------------------------------------- -------------------------------------------------------------------------------- -------------------------------------------------------------------------------- -------------------------------------------------------------------------------- -------------------------------------------------------------------------------- -------------------------------------------------------------------------------- -------------------------------------------------------------------------------- -------------------------------------------------------------------------------- -------------------------------------------------------------------------------- ---------------------------------------------------------------------------(-(-( -(-(-(-(-(-(-(-(-(-(-(-(-(-(-(-))))))))))))))))))-(-(-))-(-(-))-(-(-))-(-(-))-(- (-))-(-(-))-(--(-(-(-(-(-(-(-(-(-(-(-(-(-(-(-(-(-)))))))))))))))))-(------------ -----()(-)-()(-)(-())-()(-)(-())-()(-)(-())-()(-)(-())-()(-)(-())-()(-)(-)----() -----------------())-(----------------()(-)-()(-)(-())-()(-)(-())-()(-)(-())-()( -)(-())-()(-)(-())-()(-)(-)-----()-----------------())-(---------------()(-)-()( -)(-())-()(-)(-())-()(-)(-())-()(-)(-())-()(-)(-())-()(-)(-)------()------------ -----())-(--------------()(-)-()(-)(-())-()(-)(-())-()(-)(-())-()(-)(-())-()(-)( -())-()(-)(-)-------()-----------------())-(-------------()(-)-()(-)(-())-()(-)( -())-()(-)(-())-()(-)(-())-()(-)(-())-()(-)(-)--------()-----------------())-(-- ----------()(-)-()(-)(-())-()(-)(-())-()(-)(-())-()(-)(-())-()(-)(-())-()(-)(-)- --------()-----------------())-(-----------()(-)-()(-)(-())-()(-)(-())-()(-)(-() )-()(-)(-())-()(-)(-())-()(-)(-)----------()-----------------())-(----------()(- )-()(-)(-())-()(-)(-())-()(-)(-())-()(-)(-())-()(-)(-())-()(-)(-)-----------()-- ---------------())-(---------()(-)-()(-)(-())-()(-)(-())-()(-)(-())-()(-)(-())-( )(-)(-())-()(-)(-)------------()-----------------())-(--------()(-)-()(-)-()(-)- ()(-)(-())-()(-)(-())-()(-)(-())-()(-)(-)-------------()-----------------())-(-- -----()(-)-()(-)-()(-)---(()-()(-)-()(-)-()(-)(-)--(--------------())----------- -----------()(-)-()(-)-()(-)--())(-)-()(-)-()(-)-()(-)(-)--(------------()------ ------------------()(-)-()(-)-()(-)(-())-()(-)-()(-)-()(-)-()(-)(-)--())-------- ---------------------())-(------()(-)-()(-)-()(-)-()(-)-()(-)-()(-)(-())-()(-)(- )---------------()-----------------())-(-----()(-)-()(-)-()(-)-()(-)-()(-)-()(-) (-())-()(-)(-)-------------()--------------------())-(----()(-)-()(-)-()(-)-()(- )-()(-)---(()-()(-)(-)--(----------------())--------------------()(-)-()(-)-()(- )-()(-)-()(-)--())(-)-()(-)(-)--(---------------()---------------------()(-)-()( -)-()(-)-()(-)-()(-)(-())-()(-)-()(-)(-)--())--------------------------------()) -(---()(-)-()(-)-()(-)-()(-)(-())-()(-)(-())-()(-)(-())-()(-)(-)---------------- ()-------------------())-(--()(-)---(()-()(-)-()(-)-()(-)-()(-)-()(-)(-)--(----- ------------())-------------------()(-)--())(-)-()(-)-()(-)-()(-)-()(-)-()(-)(-) --(-----------()-------------------------()(-)(-())-()(-)-()(-)-()(-)-()(-)-()(- )-()(-)(-)--())----------------------------------())-(-()(-)-()(-)-()(-)-()(-)-( )(-)-()(-)-()(-)(-)-()------------------------------------())-()(-)-()(-)-()(-)- ()(-)-()(-)-()(-)-()(-)(-)---------------------(-(-(-(-(-(-(-(-(-(-(-(-(-(-(-(-( -)))))))))))))))))-()(-)-()(-)-()(-)-()(-)-()(-)-()(-)(-)---(------------------( )-----------------()(-)-()(-)-()(-)-()(-)-()(-)-()(-)-()(-)(-)---())-(---------- --------()----------------()(-)-()(-)-()(-)-()(-)-()(-)-()(-)-()(-)(-)----())-(- -----------------()---------------()(-)-()(-)-()(-)-()(-)-()(-)-()(-)-()(-)(-)-- ---())-(------------------()--------------()(-)-()(-)-()(-)-()(-)-()(-)-()(-)-() (-)(-)------())-(------------------()-------------()(-)-()(-)-()(-)-()(-)-()(-)- ()(-)-()(-)(-)-------())-(------------------()------------()(-)-()(-)-()(-)-()(- )-()(-)-()(-)-()(-)(-)--------())-(------------------()-----------()(-)-()(-)-() (-)-()(-)-()(-)-()(-)-()(-)(-)---------())-(------------------()----------()(-)- ()(-)-()(-)-()(-)-()(-)-()(-)-()(-)(-)----------())-(------------------()------- --()(-)-()(-)-()(-)-()(-)-()(-)-()(-)-()(-)(-)-----------())-(------------------ ()--------()(-)-()(-)-()(-)-()(-)-()(-)-()(-)-()(-)(-)------------())-(--------- ---------()-------()(-)-()(-)-()(-)-()(-)-()(-)-()(-)-()(-)(-)-------------())-( ------------------()------()(-)-()(-)-()(-)-()(-)-()(-)-()(-)-()(-)(-)---------- ----())-(------------------()-----()(-)-()(-)-()(-)-()(-)-()(-)-()(-)-()(-)(-)-- -------------())-(------------------()----()(-)-()(-)-()(-)-()(-)-()(-)-()(-)-() (-)(-)----------------())-(------------------()---()(-)-()(-)-()(-)-()(-)-()(-)- ()(-)-()(-)(-)-----------------())-(------------------()--()(-)-()(-)-()(-)-()(- )-()(-)-()(-)-()(-)(-)------------------())-(------------------()-()(-)-()(-)-() (-)-()(-)-()(-)-()(-)-()(-)(-)-------------------())-------------------()(-)-()( -)-()(-)-()(-)-()(-)-()(-)-()(-)(-)-)
Reading MM-to-Etre translation's memory
For example, take this MM program:
1 inc B 2 2 inc A 3 3 inc B 4 4 dec B 4 5 5 halt
It increases B-register, then A, then B again, and then decreases B until it becomes 0, after which the program halts.
Translated to Etre using the translator, with an extra argument given, the program's output is the following:
B = 0 A = 1 5 MM lines/instructions extra arguments; will add 'C' debug character to Etre program -------------------------------------------------------------------------------- -------------------------------------------------------------------------------- -------------------------------------------------------------------------------- -------------------------------------------------------------------------------- --------------------------------------------------------------------(-(-(-(-(-(- ))))))-(-(-))-(-(-))-(-(-))-(-(-))-(--(-(-(-(-(-)))))-(-----()(-)-()(-)(-())-()( -)(-())-()(-)(-())-()(-)(-)----()-----())-(----()(-)-()(-)-()(-)-()(-)(-())-()(- )(-)-----()-----())-(---()(-)-()(-)(-())-()(-)(-())-()(-)(-())-()(-)(-)------()- ----())-(--()(-)---(()-()(-)-()(-)-()(-)(-)--(-----())-------()(-)--())(-)-()(-) -()(-)-()(-)(-)--(----()--------()(-)(-())-()(-)-()(-)-()(-)-()(-)(-)--())------ ----())-(-()(-)-()(-)-()(-)-()(-)-()(-)(-)-()------------())-()(-)-()(-)-()(-)-( )(-)-()(-)(-)---------(-(-(-(-(-)))))-()(-)-()(-)-()(-)-()(-)(-)---(------()---- -()(-)-()(-)-()(-)-()(-)-()(-)(-)---())-(------()----()(-)-()(-)-()(-)-()(-)-()( -)(-)----())-(------()---()(-)-()(-)-()(-)-()(-)-()(-)(-)-----())-(------()--()( -)-()(-)-()(-)-()(-)-()(-)(-)------())-(------()-()(-)-()(-)-()(-)-()(-)-()(-)(- )-------())-------()(-)-()(-)-()(-)-()(-)-()(-)(-)C-)
The lines
B = 0 A = 1
in the output mean the order of the registers. Since the registers appeared in that order in the MM program, B first, A then, that is the order they are in the Etre program. Yes, using '0' instead of '1' to mark '1st' is somewhat confusing, but imagine they are array indexes (which they actually are, in the Python program).
Running the program (from which the translator's note part that includes an extra 'C' is removed) in Keymaker's Etre interpreter, the interpreter outputs the following debug data:
DEBUG (C) at inst[1250]. Current memory: 0100000001011111011101101101111110 ^ 0 DEBUG (C) at inst[1250]. Current memory: 010000000110111101110110111011111111110 ^ 0 DEBUG (C) at inst[1250]. Current memory: 01000000011101110111101101110111111111111110 ^ 0 DEBUG (C) at inst[1250]. Current memory: 01000000011101111011101101110111111111111111111110 ^ 0 DEBUG (C) at inst[1250]. Current memory: 01000000011101111101101101110111111111111111111111111110 ^ 0 DEBUG (C) at inst[1250]. Current memory: 01000000011110111101101101110111111111111111111111111111111110 ^ 0 DEBUG (C) at inst[1250]. Current memory: 000000000111111111011011011101111111111111111111111111111111111110 ^ 0 Done. Final memory state: 000000000111111111011011011101111111111111111111111111111111111110 ^ 1
The debug command 'C' is executed at the end of the main loop, where execution goes after each simulated MM instruction.
The first debug
DEBUG (C) at inst[1250]. Current memory: 0100000001011111011101101101111110 ^ 0
(where memory pointer is in cell 0, as told by "^ 0" line) can be read as
0mnxxxxxyyyyyttt0BBB0tt0AA0tttttt0
where:
- The first three cells 0mn are for program's internal purposes. Can be ignored.
- xxxxx and yyyyy cells are for program's internal logic to mark what MM line/instruction to execute. The amount of them is the number of MM lines * 2 (which is 5*2=10 here). Can be ignored.
- Then follows whatever number of trash-bits there happens to be at a given time (3 in this case) followed by 0. Can be ignored.
- Then a row of 1s (or "BBB") terminated by a 0 signifying the first register (B in this case). The value of the register is the number of 1-bits minus 2. So "111" here means 3-2=1. ("11" signifies zero, the reason of which is left to the reader, if he/she has time to trace the workings of this system.) This is followed by any number of trash-bits, 2 of them here, terminated by a 0.
- Then another row of 1s (or "AA") to mark the second register (A here). Its value is presently 0 (2-2=0). This "11" is too followed by a 0, then any number of trash-bits, 6 of them here, and a 0 again.
Similarly, the final memory state
Done. Final memory state: 000000000111111111011011011101111111111111111111111111111111111110 ^ 1
(where memory pointer is in cell 1) can be read as
0mnxxxxxyyyyyttttt0BB0tt0AAA0tttttttttttttttttttttttttttttttttttt0
where
- B is 0 (as marked by two 1s here)
- A is 1 (as marked by three 1s here)
External resources
- Etre page (the specs, a MM-to-Etre translator, an interpreter in C)