20
\$\begingroup\$

Find the maximum possible number of disjoint sets of characters, that are Turing complete subsets of your language.

Rules:

  • You can assume your Turing complete subset is contained in/called from a main-function if that is required by your language

  • The subsets must not share any characters (in the native encoding of the language), this also includes new-lines

  • You are allowed to use standard library functions

  • You should not use languages like Lenguage that only use the length/positions of the code instead of the actual values of the characters.

  • Your score is the number of disjoint subsets you find.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ Related: codegolf.stackexchange.com/q/247536/91213 \$\endgroup\$
    – mousetail
    Aug 17 at 9:50
  • 8
    \$\begingroup\$ Brainfuck is Turing complete and can be converted to Unary following the rules at esolangs.org/wiki/Unary A Unary program is just a string of identical characters. Unary doesn't have to be expressed in 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\$ Aug 17 at 20:49
  • 1
    \$\begingroup\$ I really want to see Trilangle get a score >1, but I don't currently have the time to prove it. I'm fairly sure it's possible: There are six branch instructions; one program can use { and/or } to access below the ToS while the other uses j; one can use character I/O while the other uses decimal I/O... you may have to get creative with your NOPs. \$\endgroup\$
    – Bbrk24
    Aug 18 at 12:28
  • \$\begingroup\$ @LevelRiverSt: Since the semantics of a Unary program are entirely encoded by the length of the program, the content of the string, i.e. which character is chosen, is irrelevant and carries no information. Therefore, one could even argue it uses 0 characters. \$\endgroup\$ Aug 20 at 21:44

10 Answers 10

18
\$\begingroup\$

Python 3, score 3

()+1𝒸𝑒𝒽𝓇𝓍
'*.23;<=F^_{}𝓪𝓬𝓮𝓱𝓵𝓹𝓺𝓻𝓼𝔁
 "%,-0:[]acefinorst~𝐀𝐄𝐜𝐞𝐢𝐧𝐨𝐫𝐬𝐭𝐱

This is an extension of @UnrelatedString's answer, but too long to fit in a comment. Each line contains a subset of characters that can perform arbitrary code execution. A meaningless bonus is that none of these require newlines, although there was a reason for this which I explain later.

Subset 1

The first subset is simple, and is the same as @UnrelatedString's second subset. The code itself looks something like this:

𝑒𝓍𝑒𝒸(𝒸𝒽𝓇(1+1+...+1)+𝒸𝒽𝓇(...)+...)

Subset 2

In the other answer, they wondered whether it was possible to set attributes on a type without creating a new class. Yes we can, and a quick examination shows that the following built-ins are available:

__loader__, quit, exit, copyright, credits, license, help

Using one of these built-ins, we can redefine one of its class attributes to avoid using parentheses. We can for example, redefine the less-than operator (<):

help.__class__.__lt__=exec;help<'print(1)'

To construct arbitrary strings, f-strings are a reasonable replacement for concatenation. We can also re-use the trick of redefining operators to call chr(). Here's how to execute print(1) using this subset:

𝓱𝓮𝓵𝓹.__𝓬𝓵𝓪𝓼𝓼__.__𝓮𝓺__=𝓮𝔁𝓮𝓬;𝓱𝓮𝓵𝓹.__𝓬𝓵𝓪𝓼𝓼__.__𝓵𝓮__=𝓬𝓱𝓻;𝓱𝓮𝓵𝓹==F'{𝓱𝓮𝓵𝓹<=2*2*2*2^2*2*2*2*2^2*2*2*2*2*2}{𝓱𝓮𝓵𝓹<=2^2*2*2*2^2*2*2*2*2^2*2*2*2*2*2}{𝓱𝓮𝓵𝓹<=2^3^2*2*2^2*2*2*2*2^2*2*2*2*2*2}{𝓱𝓮𝓵𝓹<=2^2*2^2*2*2^2*2*2*2*2^2*2*2*2*2*2}{𝓱𝓮𝓵𝓹<=2*2^2*2*2*2^2*2*2*2*2^2*2*2*2*2*2}{𝓱𝓮𝓵𝓹<=2*2*2^2*2*2*2*2}{𝓱𝓮𝓵𝓹<=2^3^2*2*2*2^2*2*2*2*2}{𝓱𝓮𝓵𝓹<=2^3^2*2*2^2*2*2*2*2}'

Subset 3

We've already used up ., =, and (), so finding a way to call exec is becoming difficult. The one thing that is free are variable names, since Unicode provides us with more than enough variations of each letter. However, it is possible to do so by abusing asserts:

AssertionError=exec;assert 0,'print(1)'

assert takes two arguments: the pass/fail condition, and a string which is printed when the condition fails. This is roughly equivalent to if cond: raise AssertionError(msg). By reassigning AssertionError to exec, the msg parameter effectively becomes the first argument of exec. Curiously, this feature seems exclusive to AssertionError, as other error types I've tried don't behave like this. Anyway, this by itself doesn't work because we can't use = or ;.

The second trick is to abuse for loops. Let's just do for AssertionError in[exec]: instead! The last thing we need is the string construction, which can be done using %-formatting and repeated -~s. The size of the code grows exponentially, but here's an exec('print(1)'):

for 𝐀𝐬𝐬𝐞𝐫𝐭𝐢𝐨𝐧𝐄𝐫𝐫𝐨𝐫 in[𝐞𝐱𝐞𝐜]:assert 0,"%c%%c%%%%c%%%%%%%%c%%%%%%%%%%%%%%%%c%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%c%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%c%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%c"%-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~0%-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~0%-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~0%-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~0%-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~0%-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~0%-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~0%-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~0

Subset 4??

Originally, I planned for a 4th subset through executing Python bytecode, since Python is able to natively run pyc files. The magic header for pyc files in Python 3.11 is \xa7\x0d\x0d\x0a. I noticed the \x0d and \x0a as being newlines, so I crafted my other solutions specifically without them. But I somehow missed the \xa7 byte which is not representable in UTF-8, making this solution automatically invalid.

Still, there is some good potential for a 4th subset. For example, using #coding:u7 to change the source's encoding could've also worked in place of Subset 3. Decorators are a possibility as well. I also vaguely recall Python also being able to natively handle zip files, and the PKZip magic header makes this a possibility: \x50\x4b\x03\x04.

Lastly, the challenge only asks for "Turing-completeness", not arbitrary code execution. I only tried to do the latter, so it's possible that scoring 4 is quite a bit easier than I'm making it.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Wow! It would certainly never have occurred to me that freeing : up for loops would be precisely the substitute for =. Regarding decorators, I don't think there's any way to use them that doesn't use :, but it's not inconceivable that something like this might be useful. But, the most obvious upshot of that would be saving [], which we can do already. \$\endgroup\$ Aug 19 at 12:53
  • 1
    \$\begingroup\$ @UnrelatedString I thought about a way to use a list comprehension to remove the :, which then makes room for the decorator/class-based solution. It doesn't work with assert, so another approach would have to be discovered. Or maybe there's some import that opens up a class that can be abused in some way... not sure :/ \$\endgroup\$ Aug 19 at 21:36
  • \$\begingroup\$ Ooh, come to think of it, rather than using them for more weird bindings, list comprehensions in and of themselves ought to be capable of computing any finite number of steps of some kind of Turing complete computation--at least so long as the "program" is encoded with essentially an enumerate at every level. The problem is turning that into infinitely many steps... \$\endgroup\$ Aug 20 at 0:26
14
\$\begingroup\$

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 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!

  1. 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").
  2. 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.
  3. 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¤.
  4. 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¤¤
  5. …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.
  6. 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.
  7. 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.).
  8. 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 , or strung together into long strings in – 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).

\$\endgroup\$
1
  • 2
    \$\begingroup\$ <3 <3 <3 <3 <3 <3 \$\endgroup\$
    – Jonah
    Aug 20 at 1:44
8
\$\begingroup\$

Incident, 128 or 557056

If "character" means byte

Any set of two bytes is Turing-complete in Incident; thus it's possible to create 128 disjoint subsets, e.g. {0x00, 0x01}, {0x02, 0x03}, {0x04, 0x05}, and so on up to {0xFE, 0xFF}.

The reason is that the language determines its token set at runtime: the set of tokens used by a program is the set of substrings of that program that appear exactly three times (without being contained within or overlapping other such substrings within the input program). The language gives meanings to tokens based on their relative positioning, rather than the bytes that make them up. As such, an Incident program is tr-invariant; you can change the character set it uses simply by consistently replacing bytes, because that doesn't change the token structure of the program.

(The creation of Incident was actually inspired by this site: I wanted to find a way to avoid questions getting stuck in a set of bytes that they had no way to get themselves out of. So being Turing-complete off any set of two bytes is a natural consequence of the way the language developed.)

If "character" means Unicode character

Incident doesn't attempt to parse its input into characters; it just looks at it as a single binary stream of bytes. However, that doesn't mean that you can't just simply feed a text file to the Incident interpreter. As such, it's meaningful to ask about what subsets of Unicode characters are Turing-complete if you put them into a text file, and ask the Incident interpreter to run the resulting text file as a program.

Assuming that the two characters in question have no bytes in common in their encodings, you actually end up with the exact same case as when you're using two different bytes: the "identify substrings that occur three times" routine is invariant under the operation of replacing one byte with two or more, so long as each byte that appear within the encoding always uniquely comes from one of the same two original characters. As such, the goal is to find 557056 subsets (because there are 1114112 encodeable Unicode characters).

This can be done fairly simply using UTF-8, choosing the two characters in each subset to always be the same length as each other:

  • For ASCII (0x00 to 0x7F), simply pair the characters as bytes, as in the previous case;

  • For two-byte characters, sort the characters into four groups {00, 01, 10, 11}, based on the least significant bit of their leading byte and least significant bit of their trailing byte: all four groups are the same size. Characters in group 00 have no bytes in common with characters in group 11, so you can form a subset by pairing an arbitrary character in each group. Likewise, characters in group 01 have no bytes in common with characters in group 10, so those form subsets in the same way.

  • For three-byte characters, divide into groups based on the least significant bit of the leading byte and the least significant two bits of the trailing byte: this produces 32 groups which are all the same size. The groups can be paired into 16 pairs as follows:

    0 00 00 with 1 11 11
    0 00 01 with 1 11 10
    0 00 10 with 1 11 01
    0 00 11 with 1 01 10
    0 01 00 with 1 10 11
    0 01 01 with 1 10 10
    0 01 10 with 1 00 11
    0 01 11 with 1 10 00
    0 10 00 with 1 01 11
    0 10 01 with 1 11 00
    0 10 10 with 1 01 01
    0 10 11 with 1 01 00
    0 11 00 with 1 10 01
    0 11 01 with 1 00 10
    0 11 10 with 1 00 01
    0 11 11 with 1 00 00
    

    For each pair of groups, picking an arbitrary character from each group will produce a valid subset (i.e. no bytes that exist in one character in UTF-8 will exist in the other).

  • Four-byte characters use a similar construction, but now 1024 groups are used (taking one bit from the leading byte and three bits from each of the trailing bytes). Listing all the pairings wouldn't easily fit in the post, so here are the rules:

    • Label the bits of each group as A BCD EFG HIJ.
    • Consider the three values obtained by bitwise-XORing two of BCD, EFG and HIJ:
      • if none of them are 1 (001), XOR the group number with 1 001 001 001 to produce the group number it's paired with; otherwise,
      • if none of them are 2 (010), XOR the group number with 1 010 010 010 to produce the group number it's paired with; otherwise,
      • if none of them are 4 (100), XOR the group number with 1 100 100 100 to produce the group number it's paired with.

    It is not possible for the three resulting values to be 1, 2 and 4 (if BCD xor EFG is 1 and EFG xor HIJ is 2, then BCD xor HIJ is BCD xor EFG xor EFG xor HIJ which is 3; likewise for other assigments of positions to values). So these rules will always produce a result. Additionally, the pairing is consistent (i.e. if X is paired with Y, then Y will be paired with X); this is because the same number is being XORed into all three of the relevant segments of the trailing bytes, so it won't change the result you get when you XOR two of those segments together. Finally, it will ensure that the two members of each subset have no bytes in common because their leading bytes have different parities, and there is no way for a trailing byte of one member to equal a trailing byte of the other member (which can be seen by considering the pairwise XORs of the two equal trailing bytes, and the bytes in the corresponding position of the other member).

There is some room for interpretation as to whether 557056 is actually the correct number of subsets here, depending on what exactly you consider a Unicode character to be. For example, the original version of UTF-8 allowed up to 231 different characters, meaning 230 subsets, but Unicode is nowadays capped at 1114112. Additionally, some of the characters may be considered invalid due to, e.g., being noncharacters or surrogates. However, the Incident interpreter doesn't care about any of this because it isn't trying to parse the UTF-8 anyway, and just looks at the bytes that make it up.

\$\endgroup\$
3
  • \$\begingroup\$ > You should not use languages like Lenguage that only use the length/positions of the code instead of the actual values of the characters. \$\endgroup\$
    – xigoi
    Aug 18 at 14:03
  • \$\begingroup\$ @xigoi The values do matter; what doesn't matter is what they in and of themselves are. (It's kind of a stupid rule anyways; it's not like it's a competition between languages, and if you really don't want a ton of upvotes on a trivial high score then why not CW it yourself) \$\endgroup\$ Aug 18 at 15:04
  • 3
    \$\begingroup\$ @xigoi: This answer predates that rule being edited into the challenge. The rule is somewhat ambiguously worded, and it's unclear whether Incident breaks it: Incident cares a lot about which tokens are the same as each other, so the input definitely needs to be inspected (things other than the program's length are very relevant), it just doesn't care about how the tokens are specifically spelled. \$\endgroup\$
    – ais523
    Aug 18 at 15:44
8
\$\begingroup\$

Python 2, score 2

Arbitrary code execution with exec and % formatting (from this answer by xsot)

exc="%

(six visible chars and newline)

Untyped lambda calculus with lambda (from this answer of mine)

lambd :()

The score for Python 3 would be very likely 1 since ()s are necessary for more things.

\$\endgroup\$
3
6
\$\begingroup\$

Python 3, score 2

Arbitrary code execution without ()

clags x:[]
_.time=hr+1

Any function f of a single argument can be called without parentheses as so:

class F:[]
F.__class_getitem__=f
F[arg]

where F can obviously be any identifier constructed from the characters in the set, and the [] is just a funny way to pass because it would feel weird to put p in the set just for that. exec and chr only need one argument, and + doesn't need parentheses to begin with.

Translate here.

Arbitrary code execution without =, or the characters in exec

(~{f0r"chex}-)

I guess the lack of = isn't a big deal since this doesn't have to milk out every last character, actually; the real highlight is execing without exec by abusing Python's NFKC normalization of identifiers. With +1 taken, arbitrary integers are constructed with -~0, and the characters are concatenated in an f-string.

Translate here.


While it's difficult to imagine a score-3 solution, a few extra bits of note:

  • Spaces can be replaced with backslash-newline combinations.
  • There's plenty of other stuff that normalizes to exec, provided you can find a third way to call it.
  • Obviously, arbitrary code execution isn't necessary for Turing completeness; I actually meant to do the __class_getitem__ set without exec to begin with by implementing ais's Waterfall Model but once I started using list comprehensions I realized I may as well just cheap out and do something easier to play with.
  • If there's any way to get a type you can set __class_getitem__ on (or make a type you can define normal __getitem__ for) without a class definition (or calling type), then that frees : up for control flow statements. How to do anything with them without newlines, parentheses, or = is beyond me.
\$\endgroup\$
6
\$\begingroup\$

Vyxal, score 11

1+C†
k⟇hoĖ
⌈¢ `
‛p"øV
56S)ŀẊ
⟨⟩|₅ṫ⁽İ$J
4L{ḣτ0€∇iWfḢ…
λ;←→wMt∧
Þ∞(„‟[]¬₈Q
\01ḊȧḞƛ‡∷¥£Ṫẋ
2ʁṘ⅛≬ḭ'¼¦ɖ*-aNßX:^}

For a language to be Turing-Complete, it must be (among other things) possible to loop infinitely. There are several ways to do this in Vyxal:

  • Ė and evaluate a string as Vyxal and Python respectively.

  • In versions 2.6-2.8.2 an ACE vulnerability exists that allows passing arbitrary Python code into any sympy builtin. All variants of this require , the math element digraph.

  • (ƛ'µ⟑, ¨2 and ¨3 can all iterate over an infinite list. However, there aren't that many ways to create infinite lists:

    • Various digraphs starting with Þ push a constant infinite list to the stack, or have the ability to create infinite lists from finite ones
    • The builtin can create an infinite list based on a generating function, which may not be usable (see below)
  • λ⁽‡≬), and until recently @, can define functions. There are a wide range of builtins which call functions in certain ways, which can be used to implement some form of lambda calculus or similar.

  • ¢ and øV perform repeated replacement in different ways, which allows implementing some form of string rewriting system.

  • { creates a while/infinite loop by itself.

I'll start with the eval solutions, because they're the easiest:

Easy eval

1+C† allows getting any number with 1+, converting it to a character with C, concatenating those into a program with +, and evaluating with .

To create a character with character code n, we start with 1CC, then append n-1 copies of 1+, and append a C to turn into a character. (CC is a no-op, casting to char then back). We can repeat this as many times as we want and use + to concatenate the result into a single string before evaluating as Python with .

Here's a compiler from Python to this, and here's a program running print(5).

Harder eval

k⟇hoĖ allows getting the Vyxal codepage with k⟇, accessing any character by repeatedly removing (o) the first item (h). (The cost of this is exponential but it doesn't matter). Then we can evaluate this as Vyxal code with Ė. (note: Unlike the above we can just evaluate single characters, as 1-byte Vyxal programs still work).

Here's an example: k⟇h gets λ, the first character in the Vyxal codepage. Then, k⟇k⟇ho removes λ from the vyxal codepage, leaving ƛ, the second character, in the first position, which can be obtained with another h. This can be repeated any number of times, gaining access to any character in the Vyxal codepage. More examples of this technique can be found here.

Here's a program that compiles a single-character program into this. To create strings we can evaluate + (although the program that does so has length 244 ≈ 17 trillion bytes) and concatenate two characters.

String rewriting

The builtins ¢ and øV can be used to repeatedly perform string replacments until nothing changes, similar to Thue. For example, here's a binary-to-unary converter.

The main difference is that, while Thue performs replacements randomly, these builtins perform all replacements in parallel. However, this turns out not to be an issue as it's possible to write Thue programs that only allow one replacement at a time.

With this in mind, we need two disjoint ways to generate arbitrary strings and sequences of strings. We don't need access to all ASCII characters, as Thue is Turing-complete with only two characters.

The easy way: string literals

⌈¢ `

In Vyxal, strings are delimited by backticks, for example `abc` represents "abc". We can then split these strings by spaces with . This does come with the slight snag that non-ASCII characters within strings represent compressed words, but we can still write a turing machine with the symbols disappointed and aquarium. here's the binary-to-unary converter from before, using disappointed as 1 and aquarium as 0.

The hard way: more annoying string literals

‛p"øV

Backtick-delimited strings aren't the only way of creating string literals. There's also , which groups the two characters in front of it as a string.

We can then concatenate these strings with p, or pair two into a list with " and prepend other strings with p. While this does restrict us to even-length strings, that doesn't really matter - we can simply use pairs of tokens to represent single tokens.

Again, here's the binary converter, this time using "p as 1 and "V as 0.

The even more annoying way - reject string, return to number

56S)ŀẊ

There's one more builtin that performs infinite replacement - ŀ. Unfortunately, this only works on strings, not on string lists, so it needs another operation to work.

We use ), which groups all elements up to the previous newline into a function, then use to repeatedly apply that function to a value until something repeats.

As before, we only need two symbols - we can use the digits 5 and 6, and use S to stringify them (since ŀ only works on strings).

Here's the binary converter from before, representing 1 with 655 and 0 with 656.

Tag systems

⟨⟩|₅ṫ⁽İ$J

Tag systems are turing-complete languages that use a constantly-changing tape. They have a set of rules, which decide how to map one value to several other values, and repeatedly remove the first few characters from the tape, and append the sequence corresponding to the first removed item.

So, I've implemented the tag system from ais523's answer here. The map is hardcoded as a 2d list of numbers - Vyxal lists are delimited by ⟨⟩ and each term is separated by |. The list of numbers, and the initial value, are the program; everything else is fixed.

The program starts by removing the last item and pushing it separately (), then indexes that into the rule list. After that, it prepends the rule to what remains and removes the last item. It's quite a bit more complicated than it needs to be due to my attempts to minimise the amount of unique characters.

This is then iterated until a repeated state is detected, using the builtin İ. The program halts by repeating states. Since the progression from one state to the next is entirely deterministic, a tag system has no meaningful behaviour once states repeat anyway. An explicit halt symbol could be added in without too much trouble. The output is all the states the program has gone through, which is definitely sufficient.

Finally, all the integers can be replaced with getting the length of a list, since we can construct arbitrary lists. I'm using the builtin here (push length without popping) instead of L because L can also be used to get the length of a number.

While writing this, I also realised I can use the single-element lambda builtin here, which is otherwise not particularly useful, because I can wrap the whole output in a list.

Here's the tag system from before without digits.

More tag systems

4L{ḣτ0€∇iWfḢ…

So, we don't necessarily need to explicitly hardcode the rule table. We can construct it. We can represent any number n as n 4s followed by an L - taking the length of the number with n 4s. If we use base conversion (τ) to convert this to base 4, and then split on 0s, we've created a way to define arbitrary 2d lists of integers. If we need numbers greater than 4 we can just use base-44. (note: This does come with an exponentially large program size. Representing the rule table from before is 80 megabytes)

So, here's another implementation of the same tag system, but backwards – This one pops from the start and appends to the end, and consequentially all the values are backwards.

This one uses a while loop ({) and just prints every value. It doesn't halt, but Vyxal has live output and I can define "halting behaviour" as printing a value that's already been printed, which shows the program has entered a permanent loop, and is fully distinguishable from any nonhalting behaviour.

And here is the same program with the rule table encoded properly. (note: the 80603272277 would be replaced with that many 4s followed by an L).

There's probably quite a few characters to be saved here.

Lambda calculus / combinatory logic

λ;←→wMt∧

In Vyxal, we can define lambda functions with λ...;. Additionally, although lambdas can't have named arguments, we can set/get variables with →a/←a. Vyxal's variables are actually local by default, inheriting Python's behaviour.

Calling a function is a little difficult, as (function call) is taken, but we can wrap our arguments in a list (w), map (M) the function over the list, and unwrap the result (t). M does take the argument followed by the function, so some tricky stack manipulation is required for this to work.

So, we can implement the SKI combinators quite simply with this:

λ; # I
λ→aλ←a;; # K
λ→aλ→bλ→c ←c w ←b M ←c w ←a M t M t ;;; # S

The first two are fairly self-explanatory. The third, however, nedds its own explanation so I can understand it:

λ→a                                   ; # a => 
   λ→b                               ;  # b =>
      λ→c                           ;   # c => 
          ←c w                    t     # c
               ←b M                     # b(c)
                    ←c w      t         # c
                         ←a M           # a(c)
                                M       # a(c)(b(c))

Note that the variables are named a, b, c for clarity – they could just be named a, aa, aaa.

However, there's another issue here: Variable names can have multiple alphabetic characters, so we can't just run ←aM as that will get interpreted as retrieving the variable aM. We need some form of no-op (or similar).

Space and newline are both no-ops, but there's a better alternative: , logical or, which takes two arguments and returns the first truthy argument. The definition of "first" is a little weird due to being on a stack, but all we have to care about is that, when given two functions, it returns the second.

With that in mind, here's the list of functions. With a careful ordering of these we can call any combination of S, K, and I, which is sufficient for Turing-Completeness.

A solution based on Picofuck

Þ∞(„‟[]¬₈Q

Picofuck is a brainfuck derivative in which the program loops indefinitely, and the only conditionals allowed are unnested if statements. The instructions translate quite easily to Vyxal:

  • > (shift pointer right) becomes (rotate stack left)
  • < (shift pointer left) becomes (rotate stack right)
  • * (invert bit at pointer) becomes ¬ (logical not)
  • ( (open if statement) becomes [
  • ) (close if statement) becomes ]

I/O is not required for Turing Completeness, and the entire program runs in an infinite loop (Þ∞(). Þ∞ represents the list of all positive integers, and ( iterates over it.

There are a couple of minor differences between the two approaches:

  • Picofuck requires if statements to not be nested, but this allows nesting if statements, which makes some constructions to bypass the following requirements easier.
  • While Picofuck runs on a unbounded tape, this runs on a cyclic tape. To add elements to the tape, we have , which pushes 256 (could be any integer). Since we can run in a loop to give the tape an arbitrary length, this allows us to initialise an arbitrary amount of memory.
  • While if statements in Picofuck preserve the condition, [ in Vyxal pops from the stack. This can be bypassed by working with multiple copies of each value, and ensuring popped values are restored. (I could just add : (duplicate) to the command set but I might need that later)
  • In Picofuck, the program terminates when the program attempts to move the pointer to the left of the start point. While termination isn't strictly necessary, some form of distinguishable output is necessary, so I've added Q (quit) to halt execution.

For reasons the author hasn't written down, Picofuck is Turing-Complete, but it's not hard to imagine a potential construction with the increased flexibility of this language.

Compiling from Bitwise Cyclic Tag

\01ḊȧḞƛ‡∷¥£Ṫẋ

Bitwise Cyclic Tag is a minimalist Turing-Complete tag-system-based language. It operates on a string of bits, and has two instructions:

  • 0 deletes the leftmost bit
  • 1x (where x is 1 or 0) appends x if the leftmost bit is 1.

The program is made of a sequence of bits, and loops forever.

These instructions can be quite easily mapped to Vyxal, however we're running out of ways to concatenate/append. Fortunately, Ḋȧ does the trick - concatenating with a space in between and removing the space.

We also don't have many ways left to get the first/last item of a string, but we can cast to an integer and take it modulo 2.

With this, it's fairly simple to translate BCT to Vyxal:

  • 0 becomes
  • 1x becomes :⌊∷\xẋḊȧ

Additionally, we need a looping construct. There aren't many left, so I've decided to use 0‡∷∷Ḟƛ. ‡∷∷ is a function that modulos its input by 2 twice (could be anything really), then uses that combined with the 0 to generate an infinite list of values, which ƛ can then iterate over.

Unlike some of the previous looping constructs, this doesn't maintain state between calls, so we need to use the register. £ and ¥ respectively set and retrieve the register, a global variable initialised at 0. We can also use £¥¥ to replace duplication (:).

The data-string also needs to be initialised. This can be done by repeatedly prepending characters using Ḋȧ, and then storing this in the register.

Here's a compiler from BCT to this subset of Vyxal. And here's the example Collatz Sequence program from the esolangs page.

Although this doesn't halt per se, due to how Vyxal handles printing lists it outputs the state of the data string every cycle - i.e. each time the whole program is iterated through. Since, once again, the transformation of the data string from one cycle to another is completely deterministic, we can define "halting behaviour" as entering an infinite loop. Again, it's still possible to create programs that loop forever by this definition as long as they don't end up in a loop with the same state.

Blindfolded Arithmetic

2ʁṘ⅛≬ḭ'¼¦ɖ*-aNßX:^}

I stole this idea from ais523's answer, and I'd recommend reading the Blindfolded Arithmetic section on that as its explanation is far better than mine.

Blindfolded Arithmetic is a language with six variables, although only two are needed for Turing-Completeness. The variables are named X and Y, and start at 1 and 0 respectively. Each operation performs some arithmetic operation on two variables and stores the result into another variable. The operations are cyclically repeated until a division by 0 occurs.

As ais discovered, (almost) all of the possible operations can be emulated on an array of [X, Y]. Here's the direct translations of the operations:

Y = X + Y: ¦
Y = X * Y: ɖ*
Y = X - Y: ɖ-
Y = Y - X: ɖ-2ʁ2*2Ṙ2ḭ-Ṙ*
Y = X // Y: :2ʁ*a2:ḭ-2:ḭ2-*:ßX-ɖḭ
Y = Y // X: :2ʁṘ*a2:ḭ-2:ḭ2-*:ßX-::Ṙḭ2ʁ*^2ʁ2Ṙ2ḭ-*-

Swap Y, X: Ṙ
Y = Y + Y = Y * 2: 2ʁ2:ḭ2--*
Y = Y // 2: 2ʁ2:ḭ2--ḭ

Here's all the operators working.

Here ɖ is the scan operator. When given a list [x, y, z, ...] and a binary operation *, it computes [x, x * y, x * y * z ...] which is very useful for these purposes. is the floor division operator, and * and - do what you'd expect.

Only operations assigning to Y are implemented here because we can use Ṙ, reverse, to swap X and Y.

While Jelly has the quick @, which inverts the order of an element's arguments, Vyxal does not, so inverse subtraction/division is decidedly more complicated. Here's the subtraction one explained:

ɖ-            # Y = X - Y
  2ʁ          # [0, 1]
    2*        # [0, 2]
      2Ṙ2ḭ    # 1
          -   # [0, 2] - 1 = [-1, 1]
           Ṙ  # [1, -1]
            * # Multiply by that (negate second element)

The division one is even more complicated. Because of this I've been forced to bring in two stack-manipulation operators: :, duplicate, and ^, which reverses the stack (essentially behaving like swap for our purposes)

:2ʁṘ*a2:ḭ-2:ḭ2-*:ßX- # Halt check (see below)
 :Ṙḭ                 # [X, Y] / [Y, X] = [X / Y, Y / X]
    2ʁ*              # [X / Y, Y / X] * [0, 1] = [0, Y / X]
        2ʁ           # [0, 1]
          2Ṙ2ḭ-      # [0, 1] - 1 = [-1, 0]
:      ^       *     # [X, Y] * [-1, 0] = [-X, 0]
                -    # [0, Y / X] - [-X, 0] = [X, Y / X]

Here we can't use + because that's already taken. Double negation is fine though.

We can also generate the list [1, 2] with 2ʁ2:ḭ2--. By multiplying or dividing by this we can halve or double Y. As explained in ais's answer, this is sufficient for Turing-Completeness.

Now we need a looping construct. We can use to group the next three elements as a function, and combine this with '...} (filter by) to contain arbitrarily long code. By using the construct ≬ḭ'...2:-}a, we can filter the list [1] by our code, returning a 0 by default, unless the program is halted. Then, each iteration, the a will only return true if the program has halted.

We can then use a builtin like N (first natural number for which a function is true) to call this repeatedly until it halts.

We also need to store data between each cycle. This can be done by pushing/popping to/from the global array, /¼ respectively.

We also need to initialise [X, Y] as [1, 0], which can be done with 2ʁṘ⅛.

The one thing that remains is halting. We still have the element X available, which returns from a function. By using the modifier ß we can return a truthy value (and halt) if the dividend is 0.

We can do this fairly simply with :2ʁ*a2:ḭ-2:ḭ2-*:ßX*.

:2ʁ*                # [X, Y] * [0, 1] = [0, Y]
    a               # Any - 0 if Y=0
     2:ḭ-2:ḭ2-*     # Not ^ - 1 if Y=0
               :ßX  # If true return 1, halting
                  - # Else subtract 0 from whatever was on the stack, NOP

For Y = Y / X we multiply by [1, 0] instead of [0, 1], checking that X ≠ 0.

Subtracting a variable from itself, self-multiplication and self-division are also possible, although not necessary as shown by ais.

Here's an example compiled program.

Solution 12?

As far as I'm aware, I've used up every single listed looping construct. ¨@ can be used to define a named function, but that requires |, which would require completely rewriting one of the tag systems in a way which may not be possible.

There is always the sympy ACE, but using an older version of Vyxal feels questionable.

In older versions of Vyxal (I'm not sure when it was changed) it was possible to do a recursive call (x) within a mapping lambda / similar, allowing for an infinite loop. Again, though, downgrading Vyxal is questionable and may have some side effects on these solutions' functionality.

So, I'm going to say 11 is close to optimal, and certainly as far as I'm prepared to go with this.

\$\endgroup\$
1
  • 2
    \$\begingroup\$ 11 different ways of being Turing complete. I'm good at this language design stuff! \$\endgroup\$
    – lyxal
    Aug 22 at 11:19
3
\$\begingroup\$

Javascript, score 2

(x)=>

With this we can implement untyped lambda calculus (idea stolen from this answer)

x=xx=>xx // I
xx=x=>xx=>x // K
xxx=x=>xx=>xxx=>x(xxx)(x(xxx)) // S

Although we don't have newlines or spaces it's easy to do something like this:

(f=()=>f)(<definition>)(<definition>)(<definition>)

Where each <definition> is a statement.


Functioesap`${}%bdf0123456789

From this we can construct

Function`a${unescape`...`}```

Where the ... is URL-encoded text, in which each character is represented by a % followed by two hexadecimal digits. This allows the execution of arbitrary code. It's not necessary to use all the hex digits, as you could evaluate some other Turing-complete subset of JS, but whatever.

I seriously doubt a score of 3 is possible. Either function calls or some form of loop is required. Function calls require () or backticks, and loops require (). While there are ways to use proxies to allow function calls with [], those require function calls themselves.

\$\endgroup\$
2
\$\begingroup\$

Lua, 2

#load(').chr

The load function allows for arbitrary code execution. ('').char allows us to construct a string using charcodes. To get a charcode, all we need to do call char with a string of a certain length. For example, ('').char(#'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa') gets us a space.

_G[]"\0123456789

Again, allows for arbitrary code execution. Every global function, including load, is located within the _G table. We can use backslash followed by a number to get an arbitrary character (\32 gives us a space). _G["\108\111\97\100"] allows us to use load, and we can keep using the same trick to execute any code we want.

I don't believe it's possible to get higher than this, as most of the keywords involved in flow control use overlapping characters (for, do, end, then, goto, while, function, etc). I'd love to be proven wrong, though.

\$\endgroup\$
1
\$\begingroup\$

JavaScript, 2 subsets

Here are the subsets, one on each line:

x=>()
Function`${re \}.al

Both implement lambda calculus, which is Turing Complete, so I'll explain both.

The first subset allows you to (trivially) express any lambda calculus expression, so it is Turing Complete.

The second subset is possible because of tagged template literals, type coercion and template literal nesting. Here is the identity function on itself:

Function`F${`return F.call\`F\${F}\``}`.call`F${Function`F${`return F`}`}`
\$\endgroup\$
1
\$\begingroup\$

C, 2

longt=-/ ?:;

others

Body must be at least 30 characters; you entered 24.

\$\endgroup\$
3
  • 12
    \$\begingroup\$ Can you add an explanation why these two sets are Turing complete. \$\endgroup\$
    – bsoelch
    Aug 18 at 8:13
  • \$\begingroup\$ @bsoelch goto is counter machine other is also counter machine \$\endgroup\$
    – l4m2
    Aug 18 at 18:30
  • \$\begingroup\$ @wizzwizz4 Fixed \$\endgroup\$
    – l4m2
    Aug 20 at 0:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.