7
\$\begingroup\$

I have noticed that questions are often looking at strictly increasing integer sequences. For these types of sequences, the task of outputting the values in the sequence is largely equivalent to the of deciding whether a number appears in the sequence.

This suggests the option of having an tag, for which both answers and answers are valid.

Should we do that? What are the pros and cons?

\$\endgroup\$
9
  • \$\begingroup\$ As far as I can tell it is not necessary for the elements of the sequence to be integers for the equivalence to hold, so increasing-sequence would be a simpler and more general name for the same concept. \$\endgroup\$
    – bsoelch
    Sep 22 at 7:34
  • \$\begingroup\$ @bsoelch while it doesn't have to be integers, it has to be discrete (so you can do something like for element in range: if valid: print(element)). It could work with strings, perhaps, but I can't think of any other data types which has that naturally \$\endgroup\$
    – Command Master
    Sep 22 at 7:46
  • \$\begingroup\$ As far as I can remember every decidable set is also recursively enumerable. Maybe "increasing" is not the right word. enumerable-set should cover the full concept (but may not be as easy to understand) \$\endgroup\$
    – bsoelch
    Sep 22 at 8:07
  • \$\begingroup\$ @bsoelch suppose the sequence is of positive rationals. It's not possible to convert an arbitrary decision procedure to a sequence, nor vice versa. You need a specific enumeration, and you can't enumerate the rationals in increasing order \$\endgroup\$
    – Command Master
    Sep 22 at 8:26
  • \$\begingroup\$ Even if the question allows any order it isn't equivalent, since not all recursively enumerable sets are decidable \$\endgroup\$
    – Command Master
    Sep 22 at 8:40
  • 4
    \$\begingroup\$ Do we really want a tag with implied rules? It's common for a sequence from a challenge to be increasing, and I wouldn't expect it to allow membership oracles just because it's tagged with a descriptive name. \$\endgroup\$
    – xnor
    Sep 22 at 20:28
  • 1
    \$\begingroup\$ @xnor What I'm saying is that for increasing integer sequences it might make sense to allow membership oracles by default, just like sequence has default I/O methods, and if it doesn't fit some challenge the author can exclude it. \$\endgroup\$
    – Command Master
    Sep 23 at 5:20
  • 1
    \$\begingroup\$ @CommandMaster I wouldn't expect or like that as a default for challenges I post, and I don't think most posters would. I guess I can post an answer to see if the votes agree with this or not. \$\endgroup\$
    – xnor
    Sep 23 at 5:23
  • 3
    \$\begingroup\$ Regardless of whether this is accepted as a default / tag, feel free to include it as an allowance in any of your own future challenges, as it is an interesting idea IMO \$\endgroup\$
    – thejonymyster
    Sep 24 at 19:57

2 Answers 2

Reset to default
20
\$\begingroup\$

This isn't a good default

I wouldn't expect or want for my challenges to allow membership-oracle solution by default just because the sequence is increasing. While allows various formats by default, what they share in common is outputting elements of the sequence, which the version does not. Yes, a membership oracle could be converted to a sequence generator, but this looping costs bytes to implement that shouldn't be "free".

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

This is a good default

This output method is very similar to outputting the \$n\$-th value in a sequence.

If you implement a function f which returns the \$n\$-th value in the sequence, then the sequence is map(f, integers). If f is a membership oracle, the sequence is filter(f, integers). I think the difference between a map over the integers and a filter over them is small enough that if we allow one we should allow the other, unless the writer explicitly excludes it.

Another perspective to this similarity is the operations: outputting the \$n\$-th value in the sequence, compared to outputting the \$n\$-th value in the indicator sequence. A strictly increasing integer sequence and its indicator sequence are very closely tied, so I think both output methods should be allowed. In fact, this even suggests a broadening of the suggestion — answers can choose whether to output the sequence or the indicator sequence, using any of the default methods for either, although that's a discussion for another time.

\$\endgroup\$

You must log in to answer this question.

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