Jelly, score 7 8 9 10
VŻỌ‘’
01uvọŒ⁾¤
2ṭḊḢĿ¶
5[,]?`FñṖṪị
&Hrx}Æçƭḷ¹⁹€
:@U\_½ÄÇ×Ø
jµœƬṣ“”
"$+8DLMṀns¿
CNt©®ÐƊḌḶṃṄẒE
%34b¡ÑḅẸ⁺
There is some room for interpretation as to what a Turing-complete language is, and thus what a Turing-complete subset of a language is. For these answers, I have used the strictest common definition: these are subsets for which it is possible to compile a Turing machine into that subset of Jelly, producing a finitely long program that halts if and only if the Turing machine halts. (Note that the proofs below don't start all the way from Turing machines, but from other Turing-complete languages; this is valid because you can first compile the Turing machine into the language I started from because it's Turing-complete, and then into Jelly.) Halt behaviour is the only thing that matters for Turing-completeness; things like I/O are not important, and the compiled Jelly programs are thus written as full programs that take no input.
Although I've improved this answer quite a bit since it was first posted, it is probably still improvable: I still have lots of characters unused, and some of these character sets are slightly larger than necessary (but easier to explain than a fully-"golfed" set would be). However, it's becoming increasingly hard to find ways to do things like express constants, create potentially infinite loops, and to get the program to halt when the emulated program halts. Still probably possible, though.
Note that many of these character sets can be considered as interesting "cop problems" for a hypothetical cops-and-robbers question; some readers might find it fun to try to figure out for themself how some of these subsets are Turing-complete before reading onwards.
Explanations
There are a lot of solutions here (by "solution", I mean a subset of characters via which Jelly is Turing-complete, with the solutions chosen so that none of them overlap in characters), with some parts of the explanation common to multiple solutions but most of it specific to a particular solution. As such, each answer is going to get its own individual explanation, but sometimes there will be shared explanation in a section beforehand.
Eval-based solutions
One way (but not the only way!) to prove a character subset Turing-complete is to show that it can eval arbitrary code in a Turing-complete language, using an eval builtin or equivalent. Jelly has a few different ways to eval code, but all of them are spelled using the character v or V, meaning that there is a limit of two eval-based solutions.
Now, there's one property of Jelly that makes writing eval-based solutions fairly difficult: Jelly does not like to do arithmetic on characters, and has very few operations that can change a character into a different character, or create an arbitrary character from scratch. This is a problem because the eval functions operate on strings (which in Jelly are lists of characters), but in order to evaluate arbitrary code, we have to be able to produce arbitrary strings starting from a limited character set (ideally as small as possible, to leave more characters for the other subsets).
The usual approach for constructing arbitrary strings in Jelly is to use the Ọ command, which takes an integer (or list of integers) as its argument, and outputs the character with the given character code (or string whose characters have the specified character code). That's one perfectly fine solution to the problem of "starting from a limited character set, produce an arbitrary string in Jelly". The problem is that it's only one solution, but there's space for two eval-based solutions, meaning that a second way to produce strings is needed. See below for how I managed it!
eval, the easy approach: using Ọ
Character set: VŻỌ‘’
A very simple approach to get things started. Using Ż at the start of a 0-argument program produces the list [0]. That element can be incremented and decremented to any desired value with the increment instruction ‘ and decrement instruction ’. Then a new 0 can be prepended to the list with Ż, and the increment and decrement instructions will then affect the entire list, and this can be continued making the list longer and longer over time. It's possible to produce an arbitrary list of integers this way: just set each element to its correct value relative to the previous element, and finally set the first element to its correct value, which will cause all the other values to be correct.
After producing an arbitrary list of integers, it can be converted to a string with Ọ and evaluated as a program with V.
Here's an example program written in this subset. And here's a compiler. This construction is simple and small enough that it's possible to run the compiler, and the compiled program is small enough to fit in this post. This will not be the case for all the future constructions!
eval, the hard approach: without using Ọ
Character set: 01uvọŒ⁾¤
Ọ makes things easy, but it turns out that avoiding it is just about possible. The basic idea is to note that because we have an eval operator in our character set, it's possible to get at the effect of Ọ either by using the Ọ command itself (which we can't use), or by producing the string "Ọ" and evaling it. However, this is still fairly difficult as Ọ is the primary way to produce arbitrary strings in Jelly, with the main obstacle reducing to "how do you produce an 'Ọ' if you don't have one already?".
I could actually only find two ways in Jelly to produce an 'Ọ' without already having a string that contained an 'Ọ'. One possible approach is to index into ØJ, a predefined constant that contains all the characters used by Jelly (including 'Ọ'); but indexing operators are really useful when implementing Turing-complete languages from scratch, so I didn't really want to spend them here. Instead, I used the other approach: Jelly has a few case-changing operators that take strings as input and return strings as output, meaning that it is possible to produce 'Ọ' by uppercasing a lowercase 'ọ', and although a few different commands work, I couldn't find a reason to use anything other than the uppercasing command Œu (all casing commands contain Œ so there is no way to avoid using that, and u is not useful except to spell Œu – it doesn't spell any other commands).
Producing ọ is basically as difficult as producing Ọ, but because ọ is in our character set, it's possible to just write it in a string literal. For this subset, I used the ⁾ form of string literals, which is limited to strings that are exactly two characters long – this is sufficient for this subset, and the least generally useful for other subsets.
This approach needs at least uvọŒ⁾, and adding 01¤ produces a complete Turing-complete subset. Unfortunately, this is one of those JSFuck-style subsets in which a full construction gets slowly built up out of smaller parts and the resulting programs are basically unreadable, so I'm going to go through the steps one at a time.
A snippet demonstrating each step, at Try It Online!
- Jelly is normally a fairly linear language (start with value y, do A to it, then do B to it, etc.), but the construction here contains expressions which are more complicated in shape. As such, I'm using the grouping operator
¤ which basically makes Jelly into a postfix language if used everywhere: what would be written 1 + 2 in an infix language becomes 1 2 + in a postfix language and 1+2¤ in Jelly, and what would be written ¬3 in a language with prefix unary operators becomes 3 ¬ in a postfix language and 3¬¤ in Jelly. As such, the string "ỌỌ" (which has the same effect when executed as "Ọ" – Ọ is idempotent) can be written as ⁾ọọŒu¤, i.e. "Œu applied to "ọọ", written as a postfix expression").
- In addition to being a lowercase
Ọ, the ọ command is actually mildly useful in its own right; it returns the number of times its right-hand argument divides into its left-hand argument. This means that with 01ọ¤ it is possible to write arbitrary nonnegative integers, e.g. 1000ọ10¤ is 3 because \$10^3=1000\$, and it is possible to create larger numbers simply by adding more zeroes.
- Being able to construct
"ỌỌ", it is then possible to evaluate it using the evaluate-with-argument command v. Because it's possible to produce arbitrary integers, this can produce arbitrary single characters. The example in the TIO! link produces 'D' by doing “ỌỌ”v68¤.
- By nesting uses of
…v…¤ it is possible to produce arbitrary expressions that consist of a constant, followed by any number of single-character unary builtins. The expression shown here is “U”v“D”v12¤¤…
- …which is just another way to write
12DU, i.e. "reverse the digits of 12". I will be writing the remaining examples in this linear form, because it's much easier to read, but all of them can in theory be expanded to use …v…¤ rather than being written linearly.
- Directly producing arbitrary strings using only the single-character unary builtins is nontrivial (the single-character nullary builtins aren't useful, and the single-character binary builtins aren't useful here because
v has no way to give them two different arguments). There are some strings that can be constructed, though. On this line, I construct the string "Œg" by starting with a number with 338 0 digits and 103 1 digits (which can just be written directly because the character set contains both 0 and 1), taking its digits (D), grouping the digit positions by their values (Ġ – this produces a list of a 338-element list and a 103-element list), taking the length of each of the inner lists (Ẉ) to produce [338, 103], and then converting those character codes to characters to produce "Œg". Note that the D, Ġ, etc. don't need to appear literally in the source; they are all produced using the technique shown in step 3, and combined into a single expression using the technique shown in step 4.
- Now that it's possible to produce the string
"Œg", it can be evaluated in order to run the Œg builtin. It's possible to produce an arbitrary list whose elements are 0 and 1 (starting with 1) by using D on a number that can be written directly using our character set. Œg does run-length grouping, so it produces a list of lists for which the length of each internal element matches a run length in the original array. Ẉ can convert that format into an arbitrary list of positive integers. In the example, starting with 11111111110011110000000000001111 gives us [10,2,4,12,4] – the run lengths of the original constant (it has 10 1s, then 2 0s, then 4 1s, etc.).
- Being able to produce arbitrary lists and run
ỌỌ on them makes it possible to produce arbitrary strings; these can be given to v to make it possible to run arbitrary code in Jelly's character set (because the character set does not contain NUL, all its characters have positive Unicode codepoints and thus it doesn't matter that step 7 generates positive integers only). The TIO! example runs a program that prints the positive prime integers below 1000.
So in summary: there is a way to bracket expressions arbitrarily, ọ can be used to produce arbitrary integers, and that makes it possible to produce and evaluate single-character strings. That isn't fully general on its own but is good enough to produce "Œg", which in turn makes it possible to write arbitrary arrays of integers, and those can be converted to strings and evaluated in order to write any program.
Solutions based on tag systems
A tag system is a simple Turing-complete language that works as follows. A program consists of a map from characters to strings, and a number m, together with an initial string. Data storage is done by using a string that acts like a queue (and starts with the specified value). To execute the program, delete the leftmost m characters of the queue-string; then, look up the string that corresponds to the first of the deleted characters according to the map, and append that string to the queue-string. There are various definitions of a halting (e.g. "delete when a special 'halt' character is looked up in the map", "halt when the queue is empty", "halt when the queue has less than m elements"). All are Turing-complete for all m ≥ 2 (e.g. UT19 is a tag system that's Turing-complete witih all three definitions).
Using Ŀ
Character set: 2ṭḊḢĿ¶
One simple way to compile a tag system to Jelly is to use the Ŀ builtin. Here's what that could look like if we had Jelly's full character set available, implementing the example tag system on Esolang:
Ḋ3ṭ3ṭ2ṭ1ṭ4ṭḢĿ
Ḋ3ṭ3ṭ1ṭḢĿ
Ḋ3ṭ3ṭḢĿ
2Ḋ1ṭ2Ŀ
Try it online! (has added Ṅ to show the steps of execution)
The Ŀ builtin is designed for function calls, but in this program, it is used only at the end of a function – in tail position – so it effectively acts like a goto command (as soon as any function returns, all of them return, so the call stack is irrelevant). It is preceded by an argument that specifies which line to jump to, so this version of the construction needs newlines (in Jelly's character set, the newline character can be rendered either with an actual newline or as ¶, but the two are equivalent views of the same character rather than being two separate characters, so it's usual to use whichever rendering makes more sense in the context). The key observation is that ḢĿ – "jump to the line given by the first element {of the list on which we're currently operating}" – can be used as a lookup-in-map operation: using line numbers as the characters of the string, the code on line n can be code that appends a specific string literal to the string (and then removes the characters from the start and jumps with ḢĿ). A halt symbol can be implemented using a line with no code.
To implement this in Jelly, the idea is for each line of code to remove characters from the start (Ḋ – this can be repeated to remove as many characters as needed, with one already having been removed by Ḣ), and to append the appropriate elements at the end (e.g. [3,3,1] can be appended using 3ṭ3ṭ1ṭ, using the "append element" command ṭ).
The initial string can be implemented using very similar code, but there's a need to produce a list to append to so that ṭ behaves appropriately. Ḋ is overloaded to produce a list from 2 to the given integer inclusive, so 2Ḋ produces the list [2]. This means that the second element of the initial string must be 2, but fortunately that's one of the elements that is skipped, so its value has no effect on the resulting program.
In the "all of Jelly is allowed" method of compiling a tag system, the used characters are 0123456789ṭḊḢĿ¶. However, if you spread the program out enough, only 2 is actually needed (for 2Ḋ): nothing goes wrong if you name the elements of the tag system 2, 22, 222, etc. rather than 1, 2, 3, etc., and simply add a lot of newlines to the program to put the various code that implements map elements onto the appropriate line.
Using ị
Character set: 5[,]?`FñṖṪị
Instead of baking the tag system's map into our program's control flow, it's also possible to simply just use a list as though it were a map; the tag system alphabet can be made out of integers, and those integers can be list indexes. Reading from the map can thus be done with a list indexing instruction, such as ị.
Here's what that might look like if we had Jelly's entire character set to play with, implementing Liesbeth De Mol's Collatz tag system:
Ṫị[[3,2],[1],[1,1,1],[1,1,1]];ṖÑ5Ṗ?
Try it online! (contains added print statements so that you an see what is happening)
The implementation starts by removing the last element from the current value (Ṫ) and using it to index (ị) into a list literal (specified using Jelly's list literal syntax, which involves [,] and decimal integers) – the queue is stored "backwards" compared to the previous case. It then appends (;) the current value minus its last element (Ṗ) – two elements were removed from the end, of which only one was used, and so this is a 2-tag implementation. It is possible to add additional Ṗ at this point in order to implement higher values of m.
All that's needed after this is to handle halting, which here is done with an if statement, Ñ5Ṗ? (? specifies an if statement, and is preceded by the true case Ñ, the false case 5, and the condition Ṗ). If the list has multiple elements, it'll be truthy when an element is removed with Ṗ, so Ñ is run, which is a recursive call to the main program. (This Ṗ does not actually affect the content of the list – it just provides a truth value to the if statement.) If the list does not have multiple elements, removing an element will produce an empty list, which is falsey, so 5 runs – that isn't a recursive call (it's an integer constant), so the program exits.
There is something apparently missing in the above explanation: how does the initial string get there, given that the program is run with no argument? The behaviour of ị when given no useful input data is to return the last element of the list it's indexing into, so it's possible to simply append the input string ([1,1,1]) to the end of the list that serves as the tag system's map, as an additional element that's never read once the program has started but will be used on the first iteration. (If m>2, some of the elements at the end will get removed on the first pass through the program, but this can be compensated for by adding extra junk elements to the initial string.)
One thing worth noting is that Jelly's list literal syntax is broken and doesn't support empty lists ([] seems like it should work, but actually causes the lexer to crash). Fortunately, this turns out not to matter.
As in the previous solution, it's possible to remove digits other than 5 from the character set by using only list elements whose indexes are 5, 55, 555, etc., with irrelevant data in the others. However, it's possible to go further with this, saving some valuable characters for other solutions:
- Because this solution uses
, anyway (to write the list literals), it makes more sense to write ; (append) as ,F (pair and flatten), which does the same thing on one-dimensional lists.
Ñ is a convenient way to do recursion – convenient enough that it is better to use it in another solution! It is possible to use ñ` instead, which is also a recursive call, but uses a different parser (designed for functions with two arguments). The program can be made robust, so that it parses correctly either as a two-argument function or as a full program, by doubling the F (one of the Fs will always be a no-op, but which one depends on the parser in use – and F is idempotent so doubling it is OK).
The resulting program looks like this (and can be padded to use no digits but 5s in the literals):
Ṫị[[3,2],[1],[1,1,1],[1,1,1]],FFṖñ`5Ṗ?
Try it online!
The only part of the program that varies is the list literal, written using [5,], and the rest of the program is fixed and the only additional characters it uses are ?ñ`FṖṪị.
A solution based on Echo Tag
Character set: &Hrx}Æçƭḷ¹⁹€
Echo Tag is a simplified version of cyclic tag. It works as follows: there is are two queues of 0s and 1s, a data queue and a program queue, and a number n. Execution proceeds by repeatedly dequeuing from both queues simultaneously; the value dequeued from the program queue is enqueued once back onto the program queue (so it cycles forever), and onto the data queue n times if a 1 was dequeued from the data queue, but not at all if a 0 was dequeued from the data queue. It has been proven Turing-complete for all n≥68 (and is probably Turing-complete for all n≥2). This answer uses n=256.
The basic form of the program is as follows:
⁹…ƭ€&⁹x⁹ḷÆr}⁹ç
To implement the program queue, this solution uses Jelly's "tie" builtin ƭ. This is preceded by two commands, e.g. ABƭ, and alternates between them every time it runs; if you ran ABƭ in a loop (even one created by recursion), it would alternate betwen running A and B each time. A tie builtin can be preceded by another tie builtin, which means that it's possible to create a builtin that cycles through 2x different commands (and there is a UT19 implementation in Echo Tag with n=256 and a 256×256×2=131072-element program queue, which is a power of 2, so the restriction to power-of-2-length programs doesn't matter); the 0 and 1 of Echo Tag are implemented using H (halve) and ¹ (do nothing).
The data queue is implemented using a list of 256 (representing 1) and 0 (representing 0); the program queue is mapped over it using € (so 256 becomes 128 where the program queue is 0) and bitwise-anded with it using & (so 128 becomes 0). x then repeats each element of the mapped queue a number of times equal to the corresponding value in the original data queue; thus, where the data queue had a 0, it now has nothing: where the data queue had a 256, it now has 256 256s or 256 0s, depending on the value in the program queue. The position in the program queue is remembered across both the € loop, and the recursive loop that makes up the whole program.
To handle halting, the code fragment ḷÆr} is used. This runs the Ær builtin on the command's second argument (}), and ignores the result (ḷ). Ær finds the roots of polynomials, which is very slow for lists as long as Echo Tag uses (even a trivial example program takes 12 seconds to run!), but the advantage here is that it will succeed on any non-empty list and yet it crashes when given an empty list, exiting the program when and only when the data queue empties.
Program startup is interesting, and makes use of both an arity polyglot and a data-type polyglot. When run with no arguments, ⁹ means 256, and the end of the program parses as:
⁹…ḷÆr}⁹ç
ḷ no-op
} ignore everything so far and
Ær calculate the roots of the polynomial
⁹ 256
ç 2-argument recursive call with that and
⁹ 256
meaning that the first recursive call is a 2-argument recursive call with an empty list and 256 as the arguments (256 is a valid polynomial, but it has no roots because no value of x gives 256=0). On the second call, ⁹ means "the right-hand argument" (which is still 256), but the program now parses entirely differently:
⁹…x⁹ḷÆr}⁹ç
x repeat each element a number of times equal to
⁹ the right-hand argument
Ær calculate the roots of the polynomial
} specified by the right argument
ḷ but ignore the result
ç 2-argument recursive call with
⁹ the right argument as its left argument
{and the result of x⁹ as its right argument}
On this execution, the € interprets the 256 as a range from 1 to 256 inclusive, but the & and x interpret it as just the number 256. The result is an array of 65536 elements, most of which are 0 (both 128 and 256 are possible elements in the resulting list, but the program queue can be designed to stop the 128s appearing). This is a valid data queue that creates a startup state that can be Turing-complete (as startup code can be added to the program queue, whilst retaining a power-of-2 length), so from the third iteration onwards, everything runs normally, and everything expected to be a list actually is a list.
Here's an example of a program in action, using 2 rather than 256 (with added run-length-encoded debug output). And here's an example that demonstrates startup and halting with a trivial Echo Tag program, using the full 256.
A solution based on Blindfolded Arithmetic
Character set: :@U\_½ÄÇ×Ø
Blindfolded Arithmetic is a language that I originally created as a cop in a cops-and-robbers challenge. The original version had six variables, but I subsequently proved that it is Turing-complete using only two variables. It's the two-variable version that I'm using for this solution.
The two-variable Blindfolded Arithmetic has two unbounded integer variables (here called X and Y, starting at 1 and 0 respectively), and each command adds, subtracts, multiplies or floor-divides two variables and stores the result back into a variable. For example, a command might be X = X + Y or Y = Y / X. The program runs in an infinite loop forever, ending only upon division by zero. There are a couple of complications when it comes to working out how many commands need to be implemented:
- Subtractions and divisions are asymmetrical, so
Y = Y / X is a different command from Y = X / Y, and both are useful. So when taking two different variables as arguments, these need to be counted twice.
- It is occasionally useful to be able to use the same variable as both operands, along the lines of
X = X + X. The Turing-completeness proof only does this when the result is being stored back into that variable (it doesn't, e.g., self-add one variable into the other).
That comes out to a lot of commands, and this construction doesn't quite manage to implement all of them: self-subtract, self-multiply and self-divide are missing (although self-add is present). It does, however, have a "halve" command Y = Y / 2 (which is not present in the original language: it only contains the variables, no constants!). This can be used to replace the two uses of self-subtraction in the original proof; the first use appears in a sequence of commands that go from \$X=Y=e\times t\$ to \$X=e\times t, Y=t\$ (which can be accomplished easily using a "halve" command because e is a constant power of 2, so you just halve Y \$log_2 e\$ times); and the second use is used to set Y from a known value d to 0 (which can be accomplished by repeatedly halving Y until it hits zero – because the value of d is known, it is known how many halvings this will require).
Unlike some of the previous answers, this one can be given as an explicit translation of each of the commands that are implemented:
Y=Y/X :@\×ؽ:ؽ
Y=X/Y :\×ؽ:ؽ
Y=Y-X _@\
Y=X-Y _\
Y=Y+X or Y=X+Y Ä
Y=Y*X or Y+Y*X ×\
start of program ؽ:@UU:ؽU
swap X, Y U
Y=Y+Y (or Y = Y*2) ×ؽ
Y=Y/2 :ؽ
end of program U×ؽ×ؽÇ
Only the commands that assign to Y are implemented directly; for commands that assign to X, you swap X and Y, run the command with X and Y swapped, then swap X and Y back again.
Here's a demonstration of the commands doing their thing, and here's an example of a compiled program. Both have had print statements added so that you can see them in action.
The basic construction is very simple: \ is a modifier to a two-argument builtin that makes it act cumulatively on a list, e.g. [x,y,z]+\ is [x, x+y, x+y+z]. When operating on a two-argument list, this maps [x, y] to [x, x op y] which is exactly what most Blindfolded Arithmetic instructions do. As a result, by putting Jelly's operators for addition +, subtraction _, multiplication × and floor-division : before the backslash, it is possible to implement four of the Blindfolded Arithmetic commands – and the modifier @, meaning "swap arguments", immediately gives two more. Reversing the list (U) makes it possible to operate on X rather than Y, producing the twelve "basic" commands. (One small variation: although +\ is a perfectly fine implementation of Y = Y + X, I used the equivalent abbreviation Ä because I wanted to use + in a different solution.)
Three obstacles remain. One is to get the program started; the first iteration of the program needs to start with the list [1,0], but subsequent iterations need to start with the value at which the previous iteration ended. Ending the program is also nontrivial: unlike Blindfolded Arithmetic's / operator, Jelly's : does not crash when dividing by zero (returning infinity or NaN as appropriate). Extra characters will be needed simply to get at a two-element list in the first place. The other obstacle is implementing the self-additions, self-subtractions, etc.; most of these are nontrivial in Jelly (which is why this construction uses a modified version of the language which doesn't need self-subtractions/multiplications/divisions for Turing-completeness).
The same builtin happens to solve all these problems at once: the builtin ؽ, which is a constant with value [1,2]. It solves the problem of forming a two-element list, because it is a two-element list. It also immediately provides Y = Y * 2 and Y = Y / 2 instructions because × and : do pointwise multiplication and floor-division when operating on lists, thus ×ؽ multiplies X by 1 (a no-op) and Y by 2, and likewise for :ؽ and division. It also happens to be of use in starting and ending the program, but this is a bit more subtle.
This construction, when wrapping from the end to the start of the program, encodes the list not as [X, Y] but as [Y, 4X], an encoding that is easily produced directly using U×ؽ×ؽ. The start of the program, ؽ:@UU:ؽU, undoes this translation. However, the "goto" command (actually a tail-call) that goes back to the start is not the usual ß, but rather Ç, "run the next line (wrapping around the program) parsing it as a 1-argument function". This reruns the main program, but the main program is a 0-argument function, so the use of a different parser means that the start of the program parses slightly differently:
ؽ:@UU:ؽU (0-argument function)
ؽ [1,2]
:@ pointwise divide into
U the reversed {initial expression [1,2]} (i.e. [2,1])
(producing [2÷1, 1÷2] = [2,0] using floor-division)
U reverse (producing [0,2])
:ؽ pointwise divide by [1,2]
(producing [0÷1, 2÷2] = [0,1])
U reverse (producing [1,0])
ؽ:@UU:ؽU (1-argument function)
ؽ [1,2]
:@ pointwise divide into the {argument} (i.e. [Y, 4X])
(producing [Y÷1, 4X÷2] = [Y, 2X])
UU reverse twice (no-op)
:ؽ pointwise divide by [1,2]
(producing [Y÷1, 2X÷2] = [Y,X])
U reverse (producing [X,Y])
In the former case, the U is inside the :@; in the latter case, it comes afterwards. This difference in the parser isn't something that's being intentionally exploited, but rather, something that had to be worked around.
As for the end of the program, this exploits what is probably a bug in Jelly. : has been extended to handle infinities, and cases like 0/0, 0/infinity, and the like all work correctly. However, apparently only the corner cases, not the edge cases, were implemented, because dividing infinity by a normal integer (e.g. infinity/2) causes the Jelly interpreter to crash with an exception. (It took me a surprisingly long time to find this; after discovering that all the corner cases worked correctly, I assumed there was no way to get it to crash until I hit an edge case by accident.) As such, after every division, Y is immediately doubled and then halved again; this is a no-op in most cases, but after a division by zero, it will cause the program to crash, emulating Blindfolded Arithmetic's halt behaviour. (0÷0 probably doesn't work, but the halt case for Blindfolded Arithmetic's Turing-completeness proof is implemented by dividing 0 into a positive number and never uses the case of 0÷0.)
A solution based on Thue
Character set: jµœƬṣ“”
Thue is a very simple programming language based around find and replace: starting with an initial string, each instruction specifies a search string, and a string to replace it with if it is found. The instructions run in an arbitrary order, as many times as necessary, until no more instructions can be run. (The original version of Thue had a mathematically nondeterministic evaluation order – i.e. the interpreter was supposed to look ahead to work out what sequence of replacements would cause the program to halt – but that mutated at some point into "just run a random command" due to a misunderstanding of "nondeterministic", and the language turns out to be Turing-complete no matter what algorithm the interpreter uses to decide which order to run the commands in, because it is possible to write Thue programs such that only one command is runnable at a time. In fact, Turing machines compile pretty much directly into Thue with that restriction.)
Thue compiles almost directly into Jelly, as long as the program is written to not care about evaluation order. The form of the program is initial string µ productions µƬ (with µ…µT being "loop until nothing changes"), where each production is of the form string œṣ string j (i.e. "split on string 1, then join on string 2", a very simple way to implement find-and-replace). Characters like j and œ are perfectly usable as the content of string literals (and Thue only needs two different characters to be Turing-complete), so in addition to jµœƬṣ, all that is needed are the string literal delimiters “”.
Here's an example program using this character set.
A solution based on The Waterfall Model
Character set: "$+8DLMṀns¿
The Waterfall Model is what seems like one of my more fundamental programming discoveries. I stumbled across the language several times in different contexts, and it took me a while to make the connection, but nowadays it's one of my most powerful tools for proving things Turing-complete.
The basic idea behind the language is: you have a number of counters ("waterclocks") each of which holds an unbounded integer; if none of them are 0, then all of them are decreased by 1; if one of them is 0, then a specific number is added to each counter, based on which counter it is that zeroed. A program consists of initial values for each counter, plus a two-dimensional matrix that specifies the amount added to each counter when each counter zeroes (with the coordinates being the counter that zeroed, and the counter that is added to). Counters aren't allowed to go negative, so every counter is supposed to add to itself when it zeroes.
It is known that it is possible to write an interpreter for The Waterfall Model using only four different characters. Using each of them only once. That was one of the first occasions upon which I stumbled across it, and at that point it didn't even have a name yet. However, the four-byte interpreter isn't really usable for this challenge, for two reasons: a) it's an interpreter not a compiler, and the implicit input of the program is exploited to set up the data structures it uses; b) it doesn't implement the language's halting behaviour.
Still, it wasn't too hard to adapt it into a subset of characters that can be compiled into. This solution implements a variant of The Waterfall Model in which the initial counter values are all in the range 0…9, as are the values added when a counter zeroes; it's still Turing-complete with that restriction (the Turing-completeness construction uses only small integers, none as large as 10). There are two basic parts to the program: a) setting up an appropriate data structure in memory, and b) implementing the language once the data structure is set up.
First, the setup (which has a couple of accompanying examples on TIO!). This is done using the four characters 8DLs. It is possible to create integers with arbitrary numbers of digits by writing a lot of 8s in a row; DL (digit length) can then be used to construct an arbitrary integer (e.g. 88888DL is the integer 5). Following this with D (digits) can then be used to produce an arbitrary list with all elements in the range 0…9 (as long as the first is nonzero), as shown in the first line of the TIO! link.
That list can then be split using s into a list of lists (a matrix), so long as the number of columns is 8, or 88, or 888, etc.; the number of columns in the matrix equals the number of counters plus one, and it's possible to add "junk counters" that never become zero in order to top the number of counters up to an appropriate number. This forms a data structure that is used to store both the counter values, and all the zeroing triggers.
In order to shrink the set of used characters slightly, the data structure is stored "upside down" (lower numbers within the data structure correspond to higher numbers within the program that was compiled), and has the following structure:
- The first row is arbitrary, except that all elements but the first are equal to each other, with the first being smaller.
- The rest of the first column stores the counter values, encoded as the difference between the actual counter value and the largest value within the column (with lower meaning a larger value); only their relative values matter, not the absolute value. For example, counter values of [1,4,3] could be encoded as [4-1, 4-4, 4-3] (i.e. [3,0,1]), or as [9-1, 9-4, 9-3] (i.e. [8,5,6]), or even as [1000-1, 1000-4, 1000-3] (i.e. [999, 996, 997]). (This implementation has a tendency to use unnecessarily large values as a base to subtract from; with many programs they will increase exponentially over the lifetime of the program.)
- The remainder of each row stores the zeroing triggers, again with only their relative values mattering (and lower values meaning "increase the counter by more"). If the first counter zeroing increases itself by 3, the second counter by 0, and the third by 2, that could be represented as [x, 0, 3, 1] (where x represents the counter value), but, e.g., [x, 6, 9, 7] would be equally valid.
When all the counters and all the zeroing triggers are in the range 0…9, it is possible to subtract them all from 9 (and add a row of the form [1,2,2,…,2] at the start) in order to produce a matrix of the required form using only elements in the 0…9 range (which can be created using the 888…888DLDs construction).
To actually implement The Waterfall Model given this data structure, all that is needed is a loop that repeatedly finds the lexicographically largest line within the data structure, then adds the first element of that line to the entire first line, the second element of that line to the entire second line, and so on (in Jelly this addition is a builtin, +", and there is a Ṁ builtin for "maximum" to identify the appropriate line).
To see why this works, realise that the row with the largest value in the first column, if it's a counter, will be the counter nearest zero (because the encoding is upside-down), thus it will be the counter that zeroes next. The addition's effect on the first column will then change the relative values of the counters as though the appropriate value from the zeroing trigger were being added (and the absolute value doesn't matter, meaning in turn that only the relative values of the "rest of the row" matter). It also has an effect on columns other than the first, but this affects all those columns equally, so they will still have the correct relative vaues.
It is possible that the first row (which doesn't correspond to a counter) will have the largest value. In this case, it adds a smaller value to itself than it does to each of the other rows, so it doesn't change the relative values of the counters, and will eventually not be the largest any more; in other words, it ends up having no effect on the program execution as a whole.
The main tricky remaining part is to halt the program when the halt counter zeroes. It is sufficient for Turing-completeness to have a single halt counter with a fixed index; in this case, I used the seventh counter (which corresponds to the eighth row of the matrix).
The code for the main loop looks like this in Jelly:
+"Ṁ$MṀ$n8$$¿
¿ while loop
$ body (2-builtin block):
+" {to each row of the matrix}, add corresponding elements of
Ṁ the maximum {row of the matrix}
$ $$ condition (4-builtin block):
M the index of the maximum row
Ṁ tiebreak: maximum index
n8 is not equal to 8
Using lots of $ like this to introduce block structure used to be the primary way to create nontrivial loop bodies and conditions in Jelly, but is now obsolete because it takes up so many bytes. It still works, though, and is nice for minimal-subsets challenges because you can do it all with just $, you don't need any other character. The tiebreak on the maximum index is required even if there aren't ties; otherwise, Jelly tries to compare the list [4] to the number 4 and those are not equal, so the loop would never end.
Here's an example of a program compiled from The Waterfall Model running. This uses decimal rather than unary counters for space reasons (and has the halt counter in the wrong place). The arbitrary offsets applied to counter elements have a tendency to increase exponentially, so I added a footer that shows both the final value of the internal state, and the internal state normalized so that the halting counter has its value represented as 0.
Solutions based on Addition Automaton
The Waterfall Model can be implemented in Jelly in four bytes. Addition Automaton outgolfs that – it can be implemented in three, and the important ones haven't been used so far by the other subsets. So after discovering the language, I was naturally going to have to try to fit it in here.
Addition Automaton is basically a find-and-replace operation on the digits of a number, in some base b; a program specifies a replacement value for each digit, and the digits get replaced, repeatedly. The computational power comes from the way multiple-digit replacements are handled; they don't push the other digits away to make room, but instead carry into the more significant digits of the number (meaning that the higher digits of one replacement will end up adding onto the replacement of some more significant digit, thus the name "Addition Automaton").
Addition Automaton has something of a trade-off available between the ability to use small bases and the simplicity of the halt state. The lowest known Turing-complete value of b is 10, but at that point the halt state is quite complicated. If the value of b can be higher, the halt states become simpler: you can design a Turing machine to halts by erasing the entire tape and only then entering a halt state, and when you emulate that in Addition Automaton it corresponds to "halt when the number becomes 0", but making a Turing machine halt like that adds complexity that needs a higher b to implement. So a low-b and high-b implementation of the language look quite different. Maybe that means they can be implemented with different characters?
With small b (b=10)
Character set: CNt©®ÐƊḌḶṃṄẒE
The primary challenge in this situatoin is trying to get the halt state to work; with b=10, the simplest known halt condition is "halt if you see the same number twice, but possibly with a different number of trailing zeroes". That's a little complicated, but can be handled by removing zeroes while the program runs, and using one of Jelly's "loop until you see the same thing twice" loops.
Here are the TIO! examples for this section. There are actually only two steps to this solution: a) expressing the relevant values (a list of numbers, and a number) despite not having any literals available in the character set, and b) writing an Addition Automaton interpreter to run on those values.
First, the construction of the data. With N (subtract from 0) and C (subtract from 1), it is possible to reach arbitrary integers by alternating between N and C (you may have seen people use ~- and -~ in practical languages as a method of doing small adjustments to numbers in code-golf, or strung together into long strings in restricted-source – this is the same principle). © stores the result returned from a builtin in a register, so it's possible to place a © in an appropriate place in an NCNC…NC chain to construct two numbers (the current value and the register). It's then possible to use ṃ, which on numbers does base conversion, to produce an arbitrary list of integers (by expressing it as a number in a sufficiently high base), as long as the first element of the list isn't 0 (a restriction that turns out not to matter) – it can take its right-hand argument from the register, meaning that we can use any base we want here.
In the construction here, I use ṃ© to store the resulting list in the register, and then just need to create another number to serve as the initial value for the Addition Automaton state value. This is done by using E ("all elements are equal") to produce an arbitrary integer (in this case, 0), and then using repeats of NC to increment that to the desired value.
Now all that's needed is an Addition Automaton interpreter with lax loop detection:
ṃ®tẒḌƊṄƊÐḶ
ṃ Map the digits of {the state value}
® using the list stored in the register as the map
t Delete all leading and trailing
Ẓ 0s if there is a non-prime, 1s if there is a prime
Ḍ Convert from decimal to integer, with carry
Ɗ Ɗ Specifies loop body length: five builtins
Ṅ An arbitrary fifth builtin ("print with newline")
ÐḶ Loop until the same value is seen twice
There are two weirdnesses here. One is that I'm starting to run out of ways to specify the size of a loop body; Ʋ didn't work for some reason, but Ɗ did as long as I added an extra pointless builtin for it to count. I chose Ṅ because it's a no-op apart from producing output, and the output is actually useful to see the program running. The other weirdness is that I want to say "remove all trailing zeroes" (base-conversion won't produce leading zeroes, so those don't matter), but don't have any easy ways to produce zero in the character set. Instead, I use Ẓ which will test something or other for primality (I'm not entirely sure what), but there are definitely non-primes present so zeroes will be removed (trailing zeroes on the number imply that it isn't prime!). It might also remove leading and trailing digits that map to the digit 1, but it isn't difficult to write an Addition Automaton program so that those are never produced (the Turing-completeness proof for b=10 does it naturally).
The first line of the linked example shows how to create a list and an integer using CN©®ṃ. The second line shows an Addition Automaton program running in the interpreter, and halting when it reaches the end. (This one was compiled from a 4-state 2-symbol busy beaver Turing Machine – to prove Turing-completeness you would use Echo Tag instead, but the halt condition is the same.)
With large b
Character set: %34b¡ÑḅẸ⁺
The previous section used ṃ to convert from number to digits, and Ḍ to convert from digits to number. That means that Jelly's general-purpose base conversion operators bḅḃ are all available, allowing for an alternative Addition Automaton implementation. This set is powerful enough that I have written a working compiler for it that generates comparatively short programs (these both have an added Ṅ so that you can see the program running, but it isn't required for the halt behaviour to work correctly). To stay within the character set, b must be expressible with only the digits 3 and 4, but this is not a significant restriction.
The first problem: creating constants. This character set has the digits 34 and the modulo operation %, which is enough to create arbitrary nonnegative integers. (The function on the first line of the compiler linked above converts integers to this form, using a primitive-recursive algorithm. The idea is that when taking a decimal number modulo 333…3334, the place values of the digits, from least to most significant, are 1, 10, 100, 1000, …, -2, -20, -200, -2000, …, 4, 40, 400, 4000, …, -8, -80, -800, -8000; and this lets you effectively write a number in binary-coded-decimal, albeit with the digits in weird places.) Because the character set contains base conversion operators, it is possible to use these integers to create arbitrary lists of nonnegative integers.
The next problem: how to create a lookup table for the transitions, given that both ị and ṃ have been used already? The solution: use the base conversion operators! "Convert this list of digits in base x to a number" is actually the same problem as "evaluate this polynomial at the given value of x", so both problems are solved by the same Jelly builtin, ḅ. Thus, the table can be implemented as a function that returns the appropriate output for each of the possible inputs, and the function in turn can almost just be a polynomial. Creating polynomials that reach particular values at particular points is a well-known problem.
The followup problem: although it's easy to fit/interpolate a polynomial to any given number of input/output pairs (assuming all the inputs are distinct), quite frequently the coefficients are non-integer rational numbers, which can't be expressed in this character set (or indeed in Jelly as a whole). So instead, we need a way to do "division" that stays within the integers. The solution to that is modular arithmetic! When operating modulo a prime number, division (except for division by 0) is well-defined. Unfortunately, I couldn't prove that there are infinitely many primes that can be written with only 3 and 4. Fortunately, it doesn't matter; we only need to be able to divide by values no greater than b to interpolate the polynomial. For non-prime moduli, division is sometimes well-defined; you can do it the divisor and modulus are coprime (even if the dividend isn't); so what is needed is a number, written with only 3 and 4, that is coprime to b factorial (and that is sufficiently large). As it happens, for any positive integer, there are infinitely many integers of the form 444…4443 that are coprime to it (this is because for all positive integers, there are infinitely many repunits that are a multiple of it except for factors of 2 and 5; multiply a sufficiently large one of those by 4 and subtract 1, and you have a number that's coprime to it except for factors of 2 and 5; and because it ends in 3, it can't be divisible by 2 or 5 either).
All that is needed now is to express this in Jelly. The character set contains no grouping or precedence-override operators, so some creativity is needed to do all the calculations on constants without Jelly mis-parsing the code. One of the major problems here is that alternating constants and binary operands, along the lines of 3%3%3%3…, can be parsed either as 3% 3% 3% 3… or as 3 %3 %3 %3…, and Jelly prefers to pick the wrong option. It was possible to force an interpretation by starting with two constants in a row (3 3% 3% 3% is unambiguous), but with just 3 and 4 as constants you can't put two in a row because they would merge into one number. To solve this, I added ⁺ to the character set; this is an almost useless abbreviation that repeats the previous builtin, something which is actually useful here.
The program has this general form (using # to represent a numeric literal):
#⁺bḅ#%#b#ḅ%#ḅ#b#ÑẸ¡
Creating the lookup polynomial:
#⁺b a number in base itself (i.e. always [1,0])
ḅ# convert to base # (i.e. just the constant #)
%# modulo a constant, i.e. an arbitrary integer
Evaluating the polynomial:
b# convert to base #, i.e. an arbitrary list
ḅ convert base [see below] digits to number
%# modulo a constant
Do the carries:
ḅ# convert base b digits to number
b# convert number to base b digits
Loop:
¡ a number of times equal to
Ẹ 0 if all the digits are 0, else 1
Ñ call a 1-argument function
(Ñ doesn't normally call the current function, but as this program contains only one function, it has nowhere else to go.) The main trick here is in how the program starts up: on the first iteration it is being called as a 0-argument function, and in that case, the ḅ of ḅ% will take its argument from the constant at the very start of the program. That's ignored in most cases (by being represented as a number in base itself, which is always "10", which can be base-converted into another constant); and we set the value to b, a value that normally can't appear at that point in the program (which is given a list of digits in base b, which are all less than b). That makes it possible to store the initial value simply by getting the polynomial to return it when given b as an argument.
On subsequent iterations of the program, the ḅ of ḅ% takes its argument from the function argument, i.e. the list of base b digits calculated on the previous iteration.
The halt state here is "the internal state becomes 0". The loop around the program happens at a point where the number is represented as digits (rather than as an integer), so it does the zero test by using Ẹ to check whether or not all the digits are zero. The control flow here is done using a for loop around a recursive call (Jelly's equivalents of if, while, etc. have already been used by other subsets).
0s per that link; it can be expressed using any character from the entire UTF set (and possibly beyond.) If you accept that, it makes Unary the winner. \$\endgroup\${and/or}to access below the ToS while the other usesj; one can use character I/O while the other uses decimal I/O... you may have to get creative with your NOPs. \$\endgroup\$