SHITS

SHITS (Simple language witH bITS) is an esolang by User:ChuckEsoteric08 based on brainfuck minimalisations which uses binary tape.

Specification

Language uses right-infinite tape.

Commands

! - flip bit and move to the first cell
> - move right
{...} - while not zero

Optional I/O commands:

* - output bit
+ - input bit

Computational class

Language is Turing-complete, because it can simulate Cyclic Tag with initial string of 1:

Program start - !>>>!{
; - {>>}>>!{>>}!
0 - {>>}>{!!>>{>>}>>{>>}!>>{>>}}!{>>{>>}>!}!
1 - {>>}>{!!>>{>>}>>{>>}>!>>{>>}>>{>>}!>>{>>}}!{>>{>>}>!}!
Program end - }

It also proves that it is Turing-complete even with maximum nesting depth of 3.

Interpreter

Written in Python 3.

def interpret_shits(program):
  brackets = match_brackets(program)
  if brackets is None:
    raise SyntaxError("brackets are unmatched")
  
  cells = set()
  cell_pointer = 0
  i = 0
  
  while i < len(program):
    c = program[i]
    
    if c == "!":
      cells ^= {cell_pointer}
      cell_pointer = 0
    elif c == ">":
      cell_pointer += 1
    elif c == "{":
      if cell_pointer not in cells:
        i = brackets[i]
    elif c == "}":
      if cell_pointer in cells:
        i = brackets[i]
    elif c == "*":
      print("1" if cell_pointer in cells else "0", end=" ")
    elif c == "+":
      if input() != "0":
        cells.add(cell_pointer)
      elif cell_pointer in cells:
        cells.remove(cell_pointer)
    
    i += 1

def match_brackets(program):
  temp = []
  result = {}
  
  for i, c in enumerate(program):
    if c == "{":
      temp.append(i)
    elif c == "}":
      if len(temp) == 0:
        return None
      matched = temp.pop()
      result[matched] = i
      result[i] = matched
  
  return result if len(temp) == 0 else None