12
\$\begingroup\$

Let's say that there is a standard 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.

\$\endgroup\$
1

1 Answer 1

11
\$\begingroup\$

No, that doesn't satisfy the rules

In many 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.
\$\endgroup\$
3
  • \$\begingroup\$ I think this doesn't really address emanresuA's actual point, which was that for every input, there exists some limit which can be imposed to make the algorithm work. As long as the computer has a finite amount of memory, although that amount can be arbitrarily big, it can handle all inputs upto some number. On a 1GB RAM computer, maybe inputs up to N=200 can be handled; on a 2GB RAM computer, inputs up to N=400, etc. If you want it to handle N=1000, just use a computer with at least 5GB, but less than infinite, memory. \$\endgroup\$
    – pxeger
    Feb 1 at 18:32
  • 3
    \$\begingroup\$ (not saying I necessarily agree with that point; I haven't really made my mind up). But there is a distinction between "answers may assume enough memory", and "answers may assume infinite memory; the set of answers which work under the latter is not necessarily a superset of those in the case of the former. \$\endgroup\$
    – pxeger
    Feb 1 at 18:35
  • \$\begingroup\$ I'm not going to say no or yes. Word RAM also assumes resource fit the size of question, but yeah it makes something possible and something easier \$\endgroup\$
    – l4m2
    Feb 2 at 1:35

You must log in to answer this question.

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