кече

кече (read as [keˈʃe] / [ketʃe]) or keche which name means "small" in Tatar is a Stack / Deque-based (depending on how you view a stack with a "reverse" instruction) esolang by User:ChuckEsoteric08.

Description

кече works on a stack which symbols could only be . and 1 and program which are a list of possibly empty strings seperated by spaces which can also contain only . and 1 and contained on a circular tape so that going out of bounds would wrap around to the opposite side. Stack starts with 1 as initial symbol. At each step it removes a single symbol from the top and based on what it was it will do different things:

• If it tried to pop from empty stack halt the program.
• If symbol was . current string is pushed into the stack symbol by symbol (if there is any) and skips next string, moving instruction pointer after the next string.
• If symbol was 1 stack is reversed and after that current string is pushed into the stack symbol by symbol (if there is any) and instruction pointer is moved to the next string.

If a string would contain any other symbol it is treated as an empty string, which could be used to differentiate space from an empty production, which would usually be shown as two spaces.

Computational class

It is easy to compile Cyclic tag system with initial data 1 into it. Each production is converted by 0 replaced by . and 1 remaining the same, and putting all of the production along with 1 appended after it as a single string, then same resulting string is put as the next string. Then add a string consisting of a single 1 followed by an empty string. Then go from the last symbol to the first and add following strings:

• For each 0 two empty strings are added.
• For each 1 string consisting of single 1 with an empty string is added.

Thus it proves that it is Turing-complete.

See also

• Liquid DownRight - the language could be seen as stack-based version of Liquid DownRight.
• DownRight - the language from which language above was derived.