# Equivalence between strictly increasing integer sequences and decision problems

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?

• 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. Commented Sep 22, 2023 at 7:34
• @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 Commented Sep 22, 2023 at 7:46
• 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) Commented Sep 22, 2023 at 8:07
• @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 Commented Sep 22, 2023 at 8:26
• Even if the question allows any order it isn't equivalent, since not all recursively enumerable sets are decidable Commented Sep 22, 2023 at 8:40
• 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.
– xnor
Commented Sep 22, 2023 at 20:28
• @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. Commented Sep 23, 2023 at 5:20
• @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.
– xnor
Commented Sep 23, 2023 at 5:23
• 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 Commented Sep 24, 2023 at 19:57

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.