|Computational class||Turing complete|
ETAS, short for etas,teas,sate,eats,east,tase,seat,esta,ates,stae,tesa,esat,aest,saet,taes,etsa,aset,tsae,seta,atse,tsea,aets,stea,aste or, if you prefer, Especially Tiny and Annoying Self-modifier, is a language created in 2011 by User:Quintopia inspired by DNA and at the urging of User:Zzo38 to make a language wherein the same piece of code could be interpreted as two different things by reading it beginning at different places.
ETAS is structured as a circular buffer with a program pointer that jumps 8 characters after each instruction, and an independent data pointer (DP) into the same buffer. The buffer is divided into quaternary "digits" which are represented, as expected, by the letters a, e, s, and t, (equal to 00,01,10, and 11 respectively). Any 16-bit number given by eight of these digits is interpreted programmatically in the following way:
Capital letters here are metasyntactic variables, each equivalent to one of the four digits.
|aeXXXXXX||RIGHT||Move DP XXXXXX digits right|
|asXXXXXX||LEFT||Move DP XXXXXX digits left|
|ataXXXXX||OUTPUT||Output XXXXX UTF-16 code units beginning at DP. (Note that a UTF-16 code unit is the same length in digits as an instruction.)|
|ateXXXXX||INPUT||Insert XXXXX UTF-16 characters from input at DP.|
|atsXXXXX||SELECT||Select XXXXX digits beginning at DP, mark for deletion, copy to buffer.|
|attaXXXX||INSERT||Insert entire buffer before DP, delete all marked digits.|
|atteXXXX||JUMP||Move program pointer to XXXX digits past DP, do NOT move ahead 8 digits ahead afterwards.|
|attsXXXX||RESERVED||If it turns out this language is not Turing-Complete, something can be put here to make it so. Otherwise, this can be used for interpreter-dependent extended functionality.|
|atttAEST||TRANSFORM||Substitute another digit for the one at the DP by making it A if a, E if e, S if s, T if t|
A program halts when the program pointer arrives at a digit it has been at before if the program has not changed at all since the last time it was there and the DP is in the same place. (It is trivial to show that nothing interesting will ever happen again in this case. Note that this means even writing a program that produces the same output forever requires some extra effort.) An optimizing interpreter would do analysis to ensure it jumps automatically from one instruction to another without scanning the DAT/NOPs in between. In addition, it could check in advance whether this was going to be the case, and, if nothing was going to be output, halt as soon as possible. Note that a halt-checker would not have to store data about every non-self-modifying instruction, but only the first ones occurring after RIGHT, LEFT, or, INSERT commands.
Note that there is no way to shrink the length of a program, and so most programs that do useful things will grow without bound. Perhaps a DELETE command should go in the RESERVED slot to fix this?
Unknown for the moment, though it is highly likely that it is TC. Note that memory is not bounded: it can grow by SELECTing the same digit repeatedly before INSERTing it. Conditionals are easy: every command has an implicit "if the first digit is 'a' (zero)." Arithmetic can be implemented (possibly with some difficulty) using TRANSFORM (attttaes does one-digit decrementing, or atttaaes for the non-wrapping version). However, even trivial programs are difficult to implement, so proving TCness will take some thought.