24
\$\begingroup\$

Summary

We already have a challenge for the minimal number of characters for Turing completeness. But what about the minimal maximum byte?

Challenge

For a language of your choice, find a subset of characters that allows your language to be Turing complete with the minimal maximum byte value.

Example

If your language is using the UTF8 code page and Turing complete using only the characters abcd(), these characters have the byte values 97, 98, 99, 100, 40, 41, and the maximum there is d = 100, so your score would be 100.

Scoring

Your score is the maximum byte value of your Turing complete subset, expressed in the code page of your language's interpreter. For most languages this will be either LATIN-1 or UTF8, but if your language uses a different code page (such as Jelly) use that to score instead.

In the unlikely event that you require multibyte characters to be Turing complete, just use the maximum byte in the multibyte sequence to score. For example, if your UTF8 language required Ȧ, this is encoded as the literal byte sequence 200, 166, so it would score 200.

The lowest score wins.

Notes

  • The minimum score is 0, the maximum is 255.
  • For some languages (cough) this challenge will be trivial to score low on. I urge you to upvote interesting answers over trivial ones.
  • Provide an explanation of why your subset is Turing complete.
  • Your subset only needs to be Turing complete, it does not need to be able to use every feature of the language.
\$\endgroup\$
4
  • 6
    \$\begingroup\$ It might sound like a trivial modification of the original challenge, but this is actually quite different, as answers are forced to try out approaches that exclude eval (v), exec (x), {}, and any other constructs using high bytes. \$\endgroup\$ – Bubbler Sep 9 '20 at 2:52
  • \$\begingroup\$ I wonder if the opposite - Maximum minimal byte - would work as a challenge \$\endgroup\$ – Dion Sep 10 '20 at 8:50
  • \$\begingroup\$ @Dion I thought about it - I think it is the less interesting version, since ( will be hard to avoid for most mainstream languages, but I wouldn't mind if you (or someone else) posted it. \$\endgroup\$ – Sisyphus Sep 10 '20 at 9:45
  • \$\begingroup\$ Thanks for making a code golfing challenge that for once isn't just golfing program length! I enjoyed this question greatly. \$\endgroup\$ – Dewi Morgan Oct 30 '20 at 15:12

21 Answers 21

18
\$\begingroup\$

Haskell, score 61 (=)

Characters used: !#$%&()=

The SKI combinator calculus can be implemented in Haskell with nothing but basic function definition, using !#%& as identifiers. Infix function application $ is used to save on parentheses and strip down one character from both S and fix. Finally, K only takes two arguments and can be more shortly defined as an infix operator.

S combinator: s x y z = x z (y z)

(!)(#)(%)(&)=(#)(&)$(%)(&)

K combinator: k x y = x

(!)#($)=(!)

fix combinator: fix f = f (fix f)

(&)(!)=(!)$(&)(!)

Since Haskell is a strongly typed language, the fixed-point combinator fix is needed in order to make (typed) combinatory logic Turing-complete.

The I combinator is not strictly required since it is extensionally equivalent to SKK, but it can be defined as (*)(!)=(!).

Try it online!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Welcome to the site, and impressive first answer! \$\endgroup\$ – ChartZ Belatedly Sep 9 '20 at 14:51
16
\$\begingroup\$

Python 2 with exit code, 102 (f)

def TM_SIM(TRANSITIONS, STATE, TAPE=[], HEAD_POS=0):
	TAPE += ["X"]
	HEAD_POS += HEAD_POS < 0

	SYMBOL = TAPE[HEAD_POS]
	STATE, NEW_SYMBOL, HEAD_DIRECTION = TRANSITIONS[(STATE, SYMBOL)]
		
	TAPE[HEAD_POS] = NEW_SYMBOL
	HEAD_POS += HEAD_DIRECTION
			
	STATE == "REJECT" < 1/0
	STATE != "ACCEPT" == TM_SIM(TRANSITIONS, STATE, TAPE, HEAD_POS)

Try it online!

This code limits itself to the keyword def for highest character f. The function definition is used for looping via recursion. Python's logical short-circuiting is used for control flow, avoiding the need for a keyword like if, and, or, or while. For example, the recursive call in STATE != "ACCEPT" == TM_SIM(...) does not happen if we're in the accept state -- because the first inequality already fails, Python moves on without evaluating further.

Because none of the usual output method work (print, return, exit, etc), we return via exit code by terminating with or without error. So, this code is limited to decision problems. In practice, large inputs will give a stack overflow ("maximum recursion depth exceeded").

The code shown is a function simulating an arbitrary Turing machine that's given as input, which is of course Turing complete. The TIO shows it tested with a Turing machine that checks palindromes.

We avoid all keywords except the def. Since the only characters bigger than lowercase in letters in byte value are {|}~, it was easy to do without them too. For clarity, the variables in the code have been given readable names, using uppercase since these are smaller than all lowercase letters. We could get rid of these and many other symbols, though this of course wouldn't affect the score.

\$\endgroup\$
12
\$\begingroup\$

C (gcc), score=61 (=)

$01234567;=

This abuses the linker by forming a machine language program that spans several scalar variables and avoids array characters such as []{}.

The following is an example of a "Hello, World!" "program" that should work on Linux and OSX for x86 and x86_64.

$=01672007152;$$=011000000000;$$$=015733066145;$$$$=015725620054;$$$$$=04131066162;$$$$$$=010060030412;$$$$$$$=02141007620;$$$$$$$$=013100000000;$$$$$$$$$=015224251132;$$$$$$$$$$=026024655401;$$$$$$$$$$$=020063250004;$$$$$$$$$$$$=030304142203;$$$$$$$$$$$$$=037777630536;$$$$$$$$$$$$$$=012625655307;$$$$$$$$$$$$$$$=01134122;$$$$$$$$$$$$$$$$=0503601000;$$$$$$$$$$$$$$$$$=06127257132;$$$$$$$$$$$$$$$$$$=01700330300;$$$$$$$$$$$$$$$$$$$=0141405;

Try it online!

\$\endgroup\$
4
  • \$\begingroup\$ I'm curious, why do you need up to 7? Could it be done with fewer digits? \$\endgroup\$ – Spitemaster Sep 9 '20 at 21:41
  • 1
    \$\begingroup\$ @Spitemaster I don't. Yes but it wouldn't change the score unless I got rid of the = \$\endgroup\$ – ceilingcat Sep 9 '20 at 21:58
  • 1
    \$\begingroup\$ You can make it a true full program by using this setup: Hello, World! in exactly 128 bytes of $01234567;=. Flags are -zexecstack -Wl,-e$ -nostartfiles, and only works in x86-64 Linux due to syscall numbers. \$\endgroup\$ – Bubbler Sep 10 '20 at 1:17
  • 1
    \$\begingroup\$ @Spitemaster If you insist, all the number literals can be constructed using just 1+. Yeah, that doesn't change the score here, but we just got a score 5 solution for the other challenge... \$\endgroup\$ – Bubbler Sep 10 '20 at 1:23
10
\$\begingroup\$

Whitespace, score = 32

Characters: \t\n (chrs 32 9 10)

The only legal chars in the language.

\$\endgroup\$
1
  • 4
    \$\begingroup\$ For those wondering, you can't get rid of space, since that immediately removes arithmetic and stack manipulation. For control flow, you can't create a label, so that's out too, and you can't even store anything on the heap... \$\endgroup\$ – Jo King Sep 9 '20 at 8:51
8
\$\begingroup\$

05AB1E, score: 86

+1 .VB

These characters have the codepoints [43,49,32,46,86,66] in the 05AB1E codepage, of which V=86 is the maximum.

My answer for the Fewest (distinct) characters for Turing Completeness challenge in 05AB1E which I posted just yet is: +X.VB. With these 5 bytes, X=88 would have been the maximum. We avoid the X by using 1 and a space instead. After that V=86 is the maximum.
With the remaining 6 bytes we can:

  • +: Pops the top two items on the stack, and adds them together
  • 1 : Push 1 to the stack
  • .V: Pops and evaluates the top string as 05AB1E code
  • B: Pops the top two items on the stack, and does base-conversion

I've tried to get rid of V, which would only be possible with .E (execute as Python code - exec). Now we're using .V to evaluate and execute as 05AB1E code, for which we can first create the entire strings with certain single-byte builtins like J (join), « (append), etc. But if we would use .E we can't do that anymore. A potential fix for this is switching from 05AB1E to 05AB1E (legacy). In the legacy version (which is built in Python) we can use + to concatenate characters, which isn't possible in the new version (which is built in Elixir). Unfortunately, the .E builtin is (evaluate as Python code - eval) in the legacy version, and .e is exec. With just eval we unfortunately can't do everything we want, like checking if the input is a prime number. (Maybe we can, but my Python knowledge is too limited for that. If someone knows a piece of Python 3 code which can be wrapped within eval("...") and will check if the input() is a prime number, lmk.) And the e in .e would be even higher than .V, so it's pointless to use that instead.

Try it online:

Here a few example programs using these six bytes:

Try it online: 2+2.
Try it online: Check if the input is a prime number.
Try it online: Print "Hello, World!".
Try it online: Print the infinite Fibonacci sequence.

\$\endgroup\$
1
  • 2
    \$\begingroup\$ You can implement untyped lambda calculus using Python eval, so it is TC (check out this answer) \$\endgroup\$ – ChartZ Belatedly Sep 9 '20 at 12:04
7
\$\begingroup\$

Lenguage, score = 1 ()



Lenguage only cares about the length of the file, so we can use any character (in this case U+0001).

Yes, I am aware that I can use null bytes, but I wanted to give a fair chance to other people, so I made it 1.

\$\endgroup\$
8
  • 5
    \$\begingroup\$ I think this would get a score of 0 since you can use null bytes. \$\endgroup\$ – Mukundan314 Sep 9 '20 at 15:25
  • 5
    \$\begingroup\$ @DewiMorgan Wouldn't it work the same if you're just checking the size of a file? Related SO question. \$\endgroup\$ – user Sep 9 '20 at 16:10
  • 4
    \$\begingroup\$ @DewiMorgan By reading the bytes and counting how many you read, duh. \$\endgroup\$ – user253751 Sep 9 '20 at 16:18
  • 1
    \$\begingroup\$ Because it is trivial. 1 downvote doesn't matter that much, though, and I upvoted. Also, it's impossible to have a score of 0 or 1 in other languages. (Unless it's also pattern-based, of course.) \$\endgroup\$ – null Sep 11 '20 at 4:40
  • 1
    \$\begingroup\$ @null It was meant to be a joke. (Thanks for the upvote) \$\endgroup\$ – user Sep 11 '20 at 13:04
7
\$\begingroup\$

PHP, Score = 82 (R).

Rationale:

Let's start at the end of the ASCII range, and work backwards until we find a character that's required for PHP.

PHP is case-sensitive only for user-defined things (variable names, constants), and is case-insensitive for all other things, so we can ignore the lowercase range.

Other than lowercase characters, the only characters above the uppercase range are:

  • 0x7f - unused.
  • ~ - used only for bitwise negation, unnecessary for Turing completeness.
  • { and } - used for blocks, but PHP has an "alternative syntax" for control structures that doesn't use characters above the uppercase range.
  • | - used for boolean OR (|, |=, etc), unnecessary for Turing completeness, and for logical OR (||, ||=, etc), which has an alternate text form OR.
  • ` - used only for external command execution, unnecessary for Turing completeness, and anyway there are alternatives (EXEC(), PASSTHRU(), SYSTEM(), etc)
  • _ - used in many library function names and all compile-time constants, but not used by any keywords, so, since methods can be called dynamically, we can call methods that contain underscores by replacing them with CHR(95).
  • ^ - used only for bitwise XOR, and in regexes, neither required for Turing completeness.
  • [ and ] - used for array indexing, which poses a problem, but array_pop and friends can be used instead.
  • \ is used for character escapes, unnecessary for Turing completeness, and escaped characters can be generated using CHR() and similar tricks anyway.

This means our max must lie in the uppercase characters.

We could trivially use eval() and chr() to evaluate any string of numbers as PHP code, which would give us a max character of V... but I think we can do better!

If we can do everything brainfsck can, then it'll be Turing complete, so let's write one. I'll replace the [ ] square braces of normal brainfsck with ( ) round braces, just so I can have the brainfsck program inline without using any high characters.

Proof of concept:

<?PHP
// Create function refs, for those which have characters too high.
$FILL = 'ARRA' . CHR(89) . CHR(95) . 'FILL'; // Array_fill to create the tape.
$CHOP = 'ARRA' . CHR(89) . CHR(95) . CHR(83) . 'LICE'; // Array_slice for array indexing.
$POP = 'ARRA' . CHR(89) . CHR(95) . CHR(83) . 'HIF' . CHR(84); // Array_shift for array indexing.
$DEPOP = 'ARRA' . CHR(89) . CHR(95) . CHR(83) . 'PLICE'; // Array_splice for array inserting.

$LEN = CHR(83) . CHR(84) . 'RLEN'; // Strlen
$LOP = CHR(83) . CHR(84) . 'R' . CHR(95) . CHR(83) . 'PLI' . CHR(84); // Str_split

// "Hello world!" - note using round braces instead of square in the brainfsck code.
$IN =  (">+++++++++(<++++++++>-)<.>+++++++(<++++>-)<+.+++++++..+++.>>>++++++++(<++++>-)<.>>>++++++++++(<+++++++++>-)<---.<<<<.+++.------.--------.>>+.>++++++++++.");
$INLEN = $LEN($IN);
$IN = $LOP($IN);

// Init tape with 10 zeros (add more for longer tape).
$A = $FILL(0,10,0);

// Set $AA ptr to first cell of tape.
$AA = 0;

FOR ($I = 0; $I < $INLEN; $I++):
    // Extract element: $CH = $IN[$I].
    $CH = $CHOP($IN, $I);
    $CH = $POP($CH);
    // Increment element at $I.
    //$CH++;
    //$CH = $FN($AA, $I, 1, $CH);
    
    // Only need one of '+' or '-' for TC if memory wraps.
    IF ($CH == '>'):
        $AA++;
    ENDIF;
    IF ($CH == '<'):
        $AA--;
    ENDIF;

    // Only one of '+' or '-' is critical for Turing completeness.
    IF ($CH == '+'):
        // Increment element: $A[$AA]++;
        $ID = $CHOP($A, $AA);
        $ID = $POP($ID);
        $ID++;
        $DEPOP($A, $AA, 1, $ID);
    ENDIF;
    IF ($CH == '-'):
        // Decrement element: $A[$AA]--;
        $ID = $CHOP($A, $AA);
        $ID = $POP($ID);
        $ID--;
        $DEPOP($A, $AA, 1, $ID);
    ENDIF;

    IF ($CH == ')'):
        $ID = $CHOP($A, $AA);
        $ID = $POP($ID);
        IF ($ID):
            FOR ($LOOP = 1; $LOOP > 0; ):
                $CH = $CHOP($IN, --$I);
                $CH = $POP($CH);
                IF ($CH == '('):
                    $LOOP--;
                ENDIF;
                IF ($CH == ')'):
                    $LOOP++;
                ENDIF;
            ENDFOR;
        ENDIF;
    ENDIF;

    // I/O is non-critical for TC.
    IF ($CH == '.' ):
        $ID = $CHOP($A, $AA);
        $ID = $POP($ID);
        ECHO CHR($ID);
    ENDIF;
ENDFOR;

Possible improvements:

I don't see a way to avoid using CHR() for array indexing without using something worse, like backslash, or string manipulation functions that use S.

And I don't see a way to avoid FOR() for looping back without using something worse like GOTO, WHILE, or the {} of a recursive function definition.

If we can get rid of those two keywords, the next highest is the P in <?PHP, which is required, at least in later versions of PHP that deprecate short open tags. However, they have made a commitment that the short echo tag, <?= will always be supported, so that could perhaps be exploited to execute arbitrary PHP. Then there are the O's in ECHO. However, I/O isn't critical for Turing completeness, so we could just remove that. Then there's the N in ENDIF, and the I and F in IF, which could be replaced by the ternary operator, ?:.

But even if there's a way to avoid using any keywords or library functions by name, variables must begin with an alphabetic or underscore character, so I suspect we'll definitely need at least A.

\$\endgroup\$
11
  • 1
    \$\begingroup\$ Welcome to the site, and nice first answer! \$\endgroup\$ – ChartZ Belatedly Sep 9 '20 at 19:53
  • \$\begingroup\$ @cairdcoinheringaahing Ooh, code tag! I learned a thing, thank you! I guess I'll need to make a non-lazy answer now... :( \$\endgroup\$ – Dewi Morgan Sep 9 '20 at 22:03
  • \$\begingroup\$ @cairdcoinheringaahing Yeah, my answer also had bugs, so I've edited to give a working brainfsck parser to prove we can do R :D \$\endgroup\$ – Dewi Morgan Sep 10 '20 at 0:23
  • \$\begingroup\$ You're mispelling brainfuck \$\endgroup\$ – Jo King Sep 10 '20 at 0:33
  • 2
    \$\begingroup\$ @JoKing Deliberately so. It's a misspelling with enough history behind it, that it's become an accepted alternate. So, for example, you'll see that Wikipedia redirects it correctly. \$\endgroup\$ – Dewi Morgan Sep 10 '20 at 3:15
5
\$\begingroup\$

Haskell, score 95 (_) 92 (\)

i = (\_A -> _A)
k = (\_A -> \_AA -> _A)
s = (\_A -> \_AA -> \_AAA -> (_A _AAA)(_AA _AAA))
i = (\(!) -> (!))
k = (\(!) -> \(!!) -> (!))
s = (\(!) -> \(!!) -> \(!!!) -> ((!) (!!!))((!!) (!!!)))

Untyped lambda calculus. Annoying that Haskell can't have uppercase variable names, oh well.

-3 thanks to xnor

Try it online!

\$\endgroup\$
2
  • 4
    \$\begingroup\$ You can actually use operators as variable names, like (!) \$\endgroup\$ – xnor Sep 9 '20 at 11:29
  • \$\begingroup\$ Ah yeah, clever @xnor thanks again \$\endgroup\$ – rak1507 Sep 9 '20 at 11:35
4
\$\begingroup\$

Python 3, score 109 (m)

lambd :()

Check the score online!

We can implement untyped lambda calculus using just these chars:

I = lambda a:a
K = lambda a:lambda b:a
S = lambda a:lambda b:lambda d:a(d)(b(d))

With the known bound of m, we can't use any of exec, eval, import, for, while, yield. def is still available, but I doubt it will improve the score because I think making it Turing-complete necessitates the use of return.

\$\endgroup\$
4
  • \$\begingroup\$ Is there a reason you have to use lambda instead of def? \$\endgroup\$ – water_ghosts Sep 9 '20 at 7:17
  • 5
    \$\begingroup\$ @water_ghosts "I think making it Turing-complete necessitates the use of return." e.g. def a:a is not a valid implementation of I; it should be def a:return a. \$\endgroup\$ – Bubbler Sep 9 '20 at 7:18
  • 1
    \$\begingroup\$ (well for completeness, def f(d):return d: def a:return a isn't syntactically valid) \$\endgroup\$ – boboquack Sep 9 '20 at 11:33
  • \$\begingroup\$ @boboquack Right, somehow I messed up between lambda and def syntaxes. \$\endgroup\$ – Bubbler Sep 10 '20 at 3:56
4
\$\begingroup\$

JavaScript (Node.js), score 62 (>)

$=>()

Check the score online!

Untyped lambda calculus again.

I = $=>$
K = $=>$$=>$
S = $=>$$=>$$$=>$($$$)($$($$$))

I think this is optimal, because all built-ins and keywords are banned now.

\$\endgroup\$
4
\$\begingroup\$

J, score 94 (^)

 "#%()*+.0123456789:<=]^

Check the score online!

The winning J answer for least unique chars uses u: (convert charcodes to chars) to construct arbitrary string from integers. I decided to avoid u and find a more proper way for TC-ness.

Assuming ^:_ (repeat until converges) is hard to avoid, I decided to build a translation from FRACTRAN, as it looked easy enough to translate to (number_manipulation)^:_(starting_num).

A FRACTRAN program is defined as a sequence of fractions, and it runs like this: given a program 5/3 3/2 and some starting number n,

  • If n is divisible by 3, multiply n by 5/3.
  • Otherwise, if n is divisible by 2, multiply n by 3/2.
  • (The "otherwise" chain continues for longer programs)
  • If n did not change in this iteration, halt. Otherwise, move to the start of the program and continue with the updated value of n.

The if-then-else constructs can be translated to arithmetic:

If a then b else c = (a>0) * b + (a==0) * c
J: (b*(0<a))+c*0=a

The if-part says "n is divisible by a constant m". One would normally use the modulo function | for this, but it's way too high in ASCII, so I devised a way to simulate modulo using base conversion:

n modulo m = convert n into base m, interpret as base 0 and get an integer back
J: 0#.0 m#:n

The then- and else-parts are easy, because they can be simulated using multiply *, divide %, and self ].

So the translation of two-fraction FRACTRAN program 5/3 3/2 looks like this:

(((]%3"0)*5*0=0#.0 3#:])+((((]%2"0)*3*0=0#.0 2#:])+(]*0<0#.0 2#:]))*0<0#.0 3#:]))^:(%0)(starting_value)

I later changed the _ (infinity literal) to (%0) (reciprocal of zero), getting rid of _. Since I can't avoid ^: itself, the score of ^ is optimal in this approach.

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

Wolfram Language (Mathematica), score 62 (>)

#$&()-./>

Using these characters we can implement the SKI combinators:

i = #&
k = $&/.$->#&
s = (#//$$//(#//$))&/.$$->#&/.$->#&

Try it online!

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

Dreaderef (-1 flag), score 42 (*)

Dreaderef is a ZISC; the program is a description of the initial tape contents. Dreaderef programs are typically written with an assembly-like syntax that is then run through a preprocessor to produce a list of integers, but quotes (") can also be used to embed arbitrary data in the form of ASCII values.

The only restrictions on the contents of string literals are that:

  • They can't contain newlines.
  • For our purposes, they can't contain numbers greater than 42.
  • They can't contain negative numbers.

The first two aren't a problem, but the third is. Dreaderef's only arithmetic operators are addition and multiplication, so we have no way to obtain negative numbers without including them when initializing. Additionally, the instruction pointer is stored in cell -1, and without accessing it we have no way to do control flow. Thus to achieve Turing-completeness we need to include the * byte (which is replaced with an integer from the command-line arguments at initialization time) and stipulate that the user always pass -1 as an argument.

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

Keg, Score = 58

Characters:

0+-*/():

Simply the standard subset of TC chars

\$\endgroup\$
2
  • \$\begingroup\$ Also known as Deterministic Volatile \$\endgroup\$ – null Sep 9 '20 at 13:49
  • 1
    \$\begingroup\$ @downvoter why the down vote? \$\endgroup\$ – Lyxal Sep 10 '20 at 20:50
2
\$\begingroup\$

Unary, score = 48 (0)

Unary only cares about number of 0 in the file.

Inspired by the Lenguage answer

\$\endgroup\$
2
  • 2
    \$\begingroup\$ You could have said "score = '0' (48)` just to mislead people \$\endgroup\$ – user Sep 9 '20 at 16:13
  • \$\begingroup\$ Many unary interpreters only care about the length, so you can reduce this to a null byte. \$\endgroup\$ – pppery Sep 17 '20 at 21:15
2
\$\begingroup\$

C (gcc), score: 110 (n)

<space>!"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmn

Because of the trigraphs:

??= #
??( [
??/ \
??) ]
??' ^
??< {
??! |
??> }
??- ~ 

and the main function has to be defined so, no matter what, n has to be used. The ubiquitous semicolon (;) is there. And return is easily avoided through use of assignment (=) since gcc will return the last value assigned of the same type as the function return value. Type int is inferred by default for any variable or function definition.

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

Julia, Score 63 (?)

we can actually get away with no letters, by abusing the fact that === is assignable for some reason. however, without a way to index or create arrays, this is not enough. What gets us closer is tuple unpacking. this allows us to create a sort of "stack" with our one variable. (===) = (2,(===)) (===) = (3,(===)) one problem is that we need another variable to unpack the argument into. luckily \ is also assignable, so we can use that as a "register" (\,===) = (===) we can then perform some operation on these values and store the result (===) = (7+\==10,===)

(\,===) = (===) we can conditionaly execute code (and drop some parenthesies) ====(\ ? 1 : 0,===)

we can reuse names via shadowing, but this comes at the cost of recursion \ = (\) -> (\) + 3

fortunately, there's another assignable value ^ = (\) -> (\) < 2 ? (\) : ^((\)-1) + ^((\)-2)

functions can go on the stack ====(^,===)

we also have NAND logic via && and ! (curried)
^ = (^) -> (/) -> !((^)&&(/))

the biggest problem is I/O, as we can't call any Core or Base functions like print, but luckily we can use the -E flag or the REPL to print the result

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

Brainfuck, Score = 93 (]).

>   Move the pointer to the right.
<   Move the pointer to the left.
+   Increment the memory cell at the pointer.
-   Decrement the memory cell at the pointer.
.   Output the character signified by the cell at the pointer.
,   Input a character and store it in the cell at the pointer.
[   Jump past the matching ] if the cell at the pointer is 0.
]   Jump back to the matching [ if the cell at the pointer is nonzero. 

I/O is not required for Turing completeness, so . and , are optional: a canonical Turing machine leaves its calculated answer on the tape. However, I believe all other commands are required, so the highest codepoint the language uses, ], is required.

There are a number of trivially-similar languages. I'll cover these here as well, unless people feel they are genuinely worthy of separate answers. I have assumed for each language that their commands are case-sensitive unless otherwise stated.

You only need one of the two BF instructions - and + for Turing completeness. And if the tape/memory is limited and wraps around, then we only require one of < and >, too. I've updated the below lists to take these into account.

Identical to BF for our purposes:

ASCII art-, Score = 93 (]).

BFFB, Score = 93 (]) Requires code be a palindrome but uses the same characters as BF.

LolKek, Score = 93 (]).

Pi, Score = 93 (]).

ReverseFuck, Score = 93 (]).

RRF, Score = 93 (]).

BF-, Score = 93 (]).

.

TrivialBrainfuckSubstitutions:

???, Score = 59 (;) 45 (-) Not quite a trivial substitution, but close enough. Omitted ?, ; and . as unnecessary for TC.

Alphuck!, Score = 115 (s).

And then, Score = 122 (z from required preamble).

Anguish, Score = 98 (U+2062) 97 (U+2061). Omitted U+2062 as unnecessary for TC.

ASCII art, Score = 124 (|).

Blub, Score = 117 (u from Blub? Blub!).

BrainFNORD, Score = 115 (s in eris) 112 (p in pineal). Omitted eris and fnord as unnecessary for TC.

btjzxgquartfrqifjlv , Score = 90 (Z of ZXG).

Colonoscopy, Score = 123 (} of }}).

Fluffle Puff, Score = 116 (t) 115 (s of *gasp*).

FuckbeEs, Score = 115 (s).

Fuckfuck, Score = 116 (t of b..t).

GERMAN, Score = 85 (U of ADDITION or SUBTRAKTION).

Headsecks, Score = 7 (U+07).

Integral, Score = 120 (x of the polynomial expressions).

LMBC, Score = 125 (} of n\n\\n\>\<" }*/ continue;).

Morsefuck, Score = 46 (.).

Omam, Score = 46 (y of this ship will carry).

Oof, Score = 111 (o of oooooof).

Ook!, Score = 107 (k of Ook? Ook!).

oOo CODE, Score = 111 (o of OOo).

Pikalang, Score = 117 (u from chu).

POGAACK, Score = 112 (p from poock?).

PPAP++, Score = 86 (V from I HAVE AN APPLE, or I HAVE PINEAPPLE,).

Revolution 9, Score = 121 (y from if you become naked) 118 (v from Revolution 1).

RISBF, Score = 47 (/ of /+)

Roadrunner, Score = 112 (p from MEEp).

Ternary, Score = 50 (2 from 02).

There Once was a Fish Named Fred, Score = 119 (w from was) 114 (r from Fred).

tinyBF, Score = 124 (|).

Unibrain, Score = 48 (0, needs at least 1 alphanumeric).

VerboseFuck, Score = 125 (} of }; [... etc]).

wepmlrio, Score = 119 (w).

Wordfuck, Score = 32 ( space) or 33 (!) depends if chars < 32 are considered words.

ZZZ, Score = 122 (z from z-z).

.

Turing tarpits:

Braincrash, Score = 33 (!).

Placement, Score = 63 (?).

.

Binary:

Binaryfuck, Score = 255 (U+FF) or better???

Brainfoctal, Score = 255 (U+FF) or better???

CompressedFuck, Score = 255 (U+FF) or better???

ShaFuck, Score = 255 (U+FF) or better???

Triplet, Score = 255 (U+FF) or better???

ZeroBF, Score = 255 (U+FF) or better???

Now, arguably, the score could be 49 (1), or 1 (U+01), or 255 (U+FF), or whatever. I pick 255.

These each replace the 8 BF command characters with their 3-bit binary equivalents, to give an octal number from 0 to 8. This converts the program to a binary stream of ones and zeroes, which can be represented as ASCII 1 and 0 characters, or as byte values, or as bit values, or as any base you like, hence the three possible scores.

The reason for my score of 255 for the bit-values version of binary BF programs is that ] typically maps to 111, so three of them in a row gives you a byte of all 1s, or 255.

It could be argued that you COULD write a Turing machine in these languages which never used three ] commands in a row. So my score may be less generous than it need be. You can prove this, if you like! :D Until then, I'm scoring them 255.

Well, in the case of ShaFuck, it's more complicated, but still... I don't have proof that it doesn't require a 0xFF byte somewhere, so I'm giving it a score of 255 until proven otherwise.

Golunar, Score = 59 (9) or better???

So this is an interesting one. It takes a Unary program (well, any of the above "single character" solutions, and converts it to a decimal string. In this way it is much like the other "binary" options, except it's explicitly stated to be a decimal number, one presumes in ascii.

That means that, if it could be proven that any program (or at least a Turing machine program) could be written in Unary that had a length that was describable without any 9s, the score would be able to drop, perhaps even as low as 49 (1).

Replacement by sequences of a single character:

A, Score = 65 (A).

Ecstatic, Score = 33 (!).

Ellipsis, Score = 46 (.) or 38 (U+2026 ellipsis).

Lenguage, Score = 0 (U+00).

MGIFOS, Score = 42 (*).

Unary, Score = 48 (0) or 0 (U+00).

These are really just the binary options above, taken as a number that describes the length of a string made by repeating a single character.

Other weird stuff:

BF-RLE, Score = 93 (]) to 247 (U+F7BFBFBF).

Run-length encoded BF. There are various methods. Base-10 prefix or suffix methods, or indeed any standard base up to 36 gets the same score as regular BF (because ] is above the uppercase range). Base 37 then typically uses the lowercase range, for a score of 97, and each additional base up to base 62 gets one worse. Bases above 62 need additional non-alphanumeric characters, but these can be selected from those below the lowercase range until those run out at base 114 (assuming 8 characters remain reserved for the BF code itself), and they then get worse by one for each base increase to base-128. After that point, UTF-8 can be used to slow the rise of the limit so that it never hits 255 for any base within the limit for UTF-8's ability to represent (some 4 million).

I dunno:

K-on Fuck

( ͡° ͜ʖ ͡°)fuck

These use extended characters I can't be arsed to look up.

\$\endgroup\$
1
  • \$\begingroup\$ For "Poetic" (I dunno which category this falls under) the minimum maximum codepoint is 65 (or A), because it encodes brainfuck instructions as sequences of letters delimited by non-letters, and A is the first letter. mcaweb.matc.edu/winslojr/vicom128/final \$\endgroup\$ – JosiahRyanW Nov 2 '20 at 6:01
1
\$\begingroup\$

Java, score: 117 (u)

0123456789ABCDEF\u

In Java, there are a few ways to create a full program:

// Regular class with main method (Java 1+):
class M{public static void main(String[]a){/*CODE GOES HERE*/}}

// Interface with main method, where we can remove public (Java 8+):
interface M{static void main(String[]a){/*CODE GOES HERE*/}}

// Exploiting a bug with enum (Java 5 or 6):
enum M{A;{/*CODE GOES HERE*/}}

// Creating a Java AWT GUI application with Applet:
class M extends java.applet.Applet{public void paint(java.awt.Graphics x){/*CODE GOES HERE*/}}

// Creating a JavaFX GUI application with Application:
class M extends javafx.application.Application{public void start(Stage stage){/*CODE GOES HERE*/}}

// Any of the above, but with \uHEXA escaped characters - i.e. here is the interface (excluding the comment within the main-method):
\u0069\u006E\u0074\u0065\u0072\u0066\u0061\u0063\u0065\u0020\u004D\u007B\u0073\u0074\u0061\u0074\u0069\u0063\u0020\u0076\u006F\u0069\u0064\u0020\u006D\u0061\u0069\u006E\u0028\u0053\u0074\u0072\u0069\u006E\u0067\u005B\u005D\u0061\u0029\u007B\u007D\u007D

Since all of them contain } (125), except for the last one with unicode escapes where u (117) is the maximum, that is our best score available in Java.

Try it online:

Here a few example programs using these eighteen bytes:

Try it online: 2+2.
Try it online: Check if the program argument is a prime number.
Try it online: Print "Hello, World!".

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

Batch, score = 84 (T)

Batch is mostly case insensitive, so we don't need any lowercase letters. We need T in SET in order to be able to do any arithmetic. It also conveniently gives us GOTO, which makes arbitrary looping easier. What we don't get:

  • U - PAUSE (can use SET/P to a similar effect); PUSHD (can use CD and %CD% to a similar effect)
  • X - EXIT (can still GOTO :EOF but that doesn't set the error level)
  • Y - TYPE (can still use MORE for small files)
  • ^ - Quote single character (can still wrap most special characters in double quotes)
  • | - bitwise OR (can be emulated using A+B-(A&B)); logical OR (can be emulated using && and GOTO)
  • ~ - bitwise NOT (can be emulated using -1-X); string slicing (not needed for arithmetic); parameter expansion (e.g. extracting the extension or size of a file), which needs lowercase letters anyway.
  • Any executables whose names include the letters U..Z.
\$\endgroup\$
2
  • \$\begingroup\$ Well, %OS:~-1% contains a ~... \$\endgroup\$ – Bubbler Sep 10 '20 at 22:59
  • \$\begingroup\$ @Bubbler Ugh, I'd completely overlooked that. I can't use %OS:*N=% as that only deletes Win and I can't use %OS:*_N=% as that uses _, so it looks as if my bright idea to avoid T was to no avail. \$\endgroup\$ – Neil Sep 10 '20 at 23:09
0
\$\begingroup\$

perl -MAcme::Bleach, score = 32

Acme::Bleach takes a program encoded using white space, and runs it after decoding.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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