Using resource exhaustion with a semi-deciding algorithm

Question

Let's say that there is a standard code-golf question where you:

• Have to find a solution that satisfies some constraints (eg. a math equation, etc.)
• Or, if a solution doesn't exist, output the nonexistence of a solution (by erroring, returning -1, etc.)
• There are no explicitly stated limits to the "size" of the solution.

Is it valid to submit an answer, which aside from complications raising from resource exhaustion, is a semi-decision algorithm, and then utilize a recursion/memory limit to detect cases when there is no solution?

A semi-decision algorithm is an algorithm which is able to find a solution if it exists, but if a solution doesn't exists, it will go in an infinite loop.

For example, if the task was to find an integer solution for a polynomial equation \$ax^2+bxy+c=0\$, a semi-decision algorithm would try all possible combinations of \$x\$ and \$y\$, until it finds a solution. If a solution exists, this algorithm will terminate and return the solution. But, if no solution exists, the algorithm will go on forever, never returning anything.

Now is it valid to take that semi-decision algorithm, implement it in a language which has the ability to handle recursion limits, and then say that if a solution doesn't exist, a recursion-limit error is returned, and thus the submission satisfies the rules?

Background

This question has some semi-decision algorithms as answers.

Answer 1

No, that doesn't satisfy the rules

In many code-golf questions there are infinitely many inputs, which may be arbitrarily long. And, unless otherwise stated, your code should be able to handle every single input correctly, even if it's a billion billion bytes long, at least in theory. Now, most languages have limits on how much memory an object can take, or how much you can recurse, meaning that it can't really handle the infinitely many arbitrarily large inputs. To make those languages able to participate, we implicitly pretend that the resource limits don't exist (or are infinite), thus making the languages able to deal with infinitely many inputs. Sometimes, with languages like C or JavaScript, we also pretend that the numeric types are "bigints", meaning they can store arbitrarily large integers.

It's also allowed to not pretend, and utilize integer overflow or even memory exhaustion. But in the latter case the memory or recursion limit usually destroys the answers ability to handle the infinitely many inputs correctly, thus the answer doesn't satisfy the challenge rules.

Here are some other quick points:

• If these types of answers would satisfy the rules, then there exists a "solution" to the halting problem in those languages.
• If the OP thinks that a semi-decision algorithm is fine they can either say that a solution will always exist or explicitly allow a semi-decision algorithm.
• A full-decision algorithm has the additional challenge of inventing and implementing a termination condition. The termination conditions often require deeper understanding of the problem and the mathematics behind it. A semi-decision algorithm is often nothing more than a simple brute force search. By relaxing the rules this interesting and fun part of the challenge is lost.
• One argument for accepting those kinds of answers is that for every set of inputs, there exists a amount of ram, etc. where the program will always give the correct answer. However, this imo. makes the ram limit part of the code, and thus you are actually submitting a whole bunch of programs, each with different ram limits, none of which individually can satisfy the requirements of the challenge.