39
\$\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, 2021 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, 2021 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, 2021 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, 2021 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, 2021 at 11:02

31 Answers 31

1
2
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\$
1
2

Your Answer

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

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