# Transet

Paradigm(s) Markov Algorithm & Set User:GUAqwq 2023 Turing complete Implemented `.ts_`

Transet is a Set Rewriting System. There are no integers or characters in Transet, but only sets. It's the 2nd esolang of TS Series by User:GUAqwq

## Overview

The systax is similar to wikipedia:Markov algorithm. This is a example for the rules:

```{{_}} -> {_}
```

Which means transform the set in the form `{{_}}` to `{_}`

The "_" means any set. In this case, if the input is:

```{{{{{{}}}}}}
```

Then the process will be:

```{{{{{{}}}}}} ->  {{{{{}}}}} // _ = {{{{}}}}
{{{{{}}}}}   ->  {{{}}}     // _ = {{}}
{{{}}}       ->  {{}}       // _ = {}
{{}}                        // END
```

The output is the set after process.

The algorithm will always matches the outermost set in form.

## Syntactic Sugar

These are the set brackets which can be used (the brackets must be matched):

`{}` `()` `[]` `<>`

These are the identefiers which can be used (at most 1 of them in the same rule):

`_``?``*``#``A-Z``a-z`

## Computational class

Transet is Turing complete because the rules are wikipedia:Markov algorithm-like and any string(in another way, list) can be encoded to set using the following method:

Integer:

```0 : {}
successor of n : {n}
```

List/String:

```List : {[value],([rest_of_list],<>)}
Nil : <>
```

In this way, every wikipedia:Markov algorithm rules can be corresponding to two list which end with `*`

## Examples

### Binary numbers to integer

Input : a binary string which is encoded to set

Output : integer which is encoded to set

```{[<<<>>>],([{[<>],([*],<>)}],<>)} -> {[<>],([{[<<<>>>],([{[<<<>>>],([*],<>)}],<>)}],<>)}
{[<<>>],([*],<>)} -> {[<>],([{[<<<>>>],([*],<>)}],<>)}
{[<>],([*],<>)} -> *

{[<<<>>>],([<>],<>)} -> {[<<>>],(<>,<<>>,<<>,<<>>>)}
{[<<<>>>],([{[x],(<>,<<>>,<<>,<<>>>)}],<>)} -> {[<x>],(<>,<<>>,<<>,<<>>>)}
{[x],(<>,<<>>,<<>,<<>>>)} -> x
```

Rule 1,2,3 is equivalent to the following Markov Algorithm program: ( "0":`<>` , "1":`<<>>` , "|":`<<<>>>` )

```"|0" -> "0||"
"1" -> "0|"
"0" -> ""
```

Rule 4,5,6 means: (Protect by the form you see in Rule 5)

```the last "|" -> Protected 1
"|" (Protected x) -> Protected (x+1)
Protected x -> x
```

You can just not using Rule 4,5,6. In that way you'll get the String-form anwser which includes many `2`s