| --- |
| license: mit |
| library_name: transformers |
| tags: |
| - tokenizer |
| - brainfuck |
| - turing-machine |
| - esoteric |
| --- |
| |
| # Tokenizer CPU |
|
|
| A stock Hugging Face tokenizer that executes programs. Its merge rules select a machine transition; |
| decoding writes the next state. Repeating encode and decode runs the computation, without a neural |
| network. It is a plain `tokenizer.json`, with no custom code (no `trust_remote_code`). Every clock tick |
| is one encode and one decode: |
|
|
| ```python |
| from huggingface_hub import hf_hub_download |
| from transformers import AutoTokenizer |
| |
| tok = AutoTokenizer.from_pretrained("fMindstormer/tokcpu") |
| tape = open(hf_hub_download("fMindstormer/tokcpu", "start.txt"), encoding="utf-8").read() |
| while (nxt := tok.decode(tok.encode(tape))) != tape: # 154,137 ticks |
| tape = nxt |
| print(tape) |
| ``` |
|
|
| `start.txt` holds Hello World. The loop ends with the program's output written on the tape: |
|
|
| ``` |
| β’Hello World!ββ++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.βΌκ°ββ β β‘β‘€β‘β ‘β²β β£ |
| βββ output βββ βββββββββββββββββββββββββββββββββ the program ββββββββββββββββββββββββββββββββββββββββ ββ memory ββ |
| ``` |
|
|
| To run your own program, start from `"β’ββΌκ°" + program + "ββ²β Β¦" + input + "β£"`. `,` reads the input's |
| first character, and 0 once it is used up. Loops can nest up to 64 deep. |
|
|
| ## How it works |
|
|
| Exactly one character on the tape is the *head*. The BPE model has one merge for each pair the head can |
| form with a cell, so encoding splits the tape into single characters plus one two-character token. That |
| token's id is a Turing-machine rule, and the same id is an added token whose text is the rule's output, |
| so decoding applies the rule. A halted head has no merges, and the loop stops when the tape stops |
| changing. |
|
|
| The full explanation, the compiler and the tests are on GitHub: https://github.com/fMindstormer/tokcpu |
|
|
| Tag `v1.0` of this repo holds the same tokenizer files as the |
| [v1.0 release](https://github.com/fMindstormer/tokcpu/releases/tag/v1.0) on GitHub, which adds a |
| minimal runner, the expected results, checksums, and a reproduction of a tokenizer disagreement between |
| Python and JavaScript. |
|
|
| ## What's in this repo |
|
|
| | Folder | Machine | Merge rules | |
| |---|---|---:| |
| | (root) | universal Brainfuck interpreter: runs any program written on the tape | 17,210 | |
| | `hello`, `alphabet`, `grid`, `jumps` | one Brainfuck program compiled into each tokenizer | 24,173 β 38,265 | |
| | `increment` | adds one to a binary number: `start.txt` holds 1011, which becomes 1100 after 8 ticks | 16 | |
| | `4-state-busy-beaver` | the 4-state busy beaver: halts after 107 ticks with 13 ones | 24 | |
| | `binary-counter` | counts in binary forever | 7 | |
| | `sort` | a block cellular automaton: every two-letter block of the tape is rewritten in one tick, sorting it | 704 | |
| | `rule110` | Rule 110, which is Turing complete: every cell updates every two ticks, and the tape grows at both edges | 29 | |
| | `rule110-ether` | Rule 110 on its ether, the periodic background its gliders travel on, which the edges keep growing | 146 | |
|
|
| Load a subfolder with `AutoTokenizer.from_pretrained("fMindstormer/tokcpu", subfolder="hello")`. Each one has its |
| own `start.txt`. `programs/` holds the Brainfuck sources. The block automata's tapes never stop changing (a |
| phase mark flips every tick): stop the sorter when the tape repeats every two ticks, and Rule 110 whenever you |
| like. |
|
|
