5
\$\begingroup\$

Current consensus seems to be that programs must terminate by default. This makes sense in general. However, does this bar use of languages which are not designed with a halt state (other than manually stopping the program)?

For example, take something like ByteBeat, which I believe is a family of languages which evaluate a single expression at continually, infinitely increasing values of a variable t (representing time) and outputting as audio. Could we use this in an answer which did not specify anything about infinite output? Could a ByteBeat program infinitely loop outputting twinkle twinkle little star? Or maybe just play it once, and then remain silent for eternity onward?

There are also automata like rule 110 which are Turing-Complete but have no way to halt. It's easy to argue, however, that these are not languages, and that a language implementation of such a thing would have a well defined halt state / output.

Alternatively, in this language (and likely others) you are able to guarantee that after a certain point, nothing more will be output. In ByteBeat, this would be done by having an expression which always error after a certain fixed value, like this: (t>100?1/0:1). Important to note that this would not halt with error, it would simply not evaluate to any outputtable sound.

Also worth note: Languages without I/O capabilities such as /// are allowed to hardcode their input, and see the other various rules in the linked question for other examples of exceptions made for languages which lack certain features.

So, in general, programs must halt unless specified in a challenge, but do we have any exceptions for languages without halt states? Does it make a difference if their output is (fairly) well defined, and/or there is a way to guarantee finite output even in theoretically infinite time?

\$\endgroup\$
6
  • \$\begingroup\$ sorry no link for bytebeat, i couldnt find anything like a wiki \$\endgroup\$
    – thejonymyster
    Commented Jun 29, 2022 at 16:24
  • 1
    \$\begingroup\$ One such language is Gammaplex. The ending instruction E is defined to be an infinite loop. \$\endgroup\$
    – jimmy23013
    Commented Jul 5, 2022 at 4:21
  • \$\begingroup\$ Is this similar to REPL environment which will not exit after given expression calculated (but waiting for next input), or an Excel answer which show result in A1 cell but not exit the Excel program? I'm not sure how to define terminate to these environments... \$\endgroup\$
    – tsh
    Commented Jul 5, 2022 at 14:48
  • \$\begingroup\$ @tsh somewhat, but not quite the same idea. a REPL or excel type environment never stops taking program input, and thus has no clear definition of termination (as you mentioned), since it has no clear definition of even EOF. A language which takes a single, well defined program, runs all of the instructions in it (finitely or infinitely many times) and then enters an infinite loop of either doing something or doing nothing, that's what the main idea of the question is. Definitely an interesting comparison, though. \$\endgroup\$
    – thejonymyster
    Commented Jul 5, 2022 at 15:51
  • 2
    \$\begingroup\$ REPLs do have a clear concept of termination. For one many REPLs do accept an EOF. Just run echo "3+4" | ghci and you will see that it terminates, this is the usual way in which you would envoke a REPL. \$\endgroup\$
    – Wheat Wizard Mod
    Commented Jul 6, 2022 at 10:20
  • 2
    \$\begingroup\$ But even when that's not the case the REPL doesn't continuously take input, it has distinct stages (usually: Read, Evaluate, Print) returning to the read mode is a clear example of halting. If the code doesn't halt then it will not return to the read stage, which is a very clear difference. Just because the environment doesn't halt does not mean that the program doesn't halt, just as running Python script doesn't need to shut your computer down to halt. \$\endgroup\$
    – Wheat Wizard Mod
    Commented Jul 6, 2022 at 10:21

2 Answers 2

Reset to default
8
\$\begingroup\$

Non-halting languages are allowed if their output is provably finite when required to be.

If a challenge requires infinite output, non-halting languages are of course allowed.

In challenges where output must be finite, a non-halting language may output a solution and then enter some loop which can be proven to not output anything else.

This proof can be as simple as "The instruction pointer then accesses an infinite loop command which does nothing" or "The program only outputs for t < input length, and t increases infinitely as defined by the language", or as complex as need be. The non-outputting loop need not be trivial, only provably non-outputting.

\$\endgroup\$
1
  • \$\begingroup\$ Very curious about the downvote here, I hope you'll post your own response as well. \$\endgroup\$
    – thejonymyster
    Commented Jul 22, 2022 at 12:25
-2
\$\begingroup\$

Non halting languages must output a "halt message" after outputting a solution, and then provably output nothing after it.

Similar to the other answer, but I didn't want to edit the existing answer since it has votes already.

If a challenge requires/allows infinite output, non-halting languages are obviously allowed to participate.

In a challenge where output must be finite, a non-halting language may output a solution, followed by a message/output indicating that the program has halted, and then enter a loop which is proven in the answer to not output anything. This loop and its proof can be as simple as While(1){do nothing}, more nuanced as "The program only outputs while t<100, and every step of the program, t increases", or as complex as need be, just so long as it can be proven to not output anything.

The halt message ensures that the program entering its infinite non-outputting phase can not be confused with it taking a while to generate the answer. I overlooked this in my previous answer.

The halt message can be any reasonable/consistent output determined by the solver. This can range from things like outputting a 0 or a newline, printing some error to stderr, or it could be something along the lines of printing the input again if that would be reasonable for the challenge.

For example, in a challenge where you have to take n and output the nth prime number, you could output the nth prime, followed by n to indicate you were finished. It would be unreasonable, however, to output the input as your halting message if the challenge were to output the input, even if you output it twice. Use the sort of judgement you would for determining if an answer's decision problem outputs are reasonable.

\$\endgroup\$
3
  • \$\begingroup\$ To me, this raises questions about functional submissions, but I can't think of how those would be handled differently. \$\endgroup\$
    – thejonymyster
    Commented Jul 26, 2022 at 13:09
  • 2
    \$\begingroup\$ This could be abusable in some specific challenges. For example in this challenge was made a bit more complex by needing to omit the last character. With these rules you could just say the unprintable extra character is your termination character and avoid the code required to stop early. \$\endgroup\$
    – mousetail 'he-him'
    Commented Jul 26, 2022 at 13:33
  • \$\begingroup\$ @mousetail I think this approach, in general, runs into issues with kolmogorov complexity questions. Should I just delete this? It's not as well thought out as my other response, and pxeger's chat message here seems to have a better approach in mind \$\endgroup\$
    – thejonymyster
    Commented Jul 26, 2022 at 15:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .