5
\$\begingroup\$

I am currently designing a language that cannot halt unless it all of its memory is cleared, this means for any practical application it has no output whatsoever. However when the program does halt it does output HALTED.

In languages otherwise incapable of traditional output can halting and non-halting be considered outputs for that ask for two distinct outputs?

\$\endgroup\$
  • 1
    \$\begingroup\$ But it's impossible to prove it won't halt because hating problem. \$\endgroup\$ – Pavel May 8 '17 at 5:11
  • 4
    \$\begingroup\$ isn't it impossible to prove something produces the correct output for every input by the same token? it is very possible to prove that some programs don't halt (while 1:pass) \$\endgroup\$ – Destructible Lemon May 8 '17 at 5:31
  • 3
    \$\begingroup\$ The main issue I'm seeing is that it goes against this consensus. And I think if we allow halting/non-halting as truthy/falsy in general, a lot of languages might make use of that, which would probably get old really fast. So while I agree with Nathan's answer, I'd say this should only apply to languages where halting/non-halting is the only way to distinguish between results, and in those cases the policy in the link above doesn't apply. \$\endgroup\$ – Martin Ender May 8 '17 at 13:07
  • 2
    \$\begingroup\$ I recommend programming your interpreter to detect simple infinite loops and error out when it does so. That would allow a method of outputting another distinct value without changing the semantics of your language at all. (Of course, you can't detect all infinite loops, but an infinite loop that's trying to be detected is normally fairly easy to spot.) \$\endgroup\$ – user62131 May 9 '17 at 7:54
20
\$\begingroup\$

Please no

All languages should follow the same rules, and being incapable of doing something isn't reason for special treatment. And this would be a big rules change for decision problems in every language.

A good number of existing answers could be easily outgolfed by invoking this new option. For example, on Is this number an integer power of -2?, I can cut 3 bytes from the shortest Python answer, 6 bytes from the shortest Haskell answer, and many others, just by removing their bases cases of 0.

Challenges about searching for an object could now be done by enumerating them without limit until one works. For example, the challenge Reachable numbers to check if the input is the totient function of some number can now be done as:

n=input()
i=1
while phi(i)!=n:i+=1

This gets around bounding the maximum possible i, which all existing answers do. This stinks of a hidden rule: an output method that golfers and decision-problem writers wouldn't know is valid unless told so.

The obvious expectation that output methods produce a result. Running code that just keeps going isn't something one would expect to call solving a decision problem. No matter how long you run it, you don't know if it is still yet to halt. Even if you can prove it runs forever, this is not observable: it requires examining the code itself.

Moreover, it defies the meaning of "decision" in computation, that a machine that decides a language must halt by accepting or rejecting, and would let us submit entries to "solve" decision problems that are undecidable, which is ridiculous.

\$\endgroup\$
  • 3
    \$\begingroup\$ Not to mention if we made a special case for languages that cannot produce output otherwise, it would be pretty simple to make a language that is just python without output and then it would be allowed to compete, making the ban rather foolish in the first place. \$\endgroup\$ – Wheat Wizard May 8 '17 at 20:27
  • 1
    \$\begingroup\$ I'll leave my post up for voting, but the first sentence convinced me. +1 from me. \$\endgroup\$ – Nathan Merrill May 9 '17 at 13:22
4
\$\begingroup\$

Only if it's halting-ness is proven in the post

It is impossible to prove whether any arbitrary program will halt. That doesn't mean that every program can't be proven.

However, the burden of the proof lies with the poster. If they prove that it will (or won't) halt in the post, then I see no problem.

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

While halting versus not halting is the classic truthy/falsey output in Turing Machines, you run up into the halting problem when you try to use it practically. It's impossible to say in general whether or not a program in a Turing-complete language will halt. That will cause similar difficulties on PPCG: will the program never halt, or has it not been given enough time?[1]

A way around this would be to say "if it doesn't halt in N seconds, it doesn't halt", but that opens up more cans of worms about hardware configurations and such.

So, no, halting versus not halting should not be used as a way to indicate truthiness or falsiness.

[1]: On a slightly philosophical note, in reality, every program will halt eventually, whether it be due to someone tripping over the power cable, or the heat death of the universe.

\$\endgroup\$
  • \$\begingroup\$ @WheatWizard Those are all complications due to technical restrictions from the real world. Theoretically, given enough time, those programs will work. Turing (and Church) proved that, no matter how much time or space you have, you cannot prove in general whether or not a program in a Turing-complete language will halt. \$\endgroup\$ – Mego May 8 '17 at 12:06
  • \$\begingroup\$ My point was that while it is inside to verify that a general program does not halt. It is also impossible to verify whether a general program does a task as trivial as add two numbers. We obliviously allow people to make the jump and say there program add two numbers because we either understand the algorithm or tested enough inputs to believe it so why does the same not hold here? \$\endgroup\$ – Wheat Wizard May 8 '17 at 12:11
  • \$\begingroup\$ @WheatWizard At this point it seems like you're arguing just to argue. \$\endgroup\$ – Mego May 8 '17 at 12:12
  • \$\begingroup\$ I'm sorry if these seems argumentative. I don't mean to. But while I am unsure if this should be allowed I do feel that what I said is true. \$\endgroup\$ – Wheat Wizard May 8 '17 at 12:15
  • 4
    \$\begingroup\$ @Mego while I agree, you cannot prove whether any arbitrary program will halt, that doesn't necessarily mean you cannot prove that some programs won't halt. It's rather trivial to prove that while(1); won't halt. Therefore, if the user can prove that the program won't halt, then I see no problem. \$\endgroup\$ – Nathan Merrill May 8 '17 at 12:37

You must log in to answer this question.

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