34
\$\begingroup\$

Challenge

Write \$2 \le n \le 10\$ distinct, valid non-halting full programs in your language of choice. If all of them are concatenated in order, the resulting full program should be a valid halting program, but if any of them are left out, the result should still be a valid non-halting program.

More formally, write \$2 \le n \le 10\$ distinct programs \$P_1, P_2, \cdots, P_n\$ in a language \$L\$ of your choice, which satisfy the following property:

  • \$P_1 P_2 \cdots P_n\$ (where \$XY\$ means string concatenation of two programs \$X\$ and \$Y\$) is valid full program in \$L\$ and, given no input, halts in finite time.
  • If you delete any of \$1 \le x \le n-1 \$ program segments (\$P_i\$'s where \$1 \le i \le n\$) from the above, the result is still a valid full program in \$L\$, but does not halt in finite time.
    • In other words, any nonempty proper subsequence of \$P_1 P_2 \cdots P_n\$ should be a valid non-terminating program in \$L\$.

A program is valid if a compiler can successfully produce an executable or an interpreter finishes any pre-execution check (syntax parser, type checker, and any others if present) without error. A valid program is halting if the execution finishes for any reason, including normally (end of program, halt command) or abnormally (any kind of runtime error, including out-of-memory and stack overflow). The output produced by any of the programs does not matter in this challenge.

For example, a three-segment submission foo, bar, and baz is valid if

  • foobarbaz halts in finite time, and
  • each of foo, bar, baz, foobar, foobaz, and barbaz does not halt in finite time in the same language. (The behavior of barfoo or bazbar does not matter, since the segments are not in order.)

The score of your submission is the number \$n\$ (the number of program segments). The higher score wins, tiebreaker being code golf (lower number of bytes wins for the same score). It is encouraged to find a general solution that works beyond \$n = 10\$, and to find a solution that does not read its own source code (though it is allowed).

\$\endgroup\$
8
  • \$\begingroup\$ What if it halts because the interpreter times out? \$\endgroup\$
    – emanresu A
    Jun 2 at 0:51
  • 1
    \$\begingroup\$ @Ausername If the interpreter itself stops running after certain amount of time, then every program is halting by definition, and you cannot use it for this challenge. TIO timeout is a different thing, and it should be ignored (if a program would run forever assuming TIO timeout wasn't there, it is a valid non-halting program). \$\endgroup\$
    – Bubbler
    Jun 2 at 0:56
  • 1
    \$\begingroup\$ @Jonah If the program terminates in the view of the OS (i.e. the exit code is returned in finite time), I see it as halting. \$\endgroup\$
    – Bubbler
    Jun 2 at 4:11
  • 4
    \$\begingroup\$ Why do the programs have to be distinct? I'm not complaining just curious as to the rationale. \$\endgroup\$
    – Wheat Wizard
    Jun 2 at 10:09
  • 1
    \$\begingroup\$ It just occurred to me that it's impossible to do this in a concatenative language, because if P1 + ... + P(n-1) diverges then the concatenation of that with P(n) necessarily also diverges. \$\endgroup\$
    – kaya3
    Jun 3 at 11:02

29 Answers 29

26
\$\begingroup\$

JavaScript (Node.js), 10 programs, 299 bytes

(A=_=>setTimeout(A,B=_=>0))();
(B=_=>setTimeout(B,C=_=>0))();
(C=_=>setTimeout(C,D=_=>0))();
(D=_=>setTimeout(D,E=_=>0))();
(E=_=>setTimeout(E,F=_=>0))();
(F=_=>setTimeout(F,G=_=>0))();
(G=_=>setTimeout(G,H=_=>0))();
(H=_=>setTimeout(H,I=_=>0))();
(I=_=>setTimeout(I,J=_=>0))();
(J=_=>setTimeout(J,A=_=>0))()

Line breaks are added for readability. They are not a part of any programs.

Node.js will keep running if there is any timers been scheduled, and halt as soon as timer callback queue is cleared.

The order of these programs does not matter. After append an extra ; to the last one, you may shuffle them and it still meets the requirement of this challenge. It halts as long as you collected all 10 programs, and never halts if anyone is missing. You may also duplicate some programs here, and it works same as the program appears only once. :)

\$\endgroup\$
5
  • \$\begingroup\$ Whoa, how does it even work?! \$\endgroup\$
    – Bubbler
    Jun 2 at 1:53
  • \$\begingroup\$ @Bubbler Node.js will keep running if any timer is on the fly, and halt if timer callback queue is cleared. \$\endgroup\$
    – tsh
    Jun 2 at 2:02
  • \$\begingroup\$ This is ingenious. \$\endgroup\$
    – emanresu A
    Jun 2 at 2:04
  • \$\begingroup\$ is there a way, in javascript, to generate the script to be executed? if so, as your script has lots of redundancy, it could be shortened a lot ? (in a nutshell: generate lines A-J, execute generated code). edit: nevermind, the OP asks for 10 disctinct programs. But then : maybe have 1 program accepting 2 parameters, and the 10 distinct programs all call that one with 2 different parameter pairs? [not sure if it would fit the criteria] \$\endgroup\$ Jun 2 at 10:32
  • 1
    \$\begingroup\$ @OlivierDulac no it would not, it would mean it would have to depend on other code... \$\endgroup\$
    – ASCII-only
    Jun 2 at 12:08
20
\$\begingroup\$

Zsh, 56 bytes, 10 programs

until wc<<Q|grep 36
yes
yes;yes yes	yes yes ;yes
yes	yes

Try it online!

The first and most important program is:

until wc<<Q|grep 36

Each yes is part of one of the other programs.

y it online! (note: TIO kills the program very quickly because yes produces over 128 KB of output, but if you ran it elsewhere it would never halt)

Tre!

Explanation

  • <<Q: heredoc; takes the rest of the script starting from the next line, as a string
  • wc: output line, word, and character numbers
  • |grep 36: and search for the string 36 in that output
  • until : repeat this command until it succeeds

If all 10 programs are present, then there will be exactly 36 characters in the output of wc and the grep will succeed, so the loop will halt.

If the first program is removed, the remainder of the script will be interpreted as code instead of as a string in the heredoc, and yes will never halt.

All the weird whitespace around each yes is to make them all distinct and remain as short as possible (mostly 4 bytes).

If any of the yes programs is removed, there won't be a 36 in the output so the until will loop forever.

Notes

  • yes is intended to output y indefinitely so it can be piped into an interactive program that asks yes-or-no questions, but in this case it doesn't matter what it outputs

  • <<Q actually only outputs the contents until the first line containing only Q, but there is no such line, so it just goes until the end of the file

  • The exact splitting of the program is as follows; a # is used to separate each one here

until wc<<Q|grep 36
#yes

#yes;#yes #yes  #yes# yes# ;yes#
yes#    yes

Notice all the quirky whitespace, and there's a tab in there somewhere.

One of the programs is ;yes; it could just be ;yes with no space, except in the case the only remaining programs are yes;;yes: zsh would throw a syntax error because ;; is treated as one token instead of two semicolon command separators.


Zsh, 107 bytes, 10 programs

while 1=u
while 1+=i
while 1+=l
while 1+=t
while 1+=in
while 2=e
while 2+=x
while 2+=i
while 2+=t
until b$@

Try it online!

Try it onlin

Tryine!

nline!

Each line is a program.

Explanation

The idea is to use an infinite loop (well, 10 nested infinite loops), but, over the course of the 10 programs, construct and execute a string that will exit the loops.

If any program is removed, the string will no longer be a snippet that correctly exits, and the program will continue to loop.

The code to halt is built up by 1=u 1+=i etc. The string uiltin is stored in $1, and exit is stored in $2. Then, $@ represents all the assigned numeric variables; a b is prepended to those to make builtin exit, which is executed and halts the program.

Notes

  • All the loops have no body - the code is entirely in the condition. Zsh seems not to care, though.

  • The challenge states:

A program is valid if [...] an interpreter finishes any pre-execution check (syntax parser, type checker, and any others if present) without error.

Despite producing lots of errors, the program(s) meet these criteria because they only occur at runtime. (that kind of comes with the territory when golfing in zsh)

  • The b is prepended at execution instead of being made part of the string build-up, because it prevents the program where only 2 gets assigned to from halting - it will always result in bexit instead of exit (this is essentially a problem of irreducibility). There are also some substrings of uiltin exit that might be valid commands, which could end the until loop, but none exist once a b is prepended.

  • builtin is a pre-command modifier that disambiguates in case exit is a user-defined function, but in this case it serves only to get us to 10 programs of which none can be removed.

  • in is appended in one go instead of i and n separately because the 10 programs must be distinct, and 1+=i is already used.

  • For the first assignments to 1 and 2, we can use = instead of += to save a byte.

\$\endgroup\$
0
14
\$\begingroup\$

Befunge-93, 25 22 bytes (10 programs)

12+3+4+5+6+7+8+"#"`#@_

Try it online!

Thanks JoKing for the suggestion (-3 bytes).

Exaplanation

The programs are:

1     Push 1
2     Push 2, pop two value and push the sum
+     Pop two value and push the sum
3+    Push 3, pop two value and push the sum
4+    Same with 4
5+    ...
6+
7+
8+
"#"`#@_    Last program, it will halt if the stack has a number >35 in it:
           "-"        Push 35
           `          Pop two value, compare, push 1 if greater than 35
           #          Skip the next char (v)
           @          End program
           _          Pop one value, go left if 1, right otherwise

The first 9 programs cannot halt, because there is no halt instruction.
The last program takes a number from the stack, and compares it to 35: if it is greater than 35 (the sum is 36), then will halt the program; otherwise, it will let the PC run right, which will repeat the program and loop forever.

Removing any combination of program 1 to 9 will make the sum to be less than 36, so the program will never halt (comparison will always fail).

In theory, it can be extended by adding more number, and changing the value of the comparison in the last program (depending on the size available in your Befunge implementation).


Befunge-93, 63 73 bytes (10 programs)

 v
v>v
v >v
v  >v
v   >v
v    >v
v     >v
v      >v
v       >v
v       v@

Try it online!

Thanks NickKennedy for the fix.

Explanation

Each line is a program.

The first 9 lines (i.e. programs) are redirecting the PC down. Since there is no end of program instruction, they will loop forever.

The 10th line is redirecting the PC down, followed by an halt program (@) instruction. If this is executed alone, the PC will loop in the vertical direction forever.

When all together, the PC will be able to get to the @ and halt the program.

Removing any one line will break the flow and will leave the PC loop forever vertically.

It can actually be expanded to 25 programs (which is the limit of the 80x25 code size of the befunge) by just adding more v >v lines with the appropriate indentation.

If you use an implementation of befunge without the 80x25 limit, then it can be exdended indefinitely.

\$\endgroup\$
6
  • 1
    \$\begingroup\$ Does this work? tio.run/##S0pNK81LT/3/X6GMq8wOiBXABJSEUXAawUBiITPLHP7/BwA \$\endgroup\$ Jun 2 at 21:18
  • \$\begingroup\$ Actually @DLosc’s suggestion seems to work and doesn’t cost bytes \$\endgroup\$ Jun 2 at 21:20
  • \$\begingroup\$ When thinking about it, I have totally forgotten the removal of the first line (facepalm). I think the idea from @NickKennedy is closer to what I initially wanted to achieve, so I'll follow it. \$\endgroup\$
    – Redy000
    Jun 2 at 22:13
  • 1
    \$\begingroup\$ could the last program be ","`#@_ instead? With that you could also start splitting some of the other programs up into one byte each, as long as it isn't possible to exceed some constant that you're comparing to \$\endgroup\$
    – Jo King
    Jun 4 at 6:14
  • \$\begingroup\$ Thanks, that is shorter than my last program and works as well. Also true, I might split one program in two 2 / + and remove one. \$\endgroup\$
    – Redy000
    Jun 4 at 8:33
12
\$\begingroup\$

JavaScript, 10 programs / 271 bytes

Saved 12+ bytes per program thanks to @tsh

This is similar to the method used by @darrylyeo in this answer.

o={get g(){while(k);},set go(_){k--;}};k=9;o.g
o={get g(){for(;;)0}};o.g
o={get g(){for(;;)1}};o.g
o={get g(){for(;;)2}};o.g
o={get g(){for(;;)3}};o.g
o={get g(){for(;;)4}};o.g
o={get g(){for(;;)5}};o.g
o={get g(){for(;;)6}};o.g
o={get g(){for(;;)7}};o.g
o={get g(){for(;;)8}};o.g

Try it online! (non-halting)

Try it online! (halting)

\$\endgroup\$
15
  • 1
    \$\begingroup\$ The programs should be distinct. \$\endgroup\$
    – Bubbler
    Jun 2 at 1:43
  • \$\begingroup\$ @Bubbler Missed that rule entirely. Now fixed. \$\endgroup\$
    – Arnauld
    Jun 2 at 1:48
  • \$\begingroup\$ 279 bytes: o={get g(){while(k);},set go(x){k--}};k=9;o.go={get g(){while(1);}};o.go={get g(){while(2);}};o.go={get g(){while(3);}};o.go={get g(){while(4);}};o.go={get g(){while(5);}};o.go={get g(){while(6);}};o.go={get g(){while(7);}};o.go={get g(){while(8);}};o.go={get g(){while(9);}};o.g \$\endgroup\$
    – tsh
    Jun 2 at 2:22
  • \$\begingroup\$ @tsh Nice! I (Incidentally, this is the very first time I see the Setter must have exactly one formal parameter error when trying to omit it.) \$\endgroup\$
    – Arnauld
    Jun 2 at 2:36
  • 3
    \$\begingroup\$ @Jonah When concatenated, the lines form o.go using the o.g from one and the o from the second, causing all statements but the first to try to assign o.go. The final one gets o.g starting the loop. \$\endgroup\$
    – jaxad0127
    Jun 2 at 19:26
11
\$\begingroup\$

JavaScript (V8), 10 programs, 188 bytes

for(b=('a'in this);!b;);
for(c=this.b;!c;);
for(d=this.c;!d;);
for(e=this.d;!e;);
for(f=this.e;!f;);
for(g=this.f;!g;);
for(h=this.g;!h;);
for(i=this.h;!i;);
for(j=this.i;!j;);
for(var a;!this.j;);

Try it online! (all, halts)

Try it online! (not all, does not halt)

Javascript hoists the definition of a to the top of the scope, so even though it is defined later 'a' in this returns true.

\$\endgroup\$
1
  • 3
    \$\begingroup\$ Maybe first time to see var keyword in code-golf for me \$\endgroup\$
    – tsh
    Jun 2 at 7:35
10
\$\begingroup\$

Pyth, 10 programs, 23 bytes

  • Wn17l"
  • #
  • #1
  • #2
  • #3
  • #4
  • #5
  • #6
  • #7
  • #8

Try it online!

How it works

With all programs present, the concatenation is equivalent to this halting Python loop:

while 17 != len("##1#2#3#4#5#6#7#8"):
    pass

If the first program is present but another is missing, the string will no longer have length 17 and the loop will run forever.

If the first program is missing but another present, the concatenation begins with #, which loops a block until an error is raised (which will never happen):

while True:
    try:
        while True:
            try:
                print(1)
                while True:
                    try:
                        print(2)
                        while True:
                            try:
                                print(3)
                                while True:
                                    try:
                                        print(4)
                                        while True:
                                            try:
                                                print(5)
                                                while True:
                                                    try:
                                                        print(6)
                                                        while True:
                                                            try:
                                                                print(7)
                                                                while True:
                                                                    try:
                                                                        print(8)
                                                                    except Exception:
                                                                        break
                                                            except Exception:
                                                                break
                                                    except Exception:
                                                        break
                                            except Exception:
                                                break
                                    except Exception:
                                        break
                            except Exception:
                                break
                    except Exception:
                        break
            except Exception:
                break
    except Exception:
        break
\$\endgroup\$
3
  • \$\begingroup\$ Unfortunately, it doesn't seem like there is a way to make something using one of the built-in variables to save a byte, as they all either don't work in the string or break the final loop program without costing another byte. \$\endgroup\$ Jun 2 at 2:47
  • \$\begingroup\$ @FryAmTheEggman You can’t just check the end of the string anyway, since you need to verify that all the components are there. \$\endgroup\$ Jun 2 at 3:59
  • \$\begingroup\$ Ah, I missed that. Then this seems even more optimal than before! \$\endgroup\$ Jun 2 at 4:03
8
\$\begingroup\$

GNU sed, 10 programs, 99 bytes

:a s/^/A/
ba 

 

:a :b bb 

 

:b :c bc 

 

:c :d bd 

 

:d :e be 

 

:e :f bf 

 

:f :g bg 

 

:g :h bh 

 

:h :i bi 

 

:i :j s/A//
Tj

Explanation

Meta consensus lets sed programs take a single empty line as input (for, without that, sed simply won't do anything at all)

So, evidently, GNU sed will just let you define the same label multiple times, and all except the last one are ignored for execution purposes, which is nice for this challenge. Programs 1 through 9 each define a simple infinite loop (Program 1 does a bit more, which we'll get to in a minute)

:a ba 

This defines a label :a and ba is effectively a goto :a. This program does nothing but loop forever. Then if we concatenate the second

:a ba :a :b bb

Now the ba goes to the second :a label, which effectively does nothing, and then we loop on :b forever. Each program "disarms" the prior one and them introduces its own loop.

Now, the final program

:i :j s/A//
Tj

First, we disarm the :i loop from the ninth program. Then we try to remove an A from the pattern space. The pattern space started out containing an empty string (remember, our input is a single empty line), so if we run Program 10 on its own, this substitute will fail. Tj is a conditional jump. It's a goto :j that only executes if the previous substitution failed. This is an infinite loop.

However, if Program 1 is in play, then the first thing we did was introduce an A at the beginning of the pattern space, which Program 10 happily removes and then the Tj doesn't execute since the substitution was successful.

The only way a concatenation of these programs can terminate is if the following conditions are met.

  1. For N from 1 to 9, Program N contains an infinite loop trap that we can only escape if Program (N+1) is present.
  2. Program 10 contains an infinite loop trap that we can only escape if Program 1 is present.

Hence, a nonempty concatenation terminates if and only if all ten programs are present.

\$\endgroup\$
2
  • \$\begingroup\$ Nice trick, and well explained too! \$\endgroup\$
    – pxeger
    Jun 2 at 19:52
  • \$\begingroup\$ Nice solution. I think you can save a bit by using G instead of s/^/A/ so that you can do /./q in the last program. \$\endgroup\$
    – user41805
    Aug 30 at 12:27
7
\$\begingroup\$

Bash, 10 programs, 390 bytes

trap "while(($[a+=1]<55));do :;done" 0
trap "while(($[a+=2]<55));do :;done" 0
trap "while(($[a+=3]<55));do :;done" 0
trap "while(($[a+=4]<55));do :;done" 0
trap "while(($[a+=5]<55));do :;done" 0
trap "while(($[a+=6]<55));do :;done" 0
trap "while(($[a+=7]<55));do :;done" 0
trap "while(($[a+=8]<55));do :;done" 0
trap "while(($[a+=9]<55));do :;done" 0
trap "while(($[a+=10]<55));do :;done" 0

Try it online!

How?

Each line contains an exit handler that contains a while loop. The while loop will only halt if all the numbers 1..10 have been added to the variable $a. If any lines are missing, then the while condition will be true and will not halt.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ Doesn't each individual program need to be non-halting, whereas the variable assignments alone will halt? \$\endgroup\$
    – Jonah
    Jun 2 at 2:00
  • \$\begingroup\$ @Jonah - there I fixed it (I think) \$\endgroup\$ Jun 2 at 2:24
  • \$\begingroup\$ Nice, I was actually hoping you'd post a Bash answer. I had a vague idea you could do something writing to and reading from named pipes (where maybe the final program, in the halting version, consumes them all), but wasn't able to make it work. \$\endgroup\$
    – Jonah
    Jun 2 at 3:28
  • \$\begingroup\$ First thing that came to mind reading the OP, ninja'd me by 8 hours, or is that more like you Somu'd me! T_T \$\endgroup\$
    – Noodle9
    Jun 2 at 10:47
7
\$\begingroup\$

Jelly, 10 programs, 37 35 bytes

L}n27$¿“¹1¿¹2¿¹3¿¹4¿¹5¿¹6¿¹7¿¹8¿¹9¿

Try it online!

Individual programs with explanation

L}n27$¿“ | While not 27, take the length of the right argument
¹1¿ | While 1 do the identity function
¹2¿ | While 2 do the identity function
¹3¿ | While 3 do the identity function
¹4¿ | While 4 do the identity function
¹5¿ | While 5 do the identity function
¹6¿ | While 6 do the identity function
¹7¿ | While 7 do the identity function
¹8¿ | While 8 do the identity function
¹9¿ | While 9 do the identity function

When the whole lot is concatenated together, this checks the length of the string between and the end of the program is 27.

Any subsequence of these programs that does not include the first has an infinite while loop, while programs including the first one will only halt if all of the others are present so that the length is correct.

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

Python 3.8 (pre-release), 10 programs, 206 196 174 bytes

Whole program: (174 bytes)

i=1
while i:
 0#while 1:
 i=-8#while i:=2:
 i+=1#while i:=3:
 i+=1#while i:=4:
 i+=1#while i:=5:
 i+=1#while i:=6:
 i+=1#while i:=7:
 i+=1#while i:=8:
 i+=1#while i:=9:
 i+=1

Try it online!

Program 1: (16 bytes)

i=1
while i:
 0#

Program 2: (14 bytes)

while 1:
 i=-8#

Program 3 to 9: (18 char each)

while i:=2:
 i+=1#

...

while i:=8:
 i+=1#

Program 10: (17 char)

while i:=9:
 i+=1

How it works:

  • we set i to 1

  • In the first program: while i: 0 if i is not equal to 0 (wich is True at the start) we loop into the program. Otherwise the program finish.

  • In the second program, if the first program is missing, while 1 will loop indefinitely. We assign i to -8. If the second program is missing, i will always be strictly positive and the program will loop indefinitely

  • Then we increment i by 1 inside the first while loop and comment to neutralize the next while statement

  • If all 10 programs have been executed, i is now equal to 0 and the program stop. Otherwise, the program loops and i is set back to -8 in the seacond loop or will continue to be incremented.

thanks to Bubbler, who pointed me that programs should all be differents, which ended saving me many bytes :p

Thanks to Wheat Wizard♦ which inspired me to improve my solution

Python 3.8 (pre-release), 10 programs, 127 bytes

The solution where the program reads its own source code I found is:

while len(next(open(__file__)))<127:0#while 1:0#while 2:0#while 3:0#while 4:0#while 5:0#while 6:0#while 7:0#while 8:0#while 9:0

Try it online!

It is ... well ... a solution. Not clever, not even beautiful, but it is accepted so ...

First program :

while len(open(__file__).read())<127:0#

exit if the program is at least 127 char long. Else loop

Program 2 to 9:

while 1:0#

...

while 8:0#

Just infinite loop

Program 10:

while 9:0

Same but without comment

\$\endgroup\$
4
  • 1
    \$\begingroup\$ Programs should be distinct. \$\endgroup\$
    – Bubbler
    Jun 2 at 8:54
  • \$\begingroup\$ Oh? well I thnk I haven't learn to read. I will fix that \$\endgroup\$
    – Jakque
    Jun 2 at 8:56
  • 1
    \$\begingroup\$ I think this works and is shorter. \$\endgroup\$
    – Wheat Wizard
    Jun 2 at 10:21
  • \$\begingroup\$ @WheatWizard thanks \$\endgroup\$
    – Jakque
    Jun 2 at 10:55
6
\$\begingroup\$

Gol><>, score 10, 11 bytes

90.123456!;

Try it online!

At 1 point short of perfect this is as close as I can come in Gol><>.

The first 9 characters 90.123456 are all their own programs with !; being the only two byte program.

Since it contains the only halt instruction !; must be included to halt. And since it has a ! we can't simply get to ; from the right. The only other way to get to ; is with the teleport .. So . must be included as well. If . is first it will pop two zeros and teleport to itself creating an infinite loop, so something must be present before it. 0 causes the same type of infinite loop as before so 9 must be present as well. Now 0,9 is a location that can never be filled since we have no newlines. Thus any jump there creates an irretrievable infinite loop, we must have the 0 program as well. Now we know the . must take us to 9,0, and of course ; must be the character there. In order for this to happen we must have all the characters present.

This is the perfect score for Gol><> because if it were 10, 1 byte programs there would have to be a 1 byte program which halts on it's own. As suggested by @Bubbler it might be possible to use source modification to insert a halt command, however since unknown commands crash Gol><> a p on it's own will override itself with a zero byte and halt with a crash.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Perfect score might be possible by conjuring the halt command out of thin air. \$\endgroup\$
    – Bubbler
    Aug 11 at 22:39
  • \$\begingroup\$ @Bubbler I think the only way to modify the source like that is p which unfortunately halts on it's own. \$\endgroup\$
    – Wheat Wizard
    Aug 12 at 6:55
5
\$\begingroup\$

Haskell, score 10, 227 bytes

main=a;a=a where a=b;main=main;b=b where b=c;main=main;c=c where c=d;main=main;d=d where d=e;main=main;e=e where e=f;main=main;f=f where f=g;main=main;g=g where g=h;main=main;h=h where h=i;main=main;i=i where i=pure();main=main

Try it online!

Each program ends after the where except the last which just ends.

Here it is in a more readable manner.

main=a
a=a where
  a=b
  main=main
  b=b where
    b=c
    main=main
    c=c where
      c=d
      main=main
      d=d where 
        d=e
        main=main
        e=e where
          e=f
          main=main
          f=f where
            f=g
            main=main
            g=g where 
              g=h
              main=main
              h=h where
                h=i
                main=main
                i=i where
                  i=pure()
                  main=main

Try it online!

Explanation

The idea here is to use variable shadowing to create a chain of assignments. If the chain is broken the shadow means that we switch and define the variable in terms of itself an form a loop.

This is easier to see for just two programs.

main=a;a=a where a=pure();main=main

With just the first program

main=a;a=a where 

a is a loop so main is a loop. But when we add the second a gets shadowed and now a is a halting program. We do this several times each time changing the variable names so that the nothing can shadow something it is not supposed to.

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

Lenguage, 10 programs, 2324143350556659959 bytes

     -[]++++++++++++++++++
      --[]++++++++++++++++
        --[]++++++++++++++
          --[]++++++++++++
            --[]++++++++++
              --[]++++++++
                --[]++++++
                  --[]++++
                    --[]++
+)                    -.[]
---------------------------
     >+-+-+-+-+-+-+-+-+<[]
     201010101010101010367

Lacking the i-th program (\$i \in [2,10]\$), >+-+-+-++[] pattern appears (-[] when i=2).

Lacking the first several programs, ->+-+-+-+<[] pattern is still an infinite loop, or -.[] if only the 10th one left, still infloop

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

Lost, Score 2, 5 bytes

/%
@/

Try it online!

The programs are

/%

and

@/

This works because any lost program that halts must have both % and @. Since % turns off the safety to allow halting and @ actually does it. The simpler %@ doesn't work because half the time the pointer is moving vertically and can only hit one of the two. In fact in order to always halt a lost program needs some kind of redirect in every column and row (technically there are some specific exceptions to this but lets not get into them), meaning that this is certainly the smallest program that always halts.

So we can't go shorter for score 2. But ...

Lost, Score 3, 5 bytes

%^
@>

Try it online!

... we can increase the score at no cost to bytes!

The programs here are:

%^

@>

The second one being a single newline.

This is one of the specific exceptions to the one redirect in every row and column rule. It's the same length, but both of our redirects are in the same column since the other column automatically terminates by itself.

A program needs both % and @ to halt at all so any program missing one of the first two mustn't halt. So we only need to check the case where program 2 is missing.

%^@>

Here there is no possible path from the % to the @. The redirects ensure it. So there is no way for this program to halt.

And of course this can't be beat since you can't make a shorter halting program.

Lost, Score 4, 7 bytes

%\<
<@^

Try it online!

Nothing much special here it's a modified version of the above. There might be a smaller program that scores 4. I'm not sure.

The programs here are

%
\
<

<@^

Once again since a program needs % and @ to work so we have only to check

%<@^
%/<@^
%<
<@^

None of which halt.

Lost, Score 10, 19 bytes

%<ABCDE\<
<<<<<<<@^

Try it online!

And here we have an extensible solution, adding 2 bytes for every 1 score (until we run out of noop bytes). It is modified from the score 4 solution. The programs are

%<

Each letter is 1 program for 5 total

\
<

<<<<<<
<@^

The first and last program are necessary because they have the % and %. Without the newline we will have something like

%<...<@^

Which can never have a path from % to @, so the newline is needed too. We can also treat the letters as interchangeable since they are all noops, so we are only concerned with how many letters are present. At this point we can say that the only way for a program made from these to halt is if / is exactly above the @. Since it can't approach from the left or the right due to < and ^, and there is no other way to get a vertical direction on the first row. This tells us that / must be present, but also gives us a quick way of checking the programs.

Unfortunately there are still quite a few programs to check. In fact more than I think I want to list in this post. The checks are easy given what I've already shown so please have a go yourself if you doubt my work.

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

Vyxal, 4 bytes, 2 programs.

#1

{

Try it Online! Simple forever loop. The 5 flag makes it terminate after 5 seconds so it doesn't jam up the interpreter.

#2

0|{

Try it Online! Another simple loop.

Halting program

{0|{

Try it Online!

This works because | is a branch in structure when in a structure, but does nothing when in the main scope. So in the second one, it pushes 0 then executes a forever loop, but in here, it executes a loop containing a forever loop with 0 as the condition, so the inside loop is never run and the program halts.

Note that like TIO, the Vyxal interpreter times out after 60 seconds to avoid breaking, but if that was removed these two would run forever.

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

Vyxal, 19 bytes / 3 programs

#1

`{`{`

Try it Online!

#2

{`{`

Try it Online!

#3

`0|}0|{`{`

Try it Online!

Concatenated

`{`{`{`{``0|}0|{`{`

Try it Online!

A quite different approach to what I had before.

With NOPS removed, it becomes:

{        # While...
 {  }    # While
  0      # 0
   |     # Do nothing
     0   # 0
      |  # Do..
       { # Forever loop, never executed
 
\$\endgroup\$
2
\$\begingroup\$

Charcoal, 96 bytes, score 10

Wα«≔⁻αAαWα«≔⁻αBαWα«≔⁻αCαWα«≔⁻αDαWα«≔⁻αEαWα«≔⁻αFαWα«≔⁻αGαWα«≔⁻αHαWα«≔⁻αIαWα«≔⁻αJKLMNOPQRSTUVWXYZα

Try it online! Explanation: Each loop subtracts a different substring of the predefined uppercase alphabet, so the program will only finish if all of the letters get subtracted. The programs can of course be concatenated in any order. As ten separate programs:

Wα«≔⁻αAα
Wα«≔⁻αBα
Wα«≔⁻αCα
Wα«≔⁻αDα
Wα«≔⁻αEα
Wα«≔⁻αFα
Wα«≔⁻αGα
Wα«≔⁻αHα
Wα«≔⁻αIα
Wα«≔⁻αJKLMNOPQRSTUVWXYZα

This can be trivially extended to 26 programs by subtracting each letter separately. Furthermore, this can be trivially extended to 95 programs by subtracting from the whole printable ASCII character set instead of just the uppercase alphabet. (It might even be possible to extend this up to 150 programs by mixing the approaches.)

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

Julia 0.6, 10 programs, 275 256 bytes

!x=while x<1end
e+=1
!01
!x=while x*e<4end
e+=1
!01
!x=while x*e<5end
e+=1
!01
!x=while x*e<6end
e+=1
!01
!x=while x*e<7end
e+=1
!01
!x=while x*e<8end
e+=1
!01
!x=while x*e<9end
e+=1
!01
!x=while x*e<10end
e+=1
!01
!x=while x*e<11end
e+=1
!01
while e<11end

Try it online!

ry it online!

Try it line!

Try it onlin!

the separation between the programs is between each !0 and 1

uses Julia 0.6 to be able to redefine e (the euler constant)

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

Forte, 10 programs, 96 bytes

9LET0=1
10LET1=2
11LET2=3
12LET3=4
13LET4=5
14LET5=6
15LET6=7
16LET7=8
17LET8=21
20LET21=0
21END

Each line is a program, except that the last two lines together constitute the tenth program.

Explanation

Forte is a language built around redefining numbers. Execution control is achieved by redefining line numbers, thereby shuffling statements around.

The only way to exit is via the END statement. So right off the bat, if the tenth program is missing, there is no way to exit and the program loops forever.

If the tenth program is present but one of the earlier programs is missing, the LET statement on line 20 redefines the number 21 to be some value between 0 and 8 (depending on which of lines 9 through 16 were able to run). Since this number is less than the current line number of 20, the END statement moves to before the instruction pointer and is never executed. The program proceeds to loop infinitely.

If all ten programs are present, lines 9 through 17 redefine 0 (through a series of steps) to equal 21. Then line 20 redefines 21 to equal 21 (no change). Execution proceeds to line 21, which ends the program.

(I'm not sure whether all implementations of Forte will behave this way, but Forter, the version on TIO, does. This behavior seems to be in line with the description in the Esolangs article, too.)

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

Perl 5, 10+ programs, 184 bytes

BEGIN{s//t/}{redo}BEGIN{s//i/}{redo}BEGIN{s//x/}{redo}BEGIN{s//4/}{redo}BEGIN{y/4/5/}{redo}BEGIN{y/5/6/}{redo}BEGIN{y/6/7/}{redo}BEGIN{y/7/8/}{redo}BEGIN{y/8/e/}{redo}BEGIN{eval}{redo}

Try it online!

With newlines added for readability:

BEGIN{s//t/}{redo}
BEGIN{s//i/}{redo}
BEGIN{s//x/}{redo}
BEGIN{s//4/}{redo}
BEGIN{y/4/5/}{redo}
BEGIN{y/5/6/}{redo}
BEGIN{y/6/7/}{redo}
BEGIN{y/7/8/}{redo}
BEGIN{y/8/e/}{redo}
BEGIN{eval}{redo}

{redo} is a short infinite loop in perl. BEGIN blocks run before everything else, so all we need to do is exit from a BEGIN block.

To do this, we build the string exit and then eval it in a BEGIN block. s//whatever/ is a concise way to prepend whatever to the global variable $_, and then eval evaluates that string. The first four programs set $_ to 4xit and then the next programs use the transliteration operator y/// to successively change the 4 to various other numbers and finally to e.

Anything besides exit will do nothing when eval is run, and of course removing eval will keep the program from exiting, so the program will run forever.

This method can be extended to an arbitrary number of programs with additional uses of y/// and s///.

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

R, 10 programs, 156 151 bytes

while(T<-T*2)1-while(T<-T^2)1-while(T<-T*3)1-while(T<-T*4)1-while(T<-T*5)1-while(T<-T*6)1-while(T<-T*7)1-while(T<-T*8)1-while(T<-T*9)1-while(T<-T<6e5)1

Try it online!

Separate programs:

while(T<-T*2)1
while(T<-T^2)1
-while(T<-T*3)1
-while(T<-T*4)1
-while(T<-T*5)1
-while(T<-T*6)1
-while(T<-T*7)1
-while(T<-T*8)1
-while(T<-T*9)1
-while(T<-T<6e5)1

The full program works by starting with T (which starts at TRUE and becomes 1 when used arithmetically) and then multiplied by each number from 2 to 9 as well as squaring it (after T<-T*2). The last program compares T to 6e5, at which point all of the comparisons will equal 0.

Separately, no combination of programs will ever reach 0 since anything excluding the last program will just head for +infinity, while any combination including the last program will evaluate to TRUE unless all of the prior programs were present.

If any subsequence without the first program did complete its while loop, the unary minus would throw an error, but since they never do, no error is generated.

Thanks to @RobinRyder for saving a byte!

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

[Scala Interpreter], 10+ programs, 265 bytes

This challenge is impossible to solve in languages that require a global program body around their code.

Luckily, Scala Interpreter is a way to bypass this issue :)

However, the challenge is still hard to solve in a language that requires to declare variables before using them and that does not provide a simple global mutable context to share information between the subprograms. However, the necessary information sharing can be achieved indirectly by affecting the global state of the JVM.

So, here are the 10 programs (one per line). Of course, it can be extended to any number of programs:

new java.util.Timer("1");
new java.util.Timer("2");
new java.util.Timer("3");
new java.util.Timer("4");
new java.util.Timer("5");
new java.util.Timer("6");
new java.util.Timer("7");
new java.util.Timer("8");
new java.util.Timer("9");
while(Thread.activeCount!=10){};sys.exit

Explanation: Every instantiation of a new Timer creates a new background thread that prevents the program from stopping. Further, the 10th program runs forever if the number of threads (incl. main thread) is not 10. Thus, the total number of threads is the indirectly affected "global variable" here.

No concatenation of 1..9 programs halts, for example:

  • scala -e 'new java.util.Timer("2");'
  • scala -e 'new java.util.Timer("1");new java.util.Timer("5");'
  • scala -e 'while(Thread.activeCount!=10){};sys.exit'
  • scala -e 'new java.util.Timer("4");while(Thread.activeCount!=10){};sys.exit'

Only when concatenating all 10 sub-programs, the resulting program will halt.

You can try out this behavior in TIO:

Try it online!

This approach does also work via Copy&Paste into the Scala REPL or to some Scala IDE, but then you need to replace the literal 10 by 11, since in this case another JVM thread is running in the background :)

\$\endgroup\$
1
  • 1
    \$\begingroup\$ You could replace two of these with just new java.util.Timer() and new java.util.Timer(""), and !=10 can be <10 I think \$\endgroup\$
    – pxeger
    Jul 21 at 10:22
1
\$\begingroup\$

Vyxal, 10 progs, 27 bytes, take 3.

{`{
{1
{2
{3
{4
{5
{6
{7
{8
`L17<|`{

Try it Online!

I finally figured out what the others are doing. This basically checks if the string between the backticks' length is 17, and if not loops forever.

No trailing newlines, they're just formatted like this for readability.

Any character except X and | can be used instead of the digits.

\$\endgroup\$
2
  • \$\begingroup\$ @AaronMiller The challenge requires the programs to be distinct. \$\endgroup\$ Jun 2 at 16:20
  • \$\begingroup\$ @AndersKaseorg Whoops, missed that. 23 bytes, 10 programs \$\endgroup\$ Jun 2 at 16:30
1
\$\begingroup\$

Charcoal, 36 bytes, score 6

≔⁰ψWα«≔⁰αWβ«≔⁰βWγ«≔⁰γWφ«≔⁰φWχ«≔⁰χWψ«

Try it online! Explanation: This is the concatenation of six six-byte programs. Each program sets a predefined variable to zero and then loops over another predefined variable. This means that no program will finish except for the concatenation of all six, which will ensure that all of the predefined variables are set to zero, causing all of the loops to terminate. (Concatenating the programs in a different order won't work because the first program will prevent the final program's loop from executing, preventing further programs from clearing the first program's loop variable.) As six separate programs:

≔⁰ψWα«
≔⁰αWβ«
≔⁰βWγ«
≔⁰γWφ«
≔⁰φWχ«
≔⁰χWψ«
\$\endgroup\$
1
\$\begingroup\$

Ruby, 114 bytes, 10 programs

1/($.-40)while 99while$.+=11while$.+=07while$.+=06while$.+=05while$.+=04while$.+=03while$.+=02while$.+=01while$.=1

Try it online!

The programs break down like this:

1/($.-40)while 9
9while$.+=1
1while$.+=0
7while$.+=0

...

1while$.=1

The 1/($.-40) causes a ZeroDivisionError if all the other snippets successfully incremented the counter $. to 40, breaking out of all of the loops. If any parts are missing, $. will be less than 40 and the division will work, so the program will continue to loop.

Because the inner loop never terminates, the outer loops can never increment $. more than once, so there's no opportunity for $. to reach 40 except if all the programs are there.

Try nline!

y it online!

Tre!

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

Klein 000, Score 10, 17 bytes

ABCDEFG\
....!><@

Try it online!

This is a modification of my lost answer so to get a good idea of how this works I recommend reading that explanation. Since Klein is not a language designed to torture the programmer, this ends up being 2 bytes shorter.

The programs are:

The 7 letters

\

(Just a newline)

....!><@

This works of an alignment principle. The / has to be above the @ or you are not going to reach it. There are some special bits !>< for example is a trap that catches anything going rightwards, which is there for when the newline is removed.

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

PHP, 10+ programs; 342 134 127 124 123 116 bytes.

Byte count for PHP assumes you don't require and count the 8 characters of the surrounding <?php ?> tags for each program; if so, add 80 bytes.

while(!file(__FILE__)[9]);die();
for(;;);
foR(;;);
fOr(;;);
fOR(;;);
For(;;);
FoR(;;);
FOr(;;);
FOR(;;);
while(1);

I realized that FOR is case-insensitive, so I could use seven more unique fors, saving 7 bytes.

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

Befunge-93, 10 programs, 13 bytes

~1\-2*4+7`#@_

Try it online!

I think there's at least one more byte that can golfed off this. 9 of the programs are one byte apiece, with the last being 7`#@. The initial ~1\-2*4+ generates the number 8, with any lesser combination generating a smaller number. This then uses the 7`#@_ to only terminate if the number is bigger than 7. Note that if the 7`#@ section is removed, the program has no way to terminate, and if the _ is removed, there is no way for the pointer to travel left, and therefore no way to execute the @.

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

Perl 5, 10 programs, 179 175 bytes

END{{redo}}use POSIX;END{{redo}}s//)/;END{{redo}}s//0/;END{{redo}}s//(/;END{{redo}}s//_exit/;END{{redo}}s//::/;END{{redo}}s//SIX/;END{{redo}}s//O/;END{{redo}}s//P/;eval;{redo}

Try it online!

For readability, here's the same program with newlines:

END{{redo}}use POSIX;
END{{redo}}s//)/;
END{{redo}}s//0/;
END{{redo}}s//(/;
END{{redo}}s//_exit/;
END{{redo}}s//::/;
END{{redo}}s//SIX/;
END{{redo}}s//O/;
END{{redo}}s//P/;
eval;{redo}

Builds the string POSIX::_exit(0) and evals it. END blocks always run at the end of a program even if there was an error, but POSIX::_exit skips this.

\$\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.