We are currently working on new rules for what content should and shouldn't be allowed on this website, and are looking for feedback! See Esolang:2026 topicality proposal to view and give feedback on the current draft.
Extrapolated brainfuck
| Paradigm(s) | imperative |
|---|---|
| Designed by | User:Challenger5 |
| Appeared in | 2026 |
| Computational class | Unknown |
| Reference implementation | Unimplemented |
| Influenced by | brainfuck |
Extrapalot is a brainfuck derivative where loops are inferred from the program rather than being written explicitly.
An Extrapalot program is compiled to a brainfuck program by removing all characters except +, -, <, >, ,, ., and then extrapolating repeated substrings to produce loops.
Given a subprogram p, the extrapolation E(p) is defined as follows:
- Find a decomposition p = a B c such that B is a repeated nonempty string, i.e. B = bn for some n ≥ 2.
- If no such decomposition exists, then E(p) = p.
- If multiple valid choices exist, ties are broken first by longer B, then by shorter a, then by larger n.
- E(p) = E(a)
[E(b)]E(c).
Examples
The classic cat program ,[.,] cannot be written ,.,.,, because this would be parsed as (,.)2, → [,.],. Instead, we can write it as ,><.,.,.
To increment a cell by 3, we cannot use +++, since this would extrapolate to the loop [+]. Instead, we can use +>+-<+>-+<+.
Generalization
We can generalize this to (N,K)-extrapalot, which constrains valid decompositions to satisfy n ≥ N, b ≥ K. So what was just described was (2,1)-extrapalot.
We can further define ω-extrapalot as follows: a ω-extrapalot program is a triple (N, K, p) such that N ≥ 2, K ≥ 1, and p is interpreted as an (N,K)-extrapalot program.
Computational class
The author makes the following conjectures, from weakest to strongest:
- ω-extrapalot is equivalent in power to brainfuck.
- (N, K)-extrapalot is equivalent in power to brainfuck for some (N, K).
- (2, 1)-extrapalot is equivalent in power to brainfuck.